1、搜索引擎的自然語言分詞前言：計(jì)算機(jī)就像小孩子一樣，雖然什么都不懂，什么都不會(huì)，但只要耐心教導(dǎo)，他可以做的很出色，以下由天搜科技內(nèi)部員工分享整理。上一節(jié)我們分享了單詞的識別，這一節(jié)要分享的就是更加有趣也更加復(fù)雜的自然語言分詞。顧名思義，分詞就是將一句句子分成一個(gè)一個(gè)的單詞。但是各國的語言都不一樣，比如在英語中，單詞一般是用空格或者其他標(biāo)點(diǎn)符號隔開，這種語種的分詞相對比較簡單，只需要用空格來分割字符串。但是像中文，日文等等類似的語種，單詞之間是沒有任何分割的標(biāo)記，因此在分詞的過程中就有點(diǎn)難度。下面就以中文為例子，其他語言也類似。比如有一句句子：我們都喜歡玩全文搜索引擎。那么分詞的模式就有多種了，這

2、里筆者只介紹最常用的兩種一.智能模式分詞后：我們都喜歡玩全文搜索引擎。二.最細(xì)顆粒模式分詞后：我我們都喜歡玩全文搜索全文搜索引擎搜索引擎全文搜索引擎。但是分詞后我們發(fā)現(xiàn)，有很多沒有意思的單詞，比如上句中的“都”，“玩”等等副詞或者動(dòng)詞等等，當(dāng)然還有標(biāo)點(diǎn)符號。因此智能模式下我們期望是分成我們喜歡全文搜索引擎這三個(gè)詞，而不需要那么多無用的單詞。經(jīng)過上面的分詞，相信讀者很容易就能夠發(fā)現(xiàn)，智能模式是以最長單詞為分割限度，而且不回退的分割模式。而相反最細(xì)顆粒模式就是以最小單詞為限度，并逐一遞增的分割模式。比如“全文搜索引擎”在智能模式下，就是一個(gè)單詞全文搜索引擎,而在最細(xì)顆粒模式下可以分割成全文搜索全文

3、搜索引擎搜索引擎全文搜索引擎這么多個(gè)單詞。經(jīng)驗(yàn)告訴筆者，智能模式的使用范圍更廣，因?yàn)樗阉鞯木瓤梢愿訙?zhǔn)確。需要說明的是，這兩個(gè)模式在筆者通過程序?qū)崿F(xiàn)后，它們的分割時(shí)間基本持平，智能模式略快。OK,下面開始介紹整個(gè)分詞的算法與數(shù)據(jù)結(jié)構(gòu)。同樣的,開發(fā)環(huán)境還是Linux+C+EcipseCDT首先先介紹算法，由于要兼容智能模式與最細(xì)顆粒模式，在算法上，筆者采用的是著名的AC算法，全稱叫Aho-CorasicK也稱有窮自動(dòng)機(jī)類似上一節(jié)分享的Trie算法，AC算法也是在內(nèi)存中建立單詞庫，不同的是，它不僅僅可以做到單詞的識別，還可以做到字符串的多模式匹配，也就是筆者說的分詞。AC算法在Trie算法的基礎(chǔ)

4、上，添加了失敗轉(zhuǎn)換的特性。下面通過圖來了解AC算法的奧妙之處。比如我們有單詞：全文，全文搜索，全文搜索引擎，搜索引擎，分詞引擎，中文分詞，分詞。那么通過建立ac樹就如下所示通過上一節(jié)中的trie介紹，相信一看就可以明白了。打x代表單詞，只是與trie不同的是，每個(gè)節(jié)點(diǎn)增加了“虛線”（由于篇幅，沒有全部畫）這條虛線就是ac算法的奧妙，叫做失敗跳轉(zhuǎn)。即在進(jìn)行模式匹配的時(shí)候，一旦匹配失敗，就不繼續(xù)往下，而是跳轉(zhuǎn)到失敗指針?biāo)赶虻墓?jié)點(diǎn)，然后繼續(xù)匹配，所以稱他為自動(dòng)機(jī)。但是并不是所有的幾點(diǎn)的失敗指針都是有效地址，也有可能是NULL一旦出現(xiàn)NULL就條轉(zhuǎn)回root。所以又稱他有有窮自動(dòng)機(jī)，而不是無窮自動(dòng)機(jī)

5、。那么這條虛線，也就是失敗跳轉(zhuǎn)指針，就有一個(gè)比較嚴(yán)格的要求。1 .必須指向其他的路徑的節(jié)點(diǎn)。（如果指向自身所在的路徑，那就死循環(huán)了，這里的路徑，指從當(dāng)前節(jié)點(diǎn)返回到root的路徑）2 .指向的節(jié)點(diǎn)，從節(jié)點(diǎn)開始到root所形成的字符串必須是當(dāng)前節(jié)點(diǎn)到root所形成的字符串的最大子申，也就是深度最大。舉個(gè)例子:全文搜索引擎中的“擎”節(jié)點(diǎn)，的失敗指針指向的是“搜索引擎”中的“擎”，因?yàn)椤八阉饕妗笔恰叭乃阉饕妗敝械淖畲笞钟茫ǖ剐颍?在比如，“中文分詞”中的“詞”的失敗指針?biāo)髦赶虻木褪恰胺衷~引擎”中的“詞”。一次類推。如果找不到合適的失敗跳轉(zhuǎn)節(jié)點(diǎn)，則全部指向root,或者為NULL比如“分詞引擎”中

