全文搜索引擎基礎(chǔ)

1、全文檢索那么什么叫做全文檢索呢？這要從我們生活中的數(shù)據(jù)說起。我們生活中的數(shù)據(jù)總體分為兩種：結(jié)構(gòu)化結(jié)構(gòu)化數(shù)據(jù)數(shù)據(jù)和非結(jié)構(gòu)化數(shù)據(jù)非結(jié)構(gòu)化數(shù)據(jù)。結(jié)構(gòu)化數(shù)據(jù)：結(jié)構(gòu)化數(shù)據(jù)：指具有固定格式或有限長(zhǎng)度的數(shù)據(jù)，如數(shù)據(jù)庫，元數(shù)據(jù)等。非結(jié)構(gòu)化數(shù)據(jù)：非結(jié)構(gòu)化數(shù)據(jù)：指不定長(zhǎng)或無固定格式的數(shù)據(jù)，如郵件，word文檔等。非結(jié)構(gòu)化數(shù)據(jù)又一種叫法叫全文數(shù)據(jù)非結(jié)構(gòu)化數(shù)據(jù)又一種叫法叫全文數(shù)據(jù)。全文檢索的分類按照數(shù)據(jù)的分類，搜索也分為兩種：對(duì)結(jié)構(gòu)化數(shù)據(jù)的搜索對(duì)結(jié)構(gòu)化數(shù)據(jù)的搜索：如對(duì)數(shù)據(jù)庫的搜索，用SQL語句。再如對(duì)元數(shù)據(jù)的搜索，如利用windows搜索對(duì)文件名，類型，修改時(shí)間進(jìn)行搜索等。對(duì)非結(jié)構(gòu)化數(shù)據(jù)的搜索對(duì)非結(jié)構(gòu)化數(shù)據(jù)的搜索：如

2、利用windows的搜索也可以搜索文件內(nèi)容，Linux下的grep命令，再如用Google和百度可以搜索大量?jī)?nèi)容數(shù)據(jù)。非結(jié)構(gòu)化檢索兩種方法對(duì)非結(jié)構(gòu)化數(shù)據(jù)也即對(duì)全文數(shù)據(jù)的搜索主要有兩種方法：一種是順序掃描法順序掃描法(Serial Scanning)一一種是結(jié)構(gòu)化索引定位法種是結(jié)構(gòu)化索引定位法( index location )順序掃描法順序掃描法(Serial Scanning) 所謂順序掃描，比如要找內(nèi)容包含某一個(gè)字符串的文件，就是一個(gè)文檔一個(gè)文檔的看，對(duì)于每一個(gè)文檔，從頭看到尾，如果此文檔包含此字符串，則此文檔為我們要找的文件，接著看下一個(gè)文件，直到掃描完所有的文件。如利用windows的

3、搜索也可以搜索文件內(nèi)容，只是相當(dāng)?shù)穆Ｈ绻阌幸粋€(gè)80G硬盤，如果想在上面找到一個(gè)內(nèi)容包含某字符串的文件，不花他幾個(gè)小時(shí)，怕是做不到。Linux下的grep命令也是這一種方式。大家可能覺得這種方法比較原始，但對(duì)于小數(shù)據(jù)量的文件，這種方法還是最直接，最方便的。但是對(duì)于大量的文件，這種方法就很慢了。結(jié)構(gòu)化索引定位法結(jié)構(gòu)化索引定位法( index location )將非結(jié)構(gòu)化數(shù)據(jù)中的一部分信息提取出來，重新組織，使其變得有一定結(jié)構(gòu)，然后對(duì)此有一定結(jié)構(gòu)的數(shù)據(jù)進(jìn)行搜索，從而達(dá)到搜索相對(duì)較快的目的。這部分從非結(jié)構(gòu)化數(shù)據(jù)中提取出的然后重新組織的信息，我們稱之索引索引。這種說法比較抽象，舉幾個(gè)例子就很容易明

