互聯網搜索引擎工作原理的報告
?
一、搜索引擎的結構
基本結構：
?
二、主要功能模塊
??? 1
．網絡爬蟲：
???
搜索引擎的搜索器又被稱為網絡爬蟲，它日夜不停的在互聯網中搜索，不斷的訪問頁面、按超鏈接跳轉、發現新頁面，并且1）對頁面的信息進行提取、網頁快照；2）把頁面的地址連同頁面信息返回給搜索引擎，交由分析器分析整理。
???
網絡爬蟲的任務就是要盡可能多和盡可能快地搜集各種類型的新信息，同時因為互聯網上的信息更新很快，所以它還要定期更新已經搜集過的舊信息，以避免死連接和無效連接。比如說打開擺渡搜索某個關鍵字，在關鍵字的每個匹配項的最后，就注明了對這個網頁的更新日期。
??? 2
．分析器：
???
分析器的功能是對搜集端數據庫中的數據進行篩選和分析。首先對數據量不足的無用網頁和非正常頁面進行過濾，然后按特定格式將網頁壓縮成文檔，并存于信息數據庫內。文檔的格式一般包括a.DocID b.url長度 c.頁面數據長度 d.url地址 e.頁面數據。其中DocID是與通過url換算出的校驗值相對應的。
???
信息數據庫保存了所有這些網頁的文檔信息，按照DocID進行排序。
??? 3
．字典：
???
字典是一個散列表，它包含大約一千萬個關鍵字和詞語，與之對應的是這個字或詞唯一的WordID，以及它所在的桶的位置。由于這個字典無論在建立索引還是檢索關鍵字過程中都要頻繁使用，所以它被存放在一個內存中。
??? 4
．索引端數據庫：
???
是存儲索引的地方，是有很多桶組成的。它分為前向索引桶和后向索引桶兩類，其中后向索引桶又分為短索引桶(short barrel)和全索引桶(full barrel)。
??? 5
．索引器和前向索引：
???
索引器對信息數據庫中的文檔進行索引，首先對一個文檔中的每個有用詞匯建立一個采樣，把這個文檔中相同的詞匯的采樣歸為一組建立一個采樣表，并查詢字典得到這個詞的WordID。當分析完一個文檔的全部信息后，然后按照前向索引的方式（DocID->n個WordID+采樣表，其中的n數量級應該在1000之下）把這個文檔作為索引項加入桶中，這樣對信息庫的所有文檔進行分析，做成一個很龐大的索引。
??? 6
．排序器和后向索引：
???
排序器把前向索引庫重新排列，做成了后向索引庫（WordID->m個DocID+采樣表，這里的m有可能很小，但也有可能上千萬）。因為這樣是以WordID為索引關鍵字，就可以讓用戶的檢索獲得很快的相應。另外，從效率和匹配率的雙重角度考慮，還把后索引庫分為了短索引和全索引，短索引用來存放關鍵字在標題、錨信息、meta標簽中的文檔，而關鍵字在普通文本中的文檔放在全索引中，這是因為一般在前一種情況下網頁信息對用戶更重要一些。
??? 7
．檢索器
???
檢索器就是在用戶輸入關鍵字后，以盡量快的速度和盡量高的精確率做出反饋。檢索器要完成的步驟是：1）解析輸入字串，過濾掉無用詞匯，提取關鍵字；2）查找字典，得到WordID和它所在的桶的位置；3）在索引端數據庫中進行檢索，得到一個匹配網頁的集合；4）用權威值算法對網頁加權，然后按權值排列這些網頁，把權值高的排在考前的位置。
???
一般檢索器考慮先到一類桶（短索引）中查找，如果找到的匹配項不足夠多時，再去二類桶進行第二次檢索。至于權威值的算法，差不多所有的搜索引擎都在用PageRank算法，或它的改進版本。
?
三、網頁排序與PageRank算法
??? Google
使用PageRank算法排列網頁，這個算法的提出者是九幾年斯坦福大學的博士研究生Sergey Brin和Lawrence Page，他倆也就是Google的創始人。別的搜索引擎的排序方法略有變化，但實際上也是以PageRank為原型的。
??? 1
．確定問題域：
???
當檢索算法返回一個對關鍵字匹配的網頁集合V后。返回的頁面數量可能非常大，對其完全排序是很難的。這時，首先按照關鍵字出現頻率、出現位置、集中度還有網頁本身的權威值篩選出一個較小的集合S，叫做根集root set。然后加入S集所引用的頁面和引用了S集的頁面，擴展為集合T，這個集合就是排序的問題域。接下來對T使用PageRank方法排序。
??? 2
．PageRank的前置條件：
??? PageRank
算法所作的假設是
??? 1
）網頁的主體之間有相關性，并且體現在他們的相互超鏈接上。
??? 2
）用戶的大部分瀏覽具有相關性，或者說連貫性，當然也不排除用戶直接跳轉到無關網頁的可能性。
??? 3
）用戶順序瀏覽網頁，忽略了他們后退的情況，也不怎么考慮在網頁上駐留的時間。（實際上如果用戶在一個頁面駐留時間長，那應該付給這個頁面更大的權值，可惜很難找到辦法計量）
??? 3
．PagePank算法的理論表述：
??? PageRank
為每個頁面制定一個權威值(Authority)。這個權威值的計算方法基本是依據以下的三條:
??? 1
）對于某一個主題，如果一個頁面被很多別的頁面引用，那么表示這個頁面比較重要，要獲得較高的權威值：
??? 2
）如果一個頁面被很重要的頁面（比如說知名的網站Yahoo、sohu）引用，表示這個頁面比較重要，也要獲得較高的權威值；
??? 3
）頁面引用了別的頁面，則它把自己的權威值等分后傳遞給它所引用的其他頁面（其實不一定是等分，還要看鏈接的質量）；
??? 4
．算法實現：
???
網頁集合T加上相互的鏈接構成了一個有向圖，由輸出的節點集合為V，又輸入的節點集合為U，圖的有向邊集合為E：
???
最初，每個輸出點有相同的hub值且 ∑hub(v)=1，v∈V；
??? ----------------------------
???
對每個u∈U執行I操作：Authority(u)=∑hub(v)*1/Nv? 其中v∈{v|(v,u) ∈E},Nv是v的鏈接數；
???
接下來對v∈V執行O操作：hub(v)= ∑Authority(u)*1/Nu?? 其中u∈{u|(v,u) ∈E},Nu是u的被鏈接數；
???
然后分別對U和V集合的節點規格化，使∑hub(v)=1，∑Authority(u)=1。
??? ----------------------------
???
循環對其總的節點作以上的操作，直到u和v趨于穩定（可以證明u、v值在多次循環后處于收斂）
??? 5
．一些改進：
???
有很多人對這個原始算法作了改進和補充，其中比如說：
???
這個算法沒有考慮搜索的主題關鍵字對排序的影響，所以經常出現的一個問題是出題遷移，排出來的最高權值者可能不是最相關于用戶做要搜索的主題了。所以就引入了文檔相似度的一個輔助量Similarity(Q,Dj)；
???
在實際的情況中，一個頁面中的很多連接完全可能有一些很重要，與主題密切相關、另一些不重要，只是一些廣告什么的，所以有人就提出了ARC算法按不同重要性（錨文本左右相鄰的關鍵字的密度）對權值進行分割，比較準確；
???
另外，還設立一個閥值，不再把權值低的網頁的貢獻計入∑hub(v)；
???
其實還有很多對PageRank的改進算法。
???
四、之后的工作與研究方向
???
如何建立便捷與易于維護的索引是我一直在看的。可惜相關的文獻都是久遠年代的東西了，關于倒排表、后綴樹、簽名檔以及他們衍生物的性能比較也是可能的方向。另外這些東西不單是搜索引擎網站關心的，也是圖書館學的研究課題（一份期刊：Journal of the American Society for Information Science and Technology???JASIST）
???
相關性排序是一個有意思的東西，將pagerank權值引入對網頁的相關性排序是Sergey Brin和Lawrence Page的杰作。而這么多年對于算法的準確性和效率的改進一直沒有停止，很多人都對如何把搜索結果排的更整齊有自己的看法（所以說它有意思）。有一篇文章：Google の秘密 - PageRank 徹底解説? by Hajime BABA / 馬場肇