鏈接分析

我們在最開始說過，搜索引擎在查找能夠滿足用戶需求的網(wǎng)頁時，主要會考慮兩方面的因素，一方面是用戶發(fā)出的查詢與網(wǎng)頁內(nèi)容的相關(guān)性得分，另一點就是通過鏈接分析方法計算獲得的得分，也即網(wǎng)頁的重要性。

PageRank算法

PageRank算法是Google創(chuàng)始人于1997年構(gòu)建早期搜索系統(tǒng)原型時提出的鏈接分析算法，目前很多重要的鏈接分析算法都是在PageRank算法基礎(chǔ)上衍生出來的。

對于某個網(wǎng)頁A來說，該網(wǎng)頁的PageRank計算基于以下兩個基本假設(shè)：

• 數(shù)量假設(shè)：在Web圖模型中，如果一個頁面節(jié)點接收到的其他網(wǎng)頁指向的入鏈數(shù)量越多，那么這個頁面越重要。
• 質(zhì)量假設(shè)：指向頁面A的入鏈質(zhì)量不同，質(zhì)量高的頁面會通過鏈接向其他頁面?zhèn)鬟f更多的權(quán)重。所以越是高質(zhì)量的頁面指向頁面A，頁面A越重要。

PageRank計算得出的結(jié)果是網(wǎng)頁的重要性評價，這和用戶輸入的查詢是沒有任何關(guān)系的。也即如果有一個搜索引擎完全基于PageRank，那用戶不論輸入什么查詢語句，返回的結(jié)果都是相同的，都是PageRank值最高的頁面。

PageRank計算

初始階段，每個頁面設(shè)置相同的PageRank值，通過若干輪的計算，每個頁面會收斂到最終的PageRank值。

在一輪PageRank得分的更新計算中，每個頁面將其當前的PageRank值平均分配到本頁包含的出鏈上，這樣每個鏈接即獲得了相應的權(quán)值。而每個頁面將所有指向本頁面的入鏈所傳入的權(quán)值求和，即可得到新的PageRank得分。當每個頁面都獲得了更新后的PageRank值，就完成了一輪PageRank計算。

鏈接陷阱與遠程跳轉(zhuǎn)

如果仔細思考一下就會發(fā)現(xiàn)上面的PageRank算法存在問題。一個典型的例子就是鏈接陷阱，比如三個網(wǎng)頁，相互鏈接指向，形成了一個環(huán)結(jié)構(gòu)，這種結(jié)構(gòu)在計算PageRank的時候，該結(jié)構(gòu)將導致系統(tǒng)只會吸收傳入的分支，而不能將獲得的分值傳播出去，隨著PageRank一輪輪地連續(xù)計算，鏈接陷阱內(nèi)的頁面PageRank值將會越來越高。

遠程跳轉(zhuǎn)是解決鏈接陷阱的通用方式，所謂遠程跳轉(zhuǎn)，即在網(wǎng)頁向外傳遞分值的時候，不限于向出鏈所指網(wǎng)頁傳遞，也可以以一定的概率向任意其他網(wǎng)頁跳轉(zhuǎn)。權(quán)值通過這種虛擬邊向外傳遞，以此來避免鏈接陷阱導致的問題。

HITS算法（Hypertext Induced Topic Selection）

Hub頁面與Authority頁面

Hub頁面與Authority頁面是HITS算法最基本的兩個定義，所謂Authority頁面是指與某個領(lǐng)域或某個話題相關(guān)的高質(zhì)量網(wǎng)頁；所謂Hub頁面，指的是包含了很多指向高質(zhì)量Authority頁面鏈接的網(wǎng)頁。

相互增強關(guān)系

HITS算法隱含并利用了兩個基本假設(shè)：

• 一個好的Authority頁面會被很多好的Hub頁面指向
• 一個好的Hub頁面會指向很多好的Authority頁面

