搜索引擎是一個(gè)幫助用戶搜索他們需要內(nèi)容的計(jì)算機(jī)程序。換一種說(shuō)法，搜索引擎把計(jì)算機(jī)中存儲(chǔ)的信息與用戶的信息需求(information need)相匹配，并把匹配的結(jié)果展示出來(lái)。

舉個(gè)例子：大黃想賣腎買個(gè)iphone裝逼，就查一下價(jià)格。它在google的搜索框里輸入了”iphone 6 售價(jià)“，點(diǎn)擊搜索按鈕。這里大黃的關(guān)鍵詞“iphone 6 售價(jià)”就是他的信息需求。Google在展示出搜索結(jié)果的那零點(diǎn)幾秒之間，它的程序在巨大的數(shù)據(jù)庫(kù)里按照關(guān)鍵字進(jìn)行了查找，終于計(jì)算出所有關(guān)于Iphone價(jià)格的網(wǎng)頁(yè)。

網(wǎng)絡(luò)爬蟲(chóng)

互聯(lián)網(wǎng)上的信息存儲(chǔ)在無(wú)數(shù)個(gè)服務(wù)器上，任何搜索引擎要想回答用戶的搜索，首先要把網(wǎng)頁(yè)存在自己本地的服務(wù)器上，這靠的就是網(wǎng)絡(luò)爬蟲(chóng)。它不停的向各種網(wǎng)站發(fā)送請(qǐng)求，將所得到的網(wǎng)頁(yè)存儲(chǔ)起來(lái)。那么它怎么知道往哪發(fā)送請(qǐng)求呢？通常的做法是利用網(wǎng)頁(yè)之間的鏈接從一個(gè)網(wǎng)頁(yè)出發(fā)，提取出指向其他頁(yè)面的鏈接，把它們當(dāng)成將下次要請(qǐng)求的對(duì)象，不停重復(fù)這個(gè)過(guò)程。有很多細(xì)節(jié)要被考慮。比如避免循環(huán)鏈接的網(wǎng)頁(yè)；解析網(wǎng)頁(yè)文檔（通常是html格式，但也有很多其他格式）提取里邊的鏈接；當(dāng)鏈接無(wú)法打開(kāi)時(shí)對(duì)錯(cuò)誤進(jìn)行處理等。

其次，如何高效的爬取數(shù)據(jù)也是一個(gè)很大的挑戰(zhàn)。比如需要有成千上萬(wàn)個(gè)爬蟲(chóng)程序同時(shí)爬取數(shù)據(jù)，高效的將數(shù)據(jù)存儲(chǔ)起來(lái)以便之后分析等。這種分布式程序的實(shí)現(xiàn)是一個(gè)相當(dāng)大的工程。

出于安全等因素考慮，很多網(wǎng)絡(luò)服務(wù)器都有反惡意爬蟲(chóng)的功能。盡管他們所采取策略各不相同，共同點(diǎn)是他們目標(biāo)就是盡量只響應(yīng)真人用戶的請(qǐng)求。但搜索引擎爬蟲(chóng)通常不需要擔(dān)心這一點(diǎn)，因?yàn)榇蟛糠志W(wǎng)站都希望提高自己的搜索排名，歡迎搜索引擎爬蟲(chóng)到訪。通常Google等搜索引擎都和網(wǎng)站之間有約定，比如在網(wǎng)頁(yè)上加個(gè)特殊標(biāo)簽，告訴爬蟲(chóng)這個(gè)網(wǎng)頁(yè)是什么類型，包含什么信息等，以便幫助爬蟲(chóng)更好的獲取該網(wǎng)頁(yè)內(nèi)容。

好了，幾乎整個(gè)互聯(lián)網(wǎng)的內(nèi)容都被Google的爬蟲(chóng)獲得了。Google怎么幫大黃找到賣iphone 6的網(wǎng)頁(yè)呢？

索引

