作者：肖波

個(gè)人博客：http://blog.csdn.net/eaglet

2007/5 南京

這段時(shí)間通過(guò)研究目前在互聯(lián)網(wǎng)上可以搜索到的中文分詞算法，感覺(jué)很難找到既快又準(zhǔn)的分詞方法，通過(guò)幾天時(shí)間的研究，我終于找到了一種快速且較準(zhǔn)確的中文分詞方法?，F(xiàn)在回過(guò)頭來(lái)想想，覺(jué)得其實(shí)問(wèn)題并不很復(fù)雜，對(duì)于一般應(yīng)用，我覺(jué)得這個(gè)算法應(yīng)該基本夠用了，當(dāng)然目前沒(méi)有一種方法可以達(dá)到100%的分詞準(zhǔn)確度，這個(gè)算法也是一樣。對(duì)于實(shí)際應(yīng)用往往需要在效率和準(zhǔn)確度上做個(gè)折中，當(dāng)然對(duì)技術(shù)的追求是無(wú)止境的，我也將繼續(xù)努力，爭(zhēng)取在后續(xù)版本中進(jìn)一步提高準(zhǔn)確度，并維持現(xiàn)有效率。

基本技術(shù)指標(biāo)

分詞準(zhǔn)確度:90%以上(只是自己統(tǒng)計(jì)了一下，有待專家的權(quán)威評(píng)測(cè))

處理速度: 600KBytes/s (P4 3.0G)

和互聯(lián)網(wǎng)上幾個(gè)比較流行的中文分詞方法的比較

和SharpICTCLAS的比較

提到中文分詞，就不能不提到計(jì)算所開(kāi)發(fā)的ICTCLAS 中文分詞系統(tǒng)，這個(gè)系統(tǒng)采用一些語(yǔ)義分析的方法以提高分詞的準(zhǔn)確度。看了它的算法，感覺(jué)確實(shí)有很多值得學(xué)習(xí)的地方，只是算法相對(duì)復(fù)雜，維護(hù)時(shí)除了要維護(hù)詞表還要維護(hù)詞的關(guān)系，當(dāng)然復(fù)雜也有復(fù)雜的好處，對(duì)于如下句子：“請(qǐng)把手抬高一點(diǎn)兒”，比較互聯(lián)網(wǎng)上我所找到的幾個(gè)算法（包括我的算法），只有ICTCLAS可以正確分詞。

分詞速度：

ICTCLAS 的分詞速度為31.5Kbytes/s 由于沒(méi)有實(shí)際去測(cè)，只能引用其代碼中寫(xiě)的數(shù)據(jù)。這個(gè)速度比我的算法慢將近20倍。

我用了河北理工大學(xué)經(jīng)管學(xué)院呂震宇老師的SharpICTCLAS V1.0進(jìn)行了對(duì)比，可能是呂震宇老師還沒(méi)有來(lái)得及對(duì)效率進(jìn)行優(yōu)化，這個(gè)版本的分詞效率較底，每秒鐘大概在4000-6000字節(jié)，比我的算法要慢100多倍。相信SharpICTCLAS 的后續(xù)版本效率會(huì)有提高。

準(zhǔn)確度：

用SharpICTCLAS V1.0 版本對(duì)一些有歧異的句子進(jìn)行分詞，發(fā)現(xiàn)有的句子我的算法可以較好的處理，但SharpICTCLAS不能得到正確的結(jié)果。如“長(zhǎng)春市長(zhǎng)春節(jié)致詞”我的算法分析為：長(zhǎng)春/市長(zhǎng)/春節(jié)/致詞, SharpICTCLAS分析為：長(zhǎng)春市/長(zhǎng)/春節(jié)/致詞/，這個(gè)錯(cuò)誤可能并不是SharpICTCLAS的算法缺陷，可能只是V1.0版本提供的訓(xùn)練集不充分造成的，是不是算法目前我還沒(méi)有仔細(xì)研究。

SharpICTCLAS 對(duì)于一些需要根據(jù)語(yǔ)義來(lái)分析的語(yǔ)句如上面提到的“請(qǐng)把手抬高一點(diǎn)兒”分析效果很好，可以把“把手”分解為把/手 而我的算法則分解為 把手。

未登錄詞識(shí)別能力：

感覺(jué)SharpICTCLAS對(duì)于未登錄詞的識(shí)別能力并不象代碼注釋中寫(xiě)的那么高，比如下面句子：

“新浪體育訊　英超賽季結(jié)束后，曼城隊(duì)一直處在各種動(dòng)蕩之中”，SharpICTCLAS分詞的結(jié)果是 “新/浪/體育/訊/英/超/賽季/結(jié)束/后/，/曼/城/隊(duì)/一直/處在/各種/動(dòng)蕩/之中/ ”

我的算法分詞結(jié)果是 “新浪/體育/訊/英超/賽季/結(jié)束/后/，/曼城隊(duì)/一直/處在/各種/動(dòng)蕩/之中/”

