搜索引擎的工作原理

1、搜索引擎的工作(gngzu)原理共二十八頁(yè)1.什么(shn me)是搜索引擎？搜索引擎（Search Engine）是指根據(jù)一定的策略、運(yùn)用特定的計(jì)算機(jī)程序從互聯(lián)網(wǎng)上搜集信息，在對(duì)信息進(jìn)行組織和處理后，為用戶提供檢索服務(wù)，將用戶檢索相關(guān)的信息展示給用戶的系統(tǒng)。搜索引擎包括全文索引、目錄索引、元搜索引擎、垂直搜索引擎、集合(jh)式搜索引擎、門戶搜索引擎與免費(fèi)鏈接列表等一個(gè)搜索引擎由搜索器 、索引器 、檢索器 和用戶接口四個(gè)部分組成。搜索器的功能是在互聯(lián)網(wǎng)中漫游，發(fā)現(xiàn)和搜集信息。索引器的功能是理解搜索器所搜索的信息，從中抽取出索引項(xiàng)，用于表示文檔 以及生成文檔庫(kù)的索引表。檢索器的功能是根據(jù)用戶的

2、查詢?cè)谒饕龓?kù)中快速檢出文檔，進(jìn)行文檔與查詢的相關(guān)度評(píng)價(jià)，對(duì)將要輸出的結(jié)果進(jìn)行排序，并實(shí)現(xiàn)某種用戶相關(guān)性反饋機(jī)制。用戶接口的作用是輸入用戶查詢、顯示查詢結(jié)果、提供用戶相關(guān)性反饋機(jī)制。 維基百科共二十八頁(yè)2.搜索引擎的基本(jbn)分類全文索引目錄(ml)索引元索引共二十八頁(yè)3.搜索引擎的基本(jbn)組成共二十八頁(yè)4.搜索引擎的工作(gngzu)原理共二十八頁(yè)基本原理1、找到網(wǎng)站的URL并下載頁(yè)面。2、判斷頁(yè)面質(zhì)量是否達(dá)到收錄標(biāo)準(zhǔn)收錄頁(yè)面，否則刪除(shnch)。3、判斷收錄頁(yè)面是否更新，更新頁(yè)面快照。共二十八頁(yè)1.通過(guò)(tnggu)網(wǎng)絡(luò)爬蟲獲取信息網(wǎng)絡(luò)爬蟲是搜索引擎的下載系統(tǒng)，它的作用是內(nèi)容的

3、獲取，手段就是在萬(wàn)維網(wǎng)中通過(guò)鏈接不斷爬取收集各類網(wǎng)頁(yè)。但是互聯(lián)網(wǎng)的頁(yè)面浩如煙海，而且每天不斷有新的內(nèi)容產(chǎn)生，根據(jù)爬取目標(biāo)和范圍，可以將爬蟲簡(jiǎn)單分為以下幾類： 批量性爬蟲：明確的抓取目標(biāo)和范圍，達(dá)到即停止增量型爬蟲：應(yīng)對(duì)網(wǎng)頁(yè)不斷更新的狀態(tài)，爬蟲需要及時(shí)反應(yīng)。通用商業(yè)引擎(ynqng)一般都是這類垂直型爬蟲：只針對(duì)某個(gè)特定領(lǐng)域的爬蟲，根據(jù)主題過(guò)濾。共二十八頁(yè)爬蟲在爬取網(wǎng)頁(yè)(wn y)的時(shí)候，應(yīng)該怎樣確定下一步的目標(biāo)呢？主要有以下策略：寬度優(yōu)先：最簡(jiǎn)單的方式，即將某個(gè)頁(yè)面中的鏈接依次加入待爬取隊(duì)列局部PageRank：PageRank是一種網(wǎng)頁(yè)重要性指標(biāo)，這種方式根據(jù)一定(ydng)時(shí)期內(nèi)的局部Pa

4、geRank值決定下一步爬取目標(biāo)OPIC：當(dāng)下載當(dāng)前網(wǎng)頁(yè)后，將其重要性平均分給包含的鏈接，每次選取最重要的頁(yè)面，不用迭代計(jì)算，速度較快大站優(yōu)先：思想很簡(jiǎn)單，以網(wǎng)站為單位衡量頁(yè)面重要性。共二十八頁(yè)簡(jiǎn)要(jinyo)說(shuō)明蜘蛛（網(wǎng)絡(luò)爬蟲）在整個(gè)互聯(lián)網(wǎng)上爬行遇見你網(wǎng)站的一個(gè)URL，首先把URL提取出來(lái)根據(jù)網(wǎng)站權(quán)重(qun zhn)和相關(guān)性插入到URL隊(duì)列中，然后是判斷你網(wǎng)站的這條URL是否能夠解析成功，如果能解析成功，蜘蛛會(huì)爬到你網(wǎng)站，這里需要說(shuō)一下，蜘蛛并不是直接去分析你網(wǎng)頁(yè)的內(nèi)容，而是去尋找你網(wǎng)站robots文件，根據(jù)你網(wǎng)站的robots規(guī)則判斷是否抓取你這個(gè)頁(yè)面，如果robots文件不存在，則會(huì)

