雷锋网 (大众号：雷锋网) 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。因而，我们只需求关怀怎样运用它就行了。官方的教程曾经很详细地引见了 pyahocoras对于互联网金融P2P企业来说，支付市场完善的标准和管理系统将彻底改变互联网金融行业的格局，不仅给从业者提供了的巨大的发展机遇，也带来了全新的挑战。ick 的根本运用办法了，这里也不赘述。（遗憾的是，虽然 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 自动机来完成，独一的方法就是对词典一切的词都反序存储，然后对输出的句子也反序，然后停止正向最大婚配了。

最大约率组合

基于最大约率组合的办法，是目前统筹了速度和精确率的比拟优秀的办法。它说的是：关于一个句子，假如切分为词语 w ₁ ，w ₂ ，…，w _n 是最优的切分方案，那么应该使得下述概率最大：

直接估量这概率是不容易的，普通用一些近似方案，比方

这里 P(w _k |w _k−1 ) 就称为言语模型，它曾经初步地思索了语义了。当然，普通分词工具是很难估量 P(w _k |w _k−1 ) 的，普通采用愈加复杂的近似方案。

放到图论来看，这就是有向无环图里边的最大约率途径了。

上面引见用 AC 自动机，结合静态规划，来完成后一种方案。

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]

代码还是很冗长明晰，这里假定了不婚配局部的频率是 e ⁻¹⁰ ，这个可以修正。只是要留意的是，由于运用的思绪不同，因而这里的静态规划方案与普通的有向无环图的静态规划不一样，但是思绪是很自然的。要留意，假如直接用这个函数对长度为上万字的句子停止分词，会比拟慢，而且耗内存比拟大，这是由于我经过字典把静态规划进程中一切的暂时方案都保存了上去。幸亏，中文句子中还是有很多自然的断句标志的，比方标点符号、换行符，我们可以用这些标志把句子分红很多局部，然后逐渐分词，如下。

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

在效劳器上，我抽了 10 万篇文章出来（1 亿多字），比照了却巴分词的速度，发如今运用相反词典的状况下，并且封闭结巴分词的新词发现，用 AC 自动机完成的这个 map_cut 的分词速度，大约是结巴分词的 2～3 倍，大约有 1M/s。

最初，值得一提的是，max_proba_cut 这个函数的完成思绪，可以用于其他触及到静态规划的分词办法，比方最少词数分词：

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]

这里采取了罚分规则：有多少个词罚多少分，未登录词再罚一分，最初罚分最少的胜出。

总 结

现实上，只需触及到查词典的操作，AC 自动机都会有一定的用武之地。将 AC 自动机用于分词，现实上是一个十分自然的使用。我们等待有更多对中文支持更好的数据构造和算法呈现，这样我们就有能够设计出更高效率的算法了。

雷锋网版权文章，未经受权制止转载。概况见。