互聯(lián)網(wǎng)上的數(shù)據(jù)千千萬(wàn)萬(wàn)，大海撈針的搜索怎么就這么快？難道Google發(fā)明了什么逆天科技嗎？其實(shí)不是。這都要?dú)w功于搜索引擎的索引了。

如果要你在一本書(shū)里找一個(gè)關(guān)鍵詞，應(yīng)該怎么找？假設(shè)有充足的時(shí)間，最暴力的方法就是從頭到尾看一遍，最后總能找到關(guān)鍵詞所在的位置。不過(guò)這是不是太麻煩了？有更好的方法嗎？

有。索引就是幫助程序進(jìn)行快速查找的。大家都用過(guò)新華字典。字典前邊的按照偏旁部首查字的部分就是索引。搜索引擎也一樣。這里要介紹第一個(gè)最重要的數(shù)據(jù)結(jié)構(gòu)：反轉(zhuǎn)列表（inverted list）。

搜索引擎所擁有的文檔中出現(xiàn)的每一個(gè)單詞都擁有一個(gè)反轉(zhuǎn)列表。它記錄了這個(gè)單詞在多少文檔中出現(xiàn)，分別是哪些文檔，每個(gè)文檔分部出現(xiàn)多少次，分別出現(xiàn)在什么位置等信息。比如Apple這個(gè)詞出現(xiàn)在文檔1，7，19，34，102。其中文檔1中出現(xiàn)了3次，分別在位置20，105，700。這樣當(dāng)搜索Apple時(shí)，Goolge就不用遍歷所有的文檔，只需要查找每個(gè)單詞對(duì)應(yīng)的反轉(zhuǎn)列表就可以知道這個(gè)詞在哪里出現(xiàn)了。每一個(gè)網(wǎng)絡(luò)文檔不僅只有文本信息。它還可能包括URL, 文件名，引用等部分。為了提高搜索質(zhì)量，搜索引擎需要對(duì)文檔的不同部分分別處理，構(gòu)造反轉(zhuǎn)列表。每一部分的單詞都要被加入到這個(gè)詞屬于此部分的反轉(zhuǎn)列表里。

索引除了反轉(zhuǎn)列表還包含了很多各種數(shù)據(jù)結(jié)構(gòu)。比如維護(hù)文檔ID到實(shí)際文檔的Document Manager，存儲(chǔ)每個(gè)單詞屬性信息的Term Dictionary，存儲(chǔ)文檔屬性的數(shù)據(jù)結(jié)構(gòu)等等。

創(chuàng)建索引是個(gè)巨大工程。首先是對(duì)文檔進(jìn)行解析和處理。互聯(lián)網(wǎng)上的文檔格式各種各樣，對(duì)每一種格式的文檔都要有一個(gè)對(duì)應(yīng)的解析器程序，這樣才能忽略各種奇怪符號(hào)，提取出有用內(nèi)容。每一個(gè)解析器的實(shí)現(xiàn)都是一個(gè)繁瑣且困難的任務(wù)。對(duì)于解析后的干凈文檔，許多重要的自然語(yǔ)言處理算法就要派上用場(chǎng)。以英語(yǔ)為例，需要進(jìn)行分詞（tokenzation，將一句話分割成一個(gè)個(gè)單詞），詞干提?。╯temming， 將文本中出現(xiàn)的單詞還原成它的原型），part-of-speech tagging（識(shí)別單詞在一句話中的詞性），創(chuàng)建n-gram模型等操作。因?yàn)榇宋臑槟康氖菕呙?，就不深入講解每個(gè)操作了。此外還需要識(shí)別文檔中的命名實(shí)體(named entity)，比如將“iphone 6”作為一個(gè)詞，而不是 “iphone” 一個(gè)， “6” 一個(gè)。上述操作生成的信息都要存儲(chǔ)下來(lái)。這樣構(gòu)造反轉(zhuǎn)列表時(shí)就可以知道每個(gè)單詞出現(xiàn)的位置，出現(xiàn)個(gè)數(shù)等信息。

