最近實現(xiàn)的3種中文分詞算法
- 基于最大匹配（前向匹配爸舒、后向匹配、雙向匹配）
- HMM
- n-gram
基于最大匹配算法（基于詞典）
- 最大前向匹配
- 從左到右取待切分漢語句的m個字符作為匹配字段鹊奖，m為詞典中最長詞條個數(shù)涂炎。
- 查找詞典并進(jìn)行匹配，若匹配成功两蟀，則將這個匹配字段作為一個詞切分出來震缭。
- 最大后向匹配
- 從右到左切分漢語句的m個字符作為匹配字段，m為詞典中最長詞條個數(shù)党涕。
- 查找詞典并進(jìn)行匹配巡社。若匹配成功，則將這個匹配字段作為一個詞切分出來晌该。
- 雙向最大向前匹配
- 將正向最大匹配法得到的分詞結(jié)果和逆向最大匹配法得到的結(jié)果進(jìn)行比較，從而決定正確的分詞方法次企。
- 啟發(fā)式規(guī)則：1.如果正反向分詞結(jié)果詞數(shù)不同，則取分詞數(shù)量較少的那個舟茶。2.如果分詞結(jié)果詞數(shù)相同堵第。a.分詞結(jié)果相同，就說明沒有歧義阀捅，可返回任意一個针余。 b.分詞結(jié)果不同，返回其中單字較少的那個忍级。
小結(jié)：
基于最大匹配方法分詞的效果取決于分詞詞典的大小與質(zhì)量伪朽，分詞的原則是盡量避免單個字的出現(xiàn)和盡可能少的分詞數(shù)量。
基于HMM分詞算法
隱馬爾可夫模型的3個關(guān)鍵矩陣：初始概率矩陣朴肺、狀態(tài)轉(zhuǎn)移概率矩陣坚洽、發(fā)射概率矩陣。
- 根據(jù)訓(xùn)練樣本獲取每個詞的狀態(tài)（S：單字詞器瘪， B：詞的開頭绘雁，M：詞的中間庐舟，E：詞的末尾）
- 如果是單字詞住拭，則記錄第一個字的狀態(tài)历帚，用于計算初始狀態(tài)概率杠娱。如果不是單字詞，則統(tǒng)計狀態(tài)轉(zhuǎn)移次數(shù)禽拔，并計算對應(yīng)的概率室叉。
- 通過上面步驟得到3個概率矩陣茧痕，并且由訓(xùn)練樣本可得可觀測序列，通過維特比算法（Viterbi）來求得在馬爾可夫模型中最優(yōu)的隱含狀態(tài)曼氛。維特比算法其實就是一個求最短路徑的動態(tài)規(guī)劃問題令野。
基于n-gram語法模型分詞算法
- 根據(jù)語料獲取每個詞出現(xiàn)頻次與每個詞后接詞語出現(xiàn)頻次
-
尋找當(dāng)前字的最佳前驅(qū)節(jié)點(diǎn)，并記錄累計概率
基本概念如下圖：
n-gram.png
總結(jié)
算法比較
1构舟、評測語料：微軟評測語料堵幽，共3985個句子
2朴下、性能比較
| Algorithm | Precision | Recall | F1-score | Cost-Time |
|---|---|---|---|---|
| HMM | 0.65 | 0.75 | 0.70 | 4.87 |
| MaxForward | 0.76 | 0.87 | 0.81 | 244.14 |
| MaxBackward | 0.76 | 0.87 | 0.81 | 280.61 |
| MaxBiWard | 0.76 | 0.87 | 0.81 | 443.23 |
| MaxProbNgram | 0.76 | 0.87 | 0.81 | 8.99 |
| MaxBiwardNgram | 0.74 | 0.86 | 0.80 | 3.96 |
