首页 > 编程语言 > 详细

中文分词算法 之 基于词典的全切分算法

时间:2015-05-10 02:03:28      阅读:369      评论:0      收藏:0      [点我收藏+]

?

在使用?基于词典?的分词方法的时候,如果我们解决了下面4个问题:

1、如何把一句话中所有的词找出来呢?只要词典中有就一定要找出来。

2、如何利用1中找出来的词组合成完整的句子?组合成的句子要和原句一样。

3、如何保证2中组合而成的句子包含了所有可能的词序?

4、如何从所有可能的词序中选择最完美的一种作为最终的分词结果?

那么我们的分词方法称之为:基于词典的全切分算法

?

下面我们以一个实例来说明,比如句子:中华人民共和国

假设词典中包含如下词:

1
2
3
4
5
6
7
8
中华人民共和国
中华人民
中华
华人
人民共和国
人民
共和国
共和

第一步,从头到尾依次遍历句子中的每一个字,找出以该字起始的所有的词,并保留单字供下一步使用,结果如下:

1
2
3
4
5
6
7
1、[中华人民共和国,?中华人民,?中华,?中]
2、[华人,?华]
3、[人民共和国,?人民,?人]
4、[民]
5、[共和国,?共和,?共]
6、[和]
7、[国]

第二步,利用第一步找出来的词和字组合成完整的句子,我们分析第一步的生成结果即上面显示的数据,数据的行数就是句子的长度,每一行的结果是以这个字起始,有多少个词,包括字本身,每一行的第一个字符连在一起就是原句。

我们看第一个词:中华人民共和国,光是这一个词就构成一个完整的句子了,好了我们组合完成了一个完整的句子。

接下来看第二个词:中华人民,我们选定这个词后接着选第二个词,下面就麻烦了,我们可以有3个选择,即第5行的3个词[共和国, 共和, 共],如果我们选择共和国,那么我们又组合完成了一个完整的句子。别忘了还有另外两个选择哦...

接下来看第三个词和第四个词,第五个词就不用看了,因为以第四个词以后的词为起始不可能组合成完整的句子,至少少了第一个字!

第三步,从第二步的选字词组句的分析我们可以知道,如何找出所有可能的词序组成完整的句子看上去不是很简单,这个过程就像是遍历N(N等于以上数据中第一行的字词数)颗树一样,我们需要数清楚树上有多少片叶子,这里不描述具体的算法细节,具体的算法细节请看这里,所有可能的词序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
1:[中华人民共和国]
2:[中华人民,?共和国]
3:[中华人民,?共和,?国]
4:[中华人民,?共,?和,?国]
5:[中华,?人民共和国]
6:[中华,?人民,?共和国]
7:[中华,?人民,?共和,?国]
8:[中华,?人民,?共,?和,?国]
9:[中华,?人,?民,?共和国]
10:[中华,?人,?民,?共和,?国]
11:[中华,?人,?民,?共,?和,?国]
12:[中,?华人,?民,?共和国]
13:[中,?华人,?民,?共和,?国]
14:[中,?华人,?民,?共,?和,?国]
15:[中,?华,?人民共和国]
16:[中,?华,?人民,?共和国]
17:[中,?华,?人民,?共和,?国]
18:[中,?华,?人民,?共,?和,?国]
19:[中,?华,?人,?民,?共和国]
20:[中,?华,?人,?民,?共和,?国]
21:[中,?华,?人,?民,?共,?和,?国]

第四步,从上面第三步的结果中我们可以看到,所有可能的词序有21种,我们如何从中选择最完美的一种作为最终的分词结果呢?我们可以利用ngram模型来选择,具体细节请看这篇文章:一种利用ngram模型来消除歧义的中文分词方法,我们利用ngram给上面的21种切分结果计算分值,如果分值相同,则选择切分出的词的个数最少的切分结果(最少分词原则),看下面的评分过程:

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
27
28
29
30
31
32
33
34
35
36
37
38
bigram初始化完毕,bigram数据条数:1519443
?
二元模型?人民:共和国?获得分值:3.3166249
二元模型?人民:共?获得分值:4.0
二元模型?人民:共和国?获得分值:3.3166249
二元模型?人民:共?获得分值:4.0
?
人民共和国?获得分值:3.3166249
人民共和国?获得分值:3.3166249
?
ngram分值:
????1、词个数=5 ngram分值=4.0 [中华,?人民,?共,?和,?国]
????2、词个数=6 ngram分值=4.0 [中,?华,?人民,?共,?和,?国]
????3、词个数=4 ngram分值=3.3166249?? [中,?华,?人民,?共和国]
????4、词个数=3 ngram分值=3.3166249?? [中华,?人民,?共和国]
????5、词个数=2 ngram分值=3.3166249?? [中华,?人民共和国]
????6、词个数=3 ngram分值=3.3166249?? [中,?华,?人民共和国]
????7、词个数=5 ngram分值=0.0 [中,?华,?人民,?共和,?国]
????8、词个数=4 ngram分值=0.0 [中华人民,?共,?和,?国]
????9、词个数=3 ngram分值=0.0 [中华人民,?共和,?国]
????10、词个数=4??? ngram分值=0.0 [中华,?人,?民,?共和国]
????11、词个数=6??? ngram分值=0.0 [中,?华,?人,?民,?共和,?国]
????12、词个数=5??? ngram分值=0.0 [中,?华人,?民,?共和,?国]
????13、词个数=5??? ngram分值=0.0 [中,?华,?人,?民,?共和国]
????14、词个数=6??? ngram分值=0.0 [中华,?人,?民,?共,?和,?国]
????15、词个数=4??? ngram分值=0.0 [中华,?人民,?共和,?国]
????16、词个数=7??? ngram分值=0.0 [中,?华,?人,?民,?共,?和,?国]
????17、词个数=1??? ngram分值=0.0 [中华人民共和国]
????18、词个数=4??? ngram分值=0.0 [中,?华人,?民,?共和国]
????19、词个数=2??? ngram分值=0.0 [中华人民,?共和国]
????20、词个数=6??? ngram分值=0.0 [中,?华人,?民,?共,?和,?国]
????21、词个数=5??? ngram分值=0.0 [中华,?人,?民,?共和,?国]
?????
只保留最大分值:
????1、词个数=5 ngram分值=4.0 [中华,?人民,?共,?和,?国]
????2、词个数=6 ngram分值=4.0 [中,?华,?人民,?共,?和,?国]
?????
分值相同则选择词个数最少的:[中华,?人民,?共,?和,?国],词个数:5

这里选择 [中华, 人民, 共, 和, 国] 而不是?[中华, 人民, 共和国]?的原因是:bigram数据中?人民:共?的出现频率高于?人民:共和国

由此我们知道,词典的好坏以及ngram数据的好坏直接影响了分词结果的好坏。

?

基于词典的全切分算法的Java开源实现

?

?

?

?

?

?

?

?

中文分词算法 之 基于词典的全切分算法

原文:http://yangshangchuan.iteye.com/blog/2209761

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!