1.基於AC自動機的快速分詞

中文分詞

在文本挖掘中，雖然已經有不少文章探索了不分詞的處理方法，如前面推送的《文本情感分類（三）：分詞 OR 不分詞》，但在一般場合都會將分詞作為文本挖掘的第一步，因此，一個有效的分詞演算法是很重要的。

目前中文分詞主要有兩種思路：查詞典和字標註。首先，查詞典的方法有：機械的最大匹配法、最少詞數法，以及基於有向無環圖的最大概率組合，還有基於語言模型的最大概率組合，等等。

查詞典的方法簡單高效（得益於動態規劃的思想），尤其是結合了語言模型的最大概率法，能夠很好地解決歧義問題，但對於中文分詞一大難度——未登錄詞（中文分詞有兩大難度：歧義和未登錄詞），則無法解決；為此，人們也提出了基於字標註的思路，所謂字標註，就是通過幾個標記（比如4標註的是：single，單字成詞；begin，多字詞的開頭；middle，三字以上詞語的中間部分；end，多字詞的結尾），把句子的正確分詞法表示出來。

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

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

最大匹配法

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

最大匹配法是指從左到右逐漸匹配詞庫中的詞語，匹配到最長的詞語為止。這是一種比較粗糙的分詞方法，構造反例很簡單，如果詞典中有「不」、「不可」、「能」、「可能」四個詞，但沒有「不可能」這個詞，那麼「不可能」就會被切分為「不可/能」了。雖然如此，在精度要求不高的情況下，這種分詞演算法還是可以接受的，畢竟速度很快～下面是基於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是最優的切分方案，那麼應該使得下述概率最大：

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

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

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

下面介紹用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]

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

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自動機用於分詞，事實上是一個非常自然的應用。我們期待有更多對中文支持更好的數據結構和演算法出現，這樣我們就有可能設計出更高效率的演算法了。

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