“搜索”的原理，架构，实现，实践，面试不用再怕了（值得收藏）！！！

有序链表集合求交集，跳表是最常用的数据结构，它可以将有序集合求交集的复杂度由O(n)降至接近O(log(n))。

集合1{1,2,3,4,20,21,22,23,50,60,70}

集合2{50,70}

要求交集，如果用拉链法，会发现1,2,3,4,20,21,22,23都要被无效遍历一次，每个元素都要被比对，时间复杂度为O(n)，能不能每次比对“跳过一些元素”呢?

跳表就出现了：

集合1{1,2,3,4,20,21,22,23,50,60,70}建立跳表时，一级只有{1,20,50}三个元素，二级与普通链表相同。

集合2{50,70}由于元素较少，只建立了一级普通链表。

如此这般，在实施“拉链”求交集的过程中，set1的指针能够由1跳到20再跳到50，中间能够跳过很多元素，无需进行一一比对，跳表求交集的时间复杂度近似O(log(n))，这是搜索引擎中常见的算法。

简单小结一下：

(1)全网搜索引擎系统由spider, search&index, rank三个子系统构成;

(2)站内搜索引擎与全网搜索引擎的差异在于，少了一个spider子系统;

(3)spider和search&index系统是两个工程系统，rank系统的优化却需要长时间的调优和积累;

(4)正排索引(forward index)是由网页url_id快速找到分词后网页内容list的过程;

(5)倒排索引(inverted index)是由分词item快速寻找包含这个分词的网页list的过程;

(6)用户检索的过程，是先分词，再找到每个item对应的list，最后进行集合求交集的过程;

（编辑：PHP编程网 - 黄冈站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!