5、返回一個(gè)404錯(cuò)誤，但是搜索引擎已經(jīng)會(huì)繼續(xù)抓取你的網(wǎng)站內(nèi)容。搜索引擎抓取了網(wǎng)頁(yè)內(nèi)容之后會(huì)對(duì)網(wǎng)頁(yè)進(jìn)行一個(gè)簡(jiǎn)單的判斷是否達(dá)到了收錄標(biāo)準(zhǔn)，如果不符合則繼續(xù)把URL加入到URL隊(duì)列中，如果符合收錄就會(huì)下載網(wǎng)頁(yè)內(nèi)容。共二十八頁(yè)2. 建立(jinl)索引對(duì)于搜索引擎，索引更是其中最重要的核心技術(shù)之一，面對(duì)海量的網(wǎng)頁(yè)內(nèi)容，如何快速找到包含用戶查詢?cè)~的所有網(wǎng)頁(yè)？倒排索引在其中扮演了關(guān)鍵的角色。對(duì)于一個(gè)網(wǎng)頁(yè)，我們把它看做一個(gè)文檔，其中的內(nèi)容由一個(gè)個(gè)單詞組成。為了對(duì)于用戶的搜索詞快速給出文檔結(jié)果，我們要建立一個(gè)單詞-文檔的存儲(chǔ)結(jié)構(gòu)。倒排索引是實(shí)現(xiàn)單詞文檔矩陣的一種具體存儲(chǔ)形式。通過(guò)倒排索引，可以根據(jù)單詞快速獲取包

6、含這個(gè)單詞的文檔列表(li bio)。倒排索引主要由兩個(gè)部分組成：?jiǎn)卧~詞典和倒排文件。 單詞詞典主要是兩種存儲(chǔ)方式：哈希加鏈接和樹形結(jié)構(gòu)。共二十八頁(yè)索引建立(jinl)方法：（1）兩遍文檔遍歷在第一遍掃描文檔集合(jh)時(shí)，該方法并沒有立即開始建立索引，而是收集一些全局的統(tǒng)計(jì)信息。比如文檔集合(jh)包含的文檔個(gè)數(shù)N，文檔集合內(nèi)所包含的不同單詞個(gè)數(shù)M，每個(gè)單詞在多少個(gè)文檔中出現(xiàn)過(guò)的信息DF。在獲得了上述3 類信息后，就可以知道最終索引的大小，于是在內(nèi)存中分配足夠大的空間，用來(lái)存儲(chǔ)倒排索引內(nèi)容。在第二遍掃描的時(shí)候，開始真正建立每個(gè)單詞的倒排列表信息，即對(duì)某個(gè)單詞來(lái)說(shuō)，獲得包含這個(gè)單詞的每個(gè)文檔的

7、文檔ID，以及這個(gè)單詞在文檔中的出現(xiàn)次數(shù)TF共二十八頁(yè)（2）排序法排序法對(duì)此做出了改進(jìn)，該方法在建立索引的過(guò)程中，始終在內(nèi)存中分配固定大小的空間，用來(lái)存放詞典信息和索引的中間結(jié)果，當(dāng)分配的空間被消耗光的時(shí)候，把中間結(jié)果寫入磁盤，清空內(nèi)存里中間結(jié)果所占空間，以用做下一輪存放索引中間結(jié)果的存儲(chǔ)區(qū)。這種方法由于只需要固定大小的內(nèi)存，所以(suy)可以對(duì)任意大小的文檔集合建立索引。共二十八頁(yè)（3）歸并法在分配的內(nèi)存定額被消耗光時(shí)，排序法只是將中間結(jié)果寫入磁盤，而詞典信息一直在內(nèi)存中進(jìn)行維護(hù)，隨著處理的文檔越來(lái)越多，詞典里包含的詞典項(xiàng)越來(lái)越多，所以(suy)占用內(nèi)存越來(lái)越大，導(dǎo)致后期中間結(jié)果可用內(nèi)存越來(lái)

