【文章內(nèi)容簡介】 重慶理 工大學(xué)畢業(yè)論文 搜索引擎技術(shù)研究與實(shí)現(xiàn) 6 圖 21 搜索引擎 工作流程 網(wǎng)頁搜集 搜索引擎首先利用的是一種俗稱蜘蛛（ Spider)或爬蟲（ Crawler)的軟件。搜索引擎蜘蛛訪問到一個(gè)頁面，讀取它，然后跟隨這個(gè)頁面鏈接到這個(gè)站點(diǎn)的其他頁面，這就是人們所說的站點(diǎn)被套住了或者被爬過了。蜘蛛會按照固定的時(shí)間不斷的回來訪問這個(gè)站點(diǎn)，如每月或每兩個(gè)月，以便查看頁面的變化。由于互聯(lián)網(wǎng)中超鏈接的應(yīng)用很普遍，理論上，從一定范圍的網(wǎng)頁出發(fā)，就能搜集到絕大多數(shù)的網(wǎng)頁。 索引建立 搜索引擎抓到網(wǎng)頁后，還要做大量的預(yù)處理工作，才能提供檢索服務(wù)。其中，最重要的就是提 取關(guān)鍵詞，建立索引文件。其他還包括去除重復(fù)網(wǎng)頁、分詞、判斷網(wǎng)頁類型、分析超鏈接、計(jì)算網(wǎng)頁的重要度 /豐富度等。由分析索引系統(tǒng)程序?qū)κ占貋淼木W(wǎng)頁進(jìn)行分析，提取相關(guān)網(wǎng)頁信息（包括網(wǎng)頁所在 URL、編碼類型、關(guān)鍵詞、關(guān)鍵詞位置、生成時(shí)間、大小等），根據(jù)一定的相關(guān)度算法進(jìn)行大量復(fù)雜計(jì)算，得到每一個(gè)網(wǎng)頁針對頁面內(nèi)容中及超鏈中每一個(gè)關(guān)鍵詞的相關(guān)度，然后用這些相關(guān)信息建立網(wǎng)頁索引數(shù)據(jù)庫。 搜索引擎界面接口 信息檢索系統(tǒng) 查詢請求 結(jié)果集 用戶 查詢請求 結(jié)果集 索引文件庫 索引系統(tǒng) 網(wǎng)絡(luò)爬蟲 WWW 文檔 請求 響應(yīng) HTML 文檔集 搜索 結(jié)果集 重慶理 工大學(xué)畢業(yè)論文 搜索引擎技術(shù)研究與實(shí)現(xiàn) 7 提供檢索服務(wù) 用戶輸入關(guān)鍵詞進(jìn)行檢索，搜索引擎從索引數(shù)據(jù)庫中找到匹配該關(guān)鍵詞的網(wǎng)頁，為了用戶便于判斷，除了網(wǎng)頁標(biāo)題和 URL 外，還 會提供一段來自網(wǎng)頁的摘要以及其他信息，這個(gè)程序詳細(xì)審查記錄在索引中的成百上億的 Web 頁，找出與搜索要求相匹配的那些，并按他認(rèn)為最合適的相關(guān)性排列出列表，呈現(xiàn)在沖浪者的面前。 搜索引擎常用檢索方法 主要包括： 1) 簡單搜索：指輸入一個(gè)單詞 (關(guān)鍵詞 )，提交搜索引擎檢索后反饋結(jié)果，也叫單詞搜索， 這是最基本的檢索方法。 2) 詞組搜索：指輸入兩個(gè)單詞以上的詞組 (短語 )，提交搜索引擎檢索并反饋結(jié)果，也叫短語搜索?，F(xiàn)有搜索引擎一般都約定把詞組或短語放在引號“”內(nèi)。如果查找的是一個(gè)詞組或多個(gè)漢字，最好的辦法就是將它們用雙 引號括起來，這樣得到的結(jié)果最精確，這就叫使用雙引號進(jìn)行精確查找。一般說來在網(wǎng)頁搜索引擎中，用詞組搜索來縮小范圍從而找到搜索結(jié)果是最好的辦法。但是，運(yùn)用詞組搜索涉及到如何選擇一個(gè)詞組來表達(dá)檢索問題。有時(shí)簡單搜索就能奏效，有時(shí)則需要 輸入一個(gè)詞組才能奏效，故選擇合適的詞組對提高搜索效率是很重要的。 3) 高級搜索：指用布爾邏輯組配方式檢索，也叫定制搜索。常用的邏輯運(yùn)算為AND(和 )、 OR(或 )、 NOT(非 )， 對 A、 B兩詞而言， A AND B 是指取 A 和 B 的公共部分 (交集 )， A OR B 是指取 A和 B的全部 (并集 )， A NOT B 是指取 A中排除 B后的部分。 有的搜索引擎還支持以下檢索方法： 1) 語句搜索 ： 指輸入任意自然語言問句，提交搜索引擎檢索并反饋結(jié)果，這種方式也叫任意檢索，實(shí)際上就是自然語言檢索。并非所有的搜索引擎都支持這樣的 檢索，而且不同搜索引擎對語句中詞與詞之間的關(guān)系的處理方式也不同。 2) 目錄搜索 ： 指按搜索引擎提供的分類目錄逐級檢索，用戶一般不需要輸入檢索詞，而是按照檢索系統(tǒng)所給的幾種分類項(xiàng)目，選擇類別進(jìn)行搜索，也叫分類搜索(Classified Search)。 搜索引擎的分類 搜索引擎按照信 息搜集方法和服務(wù)提供方式的不同大致可分為以下四類： 重慶理 工大學(xué)畢業(yè)論文 搜索引擎技術(shù)研究與實(shí)現(xiàn) 8 全文索引 全文索引引擎是名副其實(shí)的搜索引擎，國外代表有 Google，國內(nèi)知名的百度搜索。它們從互聯(lián)網(wǎng)提取各個(gè)網(wǎng)站的信息，建立起數(shù)據(jù)庫，并能檢索與用戶查詢條件相匹配的記錄，按一定的排列順序返回結(jié)果。根據(jù)搜索結(jié)果來源的不同，全文搜索引擎可分為兩類：一類擁有自己的網(wǎng)頁抓取、索引、檢索系統(tǒng)，有獨(dú)立的“蜘蛛”（ Spider）程序、或爬蟲（ Crawler）、或“機(jī)器人”（ Robot）程序，能自建網(wǎng)頁數(shù)據(jù)庫，搜索結(jié)果直接從自身的數(shù)據(jù)庫中調(diào)用；另一類則是租用其他 搜索引擎的數(shù)據(jù)庫，并按自定的格式排列搜索結(jié)果。 目錄索引 目錄索引是按目錄分類的網(wǎng)站鏈接列表 。 雖然有搜索功能，但嚴(yán)格意義上不能稱為真正的搜索引擎。用戶完全可以按照分類目錄找到所需要的信息，不依靠關(guān)鍵詞進(jìn)行查詢。目錄索引中最具代表性的莫過于 Yahoo、新浪分類目錄搜索。 元搜索引擎 元搜索引擎接受用戶查詢請求后，同時(shí)在多個(gè)搜索引擎上搜索，并將結(jié)果返回給用戶。著名的元搜索引擎有 InfoSpace、 Dogpile、 Vivisimo 等，中文元搜索引擎中具代表性的是搜星搜索引擎。在搜索結(jié)果排列方面 ，有的直接按來源排列搜索結(jié)果；有的則按自定的規(guī)則將結(jié)果重新排列組合。 垂直搜索引擎 垂直搜索引擎為 2020 年后逐步興起的一類搜索引擎。不同于通用的網(wǎng)頁搜索引擎，垂直搜索專注于特定的搜索領(lǐng)域和搜索需求（例如：機(jī)票搜索、旅游搜索、視頻搜索等），在其特定的搜索領(lǐng)域有更好的用戶體驗(yàn)。相比通用搜索動(dòng)輒數(shù)千臺檢索服務(wù)器，垂直搜索需要的硬件成本低、用戶需求特定、查詢的方式多樣。 重慶理 工大學(xué)畢業(yè)論文 搜索引擎技術(shù)研究與實(shí)現(xiàn) 9 3 系統(tǒng)關(guān)鍵技術(shù)問題及解決 方案 網(wǎng)頁訪問問題 及 解決 方案 爬蟲程序需要根據(jù)指定的 url，訪問一個(gè)頁面，獲取該頁面的 HTML文檔（包含一個(gè)網(wǎng)頁的所有信息），然后對 HTML 文檔進(jìn)行保存和解析，以便進(jìn)行之后倒排索引的工作，所以網(wǎng)頁的訪問是搜索引擎系統(tǒng)重要的第一步工作。 問題解決方法 : 通過 命名空間中 提供 的 HttpWebRequest 和 HttpWebResponse 類來實(shí)現(xiàn)對指定 URL 頁面的下載， HttpWebRequest 對象發(fā)送 HTTP請求后，由 HttpWebResponse 接收響應(yīng)， HttpWebResponse 對象中包含了響應(yīng)體的所有信息（包括服務(wù)器響應(yīng)體的流，響應(yīng)體進(jìn)行編碼的方法，與響應(yīng)關(guān)聯(lián)的標(biāo)頭 等），如此我們便可從 HttpWebResponse 對象中獲取網(wǎng)頁信息。 圖 31 HTTP請求及響應(yīng)過程示意圖 .NET Framework 使用 HttpWebRequest 和 HttpWebResponse 類來提供對 HTTP 協(xié)議的全面支持，而 HTTP 協(xié)議構(gòu)成了所有 Inter 通信量中的絕大部分。每當(dāng)靜態(tài)方法 遇到以“ ”或“ ”開頭的 URI 時(shí)，在默認(rèn)情況下將返回這些從 WebRequest 和 WebResponse 派生的類。在大多數(shù)情況下，WebRequest 和 WebResponse 類提供生成請求所需的一切，但如果需要訪問作為屬性公開的 HTTP 特定功能，則可以將這些類的類型轉(zhuǎn)換為 HttpWebRequest 或 HttpWebResponse。 HttpWebRequest 和 HttpWebResponse 封裝“標(biāo)準(zhǔn) HTTP 請求和響應(yīng)”事務(wù)，并提供對通用 HTTP 頭的訪問。這些類還支持大部分的 HTTP 功能，其中包括管線、 WEB 應(yīng)用服務(wù)器 網(wǎng)絡(luò)爬蟲 HTTP 請求 HTTP 響應(yīng) 重慶理 工大學(xué)畢業(yè)論文 搜索引擎技術(shù)研究與實(shí)現(xiàn) 10 塊區(qū)、身份驗(yàn)證 、預(yù)身份驗(yàn)證、加密、代理支持、服務(wù)器證書驗(yàn)證以及連接管理。自定義頭和不是通過屬性提供的頭可存儲在 Headers 屬性中并可通過此屬性訪問。HttpWebRequest 是 WebRequest 使用的默認(rèn)類，不需要注冊它就可以將 URI 傳遞給 方法。 網(wǎng)頁 解析 問題及 解決方 案 在索引建立之前 ,首先要將下載的 HTML 文檔進(jìn)行解析 ,所謂的 HTML 文檔 ,實(shí)質(zhì)便是網(wǎng)頁的代碼， 代碼中肯定包含了網(wǎng)頁中所有的文字信息 ，但是 代碼同時(shí)也包含了許多的 HTML 標(biāo)簽， 這些標(biāo)簽 中的很多內(nèi) 容同樣也是無用的，比如： style???/style這樣標(biāo)簽，它中間的內(nèi)容是無用的，它只是對網(wǎng)頁的顯示效果有用；這樣的標(biāo)簽，必須對它進(jìn)行解析，才知道它運(yùn)行后會得到什么 結(jié)果，暫且不管能不能實(shí)現(xiàn)對它的解析，即使能夠?qū)懗鲞@樣的程序，也 不得不花大量的時(shí)間，從可行性方面上分析對此標(biāo)簽的解析不可取 。 所以如何去除 HTML 文檔中無用的標(biāo)簽部分 ,提取 HTML 文檔中有用的文字信息部分是一個(gè)關(guān)鍵問題。 問題解決方法：通過正則表達(dá)式的使用，來匹配 HTML 文檔中有用的標(biāo)簽部分，并提取標(biāo) 簽中間中的文字信息進(jìn)行另存，通過直接分析這些有用的文字信息部分來實(shí)現(xiàn)倒排索引，這樣大大提高了索引建立的效率。 在 .NET 中提供了對正則表達(dá)式的支持，并且提供了相關(guān)的類，分別有： Regex、Match、 Group、 Capture、 RegexOptions、 MatchCollection、 GroupCollection、CaptureCollection。提取網(wǎng)頁中的 URL，主要使用以下幾個(gè)類： Regex：正則表達(dá)式類，代表了一個(gè)不可變的正則表達(dá)式。 Match：代表了 Regex 類的實(shí)例的一次匹配結(jié)果，可以通 過 Regex 的 Match()實(shí)例方法返回一個(gè) Match 的實(shí)例。 MatchCollection：代表了 Regex 類的實(shí)例的所有匹配結(jié)果，可以通過 Regex 的Matches()實(shí)例方法返回一個(gè) MatchCollection 的實(shí)例。 正則表達(dá)式的一種最常用的場所是用于使用一些預(yù)先定義的格式校驗(yàn)用戶輸入。這些規(guī)則被典型地定義為正則表達(dá)式。正則表達(dá)式也常用于校驗(yàn)簡單的輸入，例如電子郵件地址和電話號碼。 命名空間包含一些類，重慶理 工大學(xué)畢業(yè)論文 搜索引擎技術(shù)研究與實(shí)現(xiàn) 11 這些類提供對 .NET Framework 正則表達(dá)式引擎的訪問。該命名空間提供正則表達(dá)式功能，可以從運(yùn)行在 Microsoft .NET Framework 內(nèi)的任何平臺或語言中使用該功能。 倒排索引存儲問題及解決 方 案 倒排索引源于實(shí)際應(yīng)用中需要根據(jù)屬性的值來查找記錄。這種索引表中的每一項(xiàng)都包括一個(gè)屬性值和具有該屬性值的各記錄的地址。由于不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，因而稱為倒排索引 (inverted index)。帶有倒排索引的文件我們稱為倒排索引文件，簡稱倒排文件 (inverted file)。倒排文件 （倒排索引），索引對象是文檔或者文檔集合中的單詞等，用來存儲這些單詞在一個(gè)文檔或者一組文檔中的存儲位置，是對文檔或者文檔集合的一種最常用的索引機(jī)制。 本系統(tǒng)建立的 倒排索引是從索引 詞 項(xiàng) 到 URL 的關(guān)系索引表 ，即由關(guān)鍵詞 查找相應(yīng)的 URL 信息 。索引表也要記錄索引項(xiàng)在文檔中出現(xiàn)的位置，以便檢索系統(tǒng) 計(jì)算索引項(xiàng)之間的相鄰關(guān)系或接近關(guān)系，并以特定的數(shù)據(jù)結(jié)構(gòu)存儲在硬盤上 ，為檢索系統(tǒng)服務(wù) ，因此倒排索引的存儲結(jié)構(gòu)對之后的檢索系統(tǒng)的檢索效率有 著 重要的作用和影響 。 解決方法 ：建立兩種類型文件，索引文件和詞頻文件。索引文件（即倒排索引 文件）存儲每個(gè)索引項(xiàng)的文檔頻率和該詞在各文檔中的出現(xiàn)位置。詞頻文件，存儲每個(gè)詞項(xiàng)在各文檔中的出現(xiàn)頻率 ，以便最后檢索系統(tǒng)的評分。 同時(shí)，文件中各項(xiàng)都用兩個(gè)特殊符號括起來，以便正則表達(dá)式的匹配獲取。 檢索系統(tǒng)評分問題及解決 方 案 檢索系統(tǒng)要根據(jù)用戶給出的查詢語句 ,查找倒排索引 ,根據(jù)得到的文檔和查詢語句的相關(guān)性，對結(jié)果進(jìn)行排序 ,講文檔按照相關(guān)性由大到小排序返回給用戶 ,相關(guān)性越大說明越接近用戶的查詢需求 ,因此對于文檔和查詢語句的相關(guān)性計(jì)算是一個(gè)關(guān)鍵性的問題。 解決方法： 判斷詞 (Term)之間的關(guān)系從而得到文檔相 關(guān)性的過程應(yīng)用一種叫做向量空間模型的算法 (Vector Space Model)。 首先， 影響一個(gè)詞 (Term)在一篇文檔中的重要性主要有兩個(gè)因素： Term Frequency (TF)：即此 Term 在此文檔中出現(xiàn)了多少次。 TF越大說明越重要。計(jì)算公式： TF = 該詞在該文檔中出現(xiàn)次數(shù) /該文檔中出現(xiàn)最多的詞的出現(xiàn)次數(shù) 。 重慶理 工大學(xué)畢業(yè)論文 搜索引擎技術(shù)研究與實(shí)現(xiàn) 12 Document Frequency (IDF)：即有多少文檔包含此 Term。 IDF 越大說明越重要。計(jì)算公式： IDF = lg(總文檔數(shù) /出現(xiàn)的文檔數(shù) )。 規(guī)定每個(gè)詞（ Term）的權(quán)重為 weight，計(jì)算公式一般為 TF * IDF。 我們把所有此文檔中詞 (term)的權(quán)重 (term weight) 看作一個(gè)向量。 Document = {term1, term2, ?? ,term N} Document Vector = {weight1, weight2, ?? ,weight N} 同樣我們把查詢語句看作一個(gè)簡單的文檔，也用向量來表示。 Query = {term1, term 2, ?? , term N} Query Vector = {weight1, weight2, ?? , weight N} 我們把所有索引 的文檔向量及查詢向量放到一個(gè)