通過這種相互增強關(guān)系不斷迭代計算，即可找出哪些頁面是高質(zhì)量的Hub頁面和Authority頁面。

HITS算法流程

HITS算法與PageRank一個顯著的區(qū)別就是HITS算法與用戶輸入的查詢請求密切相關(guān)，而PageRank算法是與查詢無關(guān)的全局算法。

HITS算法接收到了用戶查詢之后，會將查詢提交給某個現(xiàn)有的搜索引擎或是自己構(gòu)建的檢索模型，并在返回的搜索結(jié)果中，提取排名靠前的網(wǎng)頁，得到一組與用戶查詢高度相關(guān)的初始網(wǎng)頁集合，這個集合被稱為根集。

在根集的基礎(chǔ)上，凡是與根集網(wǎng)頁有直接鏈接指向關(guān)系（指向根集內(nèi)頁面/根集頁面有鏈接指向）的網(wǎng)頁都被擴充進擴展網(wǎng)頁集合。HITS算法在這個擴展網(wǎng)頁集合內(nèi)尋找好的Hub頁面與Authority頁面。

對于擴展網(wǎng)頁集合，我們對每個頁面都設(shè)置兩個初始權(quán)值，一般將Hub權(quán)值和Authrity權(quán)值都初始化為1

之后可以根據(jù)前面的兩條基本假設(shè)不斷進行迭代，直到權(quán)值收斂。

HITS算法存在主題漂移問題，如果在擴展網(wǎng)頁集合里包含部分與查詢主題無關(guān)的頁面，而且這些頁面之間有較多的相互鏈接指向，那么HITS算法很可能給給予這些無關(guān)網(wǎng)頁很高的排名，這種現(xiàn)象被稱為緊密鏈接社區(qū)現(xiàn)象。

HITS算法計算效率較低，且較容易被作弊者操縱結(jié)果，而PageRank因為增加了遠程跳轉(zhuǎn)，機制上優(yōu)于HITS算法。

SALSA算法

SALSA算法融合了PageRank與HITS算法的基本思想，是目前效果最好的鏈接分析算法之一。

SALSA算法有兩個階段，首先是確定計算對象集合的階段，這一階段與HITS算法基本相同；第二階段是鏈接關(guān)系傳播過程，這一階段采納了PageRank的隨機游走模型。

首先SALSA算法像HITS算法一樣算出擴展網(wǎng)頁集合。

之后，SALSA算法根據(jù)網(wǎng)頁鏈接關(guān)系，將擴展網(wǎng)頁集合轉(zhuǎn)換為一個二分圖，一個子集合是Hub集合，另一個是Authroity集合，規(guī)則如下：

• 如果一個網(wǎng)頁網(wǎng)頁包含出鏈指向擴展網(wǎng)頁集合內(nèi)其他節(jié)點，則這個網(wǎng)頁可以被歸入Hub集合
• 如果一個網(wǎng)頁網(wǎng)頁包含擴展網(wǎng)頁集合內(nèi)其他節(jié)點指向的入鏈，則這個網(wǎng)頁可以被歸入Authority集合

根據(jù)以上規(guī)則，如果某個網(wǎng)頁同時包含入鏈和出鏈，則可以同時歸入兩個集合。Hub集合內(nèi)網(wǎng)頁的出鏈組成了二分圖的邊。

與HITS算法不同，這里SALSA在形成二分圖之后，原來的有向邊不再保留方向，轉(zhuǎn)換為無向邊：

二分圖

接下來是鏈接關(guān)系傳播階段，SALSA算法舍棄了HITS的相互增強假設(shè)，轉(zhuǎn)而采用PageRank隨機游走模型的思想。

SALSA算法假設(shè)存在某個瀏覽者，從子集合中隨機選擇一個節(jié)點出發(fā)，如果節(jié)點包含多條邊，則以相等概率隨機選擇一條邊，從Hub（Authority）子集合跳到Authority（Hub）集合內(nèi)節(jié)點，如此不斷在兩個子集之間轉(zhuǎn)移，形成了SALSA自身的鏈接關(guān)系傳播模式。