總結(jié)：

SharpICTCLAS V1.0 和我的算法比較，效率明顯偏低，每秒6000字節(jié)的效率是很難滿足搜索引擎等大數(shù)量應(yīng)用要求的，但對(duì)于有些短文本的分詞，效率并不是一個(gè)重點(diǎn)需要考慮的問(wèn)題。

分詞準(zhǔn)確度方面：基于目前SharpICTCLAS提供的訓(xùn)練集比較，我認(rèn)為各有千秋，在網(wǎng)上找了幾篇文章，整篇文章分詞進(jìn)行比較，感覺(jué)我的算法總體上比SharpICTCLAS好像還要準(zhǔn)確一些。

和雨痕中英文分詞組件的比較

雨痕中英文分詞組件 (http://www.rainsts.net) 的專業(yè)版不是免費(fèi)的，所以只使用了其免費(fèi)的演示版本進(jìn)行了比較。

分詞速度：

雨痕的分詞速度大概在每秒4000字節(jié)左右，這個(gè)和SharpICTCLAS差不多，比我的算法慢100倍左右。

準(zhǔn)確度：

雨痕的分詞準(zhǔn)確度還是比較高的，但和我的算法一樣存在算法的先天缺陷，對(duì)于必須通過(guò)語(yǔ)義才能判斷的句子，無(wú)法準(zhǔn)確分詞。對(duì)于其他類型的有歧異的句子，分詞能力還是不錯(cuò)的，我只發(fā)現(xiàn)類似下面的句子“于北京時(shí)間1月1日舉行運(yùn)動(dòng)會(huì)”我的算法比雨痕要準(zhǔn)確，雨痕

分詞結(jié)果是“于北京/ 時(shí)間/ 1月1日/ 舉行/ 運(yùn)動(dòng)會(huì)”，我對(duì)算法分詞結(jié)果是“于/北京時(shí)間/1月/1日/舉行/運(yùn)動(dòng)會(huì)/”，如果北京時(shí)間這個(gè)詞在雨痕的分詞組件中有的話，我覺(jué)得雨痕的算法可能有需要改進(jìn)的地方。

未登錄詞識(shí)別能力：

還是對(duì)比如下面句子分詞：

“新浪體育訊　英超賽季結(jié)束后，曼城隊(duì)一直處在各種動(dòng)蕩之中”，雨痕分詞的結(jié)果是 “新浪/ 體育/ 訊/ 　/ 英超/ 賽季/ 結(jié)束/ 后/ ，/ 曼/ 城/ 隊(duì)/ 一直/ 處在/ 各種/ 動(dòng)蕩/ 之中”，這個(gè)結(jié)果比SharpICTCLAS還是要準(zhǔn)確一些，但“曼城隊(duì)”被分成了三個(gè)詞，這方面我的算法要稍微好一些。

總結(jié)：

雨痕中英文分詞組件的效率較低，很難滿足搜索引擎等大數(shù)量應(yīng)用要求的。準(zhǔn)確度方面還是比較高的，和我的算法的準(zhǔn)確度相比基本差不多。

和 ShootSearch 分詞組件的比較

ShootSearch （http://www.shootsoft.net）分詞組件是一個(gè)開(kāi)源的分詞組件，其分詞效率很高，和我的算法速度不相上下，但ShootSearch只采用了簡(jiǎn)單的最大匹配算法，分詞準(zhǔn)確度很低，前面舉的幾個(gè)例子都不能很好的分詞，由于準(zhǔn)確度太低，這里就不重點(diǎn)分析了。

KTDictSeg 分詞算法介紹

我把組件名名為KTDictSeg，它是由KaiToo搜索開(kāi)發(fā)的一款基于字典的簡(jiǎn)單中英文分詞組件。

分詞算法

談到分詞算法，目前有很多。比較常用的是正向最大匹配和反向最大匹配算法。但這兩種算法對(duì)于一些存在多元歧異的句子缺乏較好的支持。以“長(zhǎng)春市長(zhǎng)春節(jié)致詞”和“長(zhǎng)春市長(zhǎng)春藥店”這個(gè)兩個(gè)句子為例:

“長(zhǎng)春市長(zhǎng)春節(jié)致詞”可以依次拆分為 長(zhǎng)春、長(zhǎng)春市、市長(zhǎng)、長(zhǎng)春、春節(jié)、致詞 這幾個(gè)詞，按照正向最大匹配算法，分詞結(jié)果是長(zhǎng)春市/長(zhǎng)/春節(jié)/致詞，按照反向最大匹配算法，分詞結(jié)果是長(zhǎng)春/市長(zhǎng)/春節(jié)/致詞。

“長(zhǎng)春市長(zhǎng)春藥店”可以依次拆分為長(zhǎng)春、長(zhǎng)春市、市長(zhǎng)、長(zhǎng)春、春藥、春藥店、藥店 這幾個(gè)詞，按照正向最大匹配算法，分詞結(jié)果是 長(zhǎng)春市/長(zhǎng)春/藥店，按照反向最大匹配算法，分詞結(jié)果是“長(zhǎng)春/市長(zhǎng)/春藥店”。

可見(jiàn)無(wú)論是正向還是反向最大匹配，都存在產(chǎn)生歧異的情況。

KTDictSeg 的算法在正向匹配算法的基礎(chǔ)上做了一些改進(jìn)，用一句話描述就是找到句子中第一個(gè)未被匹配的字?jǐn)?shù)最少的單詞組合，如果多個(gè)組合未被匹配的字?jǐn)?shù)都是最少則找到其中匹配的單詞個(gè)數(shù)最少的組合。匹配順序是從左至右。還是以上面兩個(gè)句子為例：

