淺談搜尋引擎普遍原理

--lvpei.blogcn.com，公司要做的知識分享課件摘選。

1、搜尋引擎是什麼？

搜尋引擎就是為使用者提供檢索服務的系統。

2、搜尋引擎如何為使用者提供檢索服務？

1>從網際網路上抓取網頁

利用能夠從網際網路上自動收集網頁的Spider系統程式，自動通路網際網路，并沿着任何網頁中的所有URL爬到其它網頁，（深度周遊和廣度周遊）重複這過程，并把爬過的所有網頁收集回來。

2>建立索引資料庫 

由分析索引系統程式對收集回來的網頁進行分析，提取相關網頁資訊（包括網頁所在URL、編碼類型、頁面内容包含的關鍵詞、關鍵詞位置、生成時間、大小、與其它網頁的連結關系（超鍊分析就是通過分析連結網站的多少來評價被連結的網站品質）等），根據一定的相關度算法進行大量複雜計算，得到每一個網頁針對頁面内容中及超鍊中每一個關鍵詞的相關度（或重要性），然後用這些相關資訊建立網頁索引資料庫。 

3>在索引資料庫中搜尋排序 

當使用者輸入關鍵詞搜尋後，由搜尋系統程式從網頁索引資料庫中找到符合該關鍵詞的所有相關網頁。因為所有相關網頁針對該關鍵詞的相關度早已算好，是以隻需按照現成的相關度數值排序，相關度越高，排名越靠前。 

最後，由頁面生成系統将搜尋結果的連結位址和頁面内容摘要等内容組織起來傳回給使用者。 

3、搜尋引擎與資料庫的不同？

通常比較厚的書籍後面常常附關鍵詞索引表（比如：北京：12, 34頁， 上海：3,77頁……），不是前面的目錄，它能夠幫助讀者比較快地找到相關内容的頁碼。而資料庫索引能夠大大提高查詢的速度原理也是一樣，想像一下通過書後面的索引查找的 速度要比一頁一頁地翻内容高多少倍……而索引之是以效率高，另外一個原因是它是排好序的。

在使用like查詢時，資料庫搜尋過程又變成類似于一頁頁翻書的周遊過程了，是以對于含有模糊查詢的資料庫服務來說，LIKE對性能的危害是極大的。如果是需要對多個關鍵詞進行模糊比對:like"%keywordl%" and like"%keyword2%'.其效率也就可想而知了。

是以建立一個高效搜尋系統的關鍵，是建立一個類似于書籍索引一樣的反向索引機制，将資料源(比如多篇文章)順序存儲的同時，建立另外一個排好序的關鍵詞清單，用于存儲關鍵詞=》文章映射關 系，利用這樣的映射關系索引:[關鍵詞”=>出現關鍵詞的文章編号，出現次數、位置、 出現頻率，檢索過程就是把模糊查詢變成多個可以利用索引的精确查詢的邏輯組合的過程。進而大大提高了多關鍵詞查詢的效率。

是以，全文檢索問題歸結到最後是一個排序問題。

由此可以看出模糊查詢相對資料庫的精确查詢是一個非常不确定的問題，是以大部分資料庫對全文檢索支援有限的原因。

Lucene面向全文檢索的優化在于首次索引檢索後，并不把所有的記錄（Document）具體内容讀取出來，而是隻将所有結果中比對度最高的頭

100條結果（TopDocs）的ID放到結果集緩存中并傳回，在收集結果的過程中将比對度低的結果自動過濾掉。

4、如何建立反向索引機制？

先複習一個資料結構，這個資料結構并不在Lucene中使用，但是又不得不說。

B-tree結構

B-tree（多路搜尋樹，不是二叉）是一種常見的資料結構。 　　

使用B-tree結構可以顯著減少定位記錄時所經曆的中間過程，進而加快存取速度。 　

按照翻譯,B 通常認為是Balance的簡稱.這個資料結構一般用于資料庫的索引，B-tree索引是資料庫中存取和查找檔案(稱為記錄或鍵值)的一種方法，綜合效率較高。

B-tree的特性：

1、關鍵字集合分布在整顆樹中;　2、任何一個關鍵字出現且隻出現在一個結點中; 　　

3、搜尋有可能在非葉子結點結束;　4、其搜尋性能等價于在關鍵字全集内做一次二分查找;

再介紹Lucene

Lucene是一個高性能的java全文檢索工具包.。

Lucene最核心的特征是通過特殊的倒排檔案索索引結構實作了傳統資料庫不擅長的全文索引機制，并提供了擴充接口，以友善針對不同應用的定制。

該結構及相應的生成算法如下：

　　

　　0）設有兩篇文章1和2

　　文章1的内容為：Tom lives in Guangzhou,I live in Guangzhou too.

　　文章2的内容為：He once lived in Shanghai.

　　

　　1)由于lucene是基于關鍵詞索引和查詢的，首先我們要取得這兩篇文章的關鍵詞，通常我們需要如下處理措施

