1. 首頁 > 生活百科 > >

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

生活百科


舉個例子 ， 假設有3個網頁：
url1 -> “我愛北京”
url2 -> “我愛到家”
url3 -> “到家美好”
這是一個正排索引Map 。
分詞之后：
url1 -> {我 ， 愛 ， 北京}
url2 -> {我 ， 愛 ， 到家}
url3 -> {到家 ， 美好}
這是一個分詞后的正排索引Map<url, list> 。
分詞后倒排索引：
我 -> {url1, url2}
愛 -> {url1, url2}
北京 -> {url1}
到家 -> {url2, url3}
美好 -> {url3}
由檢索詞item快速找到包含這個查詢詞的網頁Map<item, list>就是倒排索引 。
正排索引和倒排索引是spider和build_index系統提前建立好的數據結構 ， 為什么要使用這兩種數據結構 ， 是因為它能夠快速的實現“用戶網頁檢索”需求（業務需求決定架構實現） 。
提問：搜索的過程是什么樣的？
假設搜索詞是“我愛” ， 用戶會得到什么網頁呢？
（1）分詞 ， “我愛”會分詞為{我 ， 愛} ， 時間復雜度為O(1)
（2）每個分詞后的item ， 從倒排索引查詢包含這個item的網頁list ， 時間復雜度也是O(1)：
我 -> {url1, url2}
愛 -> {url1, url2}
（3）求list的交集 ， 就是符合所有查詢詞的結果網頁 ， 對于這個例子 ， {url1, url2}就是最終的查詢結果
看似到這里就結束了 ， 其實不然 ， 分詞和倒排查詢時間復雜度都是O(1) ， 整個搜索的時間復雜度取決于“求list的交集” ， 問題轉化為了求兩個集合交集 。
字符型的url不利于存儲與計算 ， 一般來說每個url會有一個數值型的url_id來標識 ， 后文為了方便描述 ， list統一用list替代 。
list1和list2 ， 求交集怎么求？
方案一：for * for ， 土辦法 ， 時間復雜度O(n*n)
每個搜索詞命中的網頁是很多的 ， O(n*n)的復雜度是明顯不能接受的 。倒排索引是在創建之初可以進行排序預處理 ， 問題轉化成兩個有序的list求交集 ， 就方便多了 。
方案二：有序list求交集 ， 拉鏈法

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

文章插圖
有序集合1{1,3,5,7,8,9}
有序集合2{2,3,4,5,6,7}
兩個指針指向首元素 ， 比較元素的大小：
（1）如果相同 ， 放入結果集 ， 隨意移動一個指針
（2）否則 ， 移動值較小的一個指針 ， 直到隊尾
這種方法的好處是：
（1）集合中的元素最多被比較一次 ， 時間復雜度為O(n)
（2）多個有序集合可以同時進行 ， 這適用于多個分詞的item求url_id交集
這個方法就像一條拉鏈的兩邊齒輪 ， 一一比對就像拉鏈 ， 故稱為拉鏈法
方案三：分桶并行優化
數據量大時 ， url_id分桶水平切分+并行運算是一種常見的優化方法 ， 如果能將list1和list2分成若干個桶區間 ， 每個區間利用多線程并行求交集 ， 各個線程結果集的并集 ， 作為最終的結果集 ， 能夠大大的減少執行時間 。
舉例：
有序集合1{1,3,5,7,8,9, 10,30,50,70,80,90}
有序集合2{2,3,4,5,6,7, 20,30,40,50,60,70}
求交集 ， 先進行分桶拆分：
桶1的范圍為[1, 9]
桶2的范圍為[10, 100]
桶3的范圍為[101, max_int]
于是：
集合1就拆分成
集合a{1,3,5,7,8,9}
集合b{10,30,50,70,80,90}
集合c{}
集合2就拆分成
集合d{2,3,4,5,6,7}
集合e{20,30,40,50,60,70}
集合e{}
每個桶內的數據量大大降低了 ， 并且每個桶內沒有重復元素 ， 可以利用多線程并行計算：
桶1內的集合a和集合d的交集是x{3,5,7}
桶2內的集合b和集合e的交集是y{30, 50, 70}
桶3內的集合c和集合d的交集是z{}
最終 ， 集合1和集合2的交集 ， 是x與y與z的并集 ， 即集合{3,5,7,30,50,70}
方案四：bitmap再次優化
數據進行了水平分桶拆分之后 ， 每個桶內的數據一定處于一個范圍之內 ， 如果集合符合這個特點 ， 就可以使用bitmap來表示集合：
搜索引擎原理：搜索引擎原理構架介紹？

文章插圖
如上圖 ， 假設set1{1,3,5,7,8,9}和set2{2,3,4,5,6,7}的所有元素都在桶值[1, 16]的范圍之內 ， 可以用16個bit來描述這兩個集合 ， 原集合中的元素x ， 在這個16bitmap中的第x個bit為1 ， 此時兩個bitmap求交集 ， 只需要將兩個bitmap進行“與”操作 ， 結果集bitmap的3 ， 5 ， 7位是1 ， 表明原集合的交集為{3,5,7}

推薦閱讀