shanchen
shanchen

hi

結巴斷詞系統原理與Stanford Chinese Word Segmentation筆記

紀錄一下自己對這兩個方法的理解。有些細節不太想深入研究了,還要看code會很花時間。

結巴:

作者github說明:

  1. 基于前缀词典实现高效的词图扫描,生成句子中汉字所有可能成词情况所构成的有向无环图 (DAG)
  2. 采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合
  3. 对于未登录词,采用了基于汉字成词能力的 HMM 模型,使用了 Viterbi 算法
  4. 第一個,需要一個dict.txt當作字典。利用語料庫做成一個每個詞的出線機率,並把它做成Trie。(這段都是用Ref(1)的例子):Trie像是這樣:

一個句子,第一個出現”有”的機率為0.018,出現”意見”的機率為0.001,其他類推。理論上全部出現的機率總和應該要為1,這邊省略不畫(像”有”下面所有連結上的機率加起來為1)。然後在第一個字出現為”有”的情況下,再出現”意”的機率為0.0005。

2. 在有了這個Trie後,要做動態規劃。像是”有意見分歧”這個例子,可以分為S1:”有/ 意見/ 分歧/ “,S2:”有意/ 見/ 分歧/” 跟其他種分法。(斷詞,有a意b見c分d歧。, 每個地方可斷可不斷應該是²⁴種分法)

然後假設每個詞出現的機率與前一個詞無關(與上下文無關),一個句子出現的機率可以用

P(Sentence) = P(W1,W2,….,Wm)=P(W1)*P(W2)*……*P(Wm)

表示。所以P(S1)=P(有)*P(意見)*P(分岐), P(S2)=P(有意)*P(見)*P(分岐)。依照前面給的機率,P(S1)=1.8*10^(-9), P(S2) = 10^(-11)。P(S1)>P(S2), 所以選擇S1的斷詞方式。

不過通常句子重心在後段,所以結巴用從後面算回來的方法來求最大機率的路徑。

3. 那些沒出現在dict.txt的字,就利用HMMViterbi來做分析,找出機率最大的排列機率。(所以把dict.txt清空也可以斷,只是不太準)。狀態有{B,E,M,S}四種,產生的val有 詞性標註

Stanford Chinese Word Segmentation

利用CRF(Conditional Random Field)找最大出現機率的排序。官方網頁上提到兩篇論文,上面的說得CRF: (λ是weight, 這邊是每個詞Y在句子X中出現的機率)

算出一個sequence的斷詞方法,將所有機率相乘。比較所有機率,取機率最大也就是最可能那種分詞法. fk是研究者定義的feature function,每個函數可能跟現在這個字 前幾個字跟後幾字有關,(2005那篇只用跟前一個字有關,後來才改進)用統計過的文本資料,取出這個詞出現頻率再加上他們調整過的參數λ。把所有feature function乘上λ加起來算這樣分詞的機率。


Reference:

  1. 概率语言模型的分词方法
  2. 对Python中文分词模块结巴分词算法过程的理解和分析
CC BY-NC-ND 2.0 版权声明

喜欢我的文章吗?
别忘了给点支持与赞赏,让我知道创作的路上有你陪伴。

加载中…

发布评论