4、白，比如字典，字典的拼音表和部首檢字表就相當(dāng)于字典的索引，對(duì)每一個(gè)字的解釋是非結(jié)構(gòu)化的，如果字典沒有音節(jié)表和部首檢字表，在茫茫辭海中找一個(gè)字只能順序掃描。然而字的某些信息可以提取出來進(jìn)行結(jié)構(gòu)化處理，比如讀音，就比較結(jié)構(gòu)化，分聲母和韻母，分別只有幾種可以一一列舉，于是將讀音拿出來按一定的順序排列，每一項(xiàng)讀音都指向此字的詳細(xì)解釋的頁數(shù)。我們搜索時(shí)按結(jié)構(gòu)化的拼音搜到讀音，然后按其指向的頁數(shù)，便可找到我們的非結(jié)構(gòu)化數(shù)據(jù)也即對(duì)字的解釋。一般的搜索引擎的兩個(gè)重要的過程全文檢索大體分兩個(gè)過程，索引創(chuàng)建索引創(chuàng)建(Indexing)和搜索索引搜索索引(Search)。索引創(chuàng)建索引創(chuàng)建：將現(xiàn)實(shí)世界中所有的結(jié)構(gòu)化和

5、非結(jié)構(gòu)化數(shù)據(jù)提取信息，創(chuàng)建索引的過程。搜索索引搜索索引：就是得到用戶的查詢請(qǐng)求，搜索創(chuàng)建的索引，然后返回結(jié)果的過程。一般的搜索引擎的兩個(gè)重要的過程 三個(gè)重要問題全文檢索存在三個(gè)重要問題：1. 索引里面究竟存些什么？索引里面究竟存些什么？(Index)2. 如何創(chuàng)建索引？如何創(chuàng)建索引？(Indexing)3. 如何對(duì)索引進(jìn)行搜索？如何對(duì)索引進(jìn)行搜索？(Search)索引里面究竟存些什索引里面究竟存些什么么-原因原因首先我們來看為什么順序掃描的速度慢：其實(shí)是由于我們想要搜索的信息和非結(jié)構(gòu)化數(shù)據(jù)中所存儲(chǔ)的信息不確定性，不一致性造成的。索引里面究竟存些什索引里面究竟存些什么么-方法方法而我們想搜索的信

6、息是哪些文件包含此字符串，也即已知字符串，欲求文件已知字符串，欲求文件，也即從字符串到文件的映射。如果索引總能夠保存從字符串到文件的映射，則會(huì)大大提高搜索速度。由于從字符串到文件的映射是文件到字符串映射的反向過程，于是保存這種信息的索引稱為反向索引反向索引。索引里面究竟存些什么索引里面究竟存些什么-分解分解1反向索引的所保存的信息一般如下：假設(shè)我的文檔集合里面有100篇文檔，為了方便表示，我們?yōu)槲臋n編號(hào)從1到100，得到下面的結(jié)構(gòu)左邊保存的是一系列字符串，稱為詞典詞典。每個(gè)字符串都指向包含此字符串的文檔(Document)鏈表，此文檔鏈表稱為倒排表倒排表(Posting List)。有了索引，

7、便使保存的信息和要搜索的信息一致，可以大大加快搜索的速度。索引里面究竟存些什么索引里面究竟存些什么-分分解解2比如說，我們要尋找既包含字符串“l(fā)ucene”又包含字符串“solr”的文檔，我們只需要以下幾步：1. 取出包含字符串“l(fā)ucene”的文檔鏈表。2. 取出包含字符串“solr”的文檔鏈表。3. 通過合并鏈表，找出既包含“l(fā)ucene”又包含“solr”的文件。索引里面究竟存些什么索引里面究竟存些什么-分分解解3全文檢索的確加快了搜索的速度，但是多了索引的過程，兩者加起來不一定比順序掃描快多少。的確，加上索引的過程，全文檢索不一定比順序掃描快，尤其是在數(shù)據(jù)量小的時(shí)候更是如此。而對(duì)一個(gè)很