　　a.我們現在有的是文章内容，即一個字元串，我們先要找出字元串中的所有單詞，即分詞。英文單詞由于用空格分隔，比較好處理。中文單詞間是連在一起的 需要特殊的分詞處理。

　　b.文章中的”in”, “once” “too”等詞沒有什麼實際意義，中文中的“的”“是”等字通常也無具體含義，這些不代表概念的詞可以過濾掉

　　c.使用者通常希望查“He”時能把含“he”，“HE”的文章也找出來，是以所有單詞需要統一大小寫。

　　d.使用者通常希望查“live”時能把含“lives”，“lived”的文章也找出來，是以需要把“lives”，“lived”還原成 “live”

　　e.文章中的标點符号通常不表示某種概念，也可以過濾掉

　　在lucene中以上措施由Analyzer類完成

　　

　　經過上面處理後

　　 文章1的所有關鍵詞為：[tom] [live] [guangzhou] [i] [live] [guangzhou]

　　 文章2的所有關鍵詞為：[he] [live] [shanghai]

　　

　　2) 有了關鍵詞後，我們就可以建立反向索引了。上面的對應關系是：“文章号”對“文章中所有關鍵詞”。反向索引把這個關系倒過來，變成：“關鍵詞”對“擁有該 關鍵詞的所有文章号”。文章1，2經過倒排後變成

　　關鍵詞 文章号

　　guangzhou 1

　　he 2

　　i 1

　　live 1,2

　　shanghai 2

　　tom 1

　　

　　通常僅知道關鍵詞在哪些文章中出現還不夠，我們還需要知道關鍵詞在文章中出現次數和出現的位置，通常有兩種位置：a)字元位置，即記錄該詞是文章中第幾個字元（優點是關鍵詞亮顯時定位快）；b)關鍵詞位置，即記錄該詞是文章中第幾個關鍵詞（優點是節約索引空間、詞組（phase）查詢 快），lucene 中記錄的就是這種位置。

　　

　　加上“出現頻率”和“出現位置”資訊後，我們的索引結構變為：

　　關鍵詞 文章号[出現頻率] 出現位置

　　guangzhou 1[2] 3，6

　　he 2[1] 1

　　i 1[1] 4

　　live 1[2],2[1] 2，5，2

　　shanghai 2[1] 3

　　tom 1[1] 1

　　

　　以live 這行為例我們說明一下該結構：live在文章1中出現了2次，文章2中出現了一次，它的出現位置為“2,5,2”這表示什麼呢？我們需要結合文章号和出現 頻率來分析，文章1中出現了2次，那麼“2,5”就表示live在文章1中出現的兩個位置，文章2中出現了一次，剩下的“2”就表示live是文章2中第 2個關鍵字。

　　

　　以上就是lucene索引結構中最核心的部分。

Lucene中沒有使用商業資料庫的b tree結構,也不是經過hash（hash算法不能找出範圍）而得。而由.tii與.tis兩個檔案組成了一種二層檔案結構。

這與Lucene采用segment index索引政策有關（動态索引，更新要快）。實際上采用的是最簡單的折半二分。

索引的更新會導緻大量的IO操作，Lucene在實作中，對此稍微有所改進：不是維護一個索引檔案，而是在擴充索引的時候不斷建立新的索引檔案，然後定期 的把這些新的小索引檔案合并到原先的大索引中（針對不同的更新政策，批次的大小可以調整），這樣在不影響檢索的效率的前提下，提高了索引的效率。

假設要查詢單詞 “live”，lucene先對詞典二分查找、找到該詞，通過指向頻率檔案的指針讀出所有文章号，然後傳回結果。詞典通常非常小，因而，整個過程的時間是 毫秒級的。

　　

　　實作時 lucene将上面三列分别作為詞典檔案（Term Dictionary）、頻率檔案(frequencies)、位置檔案 (positions)儲存。其中詞典檔案不僅儲存有每個關鍵詞，還保留了指向頻率檔案和位置檔案的指針，通過指針可以找到該關鍵字的頻率資訊和位置資訊。

　　

　　 Lucene中使用了field的概念，用于表達資訊所在位置（如标題中，文章中，url中），在建索引中，該field資訊也記錄在詞典檔案中，每個關鍵詞都有一個field資訊(因為每個關鍵字一定屬于一個或多個field)。

　　

　　為了減小索引檔案的大小，Lucene對索引還使用了壓縮技術。首先，對詞典檔案中的關鍵詞進行了壓縮，關鍵詞壓縮為<字首長度，後 綴>，例如：目前詞為“阿拉伯語”，上一個詞為“阿拉伯”，那麼“阿拉伯語”壓縮為<3，語>。其次大量用到的是對數字的壓縮，數字隻儲存與上一個值的內插補點（這樣可以減小數字的長度，進而減少儲存該數字需要的位元組數）。例如目前文章号是16389（不壓縮要用3個位元組儲存），上一文章号 是16382，壓縮後儲存7（隻用一個位元組）。

5、關于中文的切分詞問題

對于英文來說語句中單詞之間是天然通過空格分開的，但亞洲語言的中日韓文語句中的字是一個字挨一個，所有，首先要把語句中按“詞”進行索引的話，這個詞如何切分出來就是一個很大的問題。

