跳至主要內容

2020年了，还有必要学习分词算法吗？

bbruceyuan大约 6 分钟分词分词算法实现

背景

上周，和某同学聊天的时候提到关于深度学习时代下，分词算法的必要性。这引起了我的一点思考，是的，由于最近深度学习的发展，并且由于机器算力的增加，字级别的模型开始慢慢的展露头角，字级别的的模型效果已经可以说超过词级别的模型了[1]，并且在前沿的自然语言处理中都开始有放弃词级别模型的研究，尤其是在命名实体识别之类的序列标注任务上面，但是，分词真的就没有用了吗？

答案显然是否定的。我们可以假设一个场景，如果百度或淘宝用户输入了一个句子(query)，难道会拿整个句子去做召回吗？显然是不可能的，肯定要先对 query 进行分词，进行一些纠错，改写，然后去文档库中做尽量多的匹配。

既然分词分词在真实场景下还是有用的，作为最简单的NLP入门学习算法，分词当然是初学者作为入门练习的最佳实践。那么常见的分词算法有哪些呢？最简单就是前向和后向匹配算法，HMM，CRF等等。下面主要介绍最大匹配算法的思路和代码实现。

分词是什么？

这个问题应该是没有必要提的，但是为了任务的定义，还是提一下比较好一点。给定一句话，比如

我硕士阶段在研究生命科学 我/硕士/阶段/在/研究/生命科学

有人会说，这不是我们小学的时候学的断句吗？emmmm... 事实好像就是如此，但是这对于一个小学生也能做的事情，对于机器来说确是比较难做到的。

基于词典的最大匹配算法

最大匹配算法[2]主要包括正向最大匹配算法、逆向最大匹配算法、双向匹配算法等

1. 最大正向匹配

最大正向匹配是一个非常简单且有效的方法。简单的说对给定的一段话，从左往右找，找到尽可能长的 一个片段，让这个片段存在于给定的词典中，然后讲这个片段找出来，画一条分词线，然后对这句话剩下的部分做同样的操作。如果第一个字符不是词典中任何一个词的前缀，那么这个字符单独作为一个词 (可以用字典树Trie Tree 实现，后续文章 来讲）。如果最后只剩下一个字了，那么这个字也是单独的一个词。继续以前面的“我硕士阶段在研究生命科学”为例。

第一步：初始使用整个句子去查找，查看 “我硕士阶段在研究生命科学”在不在词典中？不在。
第二步：去掉最后一个词，变成了“我硕士阶段在研究生命科”在不在词典中？不在。
第三步，再次去掉一个词，操作同理。
........
第12步，只剩下一个词了，“我”，只剩一个字了，进行分词。下次变成从 “硕士阶段在研究生命科学”开始。
第13步，重复第一步，查看 “硕士阶段在研究生命科学”在不在词典中？不在。
........
第 i 步，查看 “硕士”在不在词典中？在。那么就进行分词，下次 变成了 “阶段在研究生命科学”开始。
....... （后面同理，应该能懂了

算法的实现：

def forward_maximum_match_segmentation(string, dictionary):
    if string == "":
        return
    for idx in range(len(string), 0, -1):
        # tmp words 是前面几个字符
        tmp_words = string[:idx]
        remainder_str = string[idx:]
        if tmp_words in dictionary or idx == 1:
            # 使用迭代器，意思你就可以使用
            # for item in forward_maximum_match_segmentation(xx) 遍历分词结果
            yield tmp_words
            forward_maximum_match_segmentation(
                remainder_str, dictionary)

2 最大后向匹配算法

如果你有运行一下前向算法，那么你就可以发现，运用前向算法很容易就把上面提到的例句分错了 。具体体现在：

研究生命科学。 因为“研究生”和“生命科学”都会在字典中，那么按照最大前向匹配原则，就会匹配成 研究生，而不是 研究。 最次如果使用前向算法，最终结果为“我/硕士/阶段/在/研究生/命/科学”。

运用前向分词算法的结果是错的，最大后向匹配，可以解决一部分这种问题（词语重复问题）。最大后向匹配算法和前向算法是一样的，只是逻辑 变成从后往前了。

第一步，和前向一样，
第二步，输入变成了“硕士阶段在研究生命科学”，然后继续查看，
...... （后续逻辑和前向是一样的了

区别 ：前向是每次都是去掉后一个词，后向是去掉前一个词。

算法的实现：

def backward_maximum_match_segmentation(string, dictionary):
    if string == "":
        return
    for idx in range(0, len(string)):
        # tmp words 是后面几个字符
        tmp_words = string[idx:]
        # 剩下的就是前面的几个单词了
        remainder_str = string[:idx]
        if tmp_words in dictionary or idx == len(string) - 1:
            yield tmp_words
            backward_maximum_match_segmentation(
                remainder_str, dictionary)

以上两种算法实现参考[3]。

3 双向匹配算法

双向匹配算法当然指的是用前向算法分词一遍，用后向算法分词一遍。因为有文献[4]证明，对于中文来说，90%的句子最大正向匹配和最大反向匹配结果是一样的，剩下9%两者其中一个是正确的。剩下的，只有大约1%的句子，两者分词结果相同，但是结果其实是错的。因此双向匹配算法很常用。

双向匹配算法使用的启发式算法来选择最终结果描述如下：

1.正反向分词结果词数不同，则取分词数量较少的那个。 2.分词结果词数相同 ​ a.分词结果相同，就说明没有歧义，可返回任意一个。 ​ b.分词结果不同，返回其中单字较少的那个

具体算法实现

def bi_directional_maximum_match_segmentation(string, dictionary):
    def _count_single(res):
        # 计算单字的数量
        cnt = 0
        for i in res:
            if len(i) == 1:
                cnt += 1
        return cnt

    fm_res = list(forward_maximum_match_segmentation(string, dictionary))
    bm_res = list(backward_maximum_match_segmentation(string, dictionary))

    # 选词少的
    if len(fm_res) > len(bm_res):
        return bm_res
    elif len(fm_res) < len(bm_res):
        return fm_res

    # 如果两个完全相同 (考虑一下两者是相反的
    if fm_res == reversed(bm_res):
        return fm_res
    else:
        if _count_single(fm_res) > _count_single(bm_res):
            return bm_res
        else:
            return fm_res

Reference