1、搜索引擎的算法及工作原理搜索引擎算法及工作原理（Google）C1爬行和抓?。核阉饕嬷┲胪ㄟ^(guò)跟蹤鏈接訪問(wèn)頁(yè)面，獲取頁(yè)面HTML代碼存入數(shù)據(jù)庫(kù)。2預(yù)處理：搜索引擎對(duì)抓取來(lái)的頁(yè)面數(shù)據(jù)文字進(jìn)行文字提取、中文分詞、索引等處理，以備排名程序調(diào)用。3排名：用戶輸入關(guān)鍵字后，排名調(diào)用索引庫(kù)數(shù)據(jù)，計(jì)算相關(guān)性，然后按一定格式生成搜索結(jié)果頁(yè)面。 ONTENTS搜索引擎算法及工作原理（Google）C搜索引擎的工作的過(guò)程非常復(fù)雜，而簡(jiǎn)單的講搜索引擎的工作過(guò)程大體可以分成三個(gè)階段。爬行和抓取爬行和抓取 完成數(shù)據(jù)收集任務(wù)。搜索引擎用來(lái)爬行和訪問(wèn)頁(yè)面的程序被稱為蜘蛛(spider)，也稱為機(jī)器人(bot)。跟蹤鏈接為了

2、抓取網(wǎng)上盡量多的頁(yè)面，搜索引擎蜘蛛會(huì)跟蹤頁(yè)面上的鏈接，從一個(gè)頁(yè)面爬到下一個(gè)頁(yè)面，就好像蜘蛛在蜘蛛網(wǎng)上爬行那樣，這也就是搜索引擎蜘蛛這個(gè)名稱的由來(lái)。最簡(jiǎn)單的爬行遍歷策略分為兩種，一是深度優(yōu)先，二是廣度優(yōu)先。深度優(yōu)先搜索深度優(yōu)先搜索就是在搜索樹(shù)的每一層始終先只擴(kuò)展一個(gè)子節(jié)點(diǎn)，不斷地向縱深前進(jìn)直到不能再前進(jìn)(到達(dá)葉子節(jié)點(diǎn)或受到深度限制)時(shí)，才從當(dāng)前節(jié)點(diǎn)返回到上一級(jí)節(jié)點(diǎn)，沿另一方向又繼續(xù)前進(jìn)。這種方法的搜索樹(shù)是從樹(shù)根開(kāi)始一枝一枝逐漸形成的。深度優(yōu)先搜索亦稱為縱向搜索。由于一個(gè)有解的問(wèn)題樹(shù)可能含有無(wú)窮分枝，深度優(yōu)先搜索如果誤入無(wú)窮分枝(即深度無(wú)限)，則不可能找到目標(biāo)節(jié)點(diǎn)。所以，深度優(yōu)先搜索策略是不完備的

3、。另外，應(yīng)用此策略得到的解不一定是最佳解(最短路徑)。廣度優(yōu)先搜索在深度優(yōu)先搜索算法中，是深度越大的結(jié)點(diǎn)越先得到擴(kuò)展。如果在搜索中把算法改為按結(jié)點(diǎn)的層次進(jìn)行搜索， 本層的結(jié)點(diǎn)沒(méi)有搜索處理完時(shí)，不能對(duì)下層結(jié)點(diǎn)進(jìn)行處理，即深度越小的結(jié)點(diǎn)越先得到擴(kuò)展，也就是說(shuō)先產(chǎn)生 的結(jié)點(diǎn)先得以擴(kuò)展處理，這種搜索算法稱為廣度優(yōu)先搜索法。預(yù)處理 “預(yù)處理”也被簡(jiǎn)稱為“索引”，因?yàn)樗饕穷A(yù)處理最主要的步驟。 搜索引擎蜘蛛抓取的原始頁(yè)面，并不能直接用于查詢排名處理。搜索引擎數(shù)據(jù)庫(kù)中的頁(yè)面數(shù)都在數(shù)萬(wàn)億級(jí)別以上，用戶輸入搜索詞后，靠排名程序?qū)崟r(shí)對(duì)這么多頁(yè)面分析相關(guān)性，計(jì)算量太大，不可能在一兩秒內(nèi)返回排名結(jié)果。因此抓取來(lái)的頁(yè)面

