搜索引擎的工作原理是什么？
作者：雷博 什么是搜索引擎 搜索引擎是一個幫助用戶搜索他們需要內(nèi)容的計算機程序。換一種說法，搜索引擎把計算機中存儲的信息與用戶的信息需求(information need)相匹配，并把匹配的結(jié)果展示出來。 舉個例子：大黃想賣腎買個iphone裝逼，就查一下價格。它在google的搜索框里輸入了”iphone 6 售價“，點擊搜索按鈕。這里大黃的關鍵詞“iphone 6 售價”就是他的信息需求。Google在展示出搜索結(jié)果的那零點幾秒之間，它的程序在巨大的數(shù)據(jù)庫里按照關鍵字進行了查找，終于計算出所有關于Iphone價格的網(wǎng)頁。 網(wǎng)絡爬蟲 互聯(lián)網(wǎng)上的信息存儲在無數(shù)個服務器上，任何搜索引擎要想回答用戶的搜索，首先要把網(wǎng)頁存在自己本地的服務器上，這靠的就是網(wǎng)絡爬蟲。它不停的向各種網(wǎng)站發(fā)送請求，將所得到的網(wǎng)頁存儲起來。那么它怎么知道往哪發(fā)送請求呢？通常的做法是利用網(wǎng)頁之間的鏈接從一個網(wǎng)頁出發(fā)，提取出指向其他頁面的鏈接，把它們當成將下次要請求的對象，不停重復這個過程。有很多細節(jié)要被考慮。比如避免循環(huán)鏈接的網(wǎng)頁；解析網(wǎng)頁文檔（通常是html格式，但也有很多其他格式）提取里邊的鏈接；當鏈接無法打開時對錯誤進行處理等。 其次，如何高效的爬取數(shù)據(jù)也是一個很大的挑戰(zhàn)。比如需要有成千上萬個爬蟲程序同時爬取數(shù)據(jù)，高效的將數(shù)據(jù)存儲起來以便之后分析等。這種分布式程序的實現(xiàn)是一個相當大的工程。 出于安全等因素考慮，很多網(wǎng)絡服務器都有反惡意爬蟲的功能。盡管他們所采取策略各不相同，共同點是他們目標就是盡量只響應真人用戶的請求。但搜索引擎爬蟲通常不需要擔心這一點，因為大部分網(wǎng)站都希望提高自己的搜索排名，歡迎搜索引擎爬蟲到訪。通常Google等搜索引擎都和網(wǎng)站之間有約定，比如在網(wǎng)頁上加個特殊標簽，告訴爬蟲這個網(wǎng)頁是什么類型，包含什么信息等，以便幫助爬蟲更好的獲取該網(wǎng)頁內(nèi)容。 好了，幾乎整個互聯(lián)網(wǎng)的內(nèi)容都被Google的爬蟲獲得了。Google怎么幫大黃找到賣iphone 6的網(wǎng)頁呢？ 索引 互聯(lián)網(wǎng)上的數(shù)據(jù)千千萬萬，大海撈針的搜索怎么就這么快？難道Google發(fā)明了什么逆天科技嗎？其實不是。這都要歸功于搜索引擎的索引了。 如果要你在一本書里找一個關鍵詞，應該怎么找？假設有充足的時間，最暴力的方法就是從頭到尾看一遍，最后總能找到關鍵詞所在的位置。不過這是不是太麻煩了？有更好的方法嗎？ 有。索引就是幫助程序進行快速查找的。大家都用過新華字典。字典前邊的按照偏旁部首查字的部分就是索引。搜索引擎也一樣。這里要介紹第一個最重要的數(shù)據(jù)結(jié)構(gòu)：反轉(zhuǎn)列表（inverted list）。 搜索引擎所擁有的文檔中出現(xiàn)的每一個單詞都擁有一個反轉(zhuǎn)列表。它記錄了這個單詞在多少文檔中出現(xiàn)，分別是哪些文檔，每個文檔分部出現(xiàn)多少次，分別出現(xiàn)在什么位置等信息。比如Apple這個詞出現(xiàn)在文檔1，7，19，34，102。其中文檔1中出現(xiàn)了3次，分別在位置20，105，700。這樣當搜索Apple時，Goolge就不用遍歷所有的文檔，只需要查找每個單詞對應的反轉(zhuǎn)列表就可以知道這個詞在哪里出現(xiàn)了。每一個網(wǎng)絡文檔不僅只有文本信息。它還可能包括URL, 文件名，引用等部分。為了提高搜索質(zhì)量，搜索引擎需要對文檔的不同部分分別處理，構(gòu)造反轉(zhuǎn)列表。每一部分的單詞都要被加入到這個詞屬于此部分的反轉(zhuǎn)列表里。 索引除了反轉(zhuǎn)列表還包含了很多各種數(shù)據(jù)結(jié)構(gòu)。比如維護文檔ID到實際文檔的Document Manager，存儲每個單詞屬性信息的Term Dictionary，存儲文檔屬性的數(shù)據(jù)結(jié)構(gòu)等等。 創(chuàng)建索引是個巨大工程。首先是對文檔進行解析和處理?；ヂ?lián)網(wǎng)上的文檔格式各種各樣，對每一種格式的文檔都要有一個對應的解析器程序，這樣才能忽略各種奇怪符號，提取出有用內(nèi)容。每一個解析器的實現(xiàn)都是一個繁瑣且困難的任務。對于解析后的干凈文檔，許多重要的自然語言處理算法就要派上用場。以英語為例，需要進行分詞（tokenzation，將一句話分割成一個個單詞），詞干提?。╯temming， 將文本中出現(xiàn)的單詞還原成它的原型），part-of-speech tagging（識別單詞在一句話中的詞性），創(chuàng)建n-gram模型等操作。因為此文為目的是掃盲，就不深入講解每個操作了。此外還需要識別文檔中的命名實體(named entity)，比如將“iphone 6”作為一個詞，而不是 “iphone” 一個， “6” 一個。上述操作生成的信息都要存儲下來。這樣構(gòu)造反轉(zhuǎn)列表時就可以知道每個單詞出現(xiàn)的位置，出現(xiàn)個數(shù)等信息。 索引生成程序的一個設計目標就是高效。因此它被盡可能地運行在多個機器上。對于每個機器來說，索引程序一邊掃描輸入文檔，一邊在內(nèi)存中更新索引的數(shù)據(jù)結(jié)構(gòu)。當內(nèi)存中得數(shù)據(jù)大小超過一定閥值時，這些內(nèi)容被作為一個塊(block)一次性寫入硬盤文件中。當所有文檔掃描結(jié)束后這些塊會再被合并成一個大的反轉(zhuǎn)文件(Inverted file)。因為每一個塊都是排好序的，合并操作是線性的復雜度。因為數(shù)據(jù)量太大，Google為了快速處理，發(fā)明了 MapReduce。它現(xiàn)在是一個應用非常廣泛的分布式計算框架。MapReduce把一個大的任務分割成許多小任務，并下發(fā)給多個Mapper程序，Mapper計算好的中間結(jié)果會發(fā)給多個Reducer程序繼續(xù)處理，得到最終結(jié)果。這個計算模型允許成千上萬臺機器同時運算，從而極大提高了運算效率。 反轉(zhuǎn)文件要和訪問機制(access mechanism)一起可以工作。訪問機制定義了如何通過一個單詞找到它所對應的反轉(zhuǎn)列表。大概可以使用兩種數(shù)據(jù)結(jié)構(gòu)：b-tree 或 Hash table。 為了提高效率，索引中的單詞和文檔都用整形的ID表示而不是字符串。單詞ID和字符串的映射由Term Dictionary維護，它還存儲了關于此單詞一些其他信息，比如在多少文件中出現(xiàn)(document frequency)，在文檔中出現(xiàn)概率(inverse document frequency = total document count／document frequency)。這些信息在搜索排序中會提供關鍵信息。 互聯(lián)網(wǎng)內(nèi)容是不停變化的，這必然導致索引不停被更新。然而建立好的索引中，各個單詞的反轉(zhuǎn)列表是緊密的拼接在一起的，這使得更新變得非常困難。通常搜索引擎會積攢一批文件后才進行索引的更改，并且把索引分成靜態(tài)和動態(tài)兩個部分。程序把所有更改都寫入動態(tài)部分，并且周期性地將動態(tài)部分合并進靜態(tài)部分中。搜索時，動態(tài)和靜態(tài)部分都會被訪問。當從索引中刪除一個文檔時，這個文檔中出現(xiàn)的詞對應的反轉(zhuǎn)列表都會被修改，開銷極大。于是程序加入了“刪除列表（delete lists）”來記錄所有被刪除的文檔。搜索時會查詢刪除列表來把已經(jīng)被刪除的文檔從搜索結(jié)果中移除。當刪除列表足夠大，垃圾回收機制會被觸發(fā)，重新生成索引。 搜索 有了索引，就可以快速找到所需內(nèi)容了。前邊說過搜索引擎根據(jù)用戶的信息需求查找匹配的內(nèi)容。信息需求來自于用戶輸入。如何理解它有很大學問。簡單的說，大黃的搜索詞“iphone 6 售價”會被解析成一個樹形結(jié)構(gòu)：葉子節(jié)點就是一個個關鍵詞，非葉子結(jié)點是搜索引擎自己定義的查詢運算符（query operator）。比如大黃的輸入可以被解析成 AND(TERM(iphone 6)，TERM(售價) ) 這里要說第到二個重要的數(shù)據(jù)結(jié)構(gòu)：分數(shù)列表（score list）。每個單詞同樣對應一個。它記錄這個單詞所出現(xiàn)的文檔擁有的分數(shù)。為方便計算，分數(shù)通常是一個大于零小于一的浮點數(shù)。在后邊介紹結(jié)果排序時會講如何給文檔打分。 在進行搜索時，TERM運算符查詢出每一個單詞對應的反轉(zhuǎn)列表；AND運算符將每個反轉(zhuǎn)列表轉(zhuǎn)換成分數(shù)列表，并且對于每個分數(shù)列表中的文檔id集合進行求交集操作，結(jié)果是一個新的分數(shù)列表，每個文檔對應的分數(shù)是該文檔在各個輸入的分數(shù)列表中分數(shù)的乘積。 除了AND, TERM運算符，搜索引擎一般還會定義許多其他運算符，比如OR用來對文檔集合求并集操作； NEAR(term1, term2)用來查找所有term1 和 term2 相鄰的文檔, WINDOW(5, term1, term2)用來查找term1 和 term2 相隔不超過5個單詞的文檔，WEIGHTED_SUM運算符來對分數(shù)進行加權(quán)和操作等。如何定義搜索運算符取決于不同的搜索引擎。 搜索引擎用把用戶輸入的搜索字符進行一些類似于創(chuàng)建索引時對文本的處理（tokenization, stemming, stopword removal, entity recognition），然后生成解析樹。這個過程使用了各種技巧，常見的有： multiple representation model： 即一個文檔的標題， URL，主體等部分被分別處理。比如大黃的搜索會被轉(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(售價), 0.2, TITLE(售價), 0.7, BODY(售價)) ) 或者 WEIGHTED_SUM( 0.1, AND(URL(iphone 6), URL(售價)), 0.2, AND(TITLE(iphone 6), TITLE(售價)), 0.7, BODY(iphone 6), BODY(售價)), ) Sequential Dependency Model：將搜索詞按照以下三個不同方法生成解析樹，最后把他們加權(quán)求和。三個方法分別是：
最后加權(quán)求和： WEIGHTED_SUM(0.7, AND(“iphone 6”， 售價), 0.2, NEAR(“Iphone 6”， 售價), 0.1 WINDOW(8, “iphone 6”, 售價) ) 也可以把以上兩種方法生成的解析樹再進行加權(quán)求和來生成最終結(jié)果。 搜索引擎也可能會根據(jù)查詢的類型選擇不同的方法生成解析樹。具體如何解析是沒有定論的，加權(quán)操作中每部分的權(quán)重也沒有定論。這需要根據(jù)歷史數(shù)據(jù)做大量實驗最終確定參數(shù)?？傊?，以上技巧最終目標是幫助搜索引擎更好理解用戶的信息需求，以便查找出更高質(zhì)量的文檔。 排序 到這兒終于該說搜索引擎怎么給文檔打分了。根據(jù)Google的論文Brin & Page, WWW 1998，他們計算文檔最終分數(shù)是
其中 信息檢索得分（Information Retrieval Score） 假設互聯(lián)網(wǎng)里的所有網(wǎng)頁都包含有用的信息，且它們之間沒有引用，這時打分唯一的依據(jù)就是這篇文章是否和查詢相關。信息檢索得分就是這種相關性的衡量。 有很多理論來計算IRscore。比如向量空間（Vector space retrieval model），概率理論（Probabilistic retrieval models），或統(tǒng)計語言模型（Statistical language models）等。這里不細說具體每個理論是怎么回事。關鍵要記住的是，它們的公式都和一個簡單算法的公式非常接近。那就是tf-idf （term frequency–inverse document frequency）。 每個單詞－文檔組合都有一個tf-idf值。tf 表示此文檔中這個單詞出現(xiàn)的次數(shù)；df表示含有這個單詞的文檔的數(shù)量。通常如果一個單詞在文檔中出現(xiàn)次數(shù)越多說明這個文檔與這個單詞相關性越大。但是有的單詞太常用了，比如英文里“the”，“a”，或者中文里“這里”，“就是”等，在任何一個文檔中都會大量出現(xiàn)。idf表示一個文檔含有此單詞的概率的倒數(shù)，就是用來消除常用詞干擾的。如果一個詞在越多的文檔中出現(xiàn)，說明這個詞對于某一個文檔的重要性就越低。算法的公式是：
搜索引擎如果只考慮tfidf分數(shù)，會非常容易被欺騙。因為tfidf只考慮網(wǎng)頁和搜索詞之前的相關性，而不考慮網(wǎng)頁本身的內(nèi)容質(zhì)量。比如老中醫(yī)可以在自己的網(wǎng)頁上堆滿治療X病的關鍵詞，這樣當有人搜索相關內(nèi)容時tfidf就會給出高分。PageRank就是專門禰補這個缺陷的。 PageRank 分數(shù) PageRank是Google創(chuàng)始人Larry Page 和 Sergey Brin 當年在斯坦福讀博期間搞出來的一個算法。憑借此算法他們創(chuàng)立Google，迎娶白富美走向人生巔峰的故事早已成為佳話。它的作用就是對網(wǎng)頁的重要性打分。假設有網(wǎng)頁A和B，A有鏈接指向B。如果A是一個重要網(wǎng)頁，B的重要性也被提升。這種機制可靠的懲罰了沒有被別的鏈接指向的欺詐網(wǎng)站。 以下內(nèi)容涉及數(shù)學知識，不感興趣可以跳過。 PageRank是按照以下規(guī)則計算分數(shù)的。假設有n個網(wǎng)頁，他們的PageRank分數(shù)用n*1矩陣
其中n*n矩陣M的每一個元素 對
這個迭代公式是有意義的。對于網(wǎng)頁i，它的 PageRank得分為：
因為 搜索引擎將查詢結(jié)果中的文檔按照得分排序，最終給大黃顯示出所有賣 iphone 6 的網(wǎng)頁。 總結(jié) 搜索引擎是各種高深的算法和復雜的系統(tǒng)實現(xiàn)的完美結(jié)合，每一部分都在系統(tǒng)里起到關鍵作用。 洋洋灑灑寫了這么多也只觸及到皮毛，還有很多內(nèi)容沒有提及。比如搜索引擎如何評估搜索結(jié)果好壞，如何進行個性化搜索，如何進行分類搜索等。以后有機會再分別總結(jié)。 本文大部分知識來自卡內(nèi)基梅隆大學“當年”的課程11-641 Search Engine and Web Mining，說“當年”是聽說現(xiàn)在這個課已經(jīng)被拆分成兩個搜索引擎和文本挖掘兩個課了。不過授課內(nèi)容肯定更加豐富了。最后感謝Jamie Callan 教授和 Yiming Yang教授的教導！ 該文章在 2025/2/24 15:37:53 編輯過 |
關鍵字查詢
相關文章
正在查詢... 
|
400 186 1886
equation.png)
equation.png)
equation.png)
equation.png)
equation.png)
equation.png)
是由M和E的轉(zhuǎn)置矩陣加權(quán)組成的，所以注意上式中equation.png)
展開后對應的矩陣M的值是equation.png)
。equation.png)
是經(jīng)過平滑后的從網(wǎng)頁t跳轉(zhuǎn)到網(wǎng)頁i的概率。這樣即使t沒有連接指向i，它的跳轉(zhuǎn)概率也是equation.png)
。這個公式表示，網(wǎng)頁i的PageRank得分由所有其他網(wǎng)頁的PageRank得分分別乘以其跳轉(zhuǎn)至網(wǎng)頁i的概率之和得到。k是迭代次數(shù)?？梢宰C明當k足夠大時equation.png)
會收斂至一個定值。