久久99九九99九九99精品,歪歪视频在线播放无遮挡,久草网首页

搜索引擎的工作原理是什么？

當前位置：點晴教程→閑情逸致 →『微信好文』

admin

2016年5月4日 7:33 本文熱度 7667

作者：雷博

什么是搜索引擎

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

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

網絡爬蟲

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

其次，如何高效的爬取數據也是一個很大的挑戰。比如需要有成千上萬個爬蟲程序同時爬取數據，高效的將數據存儲起來以便之后分析等。這種分布式程序的實現是一個相當大的工程。

出于安全等因素考慮，很多網絡服務器都有反惡意爬蟲的功能。盡管他們所采取策略各不相同，共同點是他們目標就是盡量只響應真人用戶的請求。但搜索引擎爬蟲通常不需要擔心這一點，因為大部分網站都希望提高自己的搜索排名，歡迎搜索引擎爬蟲到訪。通常Google等搜索引擎都和網站之間有約定，比如在網頁上加個特殊標簽，告訴爬蟲這個網頁是什么類型，包含什么信息等，以便幫助爬蟲更好的獲取該網頁內容。

好了，幾乎整個互聯網的內容都被Google的爬蟲獲得了。Google怎么幫大黃找到賣iphone 6的網頁呢？

索引

互聯網上的數據千千萬萬，大海撈針的搜索怎么就這么快？難道Google發明了什么逆天科技嗎？其實不是。這都要歸功于搜索引擎的索引了。

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

有。索引就是幫助程序進行快速查找的。大家都用過新華字典。字典前邊的按照偏旁部首查字的部分就是索引。搜索引擎也一樣。這里要介紹第一個最重要的數據結構：反轉列表（inverted list）。

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

索引除了反轉列表還包含了很多各種數據結構。比如維護文檔ID到實際文檔的Document Manager，存儲每個單詞屬性信息的Term Dictionary，存儲文檔屬性的數據結構等等。

創建索引是個巨大工程。首先是對文檔進行解析和處理。互聯網上的文檔格式各種各樣，對每一種格式的文檔都要有一個對應的解析器程序，這樣才能忽略各種奇怪符號，提取出有用內容。每一個解析器的實現都是一個繁瑣且困難的任務。對于解析后的干凈文檔，許多重要的自然語言處理算法就要派上用場。以英語為例，需要進行分詞（tokenzation，將一句話分割成一個個單詞），詞干提取（stemming，將文本中出現的單詞還原成它的原型），part-of-speech tagging（識別單詞在一句話中的詞性），創建n-gram模型等操作。因為此文為目的是掃盲，就不深入講解每個操作了。此外還需要識別文檔中的命名實體(named entity)，比如將“iphone 6”作為一個詞，而不是 “iphone” 一個， “6” 一個。上述操作生成的信息都要存儲下來。這樣構造反轉列表時就可以知道每個單詞出現的位置，出現個數等信息。

索引生成程序的一個設計目標就是高效。因此它被盡可能地運行在多個機器上。對于每個機器來說，索引程序一邊掃描輸入文檔，一邊在內存中更新索引的數據結構。當內存中得數據大小超過一定閥值時，這些內容被作為一個塊(block)一次性寫入硬盤文件中。當所有文檔掃描結束后這些塊會再被合并成一個大的反轉文件(Inverted file)。因為每一個塊都是排好序的，合并操作是線性的復雜度。因為數據量太大，Google為了快速處理，發明了 MapReduce。它現在是一個應用非常廣泛的分布式計算框架。MapReduce把一個大的任務分割成許多小任務，并下發給多個Mapper程序，Mapper計算好的中間結果會發給多個Reducer程序繼續處理，得到最終結果。這個計算模型允許成千上萬臺機器同時運算，從而極大提高了運算效率。

反轉文件要和訪問機制(access mechanism)一起可以工作。訪問機制定義了如何通過一個單詞找到它所對應的反轉列表。大概可以使用兩種數據結構：b-tree 或 Hash table。

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

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

搜索

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

這里要說第到二個重要的數據結構：分數列表（score list）。每個單詞同樣對應一個。它記錄這個單詞所出現的文檔擁有的分數。為方便計算，分數通常是一個大于零小于一的浮點數。在后邊介紹結果排序時會講如何給文檔打分。

