中文分词算法 之 基于词典的逆向最大匹配算法
- - ITeye博客在之前的博文中介绍了 基于词典的正向最大匹配算法,用了不到50行代码就实现了,然后分析了词典查找算法的时空复杂性,最后使用前缀树来实现词典查找算法并做了3次优化. 下面我们看看基于词典的逆向最大匹配算法的实现,如下代码所示:. //取指定的最大长度的文本去词典里面匹配. //如果长度为一且在词典中未找到匹配,则按长度为一切分.
在之前的博文中介绍了 基于词典的逆向最大匹配算法,比如我们切分句子: 中华人民共和国万岁万岁万万岁,使用逆向最大匹配算法的切分结果为:[中华人民共和国, 万岁, 万岁, 万万岁],可以看到,切分出来的词是很长的,粒度很粗,如果我们想要切分出很细粒度的词,该怎么办呢?
本文介绍 逆向最小匹配算法,该算法和 逆向最大匹配算法相得益彰,一个强调细粒度,一个强调粗粒度。
使用 逆向最小匹配算法,必须 注意的一点是: 词典中不能有单字词,词的长度至少为2!我们看 逆向最小匹配算法和 逆向最大匹配算法的代码比较:
切分效果如下:
切分句子: 中华人民共和国万岁万岁万万岁 逆向最大匹配: [中华人民共和国, 万岁, 万岁, 万万岁] 逆向最小匹配: [中华, 人民, 共和国, 万岁, 万岁, 万, 万岁] 切分句子: 杨尚川是APDPlat应用级产品开发平台的作者 逆向最大匹配: [杨尚川, 是, APDPlat, 应用, 级, 产品开发, 平台, 的, 作者] 逆向最小匹配: [杨尚川, 是, APDPlat, 应用, 级, 产品, 开发, 平台, 的, 作者] 切分句子: 美国加州大学的科学家发现 逆向最大匹配: [美国加州大学, 的, 科学家, 发现] 逆向最小匹配: [美国, 加州, 大学, 的, 科, 学家, 发现]
参考资料:
1、 中文分词十年回顾
2、 中文信息处理中的分词问题
4、 由字构词_中文分词新方法
5、 汉语自动分词研究评述