Map-reduce for pairwise document similarity calculation

The similarity between two documents is usually calculated using vectorized document representation in the space of terms. Terms are simple words, phrases, etc. Vector components are some document's term measures.

One of the most known techniques for calculating these measures or term weights is TF-IDF. There are a bunch of options how exactly calculate TF and IDF.
 
The similarity measure between two documents can be based on those document's vectors.
There are also a number of formulas for calculating it - euclidean distance, cosine similarity, Jaccard Coefficient, Pearson Correlation Coefficient and some other esoteric methods with the cosine similarity method being the most widely used one.

Here I'd like to descibe an algorithm for calculating pairwise similarity calculation for a big corpus of documents. Given a corpus of millions of articles it is very time consuming to calculate each-to-each similarity for entire set.

Initially we have only (document-its terms) set of data. What additional data we need to calculate similarity between any two documents? The IDF factor measures the relevancy of each particular term in entire document set. It needs to get # of documents where a given term occurs and a total amount of docs. So it is a context sensitive parameter. We need to walk through entire data set to calculate each term statistics before we can apply similarity calculation formula for any document pair. It is sometimes desirable to have term statistics for different document sets inside the global set so we can calculate similarities for different contexts later on.

In a nutshell we need to calculate the sum of TF-IDF factors for each co-occuring term for a document pair:

Similarity(doc1, doc2) = sum_over_common_terms ( weight(term, doc1) * weight(term, doc2) ) / normalization(doc1, doc2)

where normalization is often just a product of vectors length.
As one can see this formula is mostly additive. This gives us a nutural way to parallelize the process.We can calculate the contribution of different term sets to similarity add merge them together as the final step.

The entire process can be parallelized using map-reduce paradigm.
The overall flow and data calculation steps for two processing nodes are shown on the following scheme:

Here [...] is a collection notation. 

The main steps are: 