8、大量的數(shù)據(jù)創(chuàng)建索引也是一個(gè)很慢的過程。然而兩者還是有區(qū)別的，順序掃描是每次都要掃描，而創(chuàng)建索引的過程僅僅需要一次，以后便是一勞永逸的了，每次搜索，創(chuàng)建索引的過程不必經(jīng)過，僅僅搜索創(chuàng)建好的索引就可以了。這也是全文搜索相對(duì)于順序掃描的優(yōu)勢(shì)之一：一次這也是全文搜索相對(duì)于順序掃描的優(yōu)勢(shì)之一：一次索引，多次使用。索引，多次使用。創(chuàng)建索創(chuàng)建索引引-搞些文檔搞些文檔第一步：一些要索引的原文檔第一步：一些要索引的原文檔(Document)。為了方便說明索引創(chuàng)建過程，這里特意用兩個(gè)文件為例：文件一：Students should be allowed to go out with their friends,

9、but not allowed to drink beer.文件二：My friend Jerry went to school to see his students but found them drunk which is not allowed.創(chuàng)建索引創(chuàng)建索引-將將原文檔傳給分次組件原文檔傳給分次組件(Tokenizer)分詞組件分詞組件(Tokenizer)會(huì)做以下幾件事情會(huì)做以下幾件事情(此過程稱為此過程稱為Tokenize)：1. 將文檔分成一個(gè)一個(gè)單獨(dú)的單詞。將文檔分成一個(gè)一個(gè)單獨(dú)的單詞。2. 去除標(biāo)點(diǎn)符號(hào)。去除標(biāo)點(diǎn)符號(hào)。3. 去除停詞去除停詞(Stop word)。所謂停詞

10、(Stop word)就是一種語言中最普通的一些單詞，由于沒有特別的意義，因而大多數(shù)情況下不能成為搜索的關(guān)鍵詞，因而創(chuàng)建索引時(shí)，這種詞會(huì)被去掉而減少索引的大小。英語中挺詞(Stop word)如：“the”,“a”，“this”等。對(duì)于每一種語言的分詞組件(Tokenizer)，都有一個(gè)停詞(stop word)集合。 經(jīng)過分詞經(jīng)過分詞(Tokenizer)后得到的結(jié)果稱為詞元后得到的結(jié)果稱為詞元(Token)。在我們的例子中，便得到以下詞元(Token)：“Students”，“allowed”，“go”，“their”，“friends”，“allowed”，“drink”，“beer”，

11、“My”，“friend”，“Jerry”，“went”，“school”，“see”，“his”，“students”，“found”，“them”，“drunk”，“allowed”。創(chuàng)建索引創(chuàng)建索引-將將得到的詞元得到的詞元(Token)傳傳給語言處理組件給語言處理組件(Linguistic Processor)語言處理組件(linguistic processor)主要是對(duì)得到的詞元(Token)做一些同語言相關(guān)的處理。對(duì)于英語，語言處理組件對(duì)于英語，語言處理組件(Linguistic Processor)一般做以下幾點(diǎn)：一般做以下幾點(diǎn)：1. 變?yōu)樾懽優(yōu)樾?Lowercase)。2

12、. 將單詞縮減為詞根形式，如將單詞縮減為詞根形式，如“cars”到到“car”等。這種操作稱為：等。這種操作稱為：stemming。3. 將單詞轉(zhuǎn)變?yōu)樵~根形式，如將單詞轉(zhuǎn)變?yōu)樵~根形式，如“drove”到到“drive”等。這種操作稱為：等。這種操作稱為：lemmatization。創(chuàng)建索引創(chuàng)建索引- Stemming 和和 lemmatization的異同的異同相同之處：Stemming和lemmatization都要使詞匯成為詞根形式。兩者的方式不同：Stemming采用的是“縮減”的方式：“cars”到“car”，“driving”到“drive”。Lemmatization采用的是“轉(zhuǎn)變

13、”的方式：“drove”到“drove”，“driving”到“drive”。兩者的算法不同：Stemming主要是采取某種固定的算法來做這種縮減，如去除“s”，去除“ing”加“e”，將“ational”變?yōu)椤癮te”，將“tional”變?yōu)椤皌ion”。Lemmatization主要是采用保存某種字典的方式做這種轉(zhuǎn)變。比如字典中有“driving”到“drive”，“drove”到“drive”，“am, is, are”到“be”的映射，做轉(zhuǎn)變時(shí)，只要查字典就可以了。Stemming和lemmatization不是互斥關(guān)系，是有交集的，有的詞利用這兩種方式都能達(dá)到相同的轉(zhuǎn)換。創(chuàng)建索引創(chuàng)建