索引生成程序的一個(gè)設(shè)計(jì)目標(biāo)就是高效。因此它被盡可能地運(yùn)行在多個(gè)機(jī)器上。對(duì)于每個(gè)機(jī)器來(lái)說(shuō)，索引程序一邊掃描輸入文檔，一邊在內(nèi)存中更新索引的數(shù)據(jù)結(jié)構(gòu)。當(dāng)內(nèi)存中得數(shù)據(jù)大小超過(guò)一定閥值時(shí)，這些內(nèi)容被作為一個(gè)塊(block)一次性寫(xiě)入硬盤(pán)文件中。當(dāng)所有文檔掃描結(jié)束后這些塊會(huì)再被合并成一個(gè)大的反轉(zhuǎn)文件(Inverted file)。因?yàn)槊恳粋€(gè)塊都是排好序的，合并操作是線性的復(fù)雜度。因?yàn)閿?shù)據(jù)量太大，Google為了快速處理，發(fā)明了 MapReduce。它現(xiàn)在是一個(gè)應(yīng)用非常廣泛的分布式計(jì)算框架。MapReduce把一個(gè)大的任務(wù)分割成許多小任務(wù)，并下發(fā)給多個(gè)Mapper程序，Mapper計(jì)算好的中間結(jié)果會(huì)發(fā)給多個(gè)Reducer程序繼續(xù)處理，得到最終結(jié)果。這個(gè)計(jì)算模型允許成千上萬(wàn)臺(tái)機(jī)器同時(shí)運(yùn)算，從而極大提高了運(yùn)算效率。

反轉(zhuǎn)文件要和訪問(wèn)機(jī)制(access mechanism)一起可以工作。訪問(wèn)機(jī)制定義了如何通過(guò)一個(gè)單詞找到它所對(duì)應(yīng)的反轉(zhuǎn)列表。大概可以使用兩種數(shù)據(jù)結(jié)構(gòu)：b-tree 或 Hash table。

為了提高效率，索引中的單詞和文檔都用整形的ID表示而不是字符串。單詞ID和字符串的映射由Term Dictionary維護(hù)，它還存儲(chǔ)了關(guān)于此單詞一些其他信息，比如在多少文件中出現(xiàn)(document frequency)，在文檔中出現(xiàn)概率(inverse document frequency = total document count／document frequency)。這些信息在搜索排序中會(huì)提供關(guān)鍵信息。

互聯(lián)網(wǎng)內(nèi)容是不停變化的，這必然導(dǎo)致索引不停被更新。然而建立好的索引中，各個(gè)單詞的反轉(zhuǎn)列表是緊密的拼接在一起的，這使得更新變得非常困難。通常搜索引擎會(huì)積攢一批文件后才進(jìn)行索引的更改，并且把索引分成靜態(tài)和動(dòng)態(tài)兩個(gè)部分。程序把所有更改都寫(xiě)入動(dòng)態(tài)部分，并且周期性地將動(dòng)態(tài)部分合并進(jìn)靜態(tài)部分中。搜索時(shí)，動(dòng)態(tài)和靜態(tài)部分都會(huì)被訪問(wèn)。當(dāng)從索引中刪除一個(gè)文檔時(shí)，這個(gè)文檔中出現(xiàn)的詞對(duì)應(yīng)的反轉(zhuǎn)列表都會(huì)被修改，開(kāi)銷極大。于是程序加入了“刪除列表（delete lists）”來(lái)記錄所有被刪除的文檔。搜索時(shí)會(huì)查詢刪除列表來(lái)把已經(jīng)被刪除的文檔從搜索結(jié)果中移除。當(dāng)刪除列表足夠大，垃圾回收機(jī)制會(huì)被觸發(fā)，重新生成索引。

搜索

