как работает поисковый индекс при запросе многих слов?

Question

Я пытаюсь создать собственную поисковую систему для экспериментов.

Я знаю про инвертированные индексы. например, при индексации слов.

ключ - это слово и список идентификаторов документов, содержащих это слово. Поэтому, когда вы ищете это слово, вы сразу получаете документы

как это работает для нескольких слов

вы получаете все документы для каждого слова и просматриваете этот документ, чтобы увидеть, есть ли оба слова?

Я чувствую, что это не так.

Кто-нибудь знает реальный ответ на это, не спекулируя?

Answer 1

Вам необходимо сохранить положение слова в документе в индексном файле.Ваша структура файла индекса должна быть такой: слово id - doc id- no.совпадений - количество попаданий.

Теперь предположим, что запрос содержит 4 слова "w1 w2 w3 w4".Выберите те файлы, содержащие большинство слов.Теперь посчитайте их относительное расстояние в документе.Документ, в котором встречается большинство слов и их относительное расстояние минимально, будет иметь высокий приоритет в результатах поиска.

Я разработал общую поисковую систему без использования какого-либо инструмента сканирования или индексации, доступного в Интернете.Вы можете прочитать подробное описание здесь - Поисковая система

для получения дополнительной информации читайте эту статью основателей Google - нажмите здесь

Answer 2

Я не очень понимаю, почему люди говорят о пересечении для этого.

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

QueryParser такжеподдерживает ключевое слово AND, которое требует наличия в документе обоих слов.

Пример (Lucene.NET, C #):

var outerQuery + new BooleanQuery();
outerQuery.Add(new TermQuery( new Term( "FieldNameToSearch", word1 ) ), BooleanClause.Occur.MUST );
outerQuery.Add(new TermQuery( new Term( "FieldNameToSearch", word2 ) ), BooleanClause.Occur.MUST );

Если вы хотите разделить слова (ваш фактическийпоисковый запрос), используя тот же анализатор, есть способы сделать это тоже.Хотя QueryParser может быть проще в использовании.

Вы можете просмотреть этот ответ, например, о том, как разбить строку, используя тот же анализатор, который вы использовали для индексации:

Нет совпадений при поиске "mvc2" с lucene.net

Answer 3

Как указывает biziclop, для запроса AND необходимо пересекать списки совпадений (или инвертированные списки) для двух условий запроса.

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

Учитывая запрос A AND B, и предположим, что есть совпадения occ (A) для совпадений A и occ (B) для B (т.е. occ (x): = длина списка совпадений для термина x),Предположим, без ограничения общности, что occ (A)> occ (B), т.е. A встречается в документах чаще, чем B. Затем вы выполняете итерацию всех совпадений для B и ищите каждое из них в списке.для A. Если действительно, списки можно искать в логарифмическом времени, это означает, что вам нужно

occ(B) * log(occ(A))

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

Отличная книга, описывающая различные аспектыреализация Управление гигабайтами .

Answer 4

Инвертированный индекс очень эффективен для получения пересечения, используя зигзагообразный алгоритм:

Предположим, ваши термины - это список T:

lastDoc <- 0 //the first doc in the collection
currTerm <- 0 //the first term in T
while (lastDoc != infinity):
  if (currTerm > T.last): //if we have passed the last term:
     insert lastDoc into result
     currTerm <- 0
     lastDoc <- lastDoc + 1
     continue
  docId <- T[currTerm].getFirstAfter(lastDoc-1)
  if (docID != lastDoc):
     lastDoc <- docID
     currTerm <- 0
  else: 
     currTerm <- currTerm + 1

Этот алгоритм предполагает эффективный getFirstAfter() который может дать вам первый документ, который соответствует термину, и его docId больше указанного параметра.Он должен возвращать бесконечность, если его нет.

Алгоритм будет наиболее эффективным, если члены отсортированы так, что самый редкий член будет первым.

Алгоритм обеспечивает максимум #docs_matching_first_term * #terms итераций,но практически - обычно это будет намного меньше итераций.

Примечание: Хотя этот алоритм эффективен, AFAIK lucene не использует его.

Более подробную информацию можно найти в этой лекции слайды 11-13 [авторские права на первой странице лекции]

Answer 5

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