搜尋引擎原理實作

基本要求：

在一個可以接受的時間内傳回一個和該使用者查詢比對的網頁資訊清單，這個清單的每一條目至少包含三個元素(标題,網址連結,摘要)。其中的關鍵字：

“可以接受的時間”：指響應時間，通常也就在“秒”這個量級。更進一步的,這樣的響應時間要求不僅要能滿足單個使用者查詢,而且要能在系統設計負載的情況下滿足所有的使用者。也就是說,系統應該在額定吞吐率的情況下保證秒級響應時間。

”比對“：搜尋結果應以某種形式包含搜尋詞

”清單“：“ 清單”這蘊含着一種“序”(rank)。在絕大多數情況下,l 是相當長的,例如超過1萬個條目，而對于一個長長的清單,很少有使用者有耐心都審視一遍

網頁搜集

這個軟體系統操作的資料不僅包括内容不可預測的使用者查詢,還要包括在數量上動态變化的海量網頁,并且這些網頁不會主動送到系統來,而是需要由系統去抓取。

搜集方法：

1.定期搜集（批量搜集）：每次搜集替換上一次的内容。對于大規模搜尋引擎來說,每次搜集的時間通常會花幾周。而由于這樣做開銷較大,通常兩次搜集的間隔時間也不會很短。這樣做的好處是系統實作比較簡單,主要缺點是“時新性”(freshness)不高,還有重複搜集所帶來的額外帶寬的消耗。

2.增量搜集：開始時搜集一批,往後隻是(1)搜集新出現的網頁,(2)搜集那些在上次搜集後有過改變的網頁,(3)發現自從上次搜集後已經不再存在了的網頁,并從庫中删除。這樣的系統表現出來的資訊時新性就會比較高,主要缺點是系統實作比較複雜

扒取實作方案：将 web 上的網頁集合看成是一個有向圖,搜集過程從給定起始 url 集合 s(或者說“種子”)開始,沿着網頁中的連結,按照先深、先寬、或者某種别的政策周遊,不停的從 s 中移除 url,下載下傳相應的網頁,解析出網頁中的超連結 url,看是否已經被通路過,将未通路過的那些 url 加入集合s。外一種可能的方式是在第一次全面網頁搜集後,系統維護相應的 url 集合 s,往後的搜集直接基于這個集合。每搜到一個網頁,如果它發生變化并含有新的 url,則将它們對應的網頁也抓回來,并将這些新 url 也放到集合 s 中;如果 s 中某個 url 對應的網頁不存在了,則将它從 s 中删除。

預處理

主要包括四個方面：

關鍵詞的提取：主要擷取出現頻率高的關鍵字，但應注意去掉要去掉諸如“的”,”在”等沒有内容訓示意義的詞

“鏡像網頁” (網頁的内容完全相同,未加任何修改)或“轉載網頁”(near-replicas,主題内容基本相同但可能有一些額外的編輯資訊等,轉載網頁也稱為“近似鏡像網頁”)的消除。據統計，當你通過一個 url在網上看到一篇網頁的時候,平均還有另外 3 個不同的 url 也給出相同或者基本相似的内容。重複的搜集會消耗機器時間和網絡帶寬資源。而且如果在查詢結果中出現,無意義地消耗了計算機顯示屏資源,也會引來使用者的抱怨。

連結分析：大量的 html 标記既給網頁的預處理造成了一些麻煩,也帶來了一些新的機遇。例如在同一篇文檔中, < h1>和< /h1>之間的資訊很可能就比在< h4>和< /h4>之間的資訊更重要。再如對“北大學報”這幾個字在北京大學學報社會科學版的首頁上是沒有的,，是以一個僅靠内容文字分析的搜尋引擎就不可能傳回該首頁作為結果。但是北京大學首頁上是用“北大學報(社)”作為連結資訊指向了北京大學學報社會科學版的首頁。是以在很好利用連結資訊的搜尋引擎中應該能傳回北京大學學報社會科學版的首頁。

