解密搜索引擎技術之排序算法
一、PageRank
算法PageRank是***的搜索引擎Google采用的一種算法策略，是根據每個網頁的超級鏈接信息計算網頁的一個權值，用于優化搜索引擎的結果。由拉里-佩奇提出。
簡單說，PageRank算法是計算每個網頁的綜合得分數，即假如網頁A鏈向網頁B，則網頁B加一分，當然。不同鏈接網頁對于指向網頁的加分也是不同的，一個頁面的得分情況是由所有鏈向它的頁面的重要性經過遞歸算法得到的。
PageRank算法的基本原理推導如下：
PR(A) = (1-d) + d*(PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
其中，PR(A)是指網頁A的PR值。
T1，T2，...，Tn是指網頁A的鏈入網頁。
PR(Ti)是指網頁Ti的PR值（i=1，2，...，n）。
C(Ti)是指網頁Ti的鏈出數量（i=1，2，...，n）。
D是一個衰減因子，0<d<1，通常取值為0.85。
從以上公式可以看出，影響一個網頁PR值的主要因素如下：
- （1）該網頁的鏈入數量。
- （2）該網頁的鏈入網頁本身的PR值。
- （3）該網頁的鏈入網頁本身的鏈出數量。
根據上面分析可以判斷：一個網頁的鏈入數量越多，這些鏈入網頁的PR值越高，這些網頁本身的鏈出數量越少，則該網頁的PR值越高。
Google給每一個網頁都賦予一個初始PR值（1-d），然后利用PageRank算法收斂計算其PR值。
網頁的鏈入鏈出關系，時刻都在變化，那么PR值也需要更新，可以用定時任務重復計算后更新，使得網頁的最終PR值達到一個均衡穩定的狀態。
Google的查詢過程是這樣的：首先根據用戶輸入的查詢關鍵詞對于網頁數據庫中的網頁盡情匹配，然后對于匹配到的網頁按照其本身的PR排序呈獻給用戶。
此外，一個網頁在檢索結果列表中的位置還與其它很多因素相關，比如檢索詞在網頁中的位置等。
PageRank的缺陷在于不考慮鏈接的價值，這對通用搜索引擎比較合適，但對主題相關的垂直搜索引擎而言并不是很好的策略。
二、HITS
PageRank算法對于向外鏈接的權值貢獻是平均的，即不考慮不同鏈接的重要性，但是頁面鏈接中可能某些是廣告、導航或者注釋鏈接，平均權值顯然不太符合實際情況。
HITS（Hyperlink Induced Topic Search）算法則是一種經典的專題信息提取策略，能夠提高垂直查準率。
1、原理
HITS算法由Jon Kleinberg提出，其對每個網頁都要計算兩個值：權威值（authority）和中心值（hub）。
（1）權威網頁
一個網頁被多次引用，則它可能是很重要的；一個網頁雖然沒有被多次引用，但是被重要的網頁引用，則它也可能是很重要的；一個網頁的重要性被平均的傳遞到它所引用的網頁。這種網頁稱為權威網頁。
（2）Hub網頁
提供指向權威網頁的鏈接集合的Web網頁，它本身可能并不重要，或者說沒幾個網頁指向它，但是它提供了指向就某個主題而言最為重要的站點的鏈接集合，這種網頁叫做Hub網頁。
（3）算法思想
首先利用通用搜索引擎得到一個網頁的初始子集I，當然I內的頁面都是和用戶查詢條件有很大相關性。然后把I指向的網頁和指向I的網頁都包含進來，形成基礎集合E，E中的每個頁面都具有一個authority權值和hub權值，分別記作a和h，a值表示網頁與查詢條件相關度的高低，h反應的是該頁面鏈出相關度頁面的多少情況。a=(a1, a2, ..., an)和h=(h1, h2, ..., hn)代表E中所有網頁的authority和hub向量，初始時把所有的ai和hi都設置為1，然后利用下面的公式進行計算：
其中，B(i)和F(i)分別表示指向該網頁的網頁鏈接集合和該網頁指向的網頁鏈接集合。用n*n的矩陣A表示集合E的網頁節點間的連接，如果節點i和節點j之間有連接，則A[i,j]=1，則A[i,j]=0，因此，上面公式可以表示為：
迭代計算a和h，直至收斂。這樣我們集中求ATA和AAT。***按照authority和hub值排序，將a和h值大于閾值M的網頁挑出來。
若一個網頁由很多好的hub指向，則其權威值會相應增加；若一個網頁指向很多好的權威頁，則hub值也會相應增加。HITS算法***輸出的一組具有較大hub值的網頁和具有較大權威值的網頁。
2、缺陷
HITS算法在提高一定的垂直查準率的同時，也存在如下缺陷：
（1）HITS算法忽略了網頁內容的差異，對于每個鏈接網頁賦予相同的加權常數，因為每個網頁中都會有一些廣告鏈接等非相關的鏈接網頁，這些非相關網頁和相關網頁同等對待，會容易產生主題漂移現象。
（2）在開始形成url集合E中，對于初始集合I中網頁的一些非相關鏈接也加入到E中，增加了無謂的下載量，也致使后邊更多的無關網頁參與到了計算，對準確率存在一定的影響。
3、改進
改進方向如下：
（1）主題漂移
（2）下載過濾