有了索引，就可以快速找到所需內(nèi)容了。前邊說(shuō)過(guò)搜索引擎根據(jù)用戶的信息需求查找匹配的內(nèi)容。信息需求來(lái)自于用戶輸入。如何理解它有很大學(xué)問(wèn)。簡(jiǎn)單的說(shuō)，大黃的搜索詞“iphone 6 售價(jià)”會(huì)被解析成一個(gè)樹(shù)形結(jié)構(gòu)：葉子節(jié)點(diǎn)就是一個(gè)個(gè)關(guān)鍵詞，非葉子結(jié)點(diǎn)是搜索引擎自己定義的查詢運(yùn)算符（query operator）。比如大黃的輸入可以被解析成 AND(TERM(iphone 6)，TERM(售價(jià)) )

這里要說(shuō)第到二個(gè)重要的數(shù)據(jù)結(jié)構(gòu)：分?jǐn)?shù)列表（score list）。每個(gè)單詞同樣對(duì)應(yīng)一個(gè)。它記錄這個(gè)單詞所出現(xiàn)的文檔擁有的分?jǐn)?shù)。為方便計(jì)算，分?jǐn)?shù)通常是一個(gè)大于零小于一的浮點(diǎn)數(shù)。在后邊介紹結(jié)果排序時(shí)會(huì)講如何給文檔打分。

在進(jìn)行搜索時(shí)，TERM運(yùn)算符查詢出每一個(gè)單詞對(duì)應(yīng)的反轉(zhuǎn)列表；AND運(yùn)算符將每個(gè)反轉(zhuǎn)列表轉(zhuǎn)換成分?jǐn)?shù)列表，并且對(duì)于每個(gè)分?jǐn)?shù)列表中的文檔id集合進(jìn)行求交集操作，結(jié)果是一個(gè)新的分?jǐn)?shù)列表，每個(gè)文檔對(duì)應(yīng)的分?jǐn)?shù)是該文檔在各個(gè)輸入的分?jǐn)?shù)列表中分?jǐn)?shù)的乘積。

除了AND, TERM運(yùn)算符，搜索引擎一般還會(huì)定義許多其他運(yùn)算符，比如OR用來(lái)對(duì)文檔集合求并集操作； NEAR(term1, term2)用來(lái)查找所有term1 和 term2 相鄰的文檔, WINDOW(5, term1, term2)用來(lái)查找term1 和 term2 相隔不超過(guò)5個(gè)單詞的文檔，WEIGHTED_SUM運(yùn)算符來(lái)對(duì)分?jǐn)?shù)進(jìn)行加權(quán)和操作等。如何定義搜索運(yùn)算符取決于不同的搜索引擎。

搜索引擎用把用戶輸入的搜索字符進(jìn)行一些類似于創(chuàng)建索引時(shí)對(duì)文本的處理（tokenization, stemming, stopword removal, entity recognition），然后生成解析樹(shù)。這個(gè)過(guò)程使用了各種技巧，常見(jiàn)的有：

multiple representation model： 即一個(gè)文檔的標(biāo)題， URL，主體等部分被分別處理。比如大黃的搜索會(huì)被轉(zhuǎn)換成：

AND(

WEIGHTED_SUM(0.1, URL(iphone 6), 0.2, TITLE(iphone 6), 0.7, BODY(iphone 6)),

WEIGHTED_SUM(0.1, URL(售價(jià)), 0.2, TITLE(售價(jià)), 0.7, BODY(售價(jià)))

)

或者

WEIGHTED_SUM(

0.1, AND(URL(iphone 6), URL(售價(jià))),

0.2, AND(TITLE(iphone 6), TITLE(售價(jià))),

0.7, BODY(iphone 6), BODY(售價(jià))),

)

Sequential Dependency Model：將搜索詞按照以下三個(gè)不同方法生成解析樹(shù)，最后把他們加權(quán)求和。三個(gè)方法分別是：

• bag of words 匹配，即 AND(“iphone 6”， 售價(jià));

