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

Question

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

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

Answer 1

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

Answer 2

Эффективный способ сделать это с помощью "зигзага":

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

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