中文分詞系列之基於 AC 自動機的快速分詞

雷鋒網 AI 研習社按，本文系廣州火焰信息科技有限公司投稿，作者蘇劍林。正文如下：

中文分詞

關於中文分詞的介紹和重要性，我就不多說了，matrix67這裡有一篇關於分詞和分詞演算法很清晰的介紹，值得一讀。在文本挖掘中，雖然已經有不少文章探索了不分詞的處理方法，如本博客的《文本情感分類（三）：分詞 OR 不分詞》，但在一般場合都會將分詞作為文本挖掘的第一步，因此，一個有效的分詞演算法是很重要的。當然，中文分詞作為第一步，已經被探索很久了，目前做的很多工作，都是總結性質的，最多是微弱的改進，並不會有很大的變化了。

目前中文分詞主要有兩種思路：查詞典和字標註。首先，查詞典的方法有：機械的最大匹配法、最少詞數法，以及基於有向無環圖的最大概率組合，還有基於語言模型的最大概率組合，等等。查詞典的方法簡單高效（得益於動態規劃的思想），尤其是結合了語言模型的最大概率法，能夠很好地解決歧義問題，但對於中文分詞一大難度——未登錄詞（中文分詞有兩大難度：歧義和未登錄詞），則無法解決。

為此，人們也提出了基於字標註的思路，所謂字標註，就是通過幾個標記（比如 4 標註的是：single，單字成詞；begin，多字詞的開頭；middle，三字以上詞語的中間部分；end，多字詞的結尾），把句子的正確分詞法表示出來。

這是一個序列（輸入句子）到序列（標記序列）的過程，能夠較好地解決未登錄詞的問題，但速度較慢，而且對於已經有了完備詞典的場景下，字標註的分詞效果可能也不如查詞典方法。總之，各有優缺點（似乎是廢話～），實際使用可能會結合兩者，像結巴分詞，用的是有向無環圖的最大概率組合，而對於連續的單字，則使用字標註的HMM模型來識別。

AC 自動機

本文首先要實現的是查詞典方法的分詞。

查詞典的過程是：1、給定一批詞，查找給定句子中是不是含有這個詞；2、如果有的話，怎麼解決歧義性問題。

其中，第1步，在計算機中稱為「多模式匹配」。這步看上去簡單，但事實上要高效地實現並不容易。要知道，一個完備的詞典，少說也有十幾萬詞語，如果一個個枚舉查找，那計算量是吃不消的，事實上我們人也不是這樣做的，我們在查字典的時候，會首先看首字母，然後只在首字母相同的那一塊找，然後又比較下一個字母，依此下去。這需要兩個條件：1、一個做好特殊排序的詞典；2、有效的查找技巧，對於第 1 個條件，我們有所謂的前綴樹（tire），第 2 個條件，我們有一些經典的演算法，比如AC 自動機（Aho and Corasick）。

對於這兩個條件，我也不多評價什麼了，不是不想說，而是我的了解也到此為止了——對於 AC 自動機，我的認識就是一個使用了 trie 數據結構的高效多模式匹配演算法。我也不用親自實現它，因為 Python 已經有對應的庫了：pyahocorasick。因此，我們只需要關心怎麼使用它就行了。官方的教程已經很詳細地介紹了 pyahocorasick 的基本使用方法了，這裡也不贅述。（遺憾的是，雖然 pyahocorasick 已經同時支持 python2 和 python3 了，但是在 python2 中，它只支持 bytes 字元串不支持 unicode 字元串，而在 python3 中，則默認使用 unicode 編碼，這對我們寫程序會帶來一點困惑，當然，不是本質性的。本文使用的是python 2.7。）

構建一個基於 AC 自動機的分詞系統，首先需要有一個文本詞典，假設詞典有兩列，每一行是詞和對應的頻數，用空格分開。那麼就可以用下面的代碼構建一個 AC 自動機。

import ahocorasick

def load_dic(dicfile):

 from math import log

 dic = ahocorasick.Automaton()

 total = 0.0

 with open(dicfile) as dicfile:

     words = []

     for line in dicfile:

         line = line.split(" ")

         words.append((line[0], int(line[1])))

         total += int(line[1])  

 for i,j in words:

     dic.add_word(i, (i, log(j/total))) #這裡使用了對數概率，防止溢出

 dic.make_automaton()

 return dic

dic = load_dic("me.dic")

pyahocorasick 構建 AC 自動機有一個很人性化的地方，它能夠以「鍵-注釋」這樣成對的形式添加辭彙（請留意 dic.add_word(i, (i, log(j/total))) 這一句），這樣，我們可以在注釋這裡，添加我們想要的信息，比如頻數、詞性等，然後在查找的時候會一併返回。有了上述 AC 自動機，我們就能很方便地構建一個全模式分詞，也就是把詞典中有的詞都掃描出來（其實這本來就是 AC 自動機的本職工作）。

def all_cut(sentence):

 words = []

 for i,j in dic.iter(sentence):

     words.append(j[0])

 return words

對於一個長句子，這可能會返回很多詞，請慎用。

最大匹配法

當然，上述所謂的全模式分詞，根本就算不上什麼分詞，只是簡單的查找罷了，下面我們來實現一個經典的分詞演算法：最大匹配法。