這個隨機游走模型看起來與PageRank不同，但實際上『以相等概率隨機選擇一條邊』與『每個頁面將其當前的PageRank值平均分配到本頁包含的出鏈上』是等價的。而HITS算法屬于權(quán)值廣播模式，即將節(jié)點本身的權(quán)值完全傳播給有鏈接指向的節(jié)點，并不根據(jù)鏈接多少進行分配。

之后我們要將二分圖轉(zhuǎn)化為Authority節(jié)點關(guān)系圖。

得到Authority節(jié)點關(guān)系圖要去掉原二分圖中的Hub節(jié)點，只保留Authority節(jié)點，并新建Authority節(jié)點之間的鏈接關(guān)系，Authority節(jié)點之間的鏈接關(guān)系繼承自二分圖中原有的鏈接關(guān)系。簡單舉個例子，Authority節(jié)點A到B的鏈接概率為原二分圖中所有A到B的間接路徑的概率和，而每條間接路徑的概率通過這條路徑上所有子路徑的概率乘積計算得出，每條子路徑的概率根據(jù)所屬節(jié)點出鏈的個數(shù)平均分配。最后得到的Authority節(jié)點關(guān)系圖如下：

可以發(fā)現(xiàn)節(jié)點1是獨立的，是因為在原二分圖中并不存在由節(jié)點1到節(jié)點3/5/6的任何間接路徑。（其實Authority節(jié)點關(guān)系圖在后面起到的作用只是判斷哪些節(jié)點之間是連通的，轉(zhuǎn)移概率并沒有用到）

建好Authority節(jié)點關(guān)系圖之后，即可根據(jù)隨機游走模型來計算每個節(jié)點的Authority權(quán)值。在實際計算過程中，SALSA將搜索結(jié)果排序問題進一步轉(zhuǎn)換為求Authority節(jié)點矩陣的主秩問題，矩陣的主秩即為每個節(jié)點的相應Authority權(quán)值得分，按照Authority得分由高到低排列，即可得到最終的搜索排序結(jié)果。

簡單說一下，我們根據(jù)Authority節(jié)點關(guān)系圖得知節(jié)點3、5、6是連通的，1是獨立的，然后我們根據(jù)如下公式計算每個Authority節(jié)點的Authority權(quán)值得分：

這個式子很好理解，第一部分就是當前節(jié)點所在的子連通圖的節(jié)點個數(shù)占總節(jié)點個數(shù)的百分比，也即當前節(jié)點所在子連通圖對于整個Authority節(jié)點關(guān)系圖的重要程度；第二部分是當前節(jié)點的入鏈個數(shù)占當前節(jié)點所在子連通圖入鏈個數(shù)的百分比，也即當前節(jié)點在當前節(jié)點所在子連通圖的重要程度。從式子中也可以看出，所有Authority節(jié)點的權(quán)值之和為1。

舉個例子，節(jié)點3的權(quán)重最后計算結(jié)果為0.25，3/4乘2/6。

另外，如果整個Authority節(jié)點關(guān)系圖是連通的，那么SALSA算法退化為根據(jù)節(jié)點入鏈個數(shù)決定排序順序的算法。

SALSA算法不需要像HITS算法一樣進行不斷的迭代，所以計算效率要快于HITS算法，也同時解決了HITS算法的主題漂移問題（一是因為去掉了Hub頁面，二是傾向于取Authority中重要連通圖中重要的子Authority節(jié)點）。SALSA算法是目前效果最好的鏈接分析算法之一。

主題敏感 PageRank（Topic Sensitive PageRank）

