Есть ли лучший способ найти множество пересечений для поискового кода?

Question

Я кодировал небольшую поисковую систему и вам нужно выяснить, есть ли более быстрый способ найти множество пересечений. В настоящее время я использую сортированный связанный список, как описано в большинстве алгоритмов поисковой системы. i.e для каждого слова у меня есть список документов, отсортированных по списку, а затем найдите пересечение между списками.

Профилирование производительности корпуса here. Любые другие идеи для более быстрого набора пересечений?

Answer 1

Эффективный способ сделать это является «зиг-заг»:

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

Более подробная информацию можно найти в this lecture notes слайдах 11-13 [прав копирования на первой странице лекционной в]

Answer 2

Вот research paper, который имеет анализ количественный для сравнения текущих алгоритмов.