алгоритмы сопоставления строк, используемые Lucene

Question

Я хочу знать алгоритмы сопоставления строк, используемые Apache Lucene. я проходил через индексный формат файла, используемый lucene, данный здесь . Похоже, что lucene хранит все слова, встречающиеся в тексте, с частотой их появления в каждом документе. но, насколько я знаю, для эффективного сопоставления строк необходимо предварительно обработать слова, встречающиеся в Документах.

Пример: поиск "iamrohitbanga является пользователем stackoverflow" (используйте нечеткое соответствие)

в некоторых документах.

возможно, что есть документ, содержащий строку "rohit banga"

чтобы обнаружить, что подстроки rohit и banga присутствуют в строке поиска, будет использовано эффективное совпадение подстрок.

Я хочу знать, какой это алгоритм. также, если это делает некоторую предварительную обработку, то вызов функции в Java API вызывает это.

Answer 1

Как объяснил Ювал, в целом Lucene ориентируется на точное совпадение (путем нормализации условий с помощью анализаторов как по индексу, так и по времени запроса).

В коде магистрали Lucene (еще не выпущенной версии) фактически используется дерево суффиксов для неточных совпадений, таких как Regex, Wildcard и Fuzzy.

Способ, которым это работает, заключается в том, что словарь терминов Lucene сам по себе является формой дерева суффиксов. Вы можете увидеть это в форматах файлов, которые вы упомянули в нескольких местах:

Таким образом, если текст предыдущего термина был «кость», а термин «мальчик», то длина префикса равна двум, а суффикс - «у».

Термин информационный индекс дает нам «произвольный доступ» путем индексации этого дерева через определенные интервалы (по умолчанию каждый 128-й термин).

На нижнем уровне это дерево суффиксов, но на более высоком уровне мы используем эти свойства (в основном те, которые указаны в IndexReader.terms, чтобы трактовать словарь терминов как детерминированный конечный автомат (DFA)):

Возвращает перечисление всех терминов, начинающихся с данного термина. Если данный термин не существует, перечисление позиционируется на первый термин больше, чем предоставленный термин. Перечисление заказано Term.compareTo (). Каждый термин больше всех предшествующих ему в перечислении.

Неточные запросы, такие как Regex, Wildcard и Fuzzy, сами по себе также определяются как DFA, а «сопоставление» - это просто пересечение DFA.

Answer 2

Базовый дизайн Lucene использует точные совпадения строк или определяет эквивалентные строки с помощью Analyzer . Анализатор разбивает текст на индексируемые токены. Во время этого процесса он может сопоставлять эквивалентные строки (например, верхний и нижний регистр, последовательные строки, удалять диакритические знаки и т. Д.) Полученные токены сохраняются в индексе в виде словаря плюс список проводок токенов в документах. Следовательно, вы можете создавать и использовать индекс Lucene, даже не используя алгоритм сопоставления строк, такой как KMP. Однако FuzzyQuery и WildCardQuery используют что-то похожее, сначала находя подходящие термины, а затем используя их для полного соответствия. Пожалуйста, см. Сообщение в блоге Роберта Мьюра об AutomatonQuery для нового, эффективного подхода к этой проблеме.

Answer 3

Как вы указали, в Lucene хранится только список терминов, встречающихся в документах. Как Lucene извлекает эти слова, зависит от вас. По умолчанию анализатор lucene просто разбивает слова, разделенные пробелами. Вы можете написать свою собственную реализацию, которая, например, для исходной строки «iamrohitbanga» дает 5 токенов: «iamrohitbanga», «i», «am», «rohit», «banga».

Пожалуйста, посмотрите документы API Lucene для класса TokenFilter.