8、越少。歸并法對(duì)此做出了改進(jìn)，即每次將內(nèi)存中數(shù)據(jù)寫入磁盤時(shí)，包括詞典在內(nèi)的所有中間結(jié)果信息都被寫入磁盤，這樣內(nèi)存所有內(nèi)容都可以被清空，后續(xù)建立索引可以使用全部的定額內(nèi)存。共二十八頁(yè)索引(suyn)的更新策略完全重建(zhn jin)再合并策略原地更新策略混合策略共二十八頁(yè)3. 內(nèi)容(nirng)檢索內(nèi)容檢索模型是搜索引擎排序的理論基礎(chǔ)，用來(lái)計(jì)算網(wǎng)頁(yè)與查詢(chxn)的相關(guān)性。A.常用的檢索模型布爾模型向量空間模型概率模型語(yǔ)言模型機(jī)器學(xué)習(xí)排序共二十八頁(yè)檢索系統(tǒng)評(píng)價(jià)(pngji)指標(biāo)精確率：搜索結(jié)果中相關(guān)文檔的比例 A/(A+B)召回(zho hu)率：結(jié)果中相關(guān)文檔占所有相關(guān)文檔的比例 A/(A+

9、C)P10 : 前10個(gè)結(jié)果中相關(guān)查詢的數(shù)目MAP指標(biāo) ：對(duì)返回結(jié)果按次序加權(quán),權(quán)值為排名的倒數(shù)查詢相關(guān)查詢無(wú)關(guān)在搜索結(jié)果內(nèi)AB不在搜索結(jié)果CD共二十八頁(yè)4. 鏈接(lin ji)分析搜索引擎在查找能夠滿足用戶請(qǐng)求的網(wǎng)頁(yè)(wn y)時(shí)，主要考慮兩方面的因素：一方面是用戶發(fā)出的查詢與網(wǎng)頁(yè)(wn y)內(nèi)容的內(nèi)容相似性得分，即網(wǎng)頁(yè)(wn y)和查詢的相關(guān)性；另一方面就是通過(guò)鏈接分析方法計(jì)算獲得的得分，即網(wǎng)頁(yè)(wn y)的重要性。鏈接分析就是通過(guò)網(wǎng)絡(luò)的鏈接結(jié)構(gòu)去獲取網(wǎng)頁(yè)(wn y)重要性的一類方法。鏈接分析算法很多，從模型上看，主要分為兩類：隨機(jī)游走：從某個(gè)網(wǎng)頁(yè)以一定的概率跳轉(zhuǎn)到它所包含的鏈接子集傳播

10、：給予某個(gè)子集一定的傳播，按照特定的條件，將權(quán)值傳給其他網(wǎng)頁(yè)共二十八頁(yè)5.搜索(su su)結(jié)果的改善優(yōu)化共二十八頁(yè)5.1 作弊(zu b)分析作弊方法內(nèi)容(nirng)作弊：設(shè)置無(wú)關(guān)關(guān)鍵字，內(nèi)容(nirng)農(nóng)場(chǎng) （大量低質(zhì)量?jī)?nèi)容(nirng)）鏈接作弊：鏈接農(nóng)場(chǎng)，互相鏈接.頁(yè)面隱藏作弊：欺騙爬蟲，隱藏?zé)o關(guān)關(guān)鍵字，重定向。WEB2.0作弊反作弊整體思路信任傳播不信傳播異常發(fā)現(xiàn)共二十八頁(yè)A.信任(xnrn)傳播模型在海量的網(wǎng)頁(yè)數(shù)據(jù)中，通過(guò)一定的技術(shù)手段或者人工半人工手段，從中篩選出部分完全值得信任的頁(yè)面，也就是肯定不會(huì)作弊的頁(yè)面（可以(ky)理解為白名單），算法以這些白名單內(nèi)的頁(yè)面作為出發(fā)點(diǎn)，