1.  Partition incoming data according to some partition scheme among processing nodes (the most suitable is that each processing node contain the equal amount of data).
2.  On each processing node process document terms sequentially, aggregating data in maps : [Context -> #docs] 
   [Term -> [context id, total # of docs with this term]]
   [Term -> [doc id, frequency]]   
3. Redistribute (for 'reducing' step) this data among processing nodes based on some partitioning       scheme for Term ids. So the first map step emits terms as keys for the reduce step.
   Context statistics (how many docs in each context) can be copied to each processing node as the amount of this data is usually quite small.
4.  On each processing node merge the incoming data maps (there will be 3 different maps).
5.  All the data for each term is now located locally on processing nodes.
   For each term calculate its contribution to the similarity value for a document set where it occurs. Upon completion of this step we have:
   [doc_i -> [doc_j, similarity contribution, normalization contribution]]
   map where similarity takes into account only terms 'local' for the current node. 
6. Drain all the results to a one node sequentially and merge the partial results.
    

Note that steps 1-4 don't depend on processing all data from the previous steps like step 5 does (it needs term statistics which is only available after completion of step 4 for entire data corpus).

This fact makes it possible to use pipelining approach for steps 1-4 above.

One of the most known mapreduce engine is Hadoop. 

Unfortunately, Hadoop's map-reduce implementation doesn't have this useful ability.

There is the independent branch project Hadoop Online Prototype which is capable of doing such things.

Anyway, we still need to wait for a completion of all data preprocessing on the step 5 above.

It is a common situation when new content is received from time to time and there is a need to update and recalculate our similarity matrix. 

It is a big challenge to keep it up-to-date. But that is another story.

Pattern matching для небольших древовидных структур данных

Одним из самых известных и эффективных алгоритмов Pattern matching-а для продукционных систем является Rete_algorithm.

Тут я не буду рассказывать что это такое и с чем его едят, т.к. об этом написаны сотни книг и статей. Расскажу лучше о том как удалось написать собственную альтернативу этому подходу для специфического случая и специфических данных и этот подход дал очень заметный прирост производительности. Прирост в моем случае сравнивается с изначальной имплементацией сделанной на основе библиотеки drools - бесплатной реализации rete-algortihm-а от JBoss. Тут я конечно сильно утрирую, drools - на самом деле это не просто Pattern matching движок а полноценный rule-engine со встроенной поддержкой объектной модели ООП языка. То есть в нем изначально встроены понятия объекта, его класса, полей, наследования и тп. Выразительная мощь такого описания данных через объекты почти равносильна логике первого порядка(FOL), (и, сдается мне, внутри drools переводит высказывания объектной формы в равносильные им высказывания FOL)
Почти, т.к. использование функциональных символов весьма ограничено. Использование последних делает любой логический вывод в FOL настоящей головной болью (т.к., по сути, делает пространство моделей бесконечным), поэтому документация drools не рекомендует их использовать.

Впрочем, этот пост о более приземленных вещах.
Итак, задача состоит в следующем: есть древовидная структура данных, глубина обычно не превышает 5-10 уровней. Каждый узел содержит ссылки на дочерние узлы, кол-во которых произвольно но обычно не превышает 5-6 штук. Каждый узел также содержит 3-4 поля "полезной нагрузки" в виде строковых или числовых полей. Требуется находить в такой модели несколько десятков паттернов-правил, которые меняют это дерево и создают слегка модифицированную его копию которую надо сохранить и также применить к ней эти же правила, и так далее.

Функционально drools замечательно справляется с этой задачей, особенно в части простоты добавления новых правил (это одно из требований задачи). А вот в плане производительности и потребления памяти это решение совсем не устроило. После применения правил и постройки набора новых деревьев нужно иметь возможность применять правила заново к одному из этих новых деревьев. Это можно сделать двумя способами - либо ввести идентификаторы версии внутри дерева либо иметь отдельную сессию drools.
Оба варианта оказались плохими в большей или меньшей степени. Введение идентификаторов усложняет описание паттернов, т.к. нужно включать идентификатор по крайней мере для одного из узлов в запросе, да и держать кучу версий (а их надо обрабатывать желательно не менее 4-6 тысяч в секунду) в памяти, когда в любой момент времени мы нуждаемся в pattern-matching-е только для одного дерева, крайне нежелательно. Создание новой сессии drools также довольно дорогостоящая операция. В итоге оба варианта потребляли около 100-150 MB хипа JVM для обработки одного запроса состоящего примерно из 4-6 тысяч вызовов матчинга правил и выполнялось непозволительно долго.


Напрашивалась возможность каким то образом сократить потребление памяти. Как можно хранить большое количество версий деревьев? Каждое из правил-паттернов в большинстве случаев изменяло лишь небольшую часть дерева, то есть большая часть узлов просто была клоном узлов дерева на котором применялись правила. Поэтому напрашивалась идея создавать новые объекты только для измененных узлов копируя ссылки на остальные. Но при этом может возникнуть ситуация когда мы поменяли узел в дереве (например добавили дочерний узел в его список ссылок) а ссылка на него есть в нескольких других деревьях, которые не должны меняться.
Вариант решения - сделать объекты узлы неизменяемыми (immutable) типами. В этом случае, чтобы опять таки не копировать все дерево, придется отказаться от ссылки на родительский узел.
Вообще, одним из традиционных недостатков immutable типов считается именно потребление памяти - мы вынуждены сделать полную копию даже если хотим поменять сколь угодно малую часть его данных. В случае же, если мы делаем составной неизменяемый объект из неизменяемых объектов то ситуация оказывает много лучшей - мы меняем только измененные объекты. В случае деревьев, мы просто создаем новые версии родительских узлов вплоть до корневого узла. То есть нам например понадобилось изменить узел N6 (см картинку)

Для этого мы просто создаем новый родительский узел N3, копируя старый список ссылок и изменяя в нем лишь ссылку на новый N6. И так далее до корня.

Таким образом мы можем пере-использовать узлы не создавая полные копии деревьев.
Кстати именно таким образом обновляются B+ деревья в базах данных в модели MVCC - обновив лишь log(N) элементов индекса для N записей мы имеем собственную, измененную копию, не мешая остальным.

Что же насчет самого матчинга ?
Простое сокращение объема потребляемой на узлы всех версий деревьев памяти не решило проблему, т.к. большинство ее потреблялось на структуры самой rete-сети. Длительность обработки также существенно не изменилась.
Было решено попробовать сделать собственный, заточенный именно под данную задачу механизм матчинга и неиспользовать drools совсем.
Исходя из данного и потенциального набора правил было замечено что все правила задают параметры узлов не больше 2-3 уровней относительно друг друга и почти все правила имеют фильтры по типам (классам) узлов. А также было очень мало правил которые бы задавали условия между узлами которые не являются предками друг друга или  не имеют непосредственногообщего предка. То есть мой набор паттернов обладал по большей части свойством локальности - большинство (почти все) паттерны задавали соотношения между близкими в дереве узлами.

Поэтому попробовал сделать так - рекурсивно обходим узлы дерева, сохраняя цепочку родительских узлов в стеке, и параллельно создаем битовую маску типов родительских и текущего узлов глубиной в 3 уровня. Для каждого из правил задаем статическую битовую маску необходимых типов исходя из его паттерна. Конечно, поскольку было много правил которые определяли соотношения между узлами с общим предком, пришлось сделать дополнительный проход по потомкам, где, при срабатывании прочих критериев, внутри самих правил делался еще проход по предыдущим "братьям" до первого срабатывания. Естественно этот дополнительный проход запускался только в случае срабатывания критерия по одному из дочерних и родительским (обычно 1+2 уровня вверх) узлам и останавливался при первом же матче.
Мое решение стало работать на 2(!) порядка быстрей по сравнению с изначальным подходом.
Конечно сложность такого алгоритма гораздо больше rete-сети, но в моем случае, для данной специфической задачи, более простой подход оказался гораздо эффективней. То есть тот самый случай когда коэффициент перед N^2 оказался гораздо ниже чем перед N, и, в итоге, на данных объемах данных перевесил почти все плюсы drools.
Почти, так как в моем случае добавление новых правил требует написания дополнительного кода для правила(если есть какие то доп. условия помимо типа узла и его предков), вместо декларативного описания правил в drools.

Простой прием для рандомизации результатов поиска

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

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

Это не такая уж большая проблема если у вас есть некое подобие сессии и вы сохраняете метки записей которые были ему показаны и ваша система не очень крупная. С увеличением нагрузки ситуация осложняется - вы уже не можете хранить в сессии такое количество данных или доставать их из какого то хранилища для каждого запроса и\или число запросов становится очень большим и скорость обработки запроса будет уменьшатся и\или каждый посетитель может менять параметры запроса и\иди данные поиска могут меняться и нужно их как-то синхронизовывать - при любых комбинациях этих факторов хранение показанных результатов и их обработка становится головной болью и может резко снизить производительность системы. К тому же, такой подход подразумевает много дополнительного кода.
Почему просто не хранить номер просмотренной страницы? Данные могут храниться в каком то упорядоченном виде (например отсортированными по алфавиту), а нам желательно делать выборку со всего набора.


Формально, мою задачу можно сформулировать следующим образом (это был не сервис знакомств):
Есть большое кол-во данных по которым производится поиск. Поиск производится по нескольким критериям. Эти критерии в общем случае меняются от запроса к запросу. Ранжирование не нужно. Обычное число результатов на каждый вызов - от сотен до десятков тысяч. Результаты должны быть представлены небольшими порциями по 20-50 штук. Полное число данных известно. Непосредственный поиск осуществлялся при помощи Lucene, на каждый подходящий результат из индекса вызывался наш слушатель с передачей ему идентификатора документа.

Основной идеей было произвольно подменять результаты в конечном списке после его предварительно заполнения первыми подходящими данными.
Пусть N - полное число данных (документов);
n - число записей удовлетворяющих параметрам поиска;
h  - размер "выходного" списка данных - 20-50 штук.

Тогда вероятность каждой записи из множества  n подходящих кандидатов быть представленными в конечно списке есть h/n (h<n). Если бы мы знали n для каждого запроса то можно было бы решить задачу так:
1. Заполнить результирующий список первыми h кандидатами.
2. С каждым новым кандидатом заменить с вероятностью h/n один из h результатов в списке  (Как выбрать конкретный элемент для замены обсуждается ниже).

К сожалению, мы не знаем n в процессе поиска. Можно посчитать это число только после того как поисковая машина пробежалась по всему индексу. Возможное решение - запускать поиск два раза - первый раз для подсчета числа n. Но запускать поиск дважды это слишком дорогое удовольствие с точки зрения нагрузки на систему.
Я "пошел другим путем" - число n можно оценивать динамически по текущей статистике результатов. Если мы пробежались по D (из N) записей и имеем d кандидатов то оцениваем n из простой пропорции d/D ~ n/N. n~d*N/D. То есть n динамически меняется во время процесса.
Вероятность каждого нового кандидата быть представленным в конечном списке есть h/n=h*D/(d*N). Если кандидаты начинают попадаться более часто в индексе то оценочное значение n растет быстрее и мы более часто подменяем результаты и наоборот.

Все эти расчеты, конечно, работают идеально только для равномерно распределенных по индексу кандидатах. Если распределение очень неравномерное то и вероятность также будет не идеальной. Для сервиса знакомств это означает что для некоторых людей вероятность оказаться в результатах поиска будет выше/ниже чем у других. Но ошибка в вычислении вероятности велика только поначалу, когда мы прошли лишь небольшую часть индекса. Чем больше мы продвигаемся вперед и накапливаем статистику тем лучше становится оценка n. На практике распределение данных оказалось достаточно хорошим для использования этого метода.

Другой резонный вопрос в этом подходе - как выбрать элемент для замены в конечном списке.
Первая, наивная мысль была выбрать этот элемент произвольным образом генерируя число из диапазона [0, h-1]. Но в этом случае каждый элемент может быть заменен несколько раз, а другие, с большой долью вероятности не заменены ни разу, так как количество замен в среднем это n*h/n=h. Это противоречит всем предыдущим предположениям о вероятностях.
Фактически, если сделать именно так, то подозрительно большая часть в конечном результате будут из первых h результатов.
Хорошим решением данной проблемы оказалось выбирать произвольное число из диапазона [0, h-1] без повторения. В этом случае каждый кандидат будет иметь равные шансы быть замененным. Что если мы уже выбрали все индексы из этого диапазона? Тогда просто начинаем выбирать сначала - это не нарушит нашу логику так как среднее число замен n*h/n=h.

Как выбирать произвольные числа из набора без повторения [0, h-1]? Это одна из широко известных задач с собеседований в компании типа Google и их решение можно легко найти в сети.

Simple technique for randomizing search results

 There have been some posts recently (like this one) where efficient and elegant solution is possible with a bit of help from probabilistic theory.
I tried to remember if I ever used it for solving tasks I faced with. Here is the one I'd like to tell you about.


Suppose you are writing the dating service and want different persons to be shown for subsequent calls of you main function - 'search for partners that suits me best'.

Imagine a man who looks for a girl and dislikes the ones presented on the first page. Then he scrolls to another chunk of data service provides. He can also launch this function on visiting the service next time.
There is a sence to present different results to him each time.

It is certainly not a big challenge when you have some kind of a session and can keep track of people shown and you system is not very large. As the system grows you can't afford for a number of reasons to store large amount of data per each request/person and|or the number of searching people is huge and processing time is important (records should be fetched from some permanent storage) and|or the search criteria can be changed by users then recording search items shown for each particular user can have a dramatic impact on performance. Tracking implies a lot of coding also.
Why not just keep the latest page number clicked by a user? Tha data in our storage system can be in some arranged form (as it was in my case), for example sorted by a second name, but we need samples from the entire set.

Formally, my task was the following:
There is a huge amount of data to search for. The search is performed with a set of criteria to match. This criteria are generally different for each call. No need for ranging the results. The ususal number of results per each call is hundreds to tens of thousands. The resulted items to be presented in chunks of a size of 20-50. The total number of items is known. The search process was performed by Lucene library with the custom results collector/listener - upon each matching criteria document its id was passed to that custom listener.


The main idea was to randomly substitute the items after filling in the needed 20-50 chunk with the first results.
Let N be total number of data items;
n - is a number of items which match search citeria;
h  - is a chunk size.
Then the probability of each item from n-matching set to be in the result chunk is h/n (h<n). If n were known it would be possible to solve the task in the following way:
1. Fill the result set with first h results.
2. Upon each new match replace one of h-results with probability of h/n (How to choose which element to subsitute is described later).

Unfortunately, we don't know the number n while searching. It is only known after search engine has walked over the entire index. One possible solution is to walk two times - the first walk is to calc n number. But having two index passes might be too expensive solution from performance point of view.
Another solution I developed was to estimate n based on the current rate of results.
If the engine has walked over D (out of N) items and there are d matches one can estimate n from a simple proportion d/D ~ n/N. n~d*N/D.
So n is dynamically changing over the search process. The probability of each new match to be presented in the resulted chunk is h/n=h*D/(d*N). If the matching data start to be densely located in the index - the estimated number of total results rises quickly and it tends to replace the items in the result chunk more often and vice versa.
This certainly works best for uniformly distributed data. If the data distribution in an index is very skew the probability of appearing in the result chunk for some items will also be skewed. For dating service it means some persons will have higher probabilty to be presented than the others.
The error of probabilty estimation will be higher for initial part of the index. The more we move to the end of the index the less the estimation error.  In practice, the data distribution appeared to be good enough to follow this way.
Another question is how to choose the item to substitute from the filled list of results.
The first, naive thought, was to choose index of element for replacement by generating uniformly distributed value from 0 to h each time replacement is needed.
In this case some items may be replaced multiple times and this contradicts to the estimation of probability to be in the list =n/N. In fact, if you do this the wrongly great part of the results will be from the first h matches.
The possible silution is to pick random value from [0, h-1] values without repetition. In this case each item will have equal probability to be replaced. If it runs out of index values for replacement - just start again as this won't harm the logic - the average number of replaces is n*h/n=h.
How to pick random value from [0, h-1] values without repetition? This is one of well-known "Google interview"-like questions and one can easily find how to solve it.

Navigating multiple inversed indexes

or the story about creating custom PhraseQuery for Lucene with black-jack non-strict number of search terms

Lucene is possibly the most known open-source full-text search engine. Having worked with it quite a lot I am very surprised that it lacks the function for efficient searching of phrases with non-strict number of terms.


Suppose you are searching for some phrase and want to see the results even if some terms in your query are not presented in the results (but those documents that have all the terms in the correct order are still on the top).
I.e. you are searching for "homes in new york with swimming pools" and still expecting to see the results with "homes in new york with pools" | "homes in new york with rooftop pools".
The standard Lucene's class to deal with phrase queries - PhraseQuery. It does the amazing thing with calculating and scoring the "slope" of your terms in the text but searches for all terms in your query. One can accomlish original task by constructing a massive tree-structure of subqueries but it will work very slowly and the code will look pretty bad and is certainly not the way to go for a performance maniac like me.

Here I present my own approach to solve this task. It can be viewed as a generalization algorithm for Lucene's PhraseQuery.

Abstracting out of Lucene this task can be described as follows:
You have a system of inverted indexes for each term(word) in you query. The inverted index in a nutchell is a list of document|row ids or pointers to docs|rows that contain the specific term|word. So this structure is designed to answer the question "which documents contain this word?". Usually such indexes are augmented with some 'fast navigation to desired document id' function. The most obvious implementation that supports this function efficiently is skip-list. Lucene has two main types of inverted indexes - TermDocs and TermPositions. The first one describes documents and frequences of a term in each document and the second class contains also the term's positions.

The simple pseudo-code for our index is:

Index {

    doc(): returns current docId

    nextDoc() : returns next docId

    scrollTo(docId)

}

So we have a set of such indexes (each per query word|term).



The main task is to find all docs which have at least m out of n possible words
For example, if m=3 then documents 4 and 12 (see pic.) should be in the results set.
If m=2 documents 2, 7, 9 should also be presented.


Scrolling an index usually possible only in the forward direction to save index space in memory (in this case it only needs the forward pointers for skip list).

This dictates the natural way of processing indexes - scroll one of them and check the current doc id of all indexes. Assume the maximum current document Id for indexes is M and minimum is m and if we increment the index with min docId and its next doc value m2 appears to be m2>M then we can be sure that there are no docs with ids<m2 that contain all the terms and we can scroll the other indexes up to m2.

Employing these facts it is possible to work out the following algorithm:

1. Move all the indexes to the first position and sort them according to docIds in ascending order

2. If the number of indexes is less than m stop the process.

3. Check the docId of the first index and the m-th index in the list.

4. If they are equal we have a match of at least m terms for doc=doc_1. We can process this result further - check if there are more than m matches and calculate the slope of terms inside the text. Suppose we have m2 matches (m<=m2<=n). Now, after the slope processing, we can increment these m2 indexes to their next docs and sort the list.

5. Otherwise doc_1<doc_m (indexes are sorted). Scroll index 1 up to doc_m as there are no new results for docId<doc_m.

6. The new doc_1>=doc_m or null when an index runs out of docs. If new doc_1 is not null insert the first index in the list of indexes in order to keep it sorted. There is only need to check for doc_1>doc_i where i>m. One can employ binary search or simple sequential iteration to scan the m-th to N tail of the index list. Usually the number of search terms is small so the simple one-by-one check would be enough.

7. If the first index runs out of docs - remove it from the index list.

8. Go to step 2.

Suppose we are searching for at least m=2 tokens in the query "word1 word2 word3" for indexes shown on the pic above. Suppose that 25, 13, 12 are the last docIds for those three indexes.

Introduce the notion of index state in the list - (i, d) - index for i-th word has current pointer to the doc=d.

Then the algorithm steps are:
The index list is (1,1) (2,2) (3,2).
Check doc_1 & doc_m=doc_2 : 1<2. Scroll index1 up to doc_2=2. The new value for the first index is 4.
So we have the index list : (1,4) (2,2) (3,2)
Insert (1,4) to the appopriate position to keep the list sorted:
  (2,2) (3,2) (1,4) - we have a match doc_1=doc_m=doc_2=2;

The further list states and matches are:
  (2,2) (3,2) (1,4)  results: [2]; increment (2,2) (3,2) and sort the list
  (2,4) (3,4) (1,4)  results: [2,4];  incrementall and sort
  (2,5) (1,7) (3,7) results: [2,4]; scroll (2,5) to doc=7 & insert in the new position
  (1,7) (3,7) (2,9) results: [2,4,7];
  (1,8) (3,9) (2,9) results: [2,4,7]; scroll (1,8) to doc=9
  (3,9) (2,9) (1,12) results: [2,4,7,9];
  (3,10) (2,12) (1,12) results: [2,4,7,9];   scroll (3,10) to doc=12
  (2,12) (1,12) (3,12) results: [2,4,7,9,12];
  (2,13) (1,20) results: [2,4,7,9,12];   scroll (2,13) to doc=20
  (1,20) results: [2,4,7,9,12]; STOP



I hope the idea of algorithm is clear now and one can use it to write his own implementation of PhraseQuery with an ability to specify the minimum number of matching terms and a custom strategy for scoring matches with different number of containing terms.

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

или история о том как написать собственный 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 с возможность задать минимальное число совпадений и собственной стратегией ранжирования документов с разным количеством совпавших термов а также их отклонением от позиций в запросе.