在進行搜索時，TERM運算符查詢出每一個單詞對應的反轉列表；AND運算符將每個反轉列表轉換成分數列表，并且對于每個分數列表中的文檔id集合進行求交集操作，結果是一個新的分數列表，每個文檔對應的分數是該文檔在各個輸入的分數列表中分數的乘積。

除了AND, TERM運算符，搜索引擎一般還會定義許多其他運算符，比如OR用來對文檔集合求并集操作； NEAR(term1, term2)用來查找所有term1 和 term2 相鄰的文檔, WINDOW(5, term1, term2)用來查找term1 和 term2 相隔不超過5個單詞的文檔，WEIGHTED_SUM運算符來對分數進行加權和操作等。如何定義搜索運算符取決于不同的搜索引擎。

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

multiple representation model：即一個文檔的標題， URL，主體等部分被分別處理。比如大黃的搜索會被轉換成：

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：將搜索詞按照以下三個不同方法生成解析樹，最后把他們加權求和。三個方法分別是：

bag of words 匹配，即 AND(“iphone 6”，售價);
N-gram 匹配，即 NEAR(“Iphone 6”，售價)
短窗口匹配，即 WINDOW(8, “iphone 6”, 售價)

最后加權求和：

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

也可以把以上兩種方法生成的解析樹再進行加權求和來生成最終結果。

搜索引擎也可能會根據查詢的類型選擇不同的方法生成解析樹。具體如何解析是沒有定論的，加權操作中每部分的權重也沒有定論。這需要根據歷史數據做大量實驗最終確定參數。總之，以上技巧最終目標是幫助搜索引擎更好理解用戶的信息需求，以便查找出更高質量的文檔。

排序

到這兒終于該說搜索引擎怎么給文檔打分了。根據Google的論文Brin & Page, WWW 1998，他們計算文檔最終分數是

其中 $IRscore(doc, query)$ 就是文檔doc對于搜索詞query的信息檢索得分， $PageRank(doc)$ 是該文檔的 PageRank得分。在論文里他們沒有說函數f是如何實現的。

信息檢索得分（Information Retrieval Score）

假設互聯網里的所有網頁都包含有用的信息，且它們之間沒有引用，這時打分唯一的依據就是這篇文章是否和查詢相關。信息檢索得分就是這種相關性的衡量。

有很多理論來計算IRscore。比如向量空間（Vector space retrieval model），概率理論（Probabilistic retrieval models），或統計語言模型（Statistical language models）等。這里不細說具體每個理論是怎么回事。關鍵要記住的是，它們的公式都和一個簡單算法的公式非常接近。那就是tf-idf （term frequency–inverse document frequency）。

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

搜索引擎如果只考慮tfidf分數，會非常容易被欺騙。因為tfidf只考慮網頁和搜索詞之前的相關性，而不考慮網頁本身的內容質量。比如老中醫可以在自己的網頁上堆滿治療X病的關鍵詞，這樣當有人搜索相關內容時tfidf就會給出高分。PageRank就是專門禰補這個缺陷的。

PageRank 分數

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

以下內容涉及數學知識，不感興趣可以跳過。

PageRank是按照以下規則計算分數的。假設有n個網頁，他們的PageRank分數用n*1矩陣 $\vec{r}$ 表示。PageRank定義了一個n*n矩陣 $B_{pr}$ 表示網頁間的連接關系。

其中n*n矩陣M的每一個元素 $m_{ij}$ 表示從網頁i跳轉到網頁j的概率。比如網頁i有10個鏈接，其中2個指向網頁j，那么 $m_{ij}$ 的值就是0.2。E是一個常量，它是一個n*n矩陣且每個元素都為 $\frac{1}{n}$ 。 $\alpha$ 用來將 $M^T$ 和加權求和。一般設為0.1~0.2之間。

對 $\vec{r}$ 的求值是一個迭代過程：

這個迭代公式是有意義的。對于網頁i，它的 PageRank得分為：

因為是由M和E的轉置矩陣加權組成的，所以注意上式中展開后對應的矩陣M的值是。是經過平滑后的從網頁t跳轉到網頁i的概率。這樣即使t沒有連接指向i，它的跳轉概率也是。這個公式表示，網頁i的PageRank得分由所有其他網頁的PageRank得分分別乘以其跳轉至網頁i的概率之和得到。k是迭代次數。可以證明當k足夠大時會收斂至一個定值。