Нечеткая строка поиска в Java


Answers

Вы можете использовать Apache Lucene, но в зависимости от варианта использования это может быть слишком тяжелым весом. Для очень простых нечетких поисков он может быть немного сложным в использовании и (исправьте меня, если я ошибаюсь), он требует, чтобы вы построили индекс.

Если вам нужен простой алгоритм онлайн (= не поддерживающий индекс), вы можете использовать алгоритм нечеткого бита . Я нашел реализацию на Java здесь . Это код подходит для одного относительно короткого метода с почти самоочевидной сигнатурой:

public static List<Integer> find(String doc, String pattern, int k)

Apache Commons StringUtils имеет реализацию алгоритма Левенштейна для нечеткого соответствия строк. Это можно рассматривать как нечеткую версию String.equals , Bitap похожа на нечеткую версию String.indexOf и по-прежнему использует дистанционную меру Левенштейна. Обычно он более эффективен, чем наивно, используя Levenshtein для сравнения шаблона поиска с каждой подстрокой, которая могла бы соответствовать.

Примечания :

  • Алгоритм Bitap, по-видимому, в основном полезен для относительно небольших алфавитов, например, простой ASCII. На самом деле версия Simon Watiau, с которой я связан, выдает исключение ArrayIndexOutOfBoundsException для символов, отличных от ASCII (> = 128), поэтому вам придется отфильтровать их.
  • Я попытался использовать Bimap в приложении для поиска списка в памяти людей по имени. Я обнаружил, что расстояние Левенштейна 2 дает слишком много ложных срабатываний. Расстояние Левенштейна 1 работает лучше, но он не может обнаружить опечатку, где вы меняете две буквы, например «Уильям» и «Уиллаим». Я могу придумать несколько способов решить эту проблему, например

    1. делать нечеткий поиск, только если точный поиск не находит совпадений (и покажет сообщение пользователю об этом)
    2. отрегулируйте Bitap, чтобы использовать расстояние Дамерау-Левенштейна, где своп имеет расстояние 1 вместо 2. Согласно википедии , это возможно, но я не смог найти существующую реализацию на Java.
    3. вместо «содержит» выполните «startsWith». Инструменты нечеткого поиска содержат префиксную версию Damerau-Levenshtein, но это дало мне ArrayIndexOutOfBoundsException
    4. скорректировать алгоритм, чтобы ввести ранжирование результатов поиска, где точные совпадения совпадают

    Если вы собираетесь делать 2 или 4, может быть лучше использовать полноценную полнотекстовую библиотеку поиска, такую ​​как Lucene.

  • Более подробную информацию о нечетком поиске можно найти в этом блоге . Автор также создал реализацию в Java под названием BitapOnlineSearcher , но вам нужно использовать java.io.Reader вместе со классом Alphabet. Это Джавадок написан на русском языке.
Question

Я ищу высокопроизводительную библиотеку Java для поиска нечетких строк.

Существует множество алгоритмов поиска похожих строк, расстояния Левенштейна, Daitch-Mokotoff Soundex, n-граммов и т. Д.

Какие реализации Java существуют? Плюсы и минусы для них? Я знаю о Люцене, любое другое решение, или Лучне?

Я нашел их, есть ли у кого-нибудь опыт с ними?




Вы можете попробовать библиотеку Completely , она полагается на предварительную обработку текста для создания индекса в памяти для эффективного ответа (нечетких) поисков в больших наборах данных. В отличие от Lucene и других полнофункциональных текстовых поисковых библиотек, API является небольшим и простым в использовании.




Вы можете попробовать битрейт. Я играл с битом, написанным на ANSI C, и было довольно быстро, что есть реализация java на http://www.crosswire.org .




SimMetrics, вероятно, вам нужно: http://sourceforge.net/projects/simmetrics/

Он имеет несколько алгоритмов для расчета различных вариантов редактирования-расстояния.

Lucene - очень мощная полнотекстовая поисковая система, но поиск FT не совсем то же самое, что и нечеткое сопоставление строк (например, если список строк найдет мне тот, который больше всего похож на некоторую строку-кандидат).