網頁重要程度的計算。根據人們參照科技文獻重要性的評估方式,核心想法就是“被引用多的就是重要的”。

查詢服務

在預處理後的網頁元素，至少包含如下幾個方面：

原始網頁文檔

url 和标題

編号

所含的重要關鍵詞的集合(以及它們在文檔中出現的位置資訊)

其他一些名額(例如重要程度,分類代碼等)

而系統關鍵詞總體的集合和文檔的編号一起構成了一個倒排檔案結構,使得一旦得到一個關鍵詞輸入,系統能迅速給出相關文檔編号的集合輸出。而使用者搜尋看到的是一個清單，是以我們需要完成集合->清單的轉化

根據使用者查詢内容切詞，如使用者查詢“網絡與分布式系統實驗室”，忽略一些幾乎沒有意義的字詞（如“的”，“與”等）将搜尋内容分成一個詞列q = {t 1, t 2 , …, t m },在本例中就是q = {網絡,分布式,系統,實驗室}。而倒排檔案就是用詞來作為索引的一個資料結構,顯然, q中的詞必須是包含在倒排檔案詞表中才有意義。有了這樣的q,它的每一個元素都對應倒排檔案中的一個倒排表(文檔編号的集合),記作l(t i ),它們的交集即為對應查詢的結果文檔集合,進而實作了查詢和文檔的比對。

結果排序。我們通過前述關鍵詞的提取過程,形成一篇文檔的關鍵詞集合,p = {t 1 , t 2 , …, t n }的時候,很容易同時得到每一個t i 在該文檔中出現的次數,即詞頻,而倒排檔案中每個倒排表的長度則對應着一個詞所涉及的文檔的篇數,即文檔頻率。但由于網頁編寫的自發性、随意性較強,僅僅針對詞的出現來決定文檔的順序,在web上做資訊檢索表現出明顯的缺點,于是我們可以通過結合在預處理階段形成的獨立于查詢次的重要性名額形成一個更可靠的排序序列

文檔摘要。摘要也是搜尋結果的重要組成部分，摘要的生成基本可以歸納成如下兩種方式

靜态方式,即獨立于查詢,按照某種規則,事先在預處理階段從網頁内容提取出一些文字,例如截取網頁正文的開頭 512個位元組(對應 256 個漢字),或者将每一個段落的第一個句子拼起來等。雖然友善簡單，但它最大的缺點是摘要和查詢無關

動态方式。即在響應查詢的時候,根據查詢詞在文檔中的位置,提取出周圍的文字來,在顯示時将查詢詞标亮。為了保證查詢的效率,需要在預處理階段分詞的時候記住每個關鍵詞在文檔中出現的位置。

網頁搜集：網頁搜集的過程是從 url 庫(初始時包含使用者指定的起始種子 url 集合,可以是1 個或多個)獲得輸入,解析 url 中标明的 web 伺服器位址、建立連接配接、發送請求和接收資料,将獲得的網頁資料存儲在原始網頁庫,并從其中提取對外連結接資訊放入網頁結構庫,同時将待抓取的 url 放入 url 庫,保證整個過程的遞歸進行,直到 url 庫為空。

定義 url 類和 page 類

<code>enum url_scheme{ scheme_http, scheme_ftp, scheme_invalid };</code>