14、索引-語語言處理組件言處理組件(linguistic processor)的結(jié)果稱為詞的結(jié)果稱為詞(Term)在我們的例子中，經(jīng)過語言處理，得到的詞(Term)如下：“student”，“allow”，“go”，“their”，“friend”，“allow”，“drink”，“beer”，“my”，“friend”，“jerry”，“go”，“school”，“see”，“his”，“student”，“find”，“them”，“drink”，“allow”。 也正是因?yàn)橛姓Z言處理的步驟，才能使搜索drove，而drive也能被搜索出來。創(chuàng)建索引創(chuàng)建索引-將將得到的詞得到的詞(Term)傳

15、傳給索引組件給索引組件(Indexer)第一：利用得到的詞(Term)創(chuàng)建一個(gè)字典。創(chuàng)建索引創(chuàng)建索引-將將得到的詞得到的詞(Term)傳給索傳給索引組件引組件(Indexer)對(duì)字典按字對(duì)字典按字母母順順序進(jìn)行排序序進(jìn)行排序創(chuàng)建索引創(chuàng)建索引-合合并相同的詞并相同的詞(Term)成為成為文檔倒排文檔倒排(Posting List)鏈表。鏈表。 可以使用算法索引-二分法把字串的排序按照checksum的值進(jìn)行二分法排序，可以快速定位字串的入口； 更多的二分法，更多的索引，加快定位速度；把字串的表單有序地排列，可以快速地定位字串的文檔。分詞不一定是單詞，也可能是短語。為復(fù)雜短語建立二次的索引。如何對(duì)

16、索引進(jìn)行搜如何對(duì)索引進(jìn)行搜索索如果僅僅只有一個(gè)或十個(gè)文檔包含我們查詢的字符串，我們的確找到了。然而如果結(jié)果有一千個(gè)，甚至成千上萬個(gè)呢？那個(gè)又是您最想要的文件呢？這要回到我們第三個(gè)問題：如何對(duì)索引進(jìn)行搜索？如何對(duì)索引進(jìn)行搜索如何對(duì)索引進(jìn)行搜索第一，查詢語句的分析；第二，字串在文檔中的權(quán)重；第三，輸出有權(quán)重的list；對(duì)索引進(jìn)行搜對(duì)索引進(jìn)行搜索索-次數(shù)次數(shù)權(quán)重計(jì)算詞的權(quán)重(term weight)有兩個(gè)參數(shù)：第一個(gè)是詞(Term)，第二個(gè)是文檔(Document)。影響一個(gè)詞(Term)在一篇文檔中的重要性主要有兩個(gè)因素：Term Frequency (tf)：即此Term在此文檔中出現(xiàn)了多少次。

17、tf 越大說明越重要。Document Frequency (df)：即有多少文檔包含次Term。df 越大說明越不重要。對(duì)索引進(jìn)行搜索對(duì)索引進(jìn)行搜索-次數(shù)次數(shù)權(quán)重 對(duì)索引進(jìn)行搜索對(duì)索引進(jìn)行搜索-使用使用權(quán)重以下為舉例：第一，記錄被點(diǎn)擊的次數(shù)；第二，記錄被查看的時(shí)間；第三，文檔產(chǎn)生的時(shí)間；流程圖 搜索過程總結(jié)1. 索引過程：索引過程：1) 有一系列被索引文件有一系列被索引文件2) 被索引文件經(jīng)過語法分析和語言處理形成一系列詞被索引文件經(jīng)過語法分析和語言處理形成一系列詞(Term)。3) 經(jīng)過索引創(chuàng)建形成詞典和反向索引表。經(jīng)過索引創(chuàng)建形成詞典和反向索引表。4) 通過索引存儲(chǔ)將索引寫入硬盤。通過索引存儲(chǔ)將索引寫入硬盤。2. 搜索過程：搜索過程：a) 用戶輸入查詢語句。用戶輸入查詢語句。b) 對(duì)查詢語句