6、的“詞”節(jié)點(diǎn)，就沒有合適他的失敗節(jié)點(diǎn)，所以就跳轉(zhuǎn)到root或者NULL接下來開始討論如何分詞。比如我們有一句句子叫“我們都喜歡玩全文搜索引擎和分詞”。搜先要討論的就是智能模式的分詞。智能模式不需要用到失敗指針。只需要順著邊往下走，直到走到葉子節(jié)點(diǎn)，也就是最長的單詞。如果能夠順利走到葉子節(jié)點(diǎn)，那么就直接截取單詞，并回到root,繼續(xù)匹配。若無法走到葉子節(jié)點(diǎn)，則從當(dāng)欠節(jié)點(diǎn)往回退，直到找到最長的單詞。舉個(gè)例子，比如句子”全文搜索引擎的分享”。可以順利走到節(jié)點(diǎn)“擎”，則分出單詞全文搜索引擎,剩下“的分享”，繼續(xù)從root開始遞歸匹配。因此匹配的路徑就是“全”，“文”->“搜”->“索”-&

7、gt;“引"->“擎"->“root”->”白r.又比如句子”全文搜索引言的講解”。走到“弓廠節(jié)點(diǎn)就無法繼續(xù)了，因此從引開始往回退，找到最長單詞全文搜索,因此分出單詞全文搜索,剩下的“引言的講解”繼續(xù)回到root繼續(xù)匹配。若在回退的過程當(dāng)中，沒有找到單詞，則認(rèn)為該字符串是無效字符用，直接廢棄！因此匹配的路徑就是“全”，“文”->“搜”->“索”->“引”->“索”->“root”->“引”.因此只要循環(huán)或者遞歸，就可以分出句子中的全部單詞（這里的單詞必須存在于我們建立的ac詞庫當(dāng)中）。下面介紹更加有趣的最細(xì)顆粒模式最細(xì)顆

8、粒模式是建立在智能模式的基礎(chǔ)上的。在智能模式中，一旦匹配失敗，則往回退直到找到單詞，分出單詞為止。而最細(xì)顆粒模式，一旦匹配失敗，并不需要回退找單詞，而是直接跳轉(zhuǎn)到失敗指針?biāo)髦赶虻墓?jié)點(diǎn)，繼續(xù)匹配，并搜集在匹配過程中經(jīng)過的路徑的所有單詞（指打上x的節(jié)點(diǎn)）。舉個(gè)例子比如句子”全文搜索引擎的分享”當(dāng)走到“擎”節(jié)點(diǎn)，整個(gè)匹配的路徑就已經(jīng)搜集的3個(gè)單詞全文全文搜索全文搜索引擎，但是“的”匹配失敗，則立即跳轉(zhuǎn)到失敗指針?biāo)髦赶虻墓?jié)點(diǎn)“搜索引擎”中的“擎”，則又搜集到單詞搜索引擎。所以整個(gè)的匹配路徑就是->“索”->從結(jié)果看這種匹配算法，看似有回退，其實(shí)并沒有回退，而且可以把句子中的單詞盡可能的分出

9、來。但是這種模式的分詞，可能會(huì)破壞句子的結(jié)構(gòu)或者本意。比如句子”全文搜索引擎”，如果詞庫不是很正確的話，通過最細(xì)顆粒模式，可能就會(huì)分出索引這樣的單詞，但是通過句子的本意并不是要表達(dá)索引的意思，而是要表達(dá)搜索和引擎的意思。也因此筆者才說，經(jīng)驗(yàn)告訴我們，智能模式的使用范圍可能相對廣一些，因?yàn)樗鼘τ谒阉鞯木瓤赡軙?huì)高一些。下面還是通過程序來驗(yàn)證分詞的效果首先是數(shù)據(jù)結(jié)構(gòu)和方法定義/* ac.h* Createdon:Aug28,2013* Author:sean* /#ifndefac_H_#defineac_H_#include<stdio.h>#include<stdlib.h&

10、gt;#include<wchar.h>#include"datatype.h/#defineDEBUG/*ac樹節(jié)點(diǎn)*/typedefstructAcNodewchar_tcharacter;boolisword;structAcNode*children;longchildrenCount;structAcNode*failure;structAcNode*parent;AcNode;/字符/是否是單詞節(jié)點(diǎn)/子節(jié)點(diǎn)數(shù)組字節(jié)點(diǎn)數(shù)量/失敗轉(zhuǎn)向節(jié)點(diǎn)/父節(jié)點(diǎn)/* 初始化ac樹，建立詞庫搜索樹* paramdic* /AcNode*ac_init(FILE*dic);詞庫字典文

11、件/*二分查找，返回目標(biāo)元素的地址，不存在返回NULL*/AcNode*ac_bin_search(AcNode*arr,intlength,wchar_tcharacter);/*獲取單詞，從指定節(jié)點(diǎn)反向到根節(jié)點(diǎn)*/voidac_getword(AcNode*node,wchar_t*word);/*獲取節(jié)點(diǎn)最近的單詞，返回節(jié)點(diǎn)與單詞的距離return成功返回回退距離，沒有單詞，返回-1*/intac_get_latest_word(AcNode*node,wchar_t*word);/*判斷字符串是不是單詞*/boolac_is_word(AcNode*root,wchar_t*word)