11、賦予白名單內(nèi)的頁(yè)面節(jié)點(diǎn)較高的信任度分值，其他頁(yè)面是否作弊，要根據(jù)其和白名單內(nèi)節(jié)點(diǎn)的鏈接關(guān)系來(lái)確定。白名單內(nèi)節(jié)點(diǎn)通過(guò)鏈接關(guān)系將信任度分值向外擴(kuò)散傳播，如果某個(gè)節(jié)點(diǎn)最后得到的信任度分值高于一定閾值，則認(rèn)為沒有問(wèn)題，而低于這一閾值的網(wǎng)頁(yè)則會(huì)被認(rèn)為是作弊網(wǎng)頁(yè)。 共二十八頁(yè)B.不信任(xnrn)模型不信任傳播模型從框架上來(lái)講，其和信任傳播模型是相似的，最大的區(qū)別在于：初始的頁(yè)面子集合不是值得信任的頁(yè)面節(jié)點(diǎn)，而是確認(rèn)存在作弊行為的頁(yè)面集合，即不值得信任的頁(yè)面集合（可以(ky)理解為黑名單）。賦予黑名單內(nèi)頁(yè)面節(jié)點(diǎn)不信任分值，通過(guò)鏈接關(guān)系將這種不信任關(guān)系傳播出去，如果最后頁(yè)面節(jié)點(diǎn)的不信任分值大于設(shè)定的閾值，則

12、會(huì)被認(rèn)為是作弊網(wǎng)頁(yè)。 共二十八頁(yè)C.異常(ychng)發(fā)現(xiàn)模型異常發(fā)現(xiàn)(fxin)模型也是一個(gè)高度抽象化的算法框架模型，其基本假設(shè)認(rèn)為：作弊網(wǎng)頁(yè)必然存在有異于正常網(wǎng)頁(yè)的特征，這種特征有可能是內(nèi)容方面的，也有可能是鏈接關(guān)系方面的。而制定具體算法的流程往往是先找到一些作弊的網(wǎng)頁(yè)集合，分析出其異常特征有哪些，然后利用這些異常特征來(lái)識(shí)別作弊網(wǎng)頁(yè)。共二十八頁(yè)5.2 分析用戶(yngh)意圖準(zhǔn)確分析用戶的搜索意圖是目前搜索引擎的重點(diǎn)研究方向。用戶的意圖可以初略分為導(dǎo)航型，信息(xnx)型，事物型搜索日志是挖掘用戶意圖的重要數(shù)據(jù)來(lái)源點(diǎn)擊圖：用戶在查詢結(jié)果出來(lái)后點(diǎn)擊的鏈接可能更是他希望的結(jié)果查詢回話：用戶在短

13、時(shí)間的連續(xù)查詢?cè)~存在相關(guān)性查詢圖：構(gòu)建用戶查詢之間的結(jié)構(gòu)關(guān)系用戶在搜索時(shí)可能想不到合適的搜索詞，或者關(guān)鍵詞輸入錯(cuò)誤，這時(shí)候就需要幫助用戶澄清搜索意圖。常見的方法是：相關(guān)搜索，查詢糾錯(cuò)共二十八頁(yè)5.3 網(wǎng)頁(yè)(wn y)去重經(jīng)過(guò)統(tǒng)計(jì)，網(wǎng)絡(luò)中有相當(dāng)比例的網(wǎng)頁(yè)是近似相同或者完全相同的，高達(dá)29%。如果搜索返回大量相似網(wǎng)頁(yè)，顯然(xinrn)降低了搜索結(jié)果質(zhì)量。針對(duì)這一現(xiàn)象，網(wǎng)頁(yè)去重就顯得十分必要。網(wǎng)頁(yè)去重一般是在爬蟲抓取到網(wǎng)頁(yè)后，對(duì)其建立索引之前。去重算法應(yīng)該兼顧準(zhǔn)確性和運(yùn)行效率。典型的網(wǎng)頁(yè)去重算法：特征抽取文檔指紋生成相似性計(jì)算共二十八頁(yè)5.4緩存機(jī)制(jzh)緩存機(jī)制可以加快用戶相應(yīng)速度，節(jié)省計(jì)算資源緩存系統(tǒng)(xtng)的目標(biāo)是最大化緩存命中率和保持緩存與索引的一致性緩存的對(duì)象主要是網(wǎng)頁(yè)搜索結(jié)果和查詢?cè)~對(duì)應(yīng)的倒排列表緩存淘汰策略主要有動(dòng)態(tài)策略和混合策略共二十八頁(yè)一個(gè)頁(yè)面(y min)是如何被搜索引擎發(fā)現(xiàn)并收錄的？共二十八頁(yè)參考資料/11.html/11.html/link?url=K1sIVc5qtD-231wz_JMB8cZgS4xHvdNG1VMzX79RrFq64QuPMu_8Pkbl0yQviHAWN2S5SKq2yaqzHDUT6fVmnK共二十八頁(yè)內(nèi)容摘要搜索引擎的工作原理。維基百科。爬蟲在爬取網(wǎng)頁(yè)的時(shí)候，應(yīng)該怎