4、必須經(jīng)過(guò)預(yù)處理，為最后的查詢排名做好準(zhǔn)備。 和爬行抓取一樣，預(yù)處理也是在后臺(tái)提前完成的，用戶搜索時(shí)感覺(jué)不到這個(gè)過(guò)程。 1.提取文字：搜索引擎預(yù)處理首先要做的就是從HTML文件中去除標(biāo)簽、程序，提取出可以用于排名處理的網(wǎng)頁(yè)面文字內(nèi)容。 2.中文分詞：搜索引擎存儲(chǔ)和處理頁(yè)面及用戶搜索都是以詞為基礎(chǔ)的。中文詞與詞之間沒(méi)有任何分隔符，搜索引擎必須首先分辨哪幾個(gè)字組成一個(gè)詞，哪些字本身就是一 個(gè)詞。比如“減肥方法”將被分詞為“減肥”和“方法”兩個(gè)詞。 3.去停止詞：無(wú)論是英文還是中文，頁(yè)面內(nèi)容中都會(huì)有一些出現(xiàn)頻率很 高，卻對(duì)內(nèi)容沒(méi)有任何影響的詞，助詞，感嘆詞，副詞或介詞。 這些詞被稱為停止詞，因?yàn)樗鼈儗?duì)

5、頁(yè)面的主要意思沒(méi)什么影響。英文中的常見(jiàn)停止詞有the，a，an，to，of等。 4.消除噪聲：絕 大部分頁(yè)面上還有一部分內(nèi)容對(duì)頁(yè)面主題也沒(méi)有什么貢獻(xiàn)，比如導(dǎo)航條、廣告等。這些區(qū)塊都屬于噪聲。搜索引擎需要識(shí)別并消除這些噪聲，排名時(shí)不使用噪聲內(nèi)容。 5.去重：在進(jìn)行索引前還需要識(shí)別和刪除重復(fù)內(nèi)容，這個(gè)過(guò)程就稱為“去 重”。 6.正向索引 7.倒排索引 8.鏈接關(guān)系計(jì)算：Google PR值就是這種鏈接關(guān)系的最主要體現(xiàn)之一。 9.特殊文件處理：目前的搜索引擎還不能處理圖片、視頻、Flash這類非文字內(nèi)容，也不能執(zhí)行腳本和程序。對(duì)圖片、視頻內(nèi)容的排名還往往是依據(jù)與之相關(guān)的文字內(nèi)容。PR的兩個(gè)比喻模型P

6、R值全稱為PageRank(網(wǎng)頁(yè)級(jí)別)，PR值是Google用于標(biāo)識(shí)網(wǎng)頁(yè)的等級(jí)、重要性、網(wǎng)站的好壞的重要標(biāo)準(zhǔn)之一。級(jí)別從0到10級(jí)為滿分。PR值越高說(shuō)明該網(wǎng)頁(yè)越受歡迎。關(guān)于PR有兩個(gè)著名的比喻。一個(gè)比喻是投票。鏈接就像民主投票一樣，A頁(yè)面鏈接到B頁(yè)面，就意味著A頁(yè)面對(duì)B頁(yè)面投了一票，使得B頁(yè)面的重要性提高。同時(shí)，A頁(yè)面本身的PR。值決定了A所能投出去的投票力，PR值越高的頁(yè)面，投出的票也更重要。在這個(gè)意義上，傳統(tǒng)基于關(guān)鍵詞匹配的算法是看頁(yè)面自己說(shuō)頁(yè)面內(nèi)容是什么，基于鏈接的PR則是看別人怎么評(píng)價(jià)一個(gè)頁(yè)面。第二個(gè)比喻是隨機(jī)沖浪比喻。假設(shè)一個(gè)訪問(wèn)者從一個(gè)頁(yè)面開(kāi)始，不停地隨機(jī)點(diǎn)擊鏈接，訪問(wèn)下一個(gè)頁(yè)面。有時(shí)候這個(gè)用戶感到無(wú)聊了，不再點(diǎn)擊鏈接，就隨機(jī)跳到了另外一個(gè)網(wǎng)址，再次開(kāi)始不停地向下點(diǎn)擊。所謂PR。值也就是一個(gè)頁(yè)面在這種隨機(jī)沖浪訪問(wèn)中被訪問(wèn)到的概率。一個(gè)頁(yè)面導(dǎo)入鏈接越多，被訪問(wèn)到的概率也越高，因此PR值也越高。 排名 經(jīng)過(guò)搜索