• N-gram 匹配，即 NEAR(“Iphone 6”， 售價(jià))

• 短窗口匹配，即 WINDOW(8, “iphone 6”, 售價(jià))

最后加權(quán)求和：

WEIGHTED_SUM(0.7, AND(“iphone 6”， 售價(jià)), 0.2, NEAR(“Iphone 6”， 售價(jià)), 0.1 WINDOW(8, “iphone 6”, 售價(jià)) )

也可以把以上兩種方法生成的解析樹(shù)再進(jìn)行加權(quán)求和來(lái)生成最終結(jié)果。

搜索引擎也可能會(huì)根據(jù)查詢的類型選擇不同的方法生成解析樹(shù)。具體如何解析是沒(méi)有定論的，加權(quán)操作中每部分的權(quán)重也沒(méi)有定論。這需要根據(jù)歷史數(shù)據(jù)做大量實(shí)驗(yàn)最終確定參數(shù)?？傊?，以上技巧最終目標(biāo)是幫助搜索引擎更好理解用戶的信息需求，以便查找出更高質(zhì)量的文檔。

排序

到這兒終于該說(shuō)搜索引擎怎么給文檔打分了。根據(jù)Google的論文Brin & Page, WWW 1998，他們計(jì)算文檔最終分?jǐn)?shù)是

其中就是文檔doc對(duì)于搜索詞query的信息檢索得分，是該文檔的 PageRank得分。在論文里他們沒(méi)有說(shuō)函數(shù)f是如何實(shí)現(xiàn)的。

信息檢索得分（Information Retrieval Score）

假設(shè)互聯(lián)網(wǎng)里的所有網(wǎng)頁(yè)都包含有用的信息，且它們之間沒(méi)有引用，這時(shí)打分唯一的依據(jù)就是這篇文章是否和查詢相關(guān)。信息檢索得分就是這種相關(guān)性的衡量。

有很多理論來(lái)計(jì)算IRscore。比如向量空間（Vector space retrieval model），概率理論（Probabilistic retrieval models），或統(tǒng)計(jì)語(yǔ)言模型（Statistical language models）等。這里不細(xì)說(shuō)具體每個(gè)理論是怎么回事。關(guān)鍵要記住的是，它們的公式都和一個(gè)簡(jiǎn)單算法的公式非常接近。那就是tf-idf （term frequency–inverse document frequency）。

每個(gè)單詞－文檔組合都有一個(gè)tf-idf值。tf 表示此文檔中這個(gè)單詞出現(xiàn)的次數(shù)；df表示含有這個(gè)單詞的文檔的數(shù)量。通常如果一個(gè)單詞在文檔中出現(xiàn)次數(shù)越多說(shuō)明這個(gè)文檔與這個(gè)單詞相關(guān)性越大。但是有的單詞太常用了，比如英文里“the”，“a”，或者中文里“這里”，“就是”等，在任何一個(gè)文檔中都會(huì)大量出現(xiàn)。idf表示一個(gè)文檔含有此單詞的概率的倒數(shù)，就是用來(lái)消除常用詞干擾的。如果一個(gè)詞在越多的文檔中出現(xiàn)，說(shuō)明這個(gè)詞對(duì)于某一個(gè)文檔的重要性就越低。算法的公式是：

搜索引擎如果只考慮tfidf分?jǐn)?shù)，會(huì)非常容易被欺騙。因?yàn)閠fidf只考慮網(wǎng)頁(yè)和搜索詞之前的相關(guān)性，而不考慮網(wǎng)頁(yè)本身的內(nèi)容質(zhì)量。比如老中醫(yī)可以在自己的網(wǎng)頁(yè)上堆滿治療X病的關(guān)鍵詞，這樣當(dāng)有人搜索相關(guān)內(nèi)容時(shí)tfidf就會(huì)給出高分。PageRank就是專門(mén)禰補(bǔ)這個(gè)缺陷的。

PageRank 分?jǐn)?shù)

