--在公司做的知識分享課件。

--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、跨媒體搜索將打通文字，圖像，聲音，視頻間的界限，使得用圖像搜圖像，用聲音
搜聲音，用圖像搜 視頻等都成為可能。