PageRank算法與查詢無關(guān)，只能作為相似度計算的一個因子體現(xiàn)作用，無法獨立使用。而主題敏感PageRank是查詢相關(guān)的，可單獨作為相似度計算公式使用。

主題敏感 PageRank 主要有兩個計算步驟，第一個是離線的分類主題PageRank數(shù)值計算；第二步是在線利用算好的主題PageRank分值，來評估網(wǎng)頁和用戶查詢的相似度。

第一步是參考ODP網(wǎng)站，ODP網(wǎng)站定義了16個大的主題類別，每個主題類別下有人工收集的精選高質(zhì)量網(wǎng)頁地址。然后以這16類主題類型的網(wǎng)頁為基礎(chǔ)，計算PageRank分值，即每個網(wǎng)頁會被賦予16個主題相關(guān)的PageRank分值。不像普通的PageRank算法，所有的權(quán)值都被初始化為1，人工收集的精選高質(zhì)量網(wǎng)頁地址會被賦予較高的權(quán)值，然后由它們根據(jù)鏈接關(guān)系向其它網(wǎng)頁傳遞權(quán)值。

第二步是在線相似度計算，首先要根據(jù)用戶查詢分類器對查詢進行分類，計算用戶屬于定義好的各個類別的概率分別是多少，然后再相應的乘以待計算相似度的網(wǎng)站每個類別的PageRank值，最終得到相似度。

主題敏感PageRank的機制非常適合作為個性化搜索的技術(shù)方案，比如在計算用戶查詢的類別時，不僅考慮用戶當前輸入的查詢詞，也考慮用戶過去的搜索記錄等個性化信息，就能更精準的提供搜索服務。

網(wǎng)頁反作弊

出于商業(yè)利益驅(qū)使，很多人會通過特殊手段將網(wǎng)頁的搜索排名提高到與其網(wǎng)頁質(zhì)量不相稱的位置，這樣會嚴重影響搜索引擎用戶的搜索體驗。

常見的作弊方法包括：內(nèi)容作弊、鏈接作弊、隱藏作弊等，這里均簡單介紹一下。

內(nèi)容作弊比如在網(wǎng)頁中重復關(guān)鍵詞、放置無關(guān)查詢詞、在圖片alt標簽以及網(wǎng)頁標題等重要標簽放置關(guān)鍵詞等，或者用一些低質(zhì)量的內(nèi)容搞內(nèi)容農(nóng)場。

鏈接作弊有鏈接農(nóng)場，就是大量互相緊密鏈接的網(wǎng)頁集合，還有利用鏈接描述性文字的谷歌轟炸等等。

頁面隱藏作弊有IP地址作弊、HTTP請求作弊來欺騙爬蟲。

反作弊的方法比如信任傳播模型，篩選出一些肯定不會作弊的白名單頁面，給予一定信任分值，然后白名單內(nèi)節(jié)點通過鏈接關(guān)系將信任度分值向外擴散傳播，然后確定一個信任度閾值；或者反過來用黑名單做不信任傳播模型；還有異常發(fā)現(xiàn)模型，傾向于去發(fā)現(xiàn)作弊網(wǎng)頁不同于正常網(wǎng)頁的特征。

用戶查詢意圖分析

用戶之所以會產(chǎn)生搜索行為，往往是在解決任務時遇到自己不熟悉的概念或問題，由此產(chǎn)生了對特定信息的需求，之后用戶會在頭腦中逐步形成描述需求的查詢詞，將查詢詞交給搜索引擎，然后對搜索結(jié)果進行瀏覽，找到滿足自身需求的信息或者根據(jù)搜索結(jié)果的啟發(fā)，修正自己的查詢關(guān)鍵詞重新搜索。

上面的問題在于，從用戶產(chǎn)生信息需求到最終形成用戶查詢，中間有很大的不確定性，用戶用的查詢語句與用戶的信息需求很難一開始就是完全等價的。因此用戶會改寫自己的需求，比如抽象化改寫、具體化改寫及同義重構(gòu)改寫。