<code>class curl { public: string m_surl;// url 字串 enum url_scheme m_escheme; // 協定名 string m_shost; // 主機名 int m_nport;// 端口号 string m_spath;// 請求資源 curl(); ~curl(); bool parseurl( string strurl ); private: void parsescheme ( const char *url ); };</code>

有了 url,搜集系統就可以按照 url 辨別抓取其所對應的網頁,網頁資訊

儲存在 page 類中。

<code>class cpage { public: string m_surl; // 網頁頭資訊 string m_sheader; int m_nlenheader; int m_nstatuscode; int m_ncontentlength; string m_slocation; bool m_bconnectionstate; // 如果連接配接關閉,是 false,否則為 true string m_scontentencoding; string m_scontenttype; string m_scharset; string m_stransferencoding; // 網頁體資訊 string m_scontent; int m_nlencontent; string m_scontentnotags; // link, in a lash-up state string m_scontentlinkinfo; // 為搜尋引擎準備的連結,in a lash-up state string m_slinkinfo4se; int m_nlenlinkinfo4se; // 為曆史存檔準備的連結, in a lash-up state string m_slinkinfo4history; int m_nlenlinkinfo4history; //為搜尋準備的連結,in a good state reflink4se m_reflink4se[max_url_references]; int m_nreflink4senum; //為曆史存檔準備的連結, in a good state reflink4history m_reflink4history[max_url_references/2]; int m_nreflink4historynum; map&lt;string,string&gt; m_maplink4se; vector&lt;string &gt; m_veclink4history; enum page_type m_etype; // 網頁類型 public: cpage(); cpage::cpage(string strurl, string strlocation, char* header, char* body, int nlenbody); ~cpage(); void parseheaderinfo(string header); // 解析網頁頭資訊 bool parsehyperlinks(); // 從網頁體中解析連結資訊 bool normalizeurl(string&amp; strurl); bool isfilterlink(string plink); private: // 解析網頁頭資訊 void getstatuscode(string header); void getcontentlength(string header); void getconnectionstate(string header); void getlocation(string header); void getcharset(string header); void getcontentencoding(string header); void getcontenttype(string header); void gettransferencoding(string header); // 從網頁體中解析連結資訊 bool getcontentlinkinfo(); bool getlinkinfo4se(); bool getlinkinfo4history(); bool findreflink4se(); bool findreflink4history(); };</code>

避免對網站的重複收集

造成重複搜集的原因,一方面是搜集程式沒有清楚記錄已經通路過的url,另一方面是由于域名與 ip 多重對應關系造成的。解決方法如下

記錄未通路、已通路 url 和網頁内容摘要資訊，通過對比未通路、已通路url去重。除了存儲上述“已通路表”和“未通路表”的摘要資訊,還存儲了已經擷取網頁内容的摘要資訊。存儲網頁内容的摘要資訊的原因是 web 上存在大量的複制網頁,它們是 url 不同,内容完全一樣。

記錄未通路和已通路 url 資訊,可以保證搜集的網頁中所有的 url 都不同。但是域名與 ip 的對應存在複雜的關系,導緻即使 url 不同,也可能指向的實體網頁是相同的。而可能導緻重複的ip與域名的對應方式有：

多個域名對應一個 ip（如使用虛拟主機）

一個域名對應多個ip（分布式系統可能用到）

多個域名對應多個ip

要解決重複收集網頁,就要找出那些指向同一實體位置 url 的多個域名和ip。這是一個逐漸累積的過程。首先要累積到一定數量的域名和 ip,比如 100 萬個,然後把這些域名和 ip 對應的首頁和首頁連結出的最開始的幾個頁面抓取回來。如果比較結果一樣,則應該歸為一組。以後搜集的時候可以隻選擇其中的一個進行搜集。選擇的時候應該優先選擇有域名的,有的網站對于直接用 ip 通路是被禁止的。

網頁預處理的第一步就是為原始網頁建立索引,實作索引網頁庫,有了索引就可以為搜尋引擎提供網頁快照功能；接下來針對索引網頁庫進行網頁切分,将每一篇網頁轉化為一組詞的集合;最後将網頁到索引詞的映射轉化為索引詞到網頁的映射,形成倒排檔案(包括倒排表和索引詞表),同時将網頁中包含的不重複的索引詞彙聚成索引詞表

1. 切詞算法

2. 建立倒排檔案

檢索算法

動态摘要算法1