最大匹配法是指從左到右逐漸匹配詞庫中的詞語，匹配到最長的詞語為止。這是一種比較粗糙的分詞方法，在 matrix67 的文章中也有說到，構造反例很簡單，如果詞典中有「不」、「不可」、「能」、「可能」四個詞，但沒有「不可能」這個詞，那麼「不可能」就會被切分為「不可/能」了。雖然如此，在精度要求不高的情況下，這種分詞演算法還是可以接受的，畢竟速度很快～下面是基於 AC 自動機的最大匹配法的實現：

def max_match_cut(sentence):

 sentence = sentence.decode("utf-8")

 words = [""]

 for i in sentence:

     i = i.encode("utf-8")

     if dic.match(words[-1] + i):

         words[-1] += i        else:

         words.append(i)

 return words

代碼很短，也挺清晰的，主要用到了 pyahocorasick 的 match 函數。在我的機器上測試，這個演算法的效率大概是 4M/s，根據 hanlp 的作者的描述，用 JAVA 做類似的事情，可以達到 20M/s 的速度！而用 python 做，則有兩個限制，一個是 python 本身速度的限制，另外一個是 pyahocorasick 的限制，導致上面的實現其實並非是最高效率的，因為 pyahocorasick 不支持 unicode 編碼，所以漢字的編碼長度不一，要不斷通過轉編碼的方式來獲取漢字長度。

上面說的最大匹配法，準確來說是「正向最大匹配法」，類似地，還有「逆向最大匹配法」，顧名思義，是從右到左掃描句子進行最大匹配，效果一般比正向最大匹配要好些。如果用 AC 自動機來實現，唯一的辦法就是對詞典所有的詞都反序存儲，然後對輸入的句子也反序，然後進行正向最大匹配了。

最大概率組合

基於最大概率組合的方法，是目前兼顧了速度和準確率的比較優秀的方法。它說的是：對於一個句子，如果切分為詞語 w1，w2，…，wn是最優的切分方案，那麼應該使得下述概率最大：

直接估計這概率是不容易的，一般用一些近似方案，比如

這裡 P(wk|wk?1) 就稱為語言模型，它已經初步地考慮了語義了。當然，普通分詞工具是很難估計 P(wk|wk?1) 的，一般採用更加簡單的近似方案。

放到圖論來看，這就是有向無環圖裡邊的最大概率路徑了。

下面介紹用 AC 自動機，結合動態規劃，來實現後一種方案。

def max_proba_cut(sentence):

 paths =

 end = 0

 for i,j in dic.iter(sentence):

     start,end = 1+i-len(j[0]), i+1

     if start not in paths:

         last = max([i for i in paths if i

         paths[start] = (paths[last][0]+[sentence[last:start]], paths[last][1]-10)

     proba = paths[start][1]+j[1]

     if end not in paths or proba > paths[end][1]:

         paths[end] = (paths[start][0]+[j[0]], proba)

 if end

     return paths[end][0] + [sentence[end:]]

 else:

     return paths[end][0]

代碼還是很簡短清晰，這裡假設了不匹配部分的頻率是 e?10，這個可以修改。只是要注意的是，由於使用的思路不同，因此這裡的動態規劃方案與一般的有向無環圖的動態規劃不一樣，但是思路是很自然的。要注意，如果直接用這個函數對長度為上萬字的句子進行分詞，會比較慢，而且耗內存比較大，這是因為我通過字典把動態規划過程中所有的臨時方案都保留了下來。幸好，中文句子中還是有很多天然的斷句標記的，比如標點符號、換行符，我們可以用這些標記把句子分成很多部分，然後逐步分詞，如下。

to_break = ahocorasick.Automaton()for i in ["，", "。", "！", "、", "？", " ", "
"]:

 to_break.add_word(i, i)to_break.make_automaton()def map_cut(sentence):

 start = 0

 words = []

 for i in to_break.iter(sentence):

     words.extend(max_proba_cut(sentence[start:i[0]+1]))

     start = i[0]+1

 words.extend(max_proba_cut(sentence[start:]))

 return words

在伺服器上，我抽了 10 萬篇文章出來（1 億多字），對比了結巴分詞的速度，發現在使用相同詞典的情況下，並且關閉結巴分詞的新詞發現，用 AC 自動機實現的這個 map_cut 的分詞速度，大概是結巴分詞的 2～3 倍，大約有 1M/s。

最後，值得一提的是，max_proba_cut 這個函數的實現思路，可以用於其他涉及到動態規劃的分詞方法，比如最少詞數分詞：

def min_words_cut(sentence):

 paths =

 end = 0

 for i,j in dic.iter(sentence):

     start,end = 1+i-len(j[0]), i+1

     if start not in paths:

         last = max([i for i in paths if i

         paths[start] = (paths[last][0]+[sentence[last:start]], paths[last][1]+1)

     num = paths[start][1]+1

     if end not in paths or num

         paths[end] = (paths[start][0]+[j[0]], num)

 if end

     return paths[end][0] + [sentence[end:]]

 else:

     return paths[end][0]

這裡採取了罰分規則：有多少個詞罰多少分，未登錄詞再罰一分，最後罰分最少的勝出。

總結

事實上，只要涉及到查詞典的操作，AC 自動機都會有一定的用武之地。將 AC 自動機用於分詞，事實上是一個非常自然的應用。我們期待有更多對中文支持更好的數據結構和演算法出現，這樣我們就有可能設計出更高效率的演算法了。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！