用戶搜索意圖分類

有人將用戶的意圖分為三個大類：導航型、信息型、事務型。

這讓我想到了有篇文章，阿里小蜜將用戶的意圖分為三種：問答型、任務型、語聊型。

• 問答與信息型相同，都是希望獲取某種信息，知道某種知識。
• 任務型與事務型相同，都是希望完成一個目標明確的任務。
• 導航型搜索引擎獨有，用戶希望查找某個網(wǎng)頁，但又不知道URL，所以借助搜索引擎。
• 語聊型chatbot獨有，畢竟沒人會和一個搜索引擎閑聊吧。

意圖識別可以采取一些通用的分類器，比如SVM、決策樹等完成。

搜索日志挖掘

搜索引擎是搜索引擎對用戶行為的記錄，一般記載了查詢、發(fā)出查詢的用戶ID，發(fā)出查詢的時間、點擊網(wǎng)頁的網(wǎng)址及這條網(wǎng)址在搜索記錄中的排名情況。

查詢會話

比如在搜索日志中，我們可以找出用戶在較短時間段內(nèi)發(fā)出的連續(xù)多個查詢，這樣的一段日志被稱作一個查詢會話，一個查詢會話中的用戶查詢語句往往會有語義上的相關(guān)性。比如我們可以依此來構(gòu)建查詢圖，用來表示查詢之間的這種相互關(guān)系。

點擊圖

點擊圖是非常有價值的信息，我們可以認為搜索結(jié)果里被點擊過的網(wǎng)頁與用戶查詢更相關(guān)。

相關(guān)搜索

相關(guān)搜索也常被稱作查詢推薦，就是百度搜索頁面拉到底的那些推薦查詢詞。

搜索引擎計算相關(guān)查詢的方法基本有兩種，基于查詢會話的方法和基于點擊圖的方法。

基于查詢會話，就是將其他用戶包含當前查詢語句的查詢會話中的其他查詢語句推薦給用戶?；邳c擊圖的方法是，如果兩個查詢各自對應的點擊網(wǎng)址中，有很大比例是相同的，那么說明這兩個查詢在語義上緊密相關(guān)，可以作為相互推薦的相關(guān)查詢。

查詢糾錯

說查詢糾錯之前我想先說一下查詢預測，《淺談機器學習基礎(chǔ)》中的Apriori算法就是用來發(fā)現(xiàn)頻繁項集并在用戶輸入查詢詞時推薦給用戶的。

查詢糾錯其實分為兩步，一是錯誤識別，而是錯誤糾正。

大多數(shù)錯誤識別機制是基于詞典的，即將用戶輸入的查詢分詞后查找詞典，如果在詞典里沒有找到，那么這很可能是一個錯誤輸入。

至于錯誤糾正，主要的方法有兩種，一個是編輯距離，另一個是噪聲信道模型。

編輯距離其實在《淺談自然語言處理基礎(chǔ)》中自動機那部分應該提到的，但是省略了，這里簡單說一下。編輯距離通常使用有限狀態(tài)自動機來實現(xiàn)，編輯距離的意義是衡量兩個字符串的拼寫差異有多大，也即對于某個字符串來說，可以通過進行幾次操作，來逐步將其轉(zhuǎn)換成另一個字符串，這些操作可以是刪除字符、添加字符、更改字符以及交換字符順序。與原錯誤串編輯距離較小的正確串很有可能就是用戶所想要輸入的字符串。

噪聲信道模型在《淺談自然語言處理基礎(chǔ)》的漢語自動分詞的N-最短路徑方法那里提到過，當時講的是，假設(shè)一串有分詞符號的字符串經(jīng)過噪聲信道，丟失了分詞符號，我們要根據(jù)其輸出反推，找出概率最大的輸入，也即完成了分詞過程。

