1. 首頁 > 生活百科 > >

搜索引擎原理：搜索引擎原理構架介紹？( 三 )

生活百科


水平分桶 ， bitmap優化之后 ， 能極大提高求交集的效率 ， 但時間復雜度仍舊是O(n)
bitmap需要大量連續空間 ， 占用內存較大
方案五：跳表skiplist
有序鏈表集合求交集 ， 跳表是最常用的數據結構 ， 它可以將有序集合求交集的復雜度由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 ， 最后進行集合求交集的過程
（7）有序集合求交集的方法有
a）二重for循環法 ， 時間復雜度O(n*n)
b）拉鏈法 ， 時間復雜度O(n)
c）水平分桶 ， 多線程并行
d）bitmap ， 大大提高運算并行度 ， 時間復雜度O(n)
e）跳表 ， 時間復雜度為O(log(n))
【搜索引擎原理：搜索引擎原理構架介紹？】 好了 ， 這篇文章的內容金華號就和大家分享到這里！

推薦閱讀