結巴分詞是國內程序員用python開(kāi)發(fā)的一個(gè)中文分詞模塊, 源碼已托管在github, 地址在: https://github.com/fxsjy/jieba
作者的文檔寫(xiě)的不是很全, 只寫(xiě)了怎么用, 有一些細節的文檔沒(méi)有寫(xiě).
以下是作者說(shuō)明文件中提到的結巴分詞用到的算法:
基于Trie樹(shù)結構實(shí)現高效的詞圖掃描，生成句子中漢字所有可能成詞情況所構成的有向無(wú)環(huán)圖（DAG)
采用了動(dòng)態(tài)規劃查找最大概率路徑, 找出基于詞頻的最大切分組合
對于未登錄詞，采用了基于漢字成詞能力的HMM模型，使用了Viterbi算法
因為最近有點(diǎn)興趣想了解中文分詞, 所以看了大量的資料, 對上面的三條有了一點(diǎn)點(diǎn)理解, 不再是兩眼一抹黑了.轉載請注明: 本文來(lái)自Django夢(mèng)之隊, http://ddtcms.com/blog/archive/2013/2/4/69/jieba-fenci-suanfa-lijie/
先推薦大家看 http://www.52nlp.cn/ （我愛(ài)自然語(yǔ)言處理）的一系列關(guān)于概率、中文分詞、HMM隱馬爾科夫模型的文章， 然后再回頭看看結巴分詞的代碼。
然后推薦大家看看《解密搜索引擎技術(shù)實(shí)戰：Lucene&Java精華版》，如果看不到， 可以看看這里的在線(xiàn)版， 雖然很短， 但是基本的思想都說(shuō)明白了， 地址： http://book.51cto.com/art/201106/269050.htm (4.6 概率語(yǔ)言模型的分詞方法)
看了這本書(shū)的第4章， 或者看了那個(gè)在線(xiàn)的那個(gè)章節的前后部分， 基本上可以說(shuō)， 結巴分詞， 在很大的程度上類(lèi)似于書(shū)中說(shuō)的例子。（上面的鏈接，是作者算法的第2條， 動(dòng)態(tài)規劃查找最大概率路徑），當然， 結巴分詞使用了HMM模型對未登錄詞進(jìn)行識別（上面的第3條）
至于第1條， 作者的trie樹(shù)，可以看這篇文章對python中如何保存trie樹(shù)結構的詞典進(jìn)行深刻理解：http://iregex.org/blog/trie-in-python.html Trie in Python 這篇寫(xiě)的很好， 主要分析 Trie 實(shí)現原理，并給出 Python 的實(shí)現，還和正則聯(lián)系到一起了。
上面列出的三個(gè)鏈接, 里面講到的知識, 基本上將結巴分詞的算法都講到了。所以有興趣的人， 一定要仔細看我上面給的三個(gè)鏈接。
下面， 結合自己看結巴分詞的代碼， 講講我自己看過(guò)資料和代碼后的理解。
先從作者的三條說(shuō)起。
第一條：基于Trie樹(shù)結構實(shí)現高效的詞圖掃描，生成句子中漢字所有可能成詞情況所構成的有向無(wú)環(huán)圖（DAG)
這個(gè)看上面的trie樹(shù)的python實(shí)現， 結巴分詞自帶了一個(gè)叫做dict.txt的詞典, 里面有2萬(wàn)多條詞, 包含了詞條出現的次數(這個(gè)次數是于作者自己基于人民日報語(yǔ)料等資源訓練得出來(lái)的)和詞性. 這個(gè)第一條的trie樹(shù)結構的詞圖掃描, 說(shuō)的就是把這2萬(wàn)多條詞語(yǔ), 放到一個(gè)trie樹(shù)中, 而trie樹(shù)是有名的前綴樹(shù), 也就是說(shuō)一個(gè)詞語(yǔ)的前面幾個(gè)字一樣, 就表示他們具有相同的前綴, 就可以使用trie樹(shù)來(lái)存儲, 具有查找速度快的優(yōu)勢.
聰明的人可能會(huì )想到把 dict.txt中所有的詞匯全部刪掉, 然后再試試結巴能不能分詞, 結果會(huì )發(fā)現, 結巴依然能夠分詞, 不過(guò)分出來(lái)的詞, 大部分的長(cháng)度為2.這個(gè)就是第三條, 基于HMM來(lái)預測分詞了.
接著(zhù)說(shuō)DAG有向無(wú)環(huán)圖, 就是后一句的 生成句子中漢字所有可能成詞情況所構成的有向無(wú)環(huán)圖, 這個(gè)是說(shuō)的, 給定一個(gè)句子, 要你分詞, 也就是給定一個(gè) 待分詞的句子, 對這個(gè)句子進(jìn)行生成有向無(wú)環(huán)圖. 如果對有向無(wú)環(huán)圖理解不了可以百度或者google搜索, 也可以看這篇 http://book.51cto.com/art/201106/269048.htm 比較形象的用圖來(lái)表示了一個(gè)待分詞句子的切分情況.
作者是怎么切分的呢? 1. 根據dict.txt生成trie樹(shù), 2, 對待分詞句子, 根據dict.txt生成的trie樹(shù), 生成DAG, 實(shí)際上通俗的說(shuō), 就是對待分詞句子, 根據給定的詞典進(jìn)行查詞典操作, 生成幾種可能的句子切分. dag是啥玩意?記錄了啥呢? 作者的源碼中記錄的是句子中某個(gè)詞的開(kāi)始位置, 從0到n-1(n為句子的長(cháng)度), 每個(gè)開(kāi)始位置作為字典的鍵, value是個(gè)list, 其中保存了可能的詞語(yǔ)的結束位置(通過(guò)查字典得到詞, 開(kāi)始位置+詞語(yǔ)的長(cháng)度得到結束位置)
例如:{0:[1,2,3]} 這樣一個(gè)簡(jiǎn)單的DAG, 就是表示0位置開(kāi)始, 在1,2,3位置都是詞, 就是說(shuō)0~1, 0~2,0~3這三個(gè)起始位置之間的字符, 在dict.txt中是詞語(yǔ).
第二條:采用了動(dòng)態(tài)規劃查找最大概率路徑, 找出基于詞頻的最大切分組合
關(guān)于動(dòng)態(tài)規劃查找最大概率路徑, 這個(gè)在一些大學(xué)課程中講的很多了, 不熟悉的或者忘記了的翻翻百度就行了. 上面給的那個(gè)在線(xiàn)書(shū)籍的鏈接中也說(shuō)的很明白了, 我這里就說(shuō)說(shuō)作者的代碼:
作者的代碼中講字典在生成trie樹(shù)的同時(shí), 也把每個(gè)詞的出現次數轉換為了頻率. 關(guān)于頻率和概率, 這里在啰嗦幾句: 按照定義, 頻率其實(shí)也是一個(gè)0~1之間的小數, 是 事件出現的次數/實(shí)驗中的總次數, 因此在試驗次數足夠大的情況下, 頻率約等于概率, 或者說(shuō)頻率的極限就是概率. 不過(guò)通常人們混淆的是頻率和次數, 經(jīng)常把頻率等同于事件出現的次數, 比如這里就是某個(gè)詞語(yǔ)出現的次數, 所以, 頻率在引起混淆的時(shí)候, 對中國人來(lái)說(shuō), 還是先理解為出現次數, 然后理解發(fā)現有問(wèn)題, 就理解為出現次數/總數這個(gè)比率吧.
動(dòng)態(tài)規劃中, 先查找待分詞句子中已經(jīng)切分好的詞語(yǔ), 對該詞語(yǔ)查找該詞語(yǔ)出現的頻率(次數/總數), 如果沒(méi)有該詞(既然是基于詞典查找, 應該是有的), 就把詞典中出現頻率最小的那個(gè)詞語(yǔ)的頻率作為該詞的頻率, 也就是說(shuō)P(某詞語(yǔ))=FREQ.get(‘某詞語(yǔ)’,min_freq), 然后根據動(dòng)態(tài)規劃查找最大概率路徑的方法, 對句子從右往左反向計算最大概率(一些教科書(shū)上可能是從左往右, 這里反向是因為漢語(yǔ)句子的重心經(jīng)常落在后面, 就是落在右邊, 因為通常情況下形容詞太多, 后面的才是主干, 因此, 從右往左計算, 正確率要高于從左往右計算, 這個(gè)類(lèi)似于逆向最大匹配), P(NodeN)=1.0, P(NodeN-1)=P(NodeN)*Max(P(倒數第一個(gè)詞))…依次類(lèi)推, 最后得到最大概率路徑, 得到最大概率的切分組合.
第三條, 對于未登錄詞，采用了基于漢字成詞能力的HMM模型，使用了Viterbi算法
未登錄詞, 作者說(shuō)的是什么意思? 其實(shí)就是詞典 dict.txt 中沒(méi)有記錄的詞. 上面說(shuō)了, 把dict.txt中的所有詞語(yǔ)都刪除了, 結巴分詞一樣可以分詞, 就是說(shuō)的這個(gè).
怎么做到的? 這個(gè)就基于作者采用的HMM模型了, 中文詞匯按照BEMS四個(gè)狀態(tài)來(lái)標記, B是開(kāi)始begin位置, E是end, 是結束位置, M是middle, 是中間位置, S是singgle, 單獨成詞的位置, 沒(méi)有前, 也沒(méi)有后. 也就是說(shuō), 他采用了狀態(tài)為(B,E,M,S)這四種狀態(tài)來(lái)標記中文詞語(yǔ), 比如北京可以標注為 BE, 即 北/B 京/E, 表示北是開(kāi)始位置, 京是結束位置, 中華民族可以標注為BMME, 就是開(kāi)始, 中間, 中間, 結束.
經(jīng)過(guò)作者對大量語(yǔ)料的訓練, 得到了finalseg目錄下的三個(gè)文件(來(lái)自結巴項目的issues):
要統計的主要有三個(gè)概率表：
prob_trans.py
1)位置轉換概率，即B（開(kāi)頭）,M（中間),E(結尾),S(獨立成詞）四種狀態(tài)的轉移概率；
{‘B’: {‘E’: 0.8518218565181658, ‘M’: 0.14817814348183422},
‘E’: {‘B’: 0.5544853051164425, ‘S’: 0.44551469488355755},
‘M’: {‘E’: 0.7164487459986911, ‘M’: 0.2835512540013088},
‘S’: {‘B’: 0.48617017333894563, ‘S’: 0.5138298266610544}}
P(E|B) = 0.851, P(M|B) = 0.149，說(shuō)明當我們處于一個(gè)詞的開(kāi)頭時(shí)，下一個(gè)字是結尾的概率
要遠高于下一個(gè)字是中間字的概率，符合我們的直覺(jué)，因為二個(gè)字的詞比多個(gè)字的詞更常見(jiàn)。
prob_emit.py
2）位置到單字的發(fā)射概率，比如P(“和”|M)表示一個(gè)詞的中間出現”和”這個(gè)字的概率；
prob_start.py
3) 詞語(yǔ)以某種狀態(tài)開(kāi)頭的概率，其實(shí)只有兩種，要么是B，要么是S。這個(gè)就是起始向量, 就是HMM系統的最初模型狀態(tài)
實(shí)際上, BEMS之間的轉換有點(diǎn)類(lèi)似于2元模型, 就是2個(gè)詞之間的轉移
二元模型考慮一個(gè)單詞后出現另外一個(gè)單詞的概率，是N元模型中的一種。
例如：一般來(lái)說(shuō)，”中國”之后出現”北京”的概率大于”中國”之后出現”北?！钡母怕?，也就是：中國北京 比 中國北海出現的概率大些, 更有可能是一個(gè)中文詞語(yǔ).
不過(guò), 作者這里應該不是用的2元分詞模型的, 這里的BEMS只提供了單個(gè)漢字之間的轉換, 發(fā)射概率, 并沒(méi)有提供粒度更大的, 基于詞語(yǔ)的發(fā)射和轉移概率, 當然, 也有可能我理解的不夠深入.
給定一個(gè) 待分詞的句子, 就是觀(guān)察序列, 對HMM(BEMS)四種狀態(tài)的模型來(lái)說(shuō), 就是為了找到一個(gè)最佳的BEMS序列, 這個(gè)就需要使用viterbi算法來(lái)得到這個(gè)最佳的隱藏狀態(tài)序列, 具體的python版的viterbi算法請看維基百科:http://zh.wikipedia.org/wiki/%E7%BB%B4%E7%89%B9%E6%AF%94%E7%AE%97%E6%B3%95 維特比算法
通過(guò)作者之前訓練得到的概率表和viterbi算法, 就可以得到一個(gè)概率最大的BEMS序列, 按照B打頭, E結尾的方式, 對待分詞的句子重新組合, 就得到了分詞結果. 比如 對待分詞的句子 ‘全世界都在學(xué)中國話(huà)’ 得到一個(gè)BEMS序列 [S,B,E,S,S,S,B,E,S] 這個(gè)序列只是舉例, 不一定正確, 通過(guò)把連續的BE湊合到一起得到一個(gè)詞, 單獨的S放單, 就得到一個(gè)分詞結果了: 上面的BE位置和句子中單個(gè)漢字的位置一一對應, 得到全/S 世界/BE 都/S 在/S 學(xué)/S 中國/BE 話(huà)/S 從而將句子切分為詞語(yǔ).
以上, 就是作者這三條介紹的全部理解和分析, 對于其中任何術(shù)語(yǔ)不理解, 請使用搜索引擎.
結巴分詞的過(guò)程:
1. 加載字典, 生成trie樹(shù)
2. 給定待分詞的句子, 使用正則獲取連續的 中文字符和英文字符, 切分成 短語(yǔ)列表, 對每個(gè)短語(yǔ)使用DAG(查字典)和動(dòng)態(tài)規劃, 得到最大概率路徑, 對DAG中那些沒(méi)有在字典中查到的字, 組合成一個(gè)新的片段短語(yǔ), 使用HMM模型進(jìn)行分詞, 也就是作者說(shuō)的識別新詞, 即識別字典外的新詞.
3. 使用python的yield 語(yǔ)法生成一個(gè)詞語(yǔ)生成器, 逐詞語(yǔ)返回. 當然, 我認為直接返回list, 效果也差不到哪里去.
另外談?wù)?strong>結巴分詞的不足和局限:
1 在中文分詞的時(shí)候, 字典起到的作用貌似不大, 因為基于單字的HMM(BEMS)模型貌似就可以分詞了, 不管正確率如何, 總算能分了.字典起到的作用在后面說(shuō).說(shuō)作用不大, 是因為沒(méi)有字典也能分詞. 另外, 生成了DAG之后, 又用動(dòng)態(tài)規劃, 覺(jué)得浪費步驟.小概率連乘下限可能溢出已修正, 就不多說(shuō)了.
2. 中文分詞加載dict.txt這個(gè)字典后, 占用的內存為140多M, 覺(jué)得占用內存過(guò)多. 專(zhuān)業(yè)化的詞典生成, 還不方便. 怎么訓練自己的專(zhuān)用概率表, 就沒(méi)有提供工具, 如果提供了訓練自己的HMM模型工具, 估計更好.
3. 沒(méi)有那個(gè)字典的話(huà), Trie和DAG都不起作用, 僅靠HMM模型的viterbi算法起作用, 因此看出詞典的作用就是用來(lái)矯正HMM模型的分詞結果, 但是HMM分詞的結果生成方式是把B開(kāi)始E結束的序列, 組合成一個(gè)詞, 因此, 這種判斷方法不一定正確, 比如BES能不能算作一個(gè)詞的序列我覺(jué)得值得考慮.
4. HMM是不是真的能夠識別新詞呢? 我認為是肯定的, 但是是要打折扣的. 這個(gè)跟作者訓練的詞庫有關(guān)系, 新詞的字出現的概率在一段時(shí)間內會(huì )井噴, 但在長(cháng)期的語(yǔ)言現象中, 應該還是平穩的, 除非這個(gè)詞從一出現就很流行, 而且會(huì )流行很長(cháng)的時(shí)間.因此HMM識別新詞的功能在時(shí)效性上是不足的, 他只能識別2個(gè)字的詞, 對于3個(gè)字的新詞, 估計就能力有限了. 這個(gè)有待于BEMS序列組合成詞的算法的改變和新詞獲取算法的改變, 才能得到改善.
5. 引入二元分詞的判斷, 可能對詞典的依賴(lài)會(huì )降低一點(diǎn), 現在的詞典的使用就是為了彌補HMM在識別多字詞方面能力欠佳的問(wèn)題, 所以詞典中保存的是3 ,4 個(gè)字的詞語(yǔ).
6. 詞性標注的問(wèn)題, 在分詞的時(shí)候, 不能同時(shí)識別詞性, 因為分詞的時(shí)候沒(méi)有處理詞性, 也就是說(shuō)分詞的時(shí)候, 沒(méi)有語(yǔ)義分析的.詞性標注的部分, 是使用另外的posseg模塊進(jìn)行的.還有一個(gè)問(wèn)題是新詞的詞性可能沒(méi)法識別, 同樣這個(gè)是說(shuō)那些3, 4字詞.
7. 對專(zhuān)有名詞比如人名 地名 機構名 的識別, 不能說(shuō)好.
8. 文檔太少了, 關(guān)于詞性標注, 得到的結果沒(méi)有一點(diǎn)分析, 詞性來(lái)源于哪里都沒(méi)有說(shuō)明. 不利于大家一起改進(jìn).句法分析, 語(yǔ)義分析都是沒(méi)有的.
9. 詞性標注應該也是基于BEMS標注進(jìn)行的. 不知道是不是可以獨立出來(lái).就是說(shuō)基于語(yǔ)義來(lái)標示詞性或者基于詞語(yǔ)在句子中的位置來(lái)做推斷進(jìn)行標注詞性.
10. 分詞過(guò)程中, 不能獲得這個(gè)句子中出現的詞的次數信息, 或者說(shuō)出現頻率高的詞, 不能用于抽取文章的關(guān)鍵詞.
第12次修改, 全文完, 歡迎拍磚.轉載請注明來(lái)自Django夢(mèng)之隊, http://ddtcms.com/blog/archive/2013/2/4/69/jieba-fenci-suanfa-lijie/
聯(lián)系客服