這里也是類似，我們假設(shè)正確串W是輸入，錯誤串V是輸出，那么對于多個候選正確答案，我們就要找到概率最大的作為錯誤串V對應的正確查詢串。具體的計算要用貝葉斯公式，需要找出最大的P(W|V)所對應的那個W，根據(jù)貝葉斯公式，P(W|V)=P(V|W)*P(W)/P(V)，P(V)都是相同的就不考慮了，關(guān)鍵還是求P(V|W)*P(W)，P(V|W)是正確串W被誤寫為V的概率，P(W)是正確串W的出現(xiàn)概率，這兩個概率都需要通過訓練語料統(tǒng)計出來。

網(wǎng)頁去重

最開始也提到過，互聯(lián)網(wǎng)頁面中有相當大比例的內(nèi)容是完全相同或者大體相同的，內(nèi)容重復可以歸結(jié)為以下4種類型：

• 內(nèi)容、布局均相同
• 內(nèi)容相同、布局不同
• 部分重要的內(nèi)容相同，布局相同
• 部分重要的內(nèi)容相同，布局不同

如果我們能夠找出這些重復網(wǎng)頁，那首先我們能夠節(jié)省一部分存儲空間，其次能夠提高網(wǎng)頁的收集速度。而且鏡像多的網(wǎng)頁，往往比較重要。另外，如果用戶點擊了一個死鏈接，可以將用戶引導到一個內(nèi)容相同的頁面。

通用去重算法框架

通用去重算法框架

對于給定的文檔，首先通過一定的特征抽取手段，從文檔中抽取出一系列能夠表征文檔主題內(nèi)容的特征集合。這一步往往有其內(nèi)在要求，即盡可能保留文檔重要信息，拋棄無關(guān)信息，以加快計算速度。

在文檔轉(zhuǎn)換成特征集合后，為了進一步加快計算速度，很多高效實用的算法會在特征集合的基礎(chǔ)上，對信息進一步壓縮，采用信息指紋相關(guān)算法，將特征集合壓縮為新的數(shù)據(jù)集合，其包含的元素數(shù)量遠小于特征集合數(shù)量，有時甚至只有唯一的一個文檔指紋。

把文檔壓縮為文檔指紋之后，即可開始通過相似性計算來判斷哪些網(wǎng)頁是近似重復頁面。這里常用的方法有Jaccard相似度，Jaccard相似度在《淺談推薦系統(tǒng)基礎(chǔ)》中提到過，就是交集比上并集。

Shingling算法

與上面說的通用去重算法框架相同，Shingling算法由兩個大步驟組成，第一步是從文檔中抽取能夠代表文檔內(nèi)容的特征，第二步則是根據(jù)兩個文檔對應特征集合的重疊程度來判斷文章是否近似重復。

第一步用一張圖就能說清楚：

文本文檔轉(zhuǎn)化為特征集合

把文檔按照上述方法拆分為若干個單詞片段，并對每個片段進行哈希，即得到文檔內(nèi)容的特征集合，這樣的一個特征就叫做一個shingle，進一步，如果單詞片段長度為k，就叫做k-shingle。

另外，還有另一種基于詞的shingle，這樣的形式被證明在新聞報道近似重復檢測中非常有效。對于新聞報道的重復檢測，將shingle定義為一個停用詞（the/for/a等）加上后續(xù)的兩個詞。

然后通過Jaccard相似度就可以計算兩篇文章之間的相似度，這是原始的Shingling算法，k的選擇依賴于文檔的典型長度以及典型的字符表大小，如果k太小，很有可能會導致所有網(wǎng)頁之間都有較高的Jaccard相似度?？傊?，k應該選擇的足夠大，以保證任意給定的shingle出現(xiàn)在任意文檔中的概率較低。

