Сложность поиска Lucene

Если я пишу и алгоритм, который выполняет поиск с использованием Lucene, как я могу сформулировать его вычислительную сложность? Я знаю, что Lucene использует tf * idf, но я не знаю, как это реализовано. Я обнаружил, что tf * idf имеет следующую сложность:

O(|D|+|T|)

где D - множество документов, а T - множество всех терминов.

Тем не менее, мне нужен кто-то, кто мог бы проверить, правильно ли это, и объяснить, почему.

спасибо

Ответы

Ответ 1

Lucene в основном использует модель Vector Space Model (VSM) с схемой tf-idf. Итак, в стандартной настройке мы имеем:

  • Набор документов, каждый из которых представлен как вектор
  • Текстовый запрос, также представленный как вектор

Мы определяем K документы коллекции с наивысшими оценками векторного пространства по запросу q. Как правило, мы ищем эти верхние документы K, упорядоченные по счету, в порядке убывания; например, многие поисковые системы используют K = 10 для извлечения и ранжирования первой страницы десяти лучших результатов.

Основным алгоритмом вычисления оценок векторного пространства является:

float Scores[N] = 0
Initialize Length[N]
for each query term t
do calculate w(t,q) and fetch postings list for t (stored in the index)
    for each pair d,tf(t,d) in postings list
    do Scores[d] += wf(t,d) X w(t,q)  (dot product)
Read the array Length[d]
for each d
do Scored[d] = Scores[d] / Length[d]
return Top K components of Scores[]

где

  • Length массива содержит длины (коэффициенты нормировки) для каждого из N документов, тогда как в массиве Scores хранятся оценки для каждого из документов.
  • tf - термин частота члена в документе.
  • w(t,q) - вес представленного запроса для данного термина. Обратите внимание, что запрос обрабатывается как bag of words и вектор весов можно рассматривать (как если бы это был другой документ).
  • wf(d,q) является логарифмическим весом для запроса и документа

Как описано здесь: Сложность векторного точечного произведения, векторного точечного произведения O(n). Здесь измерение - это количество терминов в нашем словаре: |T| , где T - множество членов.

Таким образом, временная сложность этого алгоритма:

O(|Q|· |D| · |T|) = O(|D| · |T|)

рассмотрим | Q | фиксированный, где Q - это набор слов в запросе (средний размер которого низкий, в среднем запрос имеет от 2 до 3 терминов), а D - набор всех документов.

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