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

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

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

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

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

Ответы

Ответ 2

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

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

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

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

Примечания:

  • Алгоритм Bitap, по-видимому, в основном полезен для относительно небольших алфавиты, например. простой ASCII. Фактически версия Simon Watiau, с которой я связан, бросает ArrayIndexOutOfBoundsException на символы, отличные от ASCII ( >= 128), поэтому вам придется отфильтровывать их.

  • Я попытался использовать Bimap в приложении для поиска списка в списке людей по имени. Я обнаружил, что расстояние Левенштейна 2 дает слишком много ложных срабатываний. Расстояние Левенштейна от 1 работ лучше, но он не может обнаружить опечатку, где вы меняете две буквы, например. "Уильям" и "Уиллаим". Я могу придумать несколько способов решить эту проблему, например

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

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

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

Ответ 3

Если вы в основном сравниваете короткие строки и хотите что-то портативное и легкое, вы можете использовать известный алгоритм python fuzzywuzzy портирован на Java.

Вы можете прочитать об этом здесь

Ответ 4

SimMetrics - это то, что вам нужно: http://sourceforge.net/projects/simmetrics/

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

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

Ответ 6

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

Ответ 7

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

Ответ 8

Apache Lucene - единственный способ, я думаю. Я не знаю лучшего поискового lib.

Apache Lucene (TM) - это высокопроизводительная полнофункциональная текстовая поисковая библиотека, полностью написанная на Java. Это технология, подходящая практически для любого приложения, которое требует полнотекстового поиска, особенно кросс-платформенного.