有人提出了針對原始Shingling算法的優(yōu)化算法，因為原始Shingling算法對于不同的網(wǎng)頁，特征集合的長度也不同，而且往往長度都較大。優(yōu)化后的Shingling算法不再采用一個哈希函數(shù)對所有的單詞片段進行哈希，而是隨機選擇m種哈希函數(shù)，對所有的原始單詞片段進行哈希，但是我們只保留每種哈希函數(shù)所有的結(jié)果里面，最小的那個，這樣文檔就能被轉(zhuǎn)換為固定大小m的最小哈希簽名。之后，我們就可以根據(jù)Jaccard相似度計算方法，計算最小哈希簽名的相似度了。

I-Match算法

I-Match算法是先根據(jù)大規(guī)模語料進行統(tǒng)計，記錄語料中的所有單詞，然后去除掉一定比例IDF得分過高以及過低的單詞，剩下的作為特征詞典。

對于需要去重的網(wǎng)頁，采用特征詞典過濾，保留在特征詞典中出現(xiàn)過的單詞，然后對所有單詞進行一次哈希，得到一個唯一的數(shù)值，通過比較該數(shù)值是否相同，來判定兩個網(wǎng)頁是否近似重復。

我們還可以進一步優(yōu)化，就是不再只使用一個特征詞典，而是使用多個大致相同而又有微小差異的詞典，來避免I-Match算法對于增刪單詞過于敏感的問題。

SimHash算法

SimHash算法可能是目前最優(yōu)秀的去重算法之一，是局部敏感哈希的一種。

第一步是文檔指紋計算，首先從文檔內(nèi)容中抽取一批能表征文檔的特征，然后將這些特征映射為固定長度的二進制表示，再利用權(quán)值改寫特征的二進制向量，形成一個實數(shù)向量，之后將所有特征對應的實數(shù)向量相加，最后再將實數(shù)向量轉(zhuǎn)換為二進制向量，方式為，如果對應位置數(shù)字大于0，則設(shè)置為1，小于等于0，則設(shè)置為0：

比如舉個例子（本例不涉及權(quán)重）：

• 選擇simhash的位數(shù)，請綜合考慮存儲成本以及數(shù)據(jù)集的大小，比如說32位
• 將simhash的各位初始化為0
• 提取原始文本中的特征，一般采用各種分詞的方式。比如對于"the cat sat on the mat"，采用兩兩分詞的方式得到如下結(jié)果：{"th", "he", "e ", " c", "ca", "at", "t ", " s", "sa", " o", "on", "n ", " t", " m", "ma"}
• 使用傳統(tǒng)的32位hash函數(shù)計算各個word的hashcode，比如："th".hash = -502157718
  ，"he".hash = -369049682，……
• 對各word的hashcode的每一位，如果該位為1，則simhash相應位的值加1；否則減1
• 對最后得到的32位的simhash，如果該位大于1，則設(shè)為1；否則設(shè)為0

第二步是相似文檔查找，SimHash的基本思想是這樣的：將索引網(wǎng)頁根據(jù)文檔指紋進行分類，新網(wǎng)頁只在部分分組內(nèi)進行匹配，以減少新文檔和索引網(wǎng)頁的比較次數(shù)。

基本思路如上圖所示。先通過分組匹配找到與新網(wǎng)頁A/B/C/D塊對應位置范圍內(nèi)完全相同的網(wǎng)頁，再一一匹配查找是否存在完全相同的文檔指紋，當然我們也可以不以完全相同為標準，比如海明距離3以內(nèi)即可。

搜索引擎緩存機制

搜索引擎通常通過緩存，也即在高速內(nèi)存硬件設(shè)備內(nèi)開辟一塊數(shù)據(jù)存儲區(qū)，用來容納常見的用戶查詢及搜索結(jié)果（或者索引數(shù)據(jù)及搜索的中間結(jié)果），同時采取一定的管理策略來維護存儲區(qū)內(nèi)的數(shù)據(jù)。

搜索引擎緩存系統(tǒng)架構(gòu)