12、;#ifdefDEBUG/*打印ac樹paramrootac樹*/voidac_print(AcNode*root);#endif#endif/*ac_H_*/* analyzer.h* Createdon:Sep3,2013* Author:sean* /#ifndefANALYZER_H_#defineANALYZER_H_#include<stdio.h>#include<stdlib.h>#include<wchar.h>#include"ac.h"#include"trie.h"#include"s

13、ynonym.h"/* 分詞結(jié)果單詞節(jié)點(diǎn)* /單詞字符串/下一個(gè)節(jié)點(diǎn)地址typedefstructWordwchar_t*word;structWord*next;Word;/*分詞* paramdic* paramstop* paramtxt* paramsmart顆粒分詞詞庫字典同義詞字典分析文本是否使用智能分詞，true-智能分詞，false-最細(xì)*/voidanalyze(AcNode*dic,SynonymNode*synonym,wchar_t*txt,boolsmart);#endif/*ANALYZER_H_*/由于篇幅，有興趣的讀者自行實(shí)現(xiàn)了下面看看程序的運(yùn)行結(jié)果，

14、整個(gè)ac詞庫采用IKAnalyzer的默認(rèn)詞庫，大概30萬個(gè)單詞intmain()(setlocale(LC_ALL,"zh_CN.utf8");char*dic_path="/home/sean/Desktop/word.dic0"FILE*fp=fopen(dic_path,"r");AcNode*ac=ac_init(fp);fclose(fp);/準(zhǔn)備大文本FILE*tmp=fopen("/home/sean/Desktop/essay.txt0","r");wchar_tessay10

15、24*1024=L'0'wchar_tline1024*100=L'0'while(fgetws(line,1024*100,tmp)!=NULL)intlen=wcslen(line);if(len>0)wcscat(essay,line);wmemset(line,L'0',1024*100);printf("%lsn",essay);fclose(tmp);printf("分詞后>n");printf("startanalyzing.n");structtimevalt

16、ime_start,time_stop;doubletime_pass;gettimeofday(&time_start,NULL);analyze(ac,synonym,映們都喜歡玩全文搜索引擎",1);/analyze(ac,NULL,essay,1);printf("n");analyze(ac,synonym,映們都喜歡玩全文搜索引擎哦",0);/analyze(ac,synonym,essay,0);gettimeofday(&time_stop,NULL);time_pass=(double)time_stop.tv_sec-

17、(double)time_start.tv_sec)*1000000+(double)time_stop.tv_usec-(double)time_start.tv_usec;printf("ncosts%lfn",time_pass);一:ISConsoleS3±Problems<terruinated>searchengineQ/CfApplicationksac電/c_workspac9/s&an±engir/Debjg/search®nq例后二T_一二二二一二一二Astartanalyzing.,【碰們11毛立搜索引

18、SI【1我幻H喜歡11全文1【全文搜索全文慢索引擎搜索田單索引costs64.B66G80可以看到，第一行是智能模式，第二行是最細(xì)顆粒模式的分詞，整個(gè)分詞的時(shí)間是64微妙，因?yàn)樵趀clipse下開發(fā)，c語言的打印速度比較慢，因此如果不打印的話，時(shí)間大概在40微秒，可見分詞的速度相當(dāng)快。下面試試相對比較大的文本，文件大小是5K的文本文件曰canssle為（2Prblemcktrrminjled?searchen4inBApplkdlbnl/home/ud/MXkipace/L-WwIu0au/MJfCheHirw/DebLJ/sEJfcheri4n（3/11/119:19PMJ惺文搜索引堂是廣疣度用的主丸搜索引攀.國附建電WoqlR國內(nèi)工儲署名的百度、模技尋.它們從工聯(lián)同星取小T網(wǎng)帖的醋只：以網(wǎng)W文字為主）專用丟件用M的記承.蚊一文的小利質(zhì)序旭需段赤濘工未弼眄不同.全支投竄引笨力分為防夷.一改翻糖豈已內(nèi)樓案程序（Iritfaxw）.能稱“JMTf