什么是搜索引擎

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

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

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

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

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

　　

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

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

　　索引

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

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

　　有。索引就是幫助程序進(jìn)行快速查找的。大家都用過新華字典。字典前邊的按照偏旁部首查字的部分就是索引。搜索引擎也一樣。這里要介紹第一個(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ì)于解析后的干凈文檔，許多重要的自然語言處理算法就要派上用場(chǎng)。以英語為例，需要進(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ǔ)下來。這樣構(gòu)造反轉(zhuǎn)列表時(shí)就可以知道每個(gè)單詞出現(xiàn)的位置，出現(xiàn)個(gè)數(shù)等信息。

　　索引生成程序的一個(gè)設(shè)計(jì)目標(biāo)就是高效。因此它被盡可能地運(yùn)行在多個(gè)機(jī)器上。對(duì)于每個(gè)機(jī)器來說，索引程序一邊掃描輸入文檔，一邊在內(nèi)存中更新索引的數(shù)據(jù)結(jié)構(gòu)。當(dāng)內(nèi)存中得數(shù)據(jù)大小超過一定閥值時(shí)，這些內(nèi)容被作為一個(gè)塊(block)一次性寫入硬盤文件中。當(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ì)算模型允許成千上萬臺(tái)機(jī)器同時(shí)運(yùn)算，從而極大提高了運(yùn)算效率。

　　

　　反轉(zhuǎn)文件要和訪問機(jī)制(access mechanism)一起可以工作。訪問機(jī)制定義了如何通過一個(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è)部分。程序把所有更改都寫入動(dòng)態(tài)部分，并且周期性地將動(dòng)態(tài)部分合并進(jìn)靜態(tài)部分中。搜索時(shí)，動(dòng)態(tài)和靜態(tài)部分都會(huì)被訪問。當(dāng)從索引中刪除一個(gè)文檔時(shí)，這個(gè)文檔中出現(xiàn)的詞對(duì)應(yīng)的反轉(zhuǎn)列表都會(huì)被修改，開銷極大。于是程序加入了“刪除列表（delete lists）”來記錄所有被刪除的文檔。搜索時(shí)會(huì)查詢刪除列表來把已經(jīng)被刪除的文檔從搜索結(jié)果中移除。當(dāng)刪除列表足夠大，垃圾回收機(jī)制會(huì)被觸發(fā)，重新生成索引。

　　搜索

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

　　這里要說第到二個(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用來對(duì)文檔集合求并集操作； NEAR(term1, term2)用來查找所有term1 和 term2 相鄰的文檔, WINDOW(5, term1, term2)用來查找term1 和 term2 相隔不超過5個(gè)單詞的文檔，WEIGHTED_SUM運(yùn)算符來對(duì)分?jǐn)?shù)進(jìn)行加權(quán)和操作等。如何定義搜索運(yùn)算符取決于不同的搜索引擎。

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

　　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è)不同方法生成解析樹，最后把他們加權(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à)) )

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

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

　　排序

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

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

　　信息檢索得分（Information Retrieval Score）

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

　　有很多理論來計(jì)算IRscore。比如向量空間（Vector space retrieval model），概率理論（Probabilistic retrieval models），或統(tǒng)計(jì)語言模型（Statistical language models）等。這里不細(xì)說具體每個(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ù)越多說明這個(gè)文檔與這個(gè)單詞相關(guān)性越大。但是有的單詞太常用了，比如英文里“the”，“a”，或者中文里“這里”，“就是”等，在任何一個(gè)文檔中都會(huì)大量出現(xiàn)。idf表示一個(gè)文檔含有此單詞的概率的倒數(shù)，就是用來消除常用詞干擾的。如果一個(gè)詞在越多的文檔中出現(xiàn)，說明這個(gè)詞對(duì)于某一個(gè)文檔的重要性就越低。算法的公式是：

　　

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

　　PageRank 分?jǐn)?shù)

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

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

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

　　

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

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

　　

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

　　

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

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

　　總結(jié)

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

　　本文轉(zhuǎn)自知乎，原文地址：https://www.zhihu.com/question/19937854

　　AD：如有侵權(quán)請(qǐng)聯(lián)系刪除