“長(zhǎng)春市長(zhǎng)春節(jié)致詞” 按正向最大匹配掃描順序可以出現(xiàn)如下匹配的單詞組合：

1) 長(zhǎng)春/市長(zhǎng)/春節(jié)/致詞 匹配單詞數(shù)4,未匹配字?jǐn)?shù)0

2) 長(zhǎng)春市/長(zhǎng)春/致詞 匹配單詞數(shù)3,未匹配字?jǐn)?shù)0

不難看出，第一中組合未匹配的字?jǐn)?shù)最少，所以取組合1。

“長(zhǎng)春市長(zhǎng)春藥店”按正向最大匹配掃描順序可以出現(xiàn)如下匹配的單詞組合：

1)     長(zhǎng)春市/長(zhǎng)春/藥店 匹配單詞數(shù)3,未匹配字?jǐn)?shù)0

2)     長(zhǎng)春市/春藥店 匹配單詞數(shù)2,未匹配字?jǐn)?shù)1

3)     長(zhǎng)春市/春藥 匹配單詞數(shù)2,未匹配字?jǐn)?shù)2

4)     長(zhǎng)春市/藥店 匹配單詞數(shù)2,未匹配字?jǐn)?shù)2

5)     長(zhǎng)春/市長(zhǎng)/春藥店 匹配單詞數(shù)3,未匹配字?jǐn)?shù)0

6)     長(zhǎng)春/市長(zhǎng)/春藥 匹配單詞數(shù)3,未匹配字?jǐn)?shù)1

7)     長(zhǎng)春/市長(zhǎng)/藥店 匹配單詞數(shù)3,未匹配字?jǐn)?shù)1

8)     長(zhǎng)春/市長(zhǎng)/藥店 匹配單詞數(shù)3,未匹配字?jǐn)?shù)1

9)     長(zhǎng)春/長(zhǎng)春/藥店 匹配單詞數(shù)3,未匹配字?jǐn)?shù)1

可見(jiàn)組合1和組合5 未匹配數(shù)最小，匹配單詞數(shù)相等，但組合1匹配順序靠前，所以取組合1。

未登錄詞識(shí)別

KTDictSeg 對(duì)未登錄詞的識(shí)別采用一個(gè)簡(jiǎn)單判定，即把未在字典中找到的連續(xù)的字組成一個(gè)詞，這種判斷是基于分詞算法比較準(zhǔn)確且詞庫(kù)中的詞足夠多的假設(shè)下做出的，由于KTDictSeg的分詞算法相對(duì)比較準(zhǔn)確且附帶的詞庫(kù)收錄了20多萬(wàn)條詞，所以KTDictSeg對(duì)未登錄詞的識(shí)別也相對(duì)比較準(zhǔn)確。

優(yōu)點(diǎn)

KTDictSeg 的 優(yōu)點(diǎn)是分詞速度非常快，且分詞準(zhǔn)確度相對(duì)簡(jiǎn)單的最大匹配算法有很大提高，所以可以應(yīng)用于一些對(duì)分詞準(zhǔn)確度要求不是非?？量蹋珜?duì)分詞效率要求較高的應(yīng)用環(huán)境中，比如大多數(shù)的中小型中文搜索引擎都可以使用這個(gè)分詞組件。

KTDictSeg 還有一個(gè)優(yōu)點(diǎn)就是簡(jiǎn)單，用戶只需維護(hù)一個(gè)漢語(yǔ)詞庫(kù)就可以達(dá)到比較準(zhǔn)確的分詞效果，減少了用戶維護(hù)的工作量和對(duì)系統(tǒng)的開(kāi)銷。

缺點(diǎn)

KTDictSeg 的致命缺點(diǎn)是無(wú)法對(duì)語(yǔ)義進(jìn)行判斷，對(duì)于一些語(yǔ)義相關(guān)的句子不能夠做到100％識(shí)別出來(lái)，而且無(wú)論怎樣調(diào)整詞庫(kù)，理論上都無(wú)法達(dá)到100%匹配。

開(kāi)源代碼

KTDictSeg 下載位置

最新動(dòng)態(tài)

KTDictSeg 1.2 版本發(fā)布及算法簡(jiǎn)介

KTDictSeg 分詞組件1.3版本 新增功能列表及下載位置