Lucas Wu

(一)漫话中文分词:最大匹配,双向最大,最小词数


中文分词是指将文本拆分为单词的过程,而结果集合连接起来是等于原始的文本,而中文分词一直作为NLP领域的比较重要的领域,而大多数的文本挖掘都是以分词为基础,但中文不同于英文,英文每个单词是用空格分隔,整体语义上相对于中文难度低很多。 而业务上一直有中文分词的需求,但是之前因为在忙于另外一个项目,所以一直没有研究。 近期稍空闲开始研究了相关的中文分词算法,发现中文分词总体算比较成熟,但是其中对于未登录词或者某个特定专业领域文本大部分算法分词的结果不尽人意,需要结合多种算法或者人工词典才能达到稍微好一点的效果。 中文分词的方式一共有两种,分别为:

  1. 词典分词:如正向最大匹配算法、反向最大匹配算法、双向最大匹配算法、最少词数法等
  2. 字标注分词:如HMM(隐马尔可夫)模型等

而这几种方式很难说出谁好谁坏,比如词典分词的方式速度非常快,但对于未登录词的识别又不太好,而HMM和Pkuseg都能识别部分未登录词,但是运行速度又降下来了,这对于在实际应用场景当中是非常致命的问题,所以最大的优解就是集各家所长,比如结巴分词就使用了词典分词算法识别能识别的词,而不能识别的则继续使用了HMM模型来处理。

词典分词

基于词典的分词算法实际上就是对于类似字典的数据结构进行查询,对于未在词典内的词识别较弱和交集型歧义理解能力也较弱,比如“结婚的和尚未结婚的”,理想的情况是"结婚/的/和/尚未/结婚/的",而实际中则会被分词为"结婚/的/和尚/未/结婚/的"。 但好在词典分词的速度则非常快,词典分词目前已有非常成熟高效的解决方案,并且有非常多的工具来帮你实现相关的高效数据结构和查询方式,比如Trie树AC自动机,但在这里为了方便理解和记录,只采用了尽可能简单的方式来记录其几种算法的实现和原理。

正向最大匹配算法(Forward Maximum Matching)

正向最大匹配算法类似于人的阅读习惯,即从左到右进行识别,而其中的"最大"是基于词典中最长字符的长度作为最大的匹配宽度,然后每次根据这个宽度对文本进行切分并取出来查询词典。如果当前取出来的词能在词典当中查询当则返回,并下一次切分的开始位置为该词的位置+1。而如果当前取出的部分没有在词典中查找到,则将该部分去掉最后一个字符后再进行查找,一直重复直到匹配到了词典中的词。如果整个部分只剩余一个字符,并没有匹配到词典中的词,则将最后剩余的这个字符输出,然后根据这个字符的位置+1开始再次进行切分和查询。 比如,有一段文本"中文分词算法",字典中只包含了一个词"分词",这个时候最大的匹配宽度也为2,所以整段文本按照2个字符进行切分。第一次得到"中文"文本,查找词典并无该词,则在该部分上去掉最后的字符,得到"中",再次查询词典并无该词,此时查找结束,所以不需要再进行匹配,则这个切分记为[“中”]。 继续进行第二次切分,得到的文本为"文分",进行查询词典,第一次查询"文分"在字典中不存在,去掉最后一个字符,继续以剩余部分’文’查询第二次,未查询到,那么返回最后这个字符"文",加上次的结果记作[“中”,“文”] 继续第三次切分,得到文本"分词",进行查询词典,查询到该词在字典当中,所以直接记录在之前的结果当中,记作[“中”, “文”, “分词”]。 继续第四次切分,得到文本"算法",进行查询字典,第一次查询"算法"在字典中不存在,去掉最后一个字符,继续以剩余部分’算’查询第二次,未查询到,那么返回最后这个字符"算",加上次的结果记作[“中”, “文”, “分词”, “算”] 继续第五次切分,因为最后只剩余一个字符,所以这个时候可以不进行匹配即返回,所以最终的结果为[“中”, “文”, “分词”, “算”, “法”] 整体分词的过程本质对每个分块进行查找,并依次去掉最后字符查询,而网上还有一部分是没有使用最大宽度切分,即会对每个字符到文本结束的位置都会依次遍历,这样的方式实际上会浪费较多的资源,因为即使从头到尾依次遍历匹配,但最长词的长度是固定的,所以真正开始匹配还是从最长词的长度开始,而其余的遍历都是浪费了资源。 正向最大匹配算法具体的实现代码:

sentence = '中文分词算法' # 输入的句子
cutList = ['分词']  # 分词词典

start = 0 #设置切分起始位置
maxWidth = len(max(cutList, key=len)) # 得到字典当中最大的切分宽度
cut_result = [] # 设置一个空的分词结果

