有没有更好的方法来找到搜索引擎代码的交集？

我一直在编码一个小的搜索引擎，需要找出是否有更快的方法来找到设置交叉点。目前，我按照大多数搜索引擎算法的说明使用排序链接列表。即对于每个单词，我都有列表中的文档列表，然后找到列表中的交集。有没有更好的方法来找到搜索引擎代码的交集？

该案件的性能分析是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

有没有更好的方法来找到搜索引擎代码的交集？

回答

相关问题