搜索引擎的工作原理

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

2、度評價(jià)，對將要輸出的結(jié)果進(jìn)行排序，并實(shí)現(xiàn)某種用戶相關(guān)性反饋機(jī)制。用戶接口的作用是輸入用戶查詢、顯示查詢結(jié)果、提供用戶相關(guān)性反饋機(jī)制。 維基百科2.搜索引擎的基本分類全文索引目錄索引元索引3.搜索引擎的基本組成4.搜索引擎的工作原理基本原理1、找到網(wǎng)站的URL并下載頁面。2、判斷頁面質(zhì)量是否達(dá)到收錄標(biāo)準(zhǔn)收錄頁面，否則刪除。3、判斷收錄頁面是否更新，更新頁面快照。1.通過網(wǎng)絡(luò)爬蟲獲取信息網(wǎng)絡(luò)爬蟲是搜索引擎的下載系統(tǒng)，它的作用是內(nèi)容的獲取，手段就是在萬維網(wǎng)中通過鏈接不斷爬取收集各類網(wǎng)頁。但是互聯(lián)網(wǎng)的頁面浩如煙海，而且每天不斷有新的內(nèi)容產(chǎn)生，根據(jù)爬取目標(biāo)和范圍，可以將爬蟲簡單分為以下幾類： 批量性爬蟲

3、：明確的抓取目標(biāo)和范圍，達(dá)到即停止增量型爬蟲：應(yīng)對網(wǎng)頁不斷更新的狀態(tài)，爬蟲需要及時(shí)反應(yīng)。通用商業(yè)引擎一般都是這類垂直型爬蟲：只針對某個(gè)特定領(lǐng)域的爬蟲，根據(jù)主題過濾。爬蟲在爬取網(wǎng)頁的時(shí)候，應(yīng)該怎樣確定下一步的目標(biāo)呢？主要有以下策略：寬度優(yōu)先：最簡單的方式，即將某個(gè)頁面中的鏈接依次加入待爬取隊(duì)列局部PageRank：PageRank是一種網(wǎng)頁重要性指標(biāo)，這種方式根據(jù)一定時(shí)期內(nèi)的局部PageRank值決定下一步爬取目標(biāo)OPIC：當(dāng)下載當(dāng)前網(wǎng)頁后，將其重要性平均分給包含的鏈接，每次選取最重要的頁面，不用迭代計(jì)算，速度較快大站優(yōu)先：思想很簡單，以網(wǎng)站為單位衡量頁面重要性。簡要說明蜘蛛（網(wǎng)絡(luò)爬蟲）在整個(gè)互

4、聯(lián)網(wǎng)上爬行遇見你網(wǎng)站的一個(gè)URL，首先把URL提取出來根據(jù)網(wǎng)站權(quán)重和相關(guān)性插入到URL隊(duì)列中，然后是判斷你網(wǎng)站的這條URL是否能夠解析成功，如果能解析成功，蜘蛛會(huì)爬到你網(wǎng)站，這里需要說一下，蜘蛛并不是直接去分析你網(wǎng)頁的內(nèi)容，而是去尋找你網(wǎng)站robots文件，根據(jù)你網(wǎng)站的robots規(guī)則判斷是否抓取你這個(gè)頁面，如果robots文件不存在，則會(huì)返回一個(gè)404錯(cuò)誤，但是搜索引擎已經(jīng)會(huì)繼續(xù)抓取你的網(wǎng)站內(nèi)容。搜索引擎抓取了網(wǎng)頁內(nèi)容之后會(huì)對網(wǎng)頁進(jìn)行一個(gè)簡單的判斷是否達(dá)到了收錄標(biāo)準(zhǔn)，如果不符合則繼續(xù)把URL加入到URL隊(duì)列中，如果符合收錄就會(huì)下載網(wǎng)頁內(nèi)容。2. 建立索引建立索引對于搜索引擎，索引更是其中最重

5、要的核心技術(shù)之一，面對海量的網(wǎng)頁內(nèi)容，如何快速找到包含用戶查詢詞的所有網(wǎng)頁？倒排索引在其中扮演了關(guān)鍵的角色。對于一個(gè)網(wǎng)頁，我們把它看做一個(gè)文檔，其中的內(nèi)容由一個(gè)個(gè)單詞組成。為了對于用戶的搜索詞快速給出文檔結(jié)果，我們要建立一個(gè)單詞-文檔的存儲(chǔ)結(jié)構(gòu)。倒排索引倒排索引是實(shí)現(xiàn)單詞文檔矩陣的一種具體存儲(chǔ)形式。通過倒排索引，可以根據(jù)單詞快速獲取包含這個(gè)單詞的文檔列表。倒排索引主要由兩個(gè)部分組成：單詞詞典和倒排文件。 單詞詞典主要是兩種存儲(chǔ)方式：哈希加鏈接和樹形結(jié)構(gòu)。索引建立方法：索引建立方法：（1）兩遍文檔遍歷在第一遍掃描文檔集合時(shí)，該方法并沒有立即開始建立索引，而是收集一些全局的統(tǒng)計(jì)信息。比如文檔集合包

