Press "Enter" to skip to content

漫话中文分词:基于词典分词

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

分词一直作为NLP领域的比较重要的领域,而大多数的文本挖掘都是以分词为基础,但中文不同于英文,英文每个单词是用空格分隔,整体语义上相对于中文难度低很多。而业务上一直有中文分词的需求,但是之前因为在忙于另外一个项目,所以一直没有研究。

 

近期稍空闲开始研究了相关的中文分词算法,发现中文分词总体算比较成熟,但是其中对于未登录词或者某个特定专业领域文本大部分算法分词的结果不尽人意,需要结合多种算法或者人工词典才能达到稍微好一点的效果。

 

中文分词的方式从我目前的了解当中一共有四种,分别为:

 

 

    1. 词典分词:如正向最大匹配算法、反向最大匹配算法、双向最大匹配算法、正向最小匹配算法、反向最小匹配算法、最少词数法

 

    1. 字标注:如HMM(隐马尔可夫)模型

 

    1. 统计方法:如最大概率路径算法

 

    1. 机器学习:如北大pkuseg分词

 

 

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

 

词典分词

 

基于词典的分词算法实际上就是对于类似的字典的查询,对于未在词典内的词识别较弱,并且对于交集型歧义理解能力也较弱,比如“中国人民欢迎你”,理想的情况是”中国人民/欢迎/你”,而实际中则会被分词为”中国人/民/欢迎/你”。

 

但好在分词的速度则非常快,词典分词目前已有非常成熟高效的解决方案,并且有非常多的工具来帮你实现相关的高效查询结构,比如 Trie树
AC自动机
,但在这里为了方便理解和记录,只采用了尽可能简单的方式来记录其几种算法的实现和原理。

 

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

 

正向最大匹配算法类似于人的阅读习惯,即从左到右进行识别,而其中的”最大”是基于词典中最长字符的长度作为最大的匹配宽度,然后每次根据这个宽度对文本进行切分并取出来查询词典。如果当前取出的部分没有在词典中查找到,则将该部分去掉最后一个字符后再进行查找,一直重复直到匹配到了词典中的词。如果直到最后的一个字符也没有匹配到词典中的词,则将取出来的这部分按照单个字符进行输出,然后根据上次切分的位置+1再次进行切分和查询。

 

比如,有一段文本”中文分词算法”,字典中只包含了一个词””,这个时候最大的匹配宽度也为2,所以整段文本按照2个字符进行切分。第一次得到”中文”文本,查找词典并无该词,则在该部分上去掉最后的字符,得到”中”,再次查询词典并无该词,此时该部分长度已为最低长度1,所以不需要再进行匹配,则这个切分记为[“中”,”文”]。然后继续进行第二次切分,得到的文本为”分词”,进行查询词典,能查找到,则记为[“分词”]。然后继续进行第三次切分,得到文本””,查找词典并无该词。所以去掉最后一个字符,得到”算”,继续查找后还是没有查询到,则记为[“算”, “法”],此时已无法再进行切割,所以分词结束,最后并返回[“中”, “文”, “分词”, “算”, “法”]。

 

正向最大匹配算法具体的实现代码:

 

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的区间内字符
    start = start + maxWidth  # 此时因为已切分,所以可以在这里计算下一次的切分开始的位置
    list_res = []  # 如果切分出来的文本第一次没有被匹配,则这里存储每次被切掉的最后一个字符
    while ( word ) :  # python对于空字符串会转换为False
        if ( word in cutList ) :  # 查看第一次切分后是否能在词典中匹配,如果匹配则放入最终的分词结果列表cut_result,并跳出循环
            cut_result.append(word)
            break 
        list_res.insert(0, word[-1]) # 如果第一次没有被匹配成功,那幺每次就会去掉最后一个字符,但是这里字符需要保存并返回
        word = word[:-1]  # 将word去掉最后一个字符串并重新计算
    cut_result.extend(list_res)  # 将去掉的字符和成功匹配的词合并到最终的分词列表当中
print(cut_result)
#['中', '文', '分词', '算', '法']

 

但正向最大匹配算法会出现一种非常出乎意料的结果,比如例子中”中文分词算法”,如果词典中有[“文分”]一词,可能出现的结果为”中/文/分/词/算/法”,这是因为这里设置的最大切分宽带为词典中最长词的长度,所以这里为2,那幺每次切分的时候实际上切分结果为”中文/分词/算法”,所以即使有”文分”再词典中,也不会匹配到,因为这个词在文本中是分为两个切分块进行处理的。

 

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

 