緩存系統(tǒng)包含兩個部分，即緩存存儲區(qū)及緩存管理策略。緩存存儲區(qū)是高速內(nèi)存中的一種數(shù)據(jù)結(jié)構(gòu)，可以存放某個查詢對應的搜索結(jié)果，也可以存放搜索中間結(jié)果，比如一個查詢單詞的倒排列表。緩存管理策略又包含兩個子系統(tǒng)，即緩存淘汰策略和緩存更新策略。

對于一個優(yōu)秀的緩存系統(tǒng)來說，應該最大化緩存命中率以及保持緩存內(nèi)容與索引內(nèi)容一致。

常見的緩存對象可以是搜索結(jié)果，或者查詢詞匯對應的倒排列表。對于搜索結(jié)果型緩存來說，用戶查詢的響應速度非?？欤欢古帕斜硇途彺娴拿新矢?。有時候我們還可以保存兩個經(jīng)常搭配出現(xiàn)單詞的倒排列表的交集，以這種中間結(jié)果形式作為緩存內(nèi)容。

搜索引擎緩存的結(jié)構(gòu)設(shè)計可以有多種選擇，最常見的是單級緩存，也可以設(shè)計為二級甚至是三級緩存結(jié)構(gòu)，比如二級緩存，就可以第一級緩存是搜索結(jié)果型緩存，第二級是倒排列表型緩存，這就兼有了響應速度快和命中率高這兩個優(yōu)點。

緩存淘汰策略

緩存淘汰策略和操作系統(tǒng)中的內(nèi)存管理策略有相似的地方。

動態(tài)策略

動態(tài)策略的緩存數(shù)據(jù)完全來自于在線用戶查詢請求，這種緩存策略的基本思路是：對緩存項保留一個權(quán)重值，這個權(quán)重值根據(jù)查詢命中情況動態(tài)調(diào)整，當緩存已滿的情況出現(xiàn)時，優(yōu)先淘汰權(quán)重值最低的那個緩存項。

比如LRU策略，就是最近最少使用策略，淘汰掉最近最少使用的緩存內(nèi)容。Landlord策略是一種加權(quán)緩存策略，計算出緩存項目的性價比，然后如果緩存已滿，淘汰掉性價比低的緩存內(nèi)容。還有SLRU策略，這是對LRU策略的改進，緩存被分為了保護區(qū)和非保護區(qū)，每個區(qū)域的緩存都按使用頻度由高到低排序，如果緩存未命中，則放入非保護區(qū)高頻端（MRU），如果命中了，則放入保護區(qū)高頻端，這樣保護區(qū)的記錄最少要被訪問兩次。

混合策略

混合策略是指其緩存數(shù)據(jù)一方面來自于用戶查詢，另一方面來自于搜索日志等歷史數(shù)據(jù)。

比如SDC策略：靜態(tài)動態(tài)混合緩存策略（Static and Dynamic Caching），靜態(tài)緩存就事先根據(jù)搜索日志統(tǒng)計出最高頻的那部分查詢請求，動態(tài)就結(jié)合LRU或者SLRU這些動態(tài)策略來搞。SDC策略是目前效果最好的緩存策略之一。還有AC策略，這里就不詳細說了。

緩存更新策略

目前的緩存更新策略可以分為兩種：緩存--索引密切耦合策略和緩存--索引非耦合策略。

緩存--索引密切耦合策略就是在索引和緩存之間增加一種直接的變換通知機制，一旦索引內(nèi)容發(fā)生變化則通知系統(tǒng)緩存，然后系統(tǒng)緩存將改變的內(nèi)容進行更新。

緩存--索引非耦合策略就是給每個緩存項設(shè)置一個過期值，隨著時間流逝，緩存項會逐漸過期。

當然如果內(nèi)容更新不頻繁，也可以簡單的，等到夜深人靜的時候統(tǒng)一更新緩存就是了。