6、含的文檔個(gè)數(shù)N，文檔集合內(nèi)所包含的不同單詞個(gè)數(shù)M，每個(gè)單詞在多少個(gè)文檔中出現(xiàn)過的信息DF。在獲得了上述3 類信息后，就可以知道最終索引的大小，于是在內(nèi)存中分配足夠大的空間，用來存儲(chǔ)倒排索引內(nèi)容。在第二遍掃描的時(shí)候，開始真正建立每個(gè)單詞的倒排列表信息，即對某個(gè)單詞來說，獲得包含這個(gè)單詞的每個(gè)文檔的文檔ID，以及這個(gè)單詞在文檔中的出現(xiàn)次數(shù)TF（2）排序法排序法對此做出了改進(jìn)，該方法在建立索引的過程中，始終在內(nèi)存中分配固定大小的空間，用來存放詞典信息和索引的中間結(jié)果，當(dāng)分配的空間被消耗光的時(shí)候，把中間結(jié)果寫入磁盤，清空內(nèi)存里中間結(jié)果所占空間，以用做下一輪存放索引中間結(jié)果的存儲(chǔ)區(qū)。這種方法由于只需要固

7、定大小的內(nèi)存，所以可以對任意大小的文檔集合建立索引。（3）歸并法在分配的內(nèi)存定額被消耗光時(shí)，排序法只是將中間結(jié)果寫入磁盤，而詞典信息一直在內(nèi)存中進(jìn)行維護(hù)，隨著處理的文檔越來越多，詞典里包含的詞典項(xiàng)越來越多，所以占用內(nèi)存越來越大，導(dǎo)致后期中間結(jié)果可用內(nèi)存越來越少。歸并法對此做出了改進(jìn)，即每次將內(nèi)存中數(shù)據(jù)寫入磁盤時(shí)，包括詞典在內(nèi)的所有中間結(jié)果信息都被寫入磁盤，這樣內(nèi)存所有內(nèi)容都可以被清空，后續(xù)建立索引可以使用全部的定額內(nèi)存。索引的更新策略完全重建再合并策略原地更新策略混合策略3. 內(nèi)容檢索內(nèi)容檢索內(nèi)容檢索模型是搜索引擎排序的理論基礎(chǔ)，用來計(jì)算網(wǎng)頁與查詢的相關(guān)性。A.常用的檢索模型布爾模型向量空間模

8、型概率模型語言模型機(jī)器學(xué)習(xí)排序檢索系統(tǒng)評價(jià)指標(biāo)精確率：搜索結(jié)果中相關(guān)文檔的比例 A/(A+B)召回率：結(jié)果中相關(guān)文檔占所有相關(guān)文檔的比例 A/(A+C)P10 : 前10個(gè)結(jié)果中相關(guān)查詢的數(shù)目MAP指標(biāo) ：對返回結(jié)果按次序加權(quán),權(quán)值為排名的倒數(shù)查詢相關(guān)查詢相關(guān)查詢無關(guān)查詢無關(guān)在搜索結(jié)果內(nèi)AB不在搜索結(jié)果CD4. 鏈接分析鏈接分析搜索引擎在查找能夠滿足用戶請求的網(wǎng)頁時(shí)，主要考慮兩方面的因素：一方面是用戶發(fā)出的查詢與網(wǎng)頁內(nèi)容的內(nèi)容相似性得分，即網(wǎng)頁和查詢的相關(guān)性；另一方面就是通過鏈接分析方法計(jì)算獲得的得分，即網(wǎng)頁的重要性。鏈接分析就是通過網(wǎng)絡(luò)的鏈接結(jié)構(gòu)去獲取網(wǎng)頁重要性的一類方法。鏈接分析算法很多，

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

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

11、常發(fā)現(xiàn)模型異常發(fā)現(xiàn)模型也是一個(gè)高度抽象化的算法框架模型，其基本假設(shè)認(rèn)為：作弊網(wǎng)頁必然存在有異于正常網(wǎng)頁的特征，這種特征有可能是內(nèi)容方面的，也有可能是鏈接關(guān)系方面的。而制定具體算法的流程往往是先找到一些作弊的網(wǎng)頁集合，分析出其異常特征有哪些，然后利用這些異常特征來識別作弊網(wǎng)頁。5.2 分析用戶意圖準(zhǔn)確分析用戶的搜索意圖是目前搜索引擎的重點(diǎn)研究方向。用戶的意圖可以初略分為導(dǎo)航型，信息型，事物型搜索日志是挖掘用戶意圖的重要數(shù)據(jù)來源點(diǎn)擊圖：用戶在查詢結(jié)果出來后點(diǎn)擊的鏈接可能更是他希望的結(jié)果查詢回話：用戶在短時(shí)間的連續(xù)查詢詞存在相關(guān)性查詢圖：構(gòu)建用戶查詢之間的結(jié)構(gòu)關(guān)系用戶在搜索時(shí)可能想不到合適的搜索詞，或者關(guān)鍵詞輸入錯(cuò)誤，這時(shí)候就需要幫助用戶澄清搜索意圖。常見的方法是：相關(guān)搜索，查詢糾錯(cuò)5.3 網(wǎng)頁去重網(wǎng)頁去重經(jīng)過統(tǒng)計(jì)，網(wǎng)絡(luò)中有相當(dāng)比例的網(wǎng)頁是近似相同或者完全相同的，高達(dá)29%。如果搜索返回大量相似網(wǎng)頁，顯然降低了搜索結(jié)果質(zhì)量。針對這一現(xiàn)象，網(wǎng)頁去重就顯得十分必要。網(wǎng)頁去重一般是在爬蟲抓取到網(wǎng)頁后，對其