本節書摘來自華章出版社《大規模元搜尋引擎技》一書中的第1章，第1.3節，作者 ［美］孟衛一(weiyi meng)， 紐約州立大學， 賓漢姆頓分校於德（clement t.yu），伊利諾伊大學芝加哥分校，更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
最早的web搜尋引擎基本上就是網頁文字檢索系統。然而，web環境中有一些特征，使得建構現代搜尋引擎與建構傳統文字檢索系統顯著不同。在本節中，簡要概述這些特征以及基于利用這些特征的搜尋引擎建構技術。
下面是web環境的一些特性，它們對搜尋引擎的發展産生了重大影響。
1)web頁面存儲在大量的自治web伺服器中。需要一種方法來查找和擷取這些web頁面，以便處理後供搜尋用。
2)大多數web頁面是html（hypertext markup language，超文本标記語言）格式，html标簽通常傳達了這些網頁中詞的豐富資訊。例如，一個詞出現在一個頁面的标題中或一個詞用特殊字型強調，這就暗示該詞在表達該頁面内容時是重要的。
3)web頁面是互相連結的。從頁面p1到頁面p2的連結允許使用者從p1浏覽到p2。這種連結還包含一些有用的資訊來提高檢索效率。第一，此連結表明兩頁的内容有較高的相關性［davison，2000］。第二，p1的作者認為p2是有價值的。第三，與連結相關的可點選文本，稱為連結的錨文本（anchor text），通常提供了一個連結頁面的簡短描述［davison，2000］。
本節中還将讨論一個問題。該問題對搜尋引擎和傳統文字檢索系統都非常重要，尤其對搜尋引擎重要。該問題是關于如何組織搜尋結果。
web爬蟲（web crawler）是一個用來從遠端web伺服器爬取網頁的程式。
它也稱為web蜘蛛（web spider）和web機器人（web robot）。它們廣泛用于建構搜尋引擎的web頁面集合。
爬蟲程式的基本思想很簡單。每個網頁都有一個辨別網頁位置的url（universal resource locator，統一資源定位符）。一個典型的爬蟲以一個或多個種子url作為輸入形成一個初始url清單。然後，爬蟲重複以下兩個步驟直到沒有新的url或已經找到足夠的頁面：1）從url清單取出下一個url，通過向伺服器發出一個超文本傳輸協定（hypertext transfer protocol，http）請求，與web頁面所在伺服器建立連接配接并擷取相應的web頁面；2）從每個擷取的web頁面提取一些新的url并将它們添加到url清單中。爬蟲擷取web頁面可以采用深度優先或廣度優先政策。若使用廣度優先爬取，url清單以一個隊列實作——新的url總是添加到清單的最後。若使用深度優先爬取，url清單以一個棧實作——新的url總是添加到清單的開始。
将僅與某個主題（比如體育）相關的一些新web頁面的url添加到url清單，web爬蟲就變成了這個主題的聚焦爬蟲（focused crawler）。聚焦爬蟲對于建立特定領域的或垂直的搜尋引擎是有用的［chakrabarti et al.，1999］。為使聚焦爬蟲有效，該爬蟲需要準确地預測一個url是否會帶來與興趣主題相關的一個或多個頁面。一種對預測有用的技術是檢查url、url相關的錨文本、錨文本相鄰文本是否包含與主題相關的詞。
實作web爬蟲的一個方面是能從一個web頁面中找出所有（新）的url。這需要識别所有可能的html标簽和可能擁有url的标簽屬性。雖然大多數url出現在錨标簽（例如，〈a href=“url”…〉…〈/a〉）中，但有些url也可以出現在其他标簽中，例如選擇标簽〈option value=“url”…〉…〈/option〉、區域标簽（映射）〈area href=“url”…〉…〈/area〉以及架構标簽〈frame src=“url”…〉…〈/frame〉。出現在web頁面p中的一個url經常不包含由web浏覽器定位這個相應web頁面所需的完整路徑，而經常使用一個部分路徑或相對路徑。在這種情況下，爬蟲需要使用相對路徑以及相關p的基本路徑來建構一條完整的路徑。
在設計web爬蟲時，需要為由此擷取web頁面的遠端伺服器着想。快速激發（rapid fire）（在短時間内從同一個伺服器爬取大量的網頁）可能會壓垮一個伺服器，等效于對伺服器進行拒絕服務攻擊。一個設計良好的web爬蟲應該控制從同一個伺服器爬取多個頁面的節奏，而從大量不同的伺服器輪流爬取。考慮妥善的web爬蟲還應滿足機器人排除協定（robot exclusion protocol），也就是說，不爬取web伺服器管理者不允許爬取的網站部分。web伺服器管理者可以通過web伺服器上名為robots.txt的檔案指定能或不能爬取的内容目錄。
為加快爬取或處理大規模的爬取結果，web爬蟲可以采用并行爬取和分布式爬取。并行爬取可以通過使用多線程或多台計算機從不同的伺服器同時執行。分布式爬取使用在不同地理位置的多台計算機，每台計算機可以集中精力從鄰近的web伺服器爬取網頁，因而減少網絡延遲使爬取更有效。
大多數web頁面是html頁面，html語言包含一組标簽，如title和font。大多數标簽成對出現，一個表示開始，另一個表示結束。例如，在html中标題的開始和結束标簽分别是〈title〉和〈/title〉。在搜尋引擎應用環境中，标簽資訊主要是用來幫助确定索引詞的重要性，而這些索引詞表示一個web頁面的内容。
1.2.2節介紹了一種方法，該方法使用一個詞的詞頻和文檔頻率資訊計算在一個文檔中這個詞的權重。也可以使用标簽資訊來影響一個詞的權重。例如，web頁面作者經常使用粗體字、斜體字、下劃線字以及各種顔色來突出顯示一個web頁面中的某些詞。這些詞可以認為是更重要的而應給予較高的權重。相反，較小字型的詞應給予較低的權重。其他标簽，如title和不同級别的header也影響權重。許多著名的搜尋引擎，包括google，給标題中的詞配置設定更高的權重。
利用标簽來調整詞權重的一般方法如下所示［cutler et al.，1999］。首先，所有的html标簽的集合劃分為若幹子集。例如，标題标簽本身可成為一個子集，所有清單标簽（即“ul”“ol”和“dl”）可以組合在一起，所有的強調标簽可以形成一個子集。其次，頁面中詞的出現情況被劃分為若幹類，每個标簽子集為一個類。例如，所有出現在标題中的詞形成一個類。此外，對每個網頁p，還可以形成其他兩類。第一類包含出現在純文字（即沒有标簽）中的詞，第二類包含的詞出現在與頁面p的後向連結有關的錨文本中。設n是所形成類的個數。使用這些類，頁面中的每個詞的詞頻可以表示成一個詞頻向量（term frequency vector）：tfv=(tf1，…，tfn)，其中tfi是在第i類中詞出現的次數，i=1,…，n。最後，可以給不同的類配置設定不同程度的重要性。設civ=(civ1，…,civn)表示類重要性向量（class importance vector），civi表示第i類的重要度，i=1，…，n。基于向量tfv和civ，傳統的詞頻率權重公式可擴充為：∑ni=1
tfi×civi。這個公式考慮了在不同類中詞的頻率以及每個類的重要性。一個有趣的問題是如何找到最優的類重要性向量，進而可以得到最高的檢索效率。有一種基于測試資料集的方法是憑經驗尋找一個最優的或近似最優的civ［cutler et al.，1999］。
傳統文字檢索系統中的文檔和搜尋引擎中的文檔之間最顯著的差異之一是web頁面之間存在大量的連結。如何利用連結資訊來提高檢索效率已經受到搜尋引擎研究者和開發者的廣泛關注。一些著名的方法都是基于利用這樣的事實：從頁面p1連結到p2表示p2被p1的作者認可。這些方法中最廣為人知的是由google的創始人提出的pagerank方法［page et al.，1998］。這種方法試圖找到不考慮頁面的内容時每個web頁面的整體重要性。我們在本節描述該方法的基本思想。
pagerank方法是将web視為一個巨大的有向圖g(v，e)，其中v表示頁面（頂點）集，e表示連結（有向邊）集。每個頁面都有許多出向邊（前向連結）和許多入向邊（後向連結）。如上所述，當一個作者在頁面p1設定一個連結指向p2時該作者認為頁面p2是有價值的。換句話說，這種連結可以視為對頁面p2投了一個支援票。一個頁面可能有很多後向連結，它們可以按某種方式聚集起來以反映這個頁面的整體重要性。頁面的pagerank用以度量該頁面在web上的相對重要性，這種方法是基于連結資訊來計算的［page et al.，1998］。web頁面的pagerank的定義和計算是基于以下三種主要思想。
1)有更多後向連結的頁面可能更重要。直覺上，一個頁面有更多的後向連結意味着它得到了更多web頁面作者的支援票。換句話說，一個頁面的重要性應該通過頁面在所有網頁作者中受歡迎的程度來反映。
2)如果一個頁面被更重要的頁面指向，那麼它的重要性應該增加。換句話說，不僅數量，還有後向連結的重要性也應該考慮。直覺上，重要網頁可能會由重要作者或機構來釋出。決定頁面的重要性時，這些作者或機構認可的頁面應該有更高的權重。這有兩個含義。首先，一個頁面的重要性應該傳播到它指向的頁面。其次，pagerank的計算是一個疊代過程，因為一個頁面的重要性受連結到它的一些頁面的影響，同時這些頁面本身的重要性也會受到指向它們的另一些頁面的影響，等等。
3)如果一個頁面獲得指向它的其他頁面的關注越專注，那麼它從這些頁面提供傳播獲得的重要性就應該越多。直覺地說，當一個頁面有更多的前向連結時，它對每一個連結頁面的重要性的影響将更小。是以，如果一個頁面有更多的子頁面，那麼它對每個子頁面僅傳播其重要性的較小部分。
從上面的讨論可知，以遞歸方式計算網頁的pagerank是很自然的。一個頁面u的pagerank的更加形式化的定義如下所述。設fu表示頁面u鍊向的頁面的集合，bu表示指向u的頁面的集合（見圖1-3）。對于集合x，用|x|表示x中元素的個數。u的pagerank，記為r(u)，可用如下公式定義：
r(u)=∑v∈bur(v)|fv|(1-3)
圖1-3 網頁u及其鄰接網頁
不難看出，式(1-3)結合了上述三種思想。第一，求和反映了第一種思想，也就是說，更多的後向連結可能導緻更大的pagerank。第二，若頁面v更重要（具有更大的r(v)），則表明u的pagerank的分子r(v)變大。第三，分母|fv|意味着網頁重要性被均勻配置設定并且傳播到它指向的每一個頁面。還要注意式(1-3)是遞歸的。
web頁面圖中web頁面的pagerank可如下計算。首先，給所有頁面一個初始pagerank值。設n表示圖中web頁面的個數。然後令1/n作為每一頁的初始pagerank值。其次，經過多次疊代應用式(1-3)計算pagerank。在每次疊代時，計算一個頁面的pagerank要使用前面已經計算過的指向它的網頁的pagerank。重複這個過程，直到所有頁面的pagerank收斂到一個給定的門檻值。設ri(u)表示頁面u經過第i次疊代後的pagerank，r0(u)表示賦給u的初始pagerank。那麼，式(1-3)可以重寫為：
ri(u)=∑v∈buri－1(v)|fv|(1-4)
式(1-4)可用矩陣表示如下。設m是一個表示web圖的n×n矩陣，其中n是圖中web頁面的個數。若頁面v有連結指向頁面u，則令矩陣項m［u，v］為1/|fv|。如果沒有從v到u的連結，那麼m［u，v］=0。令ri為一個n×1的向量，它表示第i次疊代後n個頁面的pagerank向量。式(1-4)可以表示為：
ri=m×ri－1(1-5)
其中r0是全部項值為1/n的初始pagerank向量。當pagerank收斂時，pagerank向量是矩陣m的特征向量，其相應的特征值是1。注意，如果每一頁至少有一個前向連結，那麼m的每列值的和是1且全部值都是非負的（這樣的矩陣稱為随機矩陣，stochastic matrix）。從另一個角度看，矩陣m的項可以解釋如下：考慮一個web沖浪者，每一步，沖浪者從目前頁面随機選取連結到其子頁面。是以元素m［u，v］的值可以解釋為從頁面v經過一個向其子節點的随機行走（random walk）會到達頁面u的機率。
現在考慮應用式(1-5)對頁面pagerank的作用。假設v有一些子頁面。當應用式(1-5)時，v的pagerank傳播到它的子頁面。如果每個頁面至少有一個前向連結，則所有頁面的pagerank将被傳遞給它們的子頁面。因為所有頁面pagerank的總和初始為1，是以每次疊代後這個總和會保持不變。假設通過多次應用式(1-5)，頁面的pagerank收斂了。收斂後的每個頁面的pagerank可以解釋為該頁面在web圖上随機行走時被通路的機率。
直接使用式(1-5)會有一個問題。也就是說，pagerank能保證收斂僅當m是非周期的（即web圖不是單一的大回路）且不可約的（即web圖是強連通的）［haveliwala，1999；motwani and raghavan，1995］。前者（即非周期性）對于web的實際情況能夠保證，而後者通常不成立。如果一個有向圖中的任何兩個不同的頂點都存在從一個頂點到另一個頂點(反之亦然)的有向路徑，那麼這個圖就是強連通的。當web圖不是強連通的時，可能存在一些頁面（或屬于一個回路的頁面集合）隻有後向連結但沒有前向連結。這些頁面隻能收到那些父頁面的pagerank傳播但不能傳播到其他頁面，這些頁面稱為pagerank彙點（sink）［page et al.，1998］。pagerank彙點的存在會導緻總pagerank值的損失。解決這個問題的一種方法是在web圖中概念性地添加從每個頁面到所有頁面的連結并給每個這樣的連結一個适當的正機率［haveliwala，1999］。這種方法所賦予的連結機率應該使得修改後的web圖所對應的矩陣滿足随機特征（即矩陣中每一列元素的總和是1）。假設從頁面v到頁面u概念性地添加的連結具有機率p。在随機行走模型中，這可以解釋為當web沖浪者在頁面v時，可能以機率p跳轉到頁面u。注意v和u可能是同一個頁面。在這種情況下，跳轉可以解釋為使用web浏覽器重新整理（refresh）或重載（reload）請求。
現在考慮如何給添加的連結賦予機率值。對于一個給定的頁面v，考慮以下兩種情況。
1)在沒有修改過的web圖中頁面v沒有前向連結。在這種情況下，web沖浪者隻能使用添加的連結之一（即隻能跳轉）。一個合理的假設是web沖浪者以相同的機率跳轉到任何頁面。是以，從頁面v出發的每個添加連結的機率應該為1/n。這相當于讓矩陣中對應于頁面v的列的所有元素為1/n。
2)在沒有修改過的web圖中頁面v至少有一個前向連結，即|fv|≥1。基于矩陣m，給每個這樣的連結配置設定機率1/|fv|。需要對這個機率進行調整，因為如果沒有調整，任何新添加連結的機率隻能是0，表明不可能跳轉。用c表示一個滿足0＜c＜1的權重參數。那麼對每個在沒有修改過的web圖中連結的機率可從1/|fv|調整為c×1/|fv|，而對每個從v新添加的連結賦給機率(1-c)×1/n。c越接近1，新添加連結的影響越小。容易知道這些機率之和為1。
數學上，添加連結、給新添加的連結賦予機率值以及調整在沒有修改過的web圖中原始連結的機率能夠通過修改矩陣m得到如下新矩陣來實作：
m*=c(m+z)+(1－c)k(1-6)
其中z是一個滿足如下條件的n×n矩陣：對應頁面v的列的所有元素要麼是1/n（如果v在沒有修改過的原始web圖中沒有前向連結）要麼是0（如果v在原始圖中至少有一個前向連結）；k是一個其所有元素都是1/n的n×n矩陣；c是0和1之間的一個常數。
當式(1-5)中的矩陣m被新矩陣m*替代之後，關于pagerank彙點的問題将得以解決。計算網頁pagerank的高效技術已經存在［haveliwala，1999］。
最後，當收斂之後，可以規範化頁面的pagerank，也就是說，每個頁面的pagerank除以所有頁面中最大的pagerank，使得每個頁面的規範化pagerank在0和1之間。在這種情況下，pagerank=1的頁面被認為是最重要的文檔，而pagerank=0的頁面被認為是最不重要的。
例1.3 考慮圖1-4中的有向圖。假設圖的節點對應web頁面，有向邊表示連結。現在計算每個頁面的pagerank。
圖1-4 web圖示例
根據圖1-4，得到：
m=0001/20001/211000010
由于每個節點至少有一個前向連結，是以矩陣z的所有元素為0。因為有4個頂點，是以矩陣k的所有元素為1/4。假設式(1-6)中的常數c是0.8，那麼新矩陣m*為：
m*=0.8(m+z)+0.2k
=0.050.050.050.450.050.050.050.450.850.850.050.050.050.050.850.05
假設所有頁面都有的相同初始pagerank為0.25，即r0=(0.25，0.25，0.25，0.25)t，其中vt表示向量v的轉置。經30次疊代後，獲得以下收斂的pagerank：r(a)=r(b)=0.176，r(c)=0.332，r(d)=0.316。注意頁面c被2個網頁所指，而其他每個頁面隻被1個頁面所指。是以，頁面c的pagerank高于其他頁面。因為頁面d被最重要頁面c所指，是以頁面d的pagerank高于頁面a或頁面b的pagerank。■
pagerank的計算僅根據連結資訊而沒有考慮web頁面的内容。是以，對于每個查詢，當搜尋引擎要想檢索到既重要又相關的web頁面時，必須把pagerank和基于内容的相似度（1.2.3節中讨論的那些相似度是基于内容的，因其計算是基于查詢和文檔内容的）一起使用。
對于一個給定的查詢，大多數搜尋引擎按其估計的需求度（desirability）的降序排列組織檢索結果。對于一個查詢，一個頁面的需求度可用許多不同的方式進行估計，如頁面與查詢的相似度，或包含頁面的相似度及其pagerank的某種組合度量。一個相關的問題是如何在一個結果頁面中表示搜尋結果記錄（search result record，srr），這裡srr對應一個被檢索的web頁面。針對每個被檢索的網頁，最常用的一些搜尋引擎生成的srr主要包括三方面資訊：web頁面的标題、web頁面的url和一段簡短的摘要（稱為概覽，snippet）。其他資訊，如釋出時間和web頁面的大小也包含在一些搜尋引擎的srr中。有時，标題是一個具有url編碼的可點選文本。概覽是一個簡短的描述性文本，通常含有從web頁面中提取的大約20個單詞。概覽的作用是比标題提供更多關于web頁面内容的提示資訊，以便使用者能夠就是否檢視完整的web頁面做出更明智的決定。頁面的概覽往往是一個頁面中以一個句子開始并包含較多查詢詞的文本片斷。
一些搜尋引擎把結果組織成組，使得每組網頁有某些共同的特征，如有類似内容或來自同一個web站點的在同一組中。當每組賦予資訊标簽時，特别是當查詢有多個解釋以及查詢傳回結果的個數很大時，這樣的結果組織可以更友善使用者從傳回的結果找出有用的頁面。一個衆所周知的例子是yippy搜尋引擎（原名為clusty；http：//search.yippy.com/）。它将每個查詢傳回的結果組織成組。實作一個線上的結果聚類算法時需要解決的一些問題包括：1）哪些資訊（标題、url、文檔的概覽）應該用于聚類？盡管更多的資訊可以提高聚類的品質，但是由于需要較多的計算和通信開銷，是以使用太多的資訊可能導緻使用者獲得結果的時間被長時間延遲。2）應使用什麼标準進行聚類？可以基于ssr之間的相似度，也就是說，高度相似的結果應該分在一組。也可以基于查詢的解釋，也就是說，符合相同解釋的應該分在一起。3）如何為每個組給出一個簡短且有意義的标簽?4）如何組織這些組？可以對它們按照線性或層次的排序。對于前者，線性序應該是什麼?對于後者，如何生成層次結構?其中有些問題仍是研究的熱點。
有些搜尋引擎以圖形化方式展示搜尋結果，使得不同結果之間的聯系一目了然。例如，liveplasma音樂和電影搜尋引擎（http：//www.liveplasma.com/）把結果顯示為帶有注釋的圖示，這些圖示根據一些共同的特征（如有相同男主角的電影）分成組，并且用不同的鍊路進行連接配接（如其中一個鍊路可連接配接到電影的導演）。