有沒有更好的方法來找到搜索引擎代碼的交集？

我一直在編碼一個小的搜索引擎，需要找出是否有更快的方法來找到設置交叉點。目前，我按照大多數搜索引擎算法的說明使用排序鏈接列表。即對於每個單詞，我都有列表中的文檔列表，然後找到列表中的交集。有沒有更好的方法來找到搜索引擎代碼的交集？

該案件的性能分析是here。快速設置交叉點的任何其他想法？

2012-02-09 Harisankar Krishna Swamy

您可以從二進制搜索開始，避免開始時的線性步進。（這可以通過一些'狩獵'方法擴展到重疊部分）BTW：鏈接列表不是大型有序集合的最佳表示。你可以嘗試數組。 – wildplasser 2012-02-09 11:29:11

二分查找是一個好主意。如果引入它將有助於跳過。那麼數組Vs列表是否真的很重要，如果僅在更新搜索數據結構時更改列表/數組？非常感謝 – 2012-02-09 13:13:16

一個有效的方式做到這一點是通過「曲折」：

假設你而言是一個列表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在演講的第一頁的複製權限]

來源

2012-02-09 11:25:37 amit

會給這個嘗試，看看它的票價。 thanx – 2012-02-09 13:15:48

發現這裏有一個research paper有比較當前算法quantitave分析。

來源

2012-02-09 11:44:13 kossmoboleat

將有一個經歷，謝謝你。 – 2012-02-09 13:10:44

有沒有更好的方法來找到搜索引擎代碼的交集？

回答

相關問題