首先，肯定不能用單個字元作(si-gram)為索引單元，否則查“上海”時，不能讓含有“海上”也比對。

但一句話 :“北京天安門”，計算機如何按照中文的語言習慣進行切分呢?

“北京 天安門” 還是“北京天安門”?讓計算機能夠按照語言習慣進 行切分，往往需要機器有一個比較豐富的詞庫才能夠比較準确的識别出語句中的單詞。

另外一個解決的辦法是采用自動切分算法:将單詞按照2元文法(bigram)方式切分出來，比如:

“北京天安門” ==>”北京 京天 天安 安門”。

這樣 ，在查詢的時候，無論是查詢”北京”還是查詢”天安門”，将查詢詞組按同樣 的規則進行切分:”北京”，”天安 安門”，多個關鍵詞之間按與”and"的關系組合，同樣能夠正确地映射到相應的索引中。這種方式對于其他亞洲語言:韓文，日文都是通用的。

基于自動切分的最大優點是沒有詞表維護成本，實作簡單，缺點是索引 效率低，但對于中小型應用來說，基于2元文法的切分還是夠用的。基于2元切分後的索引一般大小和源 檔案差不多，而對于英文，索引檔案一般隻有原檔案的30%-40%不同。

目前比較大的搜尋引擎的語言分析算法一般是基于以上2個機制的結合。

6、Lucene與solr

Lucene不是一個完整的全文索引應用，而是是一個用Java寫的全文索引引擎工具包，它可以友善的嵌入到各種應用中實作針對應用的全文索引/檢索功能。

Solr 就是應用

Solr是一個基于Lucene 庫的企業級搜尋伺服器，包含 XML/HTTP，JSON API, 高亮查詢結果，緩存，主從複制還有一個WEB管理界面。Solr運作在 Servlet容器中。

Solr和Lucene的本質差別有以下三點：搜尋伺服器，企業級和管理。

Lucene專注于搜尋底層的建設，而Solr專注于獨立的企業應用。

從資料庫讀取記錄，對要搜尋的字段分好詞，存成檔案索引，搜尋時再分詞，直接去索引查找每個詞有哪些索引後文檔。

7、介紹一個工具Luke

8、示範一個網際網路爬取RSS，利用Lucene\Solr存儲的程式

9、搜尋引擎的前沿

基于連結分析的第三代搜尋引擎呈現出以下幾點局限性：

1、一個關鍵字查詢詞對所有使用者呈現的搜尋結果均相同。但是實際上，比如一個計算

機使用者搜尋“樹”可能指資料結構，與其他使用者有很大差別。

2、Pagerank基于連結反映網頁品質的方法，隻反映了網頁制作者對于網頁品質的評

價， 并沒有反映網頁浏覽着對于網頁的評價。對于一些不善于進行連結優化的網站，雖

然内容可能很優質，但是Pagerank可能并不高。同時，一些新網 站很難在短期内提高

Pagerank，而一些擅長優化技術的網站會用大量垃圾連結作弊。

3、基于關鍵詞的搜尋方法是建立在使用者對于搜尋有明确目的，并能清晰表述這種目的

的假設上。但是實際上，使用者的搜尋引擎使用水準參差不齊；并且由于存在同義詞等現

象，同一個搜尋請求有不同的表示方法，搜尋結果也大為不同。

4、現在的圖像搜尋，視訊搜尋，音樂搜尋也都是基于關鍵字，如圖像Tag，音樂電影介

紹等，而文字對 于這些資訊的表現能力是很有限的，也不直覺。

5、并不是所有有價值的資訊都能被搜尋引擎爬取到，比如學校論壇，公司内網資料等

有價值的資料就無法被搜尋引擎檢索，這叫做Hidden Web現象；同時一些資訊需要經過

人腦的加工，這方面問答平台更能勝任。這部分不能被爬取的資訊實 際上占了人類所有

資訊的大部分。

1、個性化的搜尋。基于個人的網頁浏覽曆史，搜尋關鍵詞曆史，個人檔案資訊，使得

即使是同一個搜尋關鍵詞，也能為不同使用者呈現不同的搜尋結果。

個性化搜尋将基本解決提到的第一點局限。

2、社交搜尋大大提高網頁排序品質，其影響主要在兩方面：a,網頁浏覽者（普通用

戶） 對于網頁的評價（收藏行為，評分，舉報等）将可以作為排序的依據b,通過使用者的

社交圈推測使用者興趣，通過使用者間的不同程度信任關系為其提供不同權重的網頁排序推

薦。社交搜尋也包括問答系統，用優質的設定提高資訊的品質。

社交搜尋将基本解決提到的Pagerank和關鍵字搜尋的局限。

3、跨媒體搜尋将打通文字，圖像，聲音，視訊間的界限，使得用圖像搜圖像，用聲音

搜聲音，用圖像搜 視訊等都成為可能。

轉載于:https://www.cnblogs.com/lvpei/archive/2010/06/17/1759636.html