검색 엔진 코드의 교차로를 찾는 더 좋은 방법이 있습니까?

Question

저는 작은 검색 엔진을 코딩 해 왔으며 설정된 교차점을 찾는 더 빠른 방법이 있는지 알아야합니다. 현재 대부분의 검색 엔진 알고리즘에서 설명한대로 정렬 된 링크 된 목록을 사용하고 있습니다. 즉 모든 단어에 대해 목록의 문서 목록을 정렬 한 다음 목록 간의 교차점을 찾습니다.

사례의 성능 프로파일 링은 here입니다. 더 빠른 세트 교차로에 대한 다른 아이디어가 있습니까? 목록 T 당신의 기간입니다 가정

:

Answer 1

그것을 할 수있는 효율적인 방법은 "지그재그"입니다

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

에서 찾을 수 있습니다 여기에 현재의 알고리즘을 비교하기위한 quantitave 분석이있는 research paper을합니다.