0
雷鋒網(wǎng) AI 研習(xí)社按，本文系廣州火焰信息科技有限公司投稿，作者蘇劍林。正文如下：
關(guān)于中文分詞的介紹和重要性，我就不多說了，matrix67 這里有一篇關(guān)于分詞和分詞算法很清晰的介紹，值得一讀。在文本挖掘中，雖然已經(jīng)有不少文章探索了不分詞的處理方法，如本博客的《文本情感分類（三）：分詞 OR 不分詞》，但在一般場合都會將分詞作為文本挖掘的第一步，因此，一個有效的分詞算法是很重要的。當(dāng)然，中文分詞作為第一步，已經(jīng)被探索很久了，目前做的很多工作，都是總結(jié)性質(zhì)的，最多是微弱的改進(jìn)，并不會有很大的變化了。
目前中文分詞主要有兩種思路：查詞典和字標(biāo)注。首先，查詞典的方法有：機(jī)械的最大匹配法、最少詞數(shù)法，以及基于有向無環(huán)圖的最大概率組合，還有基于語言模型的最大概率組合，等等。查詞典的方法簡單高效（得益于動態(tài)規(guī)劃的思想），尤其是結(jié)合了語言模型的最大概率法，能夠很好地解決歧義問題，但對于中文分詞一大難度——未登錄詞（中文分詞有兩大難度：歧義和未登錄詞），則無法解決。
為此，人們也提出了基于字標(biāo)注的思路，所謂字標(biāo)注，就是通過幾個標(biāo)記（比如 4 標(biāo)注的是：single，單字成詞；begin，多字詞的開頭；middle，三字以上詞語的中間部分；end，多字詞的結(jié)尾），把句子的正確分詞法表示出來。
這是一個序列（輸入句子）到序列（標(biāo)記序列）的過程，能夠較好地解決未登錄詞的問題，但速度較慢，而且對于已經(jīng)有了完備詞典的場景下，字標(biāo)注的分詞效果可能也不如查詞典方法?？傊?，各有優(yōu)缺點（似乎是廢話～），實際使用可能會結(jié)合兩者，像結(jié)巴分詞，用的是有向無環(huán)圖的最大概率組合，而對于連續(xù)的單字，則使用字標(biāo)注的HMM模型來識別。
本文首先要實現(xiàn)的是查詞典方法的分詞。
查詞典的過程是：1、給定一批詞，查找給定句子中是不是含有這個詞；2、如果有的話，怎么解決歧義性問題。
其中，第1步，在計算機(jī)中稱為“多模式匹配”。這步看上去簡單，但事實上要高效地實現(xiàn)并不容易。要知道，一個完備的詞典，少說也有十幾萬詞語，如果一個個枚舉查找，那計算量是吃不消的，事實上我們?nèi)艘膊皇沁@樣做的，我們在查字典的時候，會首先看首字母，然后只在首字母相同的那一塊找，然后又比較下一個字母，依此下去。這需要兩個條件：1、一個做好特殊排序的詞典；2、有效的查找技巧，對于第 1 個條件，我們有所謂的前綴樹（tire），第 2 個條件，我們有一些經(jīng)典的算法，比如 AC 自動機(jī)（Aho and Corasick）。
對于這兩個條件，我也不多評價什么了，不是不想說，而是我的了解也到此為止了——對于 AC 自動機(jī)，我的認(rèn)識就是一個使用了 trie 數(shù)據(jù)結(jié)構(gòu)的高效多模式匹配算法。我也不用親自實現(xiàn)它，因為 Python 已經(jīng)有對應(yīng)的庫了：pyahocorasick。因此，我們只需要關(guān)心怎么使用它就行了。官方的教程已經(jīng)很詳細(xì)地介紹了 pyahocorasick 的基本使用方法了，這里也不贅述。（遺憾的是，雖然 pyahocorasick 已經(jīng)同時支持 python2 和 python3 了，但是在 python2 中，它只支持 bytes 字符串不支持 unicode 字符串，而在 python3 中，則默認(rèn)使用 unicode 編碼，這對我們寫程序會帶來一點困惑，當(dāng)然，不是本質(zhì)性的。本文使用的是python 2.7。）
構(gòu)建一個基于 AC 自動機(jī)的分詞系統(tǒng)，首先需要有一個文本詞典，假設(shè)詞典有兩列，每一行是詞和對應(yīng)的頻數(shù)，用空格分開。那么就可以用下面的代碼構(gòu)建一個 AC 自動機(jī)。
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))) #這里使用了對數(shù)概率，防止溢出
dic.make_automaton()
return dic
dic = load_dic('me.dic')
pyahocorasick 構(gòu)建 AC 自動機(jī)有一個很人性化的地方，它能夠以“鍵-注釋”這樣成對的形式添加詞匯（請留意 dic.add_word(i, (i, log(j/total))) 這一句），這樣，我們可以在注釋這里，添加我們想要的信息，比如頻數(shù)、詞性等，然后在查找的時候會一并返回。有了上述 AC 自動機(jī)，我們就能很方便地構(gòu)建一個全模式分詞，也就是把詞典中有的詞都掃描出來（其實這本來就是 AC 自動機(jī)的本職工作）。
def all_cut(sentence):
words = []
for i,j in dic.iter(sentence):
words.append(j[0])
return words
對于一個長句子，這可能會返回很多詞，請慎用。
當(dāng)然，上述所謂的全模式分詞，根本就算不上什么分詞，只是簡單的查找罷了，下面我們來實現(xiàn)一個經(jīng)典的分詞算法：最大匹配法。
最大匹配法是指從左到右逐漸匹配詞庫中的詞語，匹配到最長的詞語為止。這是一種比較粗糙的分詞方法，在 matrix67 的文章中也有說到，構(gòu)造反例很簡單，如果詞典中有“不”、“不可”、“能”、“可能”四個詞，但沒有“不可能”這個詞，那么“不可能”就會被切分為“不可/能”了。雖然如此，在精度要求不高的情況下，這種分詞算法還是可以接受的，畢竟速度很快～下面是基于 AC 自動機(jī)的最大匹配法的實現(xiàn)：
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 函數(shù)。在我的機(jī)器上測試，這個算法的效率大概是 4M/s，根據(jù) hanlp 的作者的描述，用 JAVA 做類似的事情，可以達(dá)到 20M/s 的速度！而用 python 做，則有兩個限制，一個是 python 本身速度的限制，另外一個是 pyahocorasick 的限制，導(dǎo)致上面的實現(xiàn)其實并非是最高效率的，因為 pyahocorasick 不支持 unicode 編碼，所以漢字的編碼長度不一，要不斷通過轉(zhuǎn)編碼的方式來獲取漢字長度。
上面說的最大匹配法，準(zhǔn)確來說是“正向最大匹配法”，類似地，還有“逆向最大匹配法”，顧名思義，是從右到左掃描句子進(jìn)行最大匹配，效果一般比正向最大匹配要好些。如果用 AC 自動機(jī)來實現(xiàn)，唯一的辦法就是對詞典所有的詞都反序存儲，然后對輸入的句子也反序，然后進(jìn)行正向最大匹配了。
基于最大概率組合的方法，是目前兼顧了速度和準(zhǔn)確率的比較優(yōu)秀的方法。它說的是：對于一個句子，如果切分為詞語 w1，w2，…，wn 是最優(yōu)的切分方案，那么應(yīng)該使得下述概率最大：
直接估計這概率是不容易的，一般用一些近似方案，比如
這里 P(wk|wk?1) 就稱為語言模型，它已經(jīng)初步地考慮了語義了。當(dāng)然，普通分詞工具是很難估計 P(wk|wk?1) 的，一般采用更加簡單的近似方案。
放到圖論來看，這就是有向無環(huán)圖里邊的最大概率路徑了。
下面介紹用 AC 自動機(jī)，結(jié)合動態(tài)規(guī)劃，來實現(xiàn)后一種方案。
def max_proba_cut(sentence):
paths = {0:([], 0)}
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 < start])
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 < len(sentence):
return paths[end][0] + [sentence[end:]]
else:
return paths[end][0]
代碼還是很簡短清晰，這里假設(shè)了不匹配部分的頻率是 e?10，這個可以修改。只是要注意的是，由于使用的思路不同，因此這里的動態(tài)規(guī)劃方案與一般的有向無環(huán)圖的動態(tài)規(guī)劃不一樣，但是思路是很自然的。要注意，如果直接用這個函數(shù)對長度為上萬字的句子進(jìn)行分詞，會比較慢，而且耗內(nèi)存比較大，這是因為我通過字典把動態(tài)規(guī)劃過程中所有的臨時方案都保留了下來。幸好，中文句子中還是有很多天然的斷句標(biāo)記的，比如標(biāo)點符號、換行符，我們可以用這些標(biāo)記把句子分成很多部分，然后逐步分詞，如下。
to_break = ahocorasick.Automaton()for i in ['，', '。', '！', '、', '？', ' ', '\n']:
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
在服務(wù)器上，我抽了 10 萬篇文章出來（1 億多字），對比了結(jié)巴分詞的速度，發(fā)現(xiàn)在使用相同詞典的情況下，并且關(guān)閉結(jié)巴分詞的新詞發(fā)現(xiàn)，用 AC 自動機(jī)實現(xiàn)的這個 map_cut 的分詞速度，大概是結(jié)巴分詞的 2～3 倍，大約有 1M/s。
最后，值得一提的是，max_proba_cut 這個函數(shù)的實現(xiàn)思路，可以用于其他涉及到動態(tài)規(guī)劃的分詞方法，比如最少詞數(shù)分詞：
def min_words_cut(sentence):
paths = {0:([], 0)}
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 < start])
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][1]:
paths[end] = (paths[start][0]+[j[0]], num)
if end < len(sentence):
return paths[end][0] + [sentence[end:]]
else:
return paths[end][0]
這里采取了罰分規(guī)則：有多少個詞罰多少分，未登錄詞再罰一分，最后罰分最少的勝出。
事實上，只要涉及到查詞典的操作，AC 自動機(jī)都會有一定的用武之地。將 AC 自動機(jī)用于分詞，事實上是一個非常自然的應(yīng)用。我們期待有更多對中文支持更好的數(shù)據(jù)結(jié)構(gòu)和算法出現(xiàn)，這樣我們就有可能設(shè)計出更高效率的算法了。
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
