Поиск нечетких строк в Java, включая перестановки слов

Question

Я новичок в Java, пытаюсь написать программу, которая сопоставит входные данные со списком предопределенных строк. Я посмотрел на расстояние Левенштейна, но я столкнулся с такими проблемами:

Если у меня есть ввод, такой как «филе говядины», я хочу, чтобы он соответствовал «филе говядины». Проблема в том, что «филе говядины» ближе, согласно расстоянию Левенштейна, к чему-то вроде «филе тунца», что, конечно, неправильно.

Должен ли я использовать что-то вроде Lucene для этого? Используются ли методы Lucene в классе Java?

Спасибо!

Answer 1

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

Основной процесс таков:

• Инициализация: токенизируйте поисковые термины и сохраняйте их в последовательности HashSet с, по одному на каждый термин. Или, если вы хотите дать разные веса каждому слову, используйте HashMap, где слово является ключом.
• Обработка: токенизируйте каждую входную строку и исследуйте каждый из наборов поисковых терминов, чтобы определить, насколько близко они применяются к входному сигналу. См. Выше описание алгоритмов.

Существует простой прием обработки орфографических ошибок: во время инициализации вы создаете наборы, содержащие возможные орфографические ошибки поисковых терминов. Пост Питера Норвига на « Как написать корректор орфографии » описывает этот процесс (он использует код Python, но реализация Java, безусловно, возможна).

Answer 2

Должно быть возможно применить расстояние Левенштейна к словам, а не к символам. Затем, чтобы сопоставить слова, вы можете снова применить Левенштейна на уровне персонажа, чтобы «филе» в «филе говядины» совпадало с «филе» в «филе говядины».

Answer 3

Lucene поддерживает нечеткий поиск по расстоянию Левенштейна.

https://lucene.apache.org/java/2_4_0/queryparsersyntax.html#Fuzzy%20Searches

Но lucene предназначен для поиска по множеству документов, а не по строке поиска, так что lucene может быть излишним для вас. Доступны другие реализации Java. Взгляните на http://www.merriampark.com/ldjava.htm