Поиск по нескольким инвертированным индексам 

или история о том как написать собственный PhraseQuery для Lucene с блэкджеком  необязательным присутствием всех термов

Широко известная библиотека Lucene является, пожалуй, самым известным open-source решением для полнотекстового поиска. Поработав достаточно длительное время с ним, я искренне удивлен почему в нем до сих пор нет эффективной возможности поиска фразы с необязательным присутствием всех термов из запроса.


Предположим поисковый запрос состоит из нескольких слов и вы хотите чтобы в результатах поиска были документы в которых присутствуют не все слова (но конечно те документы где присутствуют все слова в исходном порядке должны быть на первых местах в выдаче).
Например вы ищете "homes in new york with swimming pools" и ожидаете от системы выдачи результатов в которых присутствуют "homes in new york with pools"/"homes in new york with rooftop pools" и т.д.

Стандартный механизм в Lucene для таких вещей - использовать класс PhraseQuery. Для ранжирования документов содержащих все символы (в терминах Lucene правильней было бы сказать "документов с полем содержащим...", но для простоты будем считать что поиск идет по одному полю и не будем о нем упоминать) он умеет рассчитывать отклонение позиций термов от их исходного порядка в запросе. Но, к сожалению, его проблема в том что он в обязательном порядке ищет присутствие всех термов из запроса. На практике эта проблема обычно решается конструированием громоздкого дерева под-запросов которое работает очень медленно и усложняет код.

Здесь я хочу представить простой алгоритм который решает эту задачу.

Абстрагируясь от Lucene-а, эту задачу можно описать следующим образом:

Имеется набор инвертированных индексов для каждого терма(слова) из запроса.
Для тех, кто не знаком с понятием инвертированного индекса - это, грубо говоря, список документов|записей и/или их указателей которые содержат данный терм. То есть это структура данных основной целью которой является дать ответ на вопрос "какие документы содержат данное слово?". Обычно инвертированные индексы снабжены также возможностью эффективно перемещаться до заданного документа (обычно это достигается использованием "скип"-списков). В Lucene есть два основных класса-типа для работы с инвертированным индексом - TermDocs and TermPositions. Первый выдает список документов с частотой встречаемости терма а второй класс выдает вдобавок список позиций терма в поле.

Используя псевдо-код, интерфейс такого индекса можно представить следующим образом:

Index {

    doc(): returns current docId

    nextDoc() : returns next docId

    scrollTo(docId)

}

Итак, имеется набор таких индексов (по одному на каждый терм).



Задача в том чтобы найти все документы которые содержат по крайней мере m из возможных n термов (мы все же хотим иметь возможность задать границу количества необходимых тер ).
Например, для картинки выше, если m=3 тогда в результатах должны быть документы 4 и 12
Если m=2 то документы 2, 7, 9 также должны быть представлены.


Скроллинг индекса обычно возможен только в прямом направлении (по очевидной причине экономии места в памяти/диске на обратные указатели).

То есть, все что мы можем делать делаем - скроллировать или инкрементировать индексы и делать проверку всех индексов на предмет совпадения их текущих id документов. Если, допустим, наибольший текущий id документа по всем индексам есть M а наименьший m и при инкрементировании индекса с минимальным id мы получем значение m2>M то мы можем точно сказать что нет документов в id<m2 которые бы содержали все термы данного набора индексов.

Принимая в внимание эти факты можно предложить следующий алгоритм:

1. Инициализировать все индексы (переместить на первую позицию) и отсортировать их по возрастанию первого docId.

2. Если число индексов меньше заданного в условии числа m тогда останавливаемся.

3. Сравнить docId первого в списке индекса с docId m-го по счету индекса в списке.

4. Если они равны то мы получили искомый docId для по крайней мере m термов. Тут мы можем посмотреть линейным просмотром индексов после m-го точное число совпадений и передать результат дальше для вычисления slop-а , то есть , если грубо, некого суммарного отклонения термов от оригинальных позиций (это все можно взять в готовом в виде из Lucene). Тут мы можем также применить какие то свои функции для ранжирования результатов (например чтобы результаты с большим числом совпадений вне зависимости от slop-а были выше). Если у нас имеется m2 совпадений с списке индексов (m<=m2<=n), то мы инкрементим их и сортируем список (отбрасывая индексы которые "закончились"). Прыгаем на пункт 2.

5. Иначе у нас случай doc_1<doc_m (индексы ведь сортированы). Скроллируем первый индекс до значения doc_m поскольку точно знаем что результатов с docId<doc_m нет.

6. Новое значение индекса doc_1>=doc_m или null когда индекс "кончается". Если doc_1!=null, то вставляем первый индекс в список на такую позицию чтобы он оставался отсортированным. Для этого достаточно только проверить индексы после m-го то тех пор пока не найдем doc1<=doc_j. Если число индексов велико то можно воспользоваться бинарным поиском.

7. Если индекс "кончился" удаляем его из списка.

8. Возвращаемся в п.2.

Для иллюстрации работы предположим что есть поисковый запрос "word1 word2 word3" соответствующие трем индексам выше на картинке. И ищем наличие минимум 2-х слов Положим 25, 13, 12 - последние значения docId для этих 3-х индексов.

Введем обозначения состояния индекса в списке (i, d) - индекс для i-го терма имеет текущее значение документа d.

Тогда шаги алгоритма таковы:
Начальный список есть (1,1) (2,2) (3,2).
Сравнимаем doc_1 <> doc_m=doc_2 : 1<2. Скроллим первый индекс до doc_2=2. Новое значение - 4.
Имеем: (1,4) (2,2) (3,2)
Вставляем (1,4) в соответствующую позицию списка:
  (2,2) (3,2) (1,4) - есть результат doc_1=doc_m=doc_2=2;

Дальнейший список состояний списка таков:
  (2,2) (3,2) (1,4)  результат [2]; инкрементим (2,2) (3,2) и сортируем
  (2,4) (3,4) (1,4)  результат [2,4];  инкрементим и сортируем
  (2,5) (1,7) (3,7) результат  [2,4]; скроллим (2,5) до doc=7
  (1,7) (3,7) (2,9) результат [2,4,7];
  (1,8) (3,9) (2,9) результат [2,4,7]; скроллим (1,8) до doc=9
  (3,9) (2,9) (1,12) результат [2,4,7,9];
  (3,10) (2,12) (1,12) результат [2,4,7,9];   скроллим (3,10) до doc=12
  (2,12) (1,12) (3,12) результат [2,4,7,9,12];
  (2,13) (1,20) results: [2,4,7,9,12];   скроллим (2,13) до doc=20
  (1,20) results: [2,4,7,9,12]; все!


Надеюсь, идея алгоритма ясна, и теперь вы можете написать свою собственную реализацию PhraseQuery с возможность задать минимальное число совпадений и собственной стратегией ранжирования документов с разным количеством совпавших термов а также их отклонением от позиций в запросе.