PageRank是Google創(chuàng)始人Larry Page 和 Sergey Brin 當(dāng)年在斯坦福讀博期間搞出來(lái)的一個(gè)算法。憑借此算法他們創(chuàng)立Google，迎娶白富美走向人生巔峰的故事早已成為佳話。它的作用就是對(duì)網(wǎng)頁(yè)的重要性打分。假設(shè)有網(wǎng)頁(yè)A和B，A有鏈接指向B。如果A是一個(gè)重要網(wǎng)頁(yè)，B的重要性也被提升。這種機(jī)制可靠的懲罰了沒(méi)有被別的鏈接指向的欺詐網(wǎng)站。

以下內(nèi)容涉及數(shù)學(xué)知識(shí)，不感興趣可以跳過(guò)。

PageRank是按照以下規(guī)則計(jì)算分?jǐn)?shù)的。假設(shè)有n個(gè)網(wǎng)頁(yè)，他們的PageRank分?jǐn)?shù)用n*1矩陣表示。PageRank定義了一個(gè)n*n矩陣表示網(wǎng)頁(yè)間的連接關(guān)系。

其中n*n矩陣M的每一個(gè)元素表示從網(wǎng)頁(yè)i跳轉(zhuǎn)到網(wǎng)頁(yè)j的概率。比如網(wǎng)頁(yè)i有10個(gè)鏈接，其中2個(gè)指向網(wǎng)頁(yè)j，那么的值就是0.2。E是一個(gè)常量，它是一個(gè)n*n矩陣且每個(gè)元素都為。用來(lái)將和加權(quán)求和。一般設(shè)為0.1~0.2之間。

對(duì)的求值是一個(gè)迭代過(guò)程：

這個(gè)迭代公式是有意義的。對(duì)于網(wǎng)頁(yè)i，它的 PageRank得分為：

因?yàn)?b>是由M和E的轉(zhuǎn)置矩陣加權(quán)組成的，所以注意上式中展開(kāi)后對(duì)應(yīng)的矩陣M的值是。是經(jīng)過(guò)平滑后的從網(wǎng)頁(yè)t跳轉(zhuǎn)到網(wǎng)頁(yè)i的概率。這樣即使t沒(méi)有連接指向i，它的跳轉(zhuǎn)概率也是。這個(gè)公式表示，網(wǎng)頁(yè)i的PageRank得分由所有其他網(wǎng)頁(yè)的PageRank得分分別乘以其跳轉(zhuǎn)至網(wǎng)頁(yè)i的概率之和得到。k是迭代次數(shù)?？梢宰C明當(dāng)k足夠大時(shí)會(huì)收斂至一個(gè)定值。

搜索引擎將查詢結(jié)果中的文檔按照得分排序，最終給大黃顯示出所有賣 iphone 6 的網(wǎng)頁(yè)。

總結(jié)

搜索引擎是各種高深的算法和復(fù)雜的系統(tǒng)實(shí)現(xiàn)的完美結(jié)合，每一部分都在系統(tǒng)里起到關(guān)鍵作用。 洋洋灑灑寫(xiě)了這么多也只觸及到皮毛，還有很多內(nèi)容沒(méi)有提及。比如搜索引擎如何評(píng)估搜索結(jié)果好壞，如何進(jìn)行個(gè)性化搜索，如何進(jìn)行分類搜索等。以后有機(jī)會(huì)再分別總結(jié)。

本文大部分知識(shí)來(lái)自卡內(nèi)基梅隆大學(xué)“當(dāng)年”的課程11-641 Search Engine and Web Mining，說(shuō)“當(dāng)年”是聽(tīng)說(shuō)現(xiàn)在這個(gè)課已經(jīng)被拆分成兩個(gè)搜索引擎和文本挖掘兩個(gè)課了。不過(guò)授課內(nèi)容肯定更加豐富了。最后感謝Jamie Callan 教授和 Yiming Yang教授的教導(dǎo)！