BBruceyuan

2020年了,还有必要学习分词算法吗?

背景

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

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

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

分词是什么?

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

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

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

基于词典的最大匹配算法

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

1. 最大正向匹配

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

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

算法的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
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 最大后向匹配算法

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

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

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

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

区别 :前向是每次都是去掉后一个词,后向是去掉前一个词。

算法的实现:

1
2
3
4
5
6
7
8
9
10
11
12
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.分词结果不同,返回其中单字较少的那个

具体算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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

[1] Is Word Segmentation Necessary for Deep Learning of Chinese Representations?
[2] 最大分词算法
[3] https://zhuanlan.zhihu.com/p/92102484
[4] 汉语自动分词研究评述


专题:

本文发表于 2020-03-06,最后修改于 2020-03-08。

本站永久域名bbruceyuan.github.io,也可搜索「 BBruceyuan 」找到我。

期待关注我的 知乎专栏微博 ,查看最近的文章和动态。


上一篇 « 友情链接 下一篇 » 深度学习时代,分词算法的真实应用实例

赞赏支持

谢谢支持~

i ali

支付宝

i wechat

微信

推荐阅读

Big Image