while (start <= len(sentence)):  #开始循环,如果start大于等于句子长度则停止分词
    end = start + maxWidth     # 计算每次切分的停止位置
    word = sentence[start: end] # 开始切分,文本为变量start和end的区间内字符
    while ( word ) :  # python对于空字符串会转换为False
        if ( word in cutList ) :  # 查看第一次切分后是否能在词典中匹配,如果匹配则放入最终的分词结果列表cut_result,并跳出循环
            cut_result.append(word)
            start = start + len(word) - 1  # 然后将开始位置设置为当前开始位置加上被匹配词的长度
            break 
        if (len(word[:-1]) == 0):
            cut_result.append(word) # 如果最后一个字符也没有被匹配到,那么返回最后一个字符
            break
        word = word[:-1]  # 将word去掉最后一个字符串并重新计算
    start = start + 1  # 将位置加1

print(cut_result)
#['中', '文', '分词', '算', '法'] 

反向最大匹配算法(Backward Maximum Matching)

反向最大匹配算法与正向最大匹配算法是相反的,比如"中文分词算法"文本的正向最大匹配算法在切分宽度为2的时候,是从"中文"开始切分的,而反向则是从"算法"开始切分的。 除了反向的切分,其中对于切分块内的文本依次去掉最后一个字符也变为了依次去掉第一个字符,比如正向第一个切分块"中文"后,如果没有匹配到,则去掉"文",再对"中"字符进行匹配,而反向则是拿到"算法"后,如果没有匹配到,则是去掉"算",再对"法"进行匹配。 反向最大匹配算法对比于正向最大匹配算法来说,可以解决一定的交集型歧义,比如本文"他说的确实在理",理想情况下希望的分词结果中包含"确实"这一词,而正向最大匹配算法结果为"他/说/的确/实/在理",而反向最大匹配算法的结果为"他/说/的/确实/在理"。 这两种方式很难区分到底谁好谁坏,比如上面的问题中,如果你希望的分词为"的确",但是如果使用反向的话就很难被分出来。 反向最大匹配算法具体的实现代码:

sentence = '他说的确实在理' # 输入的句子
cutList = ['的确', '确实']  # 分词词典
start = len(sentence) #设置切分起始位置为该文本的最后一个字符
maxWidth = len(max(cutList, key=len)) # 得到字典当中最大的切分宽度
cut_result = [] # 设置一个空的分词结果

while (start > 0):  #开始循环,如果start大于等于句子长度则停止分词
    end = start - maxWidth   # 计算结束位置,结束位置为开始位置减去宽度
    word = sentence[end: start] # 开始切分,文本为变量end和start的区间内字符
    while ( word ) :  # python对于空字符串会转换为False
        if ( word in cutList ) :  # 查看第一次切分后是否能在词典中匹配,如果匹配则放入最终的分词结果列表cut_result,并跳出循环
            cut_result.insert(0,word)
            start = start - len(word) + 1  # 然后将开始位置设置为当前开始位置加上被匹配词的长度
            break
        if (len(word) == 1):
            cut_result.insert(0, word) # 返回最后一个字符
            break
        word = word[1:]  # 将word去掉第一个字符串并重新计算
    start = start - 1  # 将位置减1
cut_result.insert(0, sentence[0]) # 将剩余的第一个字符添加进结果

print(cut_result)
#['他', '说', '的', '确实', '在', '理'] 

双向最大匹配算法(Bidirectional Maximum Match)

双向最大匹配算法是将正向和反向结果的颗粒度进行比较的一种算法,本质上是一种规则系统,该规则为如下:

  1. 返回词数最少的结果
  2. 返回单字词更少的结果
  3. 如果两则都相同优先返回反向最大匹配算法结果

因为双向最大匹配算法实际上是一种规则系统,只需要对结果进行判断优先返回哪种结果,所以这里就不过多的说明。但需要注意的是采用双向最大匹配算法实际上运行了两种算法,所以对于运算量来说是双倍。

最少词数算法(Minimal Word Count)

最少词数算法也被称为最少切分算法,最少词数算法的本质是将一段文本分词的结果最少,最少次数算法整个过程是将字典按照长度进行排序,首先对最长的字典中的词进行匹配字符串,如果有则切分,并继续匹配下一个字典中的词,如果没有则继续匹配按照顺序匹配。 比如"独立自主和平等互利的原则",正向匹配的结果为"独立自主/和平/等/互利/的/原则",而最少词数的结果"独立自主/和/平等互利/的/原则"。 下面为一个非常简单的实现:

sentence = '独立自主和平等互利的原则' # 输入的句子
cutList = ['独立自主', '平等互利', '独立', '自主', '和平', '平等', '互利', '原则']  # 分词词典
cutList = sorted(cutList, key=len, reverse=True) # 字典排序
for cut in cutList:
    if('/%s'%cut not in sentence and '%s/'%cut not in sentence and cut in sentence) :
        sentence = sentence.replace(cut, '/%s/'%cut)

print(sentence)
#/独立自主/和/平等互利/的/原则 

参考文档

  1. https://www.cnblogs.com/cyandn/p/10891608.html
  2. https://zhuanlan.zhihu.com/p/103392455
  3. http://www.matrix67.com/blog/archives/4212
  4. https://kexue.fm/archives/3908

#数学与算法