Lucene의 검색 복잡성

Question

Lucene을 사용하여 검색을 수행하고 알고리즘을 작성하면 어떻게 계산 복잡성을 나타낼 수 있습니까? 나는 Lucene이 tf * idf 점수를 사용한다는 것을 알고 있지만 구현 방법을 모른다. 나는 TF의 *의 IDF는 다음과 복잡성을 가지고 있음을 발견했습니다 : D 문서와 T 모든 용어의 집합의 집합입니다

O(|D|+|T|) 

.

그러나이 정보가 올바른지 확인하고 이유를 설명 할 수있는 사람이 필요합니다.

는

Answer 1

루씬은 기본적으로 tf-idf 체계와 Vector Space Model (VSM)을 사용하여 감사드립니다. 따라서, 표준 설정에서 우리는이 :

• 문서의 집합 벡터
• 또한 벡터로 표현하는 텍스트 쿼리

우리는 컬렉션의 K 된 문서를 확인로 표현 각을 쿼리의 가장 높은 벡터 공간 점수는 q입니다. 전형적으로, 우리는 점수가 오름차순으로 정렬 된 K 최고 문서를 찾는다. 예를 들어 많은 검색 엔진은 10 가지 최상의 결과 중 첫 번째 페이지를 검색하고 순위를 매기 위해 K = 10을 사용합니다.

벡터 공간 점수를 계산하기위한 기본 알고리즘은 다음

• 배열 Length가 N 문서의 각 길이 (정규화 인자)를 보유

  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[] 
  

  배열 Scores 반면 각 문서에 대한 점수를 보유합니다.

• tf은 문서에있는 용어의 용어 빈도입니다.
• w(t,q)은 주어진 용어에 대해 제출 된 쿼리의 가중치입니다. 쿼리는 bag of words으로 처리되며 가중치 벡터를 고려할 수 있습니다 (다른 문서 인 것처럼). Complexity of vector dot-product, 벡터 내적이 O(n)이다
• wf(d,q) 질의 및 문서 여기 바와 같이

대한 대수 용어 가중치이다. 여기서 치수는 어휘의 용어 수입니다 : |T|, 여기서 T은 용어 집합입니다.

그래서,이 알고리즘의 시간 복잡도는 다음과 같습니다 우리가 생각

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

| Q를 | 고정되어 있으며, 여기서 Q은 검색어의 단어 집합입니다 (평균 크기는 작고 평균 검색어는 2 ~ 3 용어). D은 모든 문서 집합입니다.

그러나 검색 할 때 이러한 집합은 경계가 있으며 인덱스는 자주 커지지 않습니다.결과적으로 VSM을 사용한 검색은 매우 빠릅니다 (T 및 D이 크면 검색 속도가 매우 느리고 다른 방법을 찾아야합니다).