反向最大匹配算法与正向最大匹配算法是相反的,比如”中文分词算法”文本的正向最大匹配算法在切分宽度为2的时候,是从”中文”开始切分的,而反向则是从”算法”开始切分的。

 

除了反向的切分,其中对于切分块内的文本依次去掉最后一个字符也变为了依次去掉第一个字符,比如正向第一个切分块”中文”后,如果没有匹配到,则去掉”文”,再对”中”字符进行匹配,而反向则是拿到”中文”后,如果没有匹配到,则是去掉”中”,再对”文”进行匹配。

 

反向最大匹配算法对比于正向最大匹配算法来说,可以解决一定的交集型歧义,比如”他说的确实在理”,理想情况下希望的分词结果中包含”确实”这一词,而正向最大匹配算法结果为”他/说/的确/实/在理”,而反向最大匹配算法的结果为”他/说/的/确实/在理”。

 

这两种方式很难区分到底谁好谁坏,比如上面的问题中,如果你希望的分词为”的确”,但是如果使用反向的话就很难被分出来。

 

反向最大匹配算法具体的实现代码:

 

sentence = '他说的确实在理' # 输入的句子
cutList = ['的确', '确实']  # 分词词典
start = len(sentence) #设置切分起始位置为该文本的最后一个字符
maxWidth = len(max(cutList, key=len)) # 得到字典当中最大的切分宽度
cut_result = [] # 设置一个空的分词结果
while (start > 0):  #开始循环,如果start大于等于句子长度则停止分词
    end = start - maxWidth     # 计算结束位置,结束位置为开始位置减去宽度
    if ( end < 0 ): # 判断是end是否为负数,如果为负数说明已到最后一个切分块
        end = 0
    word = sentence[end: start] # 开始切分,文本为变量end和start的区间内字符
    start = start - maxWidth  # 此时因为已切分,所以可以在这里计算下一次的切分开始的位置
    list_res = []  # 如果切分出来的文本第一次没有被匹配,则这里存储每次被切掉的第一个字符
    while ( word ) :  # python对于空字符串会转换为False
        if ( word in cutList ) :  # 查看第一次切分后是否能在词典中匹配,如果匹配则放入最终的分词结果列表cut_result,并跳出循环
            cut_result.append(word)
            break 
        list_res.append(word[0]) # 如果第一次没有被匹配成功,那幺每次就会去掉第一个字符,但是这里字符需要保存并返回
        word = word[1:]  # 将word去掉第一个字符串并重新计算
    cut_result.extend(list_res)  # 将去掉的字符和成功匹配的词合并到最终的分词列表当中
print(cut_result)
#['在', '理', '确实', '说', '的', '他']

 

反向最大匹配算法返回的分词列表中的顺序是从后往前进行排列的,但是这里可以调整算法来返回理想的顺序。

 

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

 

双向最大匹配算法本质上是将正向和反向结果的颗粒度进行比较的一种算法,但是在网上进行查询的时候,实际上出现了几种方式,比如其中一种是按照词的数量进行比较,返回较少的数量的分词解雇,但是个人认为这种方式不太认可,因为分词少并不一定代表分词就最优。在多种查询到的资料当中,我比较认可单字的词来扣分的方式,这种方案在 matrix67
中也提到过,比如文本’他说的确实在理’,正向的结果分出来为”他/说/的确/实/在理”,结果中单字词有三个,扣3分。反向的结果为”他/说的/确实/在理”,结果中单字词有一个,扣1分,那幺这个时候就取扣分最小的方案为当前的分词最优方案。

 

最小匹配算法(Minimum Matching)

 

最小匹配算法同样也分为正向、反向、双向,算法和正向最大匹配算法相差不大,但最小匹配算法的最大宽带是词典中最小词的长度,本质上最小匹配和最大匹配是颗粒度的不同,最大匹配算法强调的是粗颗粒度,最小匹配算法是强调细颗粒度,比如文本”中文分词算法”,词典为[‘中文’, ‘中文分词’],这个时候如果为最大匹配算法则结果为”中文分词/算/法”,而如果最小匹配算法则结果为”中文/分/词/算/法”。

 

最少词数算法(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

 

    1. https://zhuanlan.zhihu.com/p/103392455

 

    1. http://www.matrix67.com/blog/archives/4212

 

    1. https://kexue.fm/archives/3908

 

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注