正向最大匹配法算法如下所示:
逆向匹配法思想与正向一样,只是从右向左切分,这里举一个例子:
输入例句:S1=”计算语言学课程有意思” ;
定义:最大词长MaxLen = 5;S2= ” “;分隔符 = “/”;
假设存在词表:…,计算语言学,课程,意思,…;
最大逆向匹配分词算法过程如下:
S2=””;S1不为空,从S1右边取出候选子串W=”课程有意思”;
查词表,W不在词表中,将W最左边一个字去掉,得到W=”程有意思”;
查词表,W不在词表中,将W最左边一个字去掉,得到W=”有意思”;
查词表,W不在词表中,将W最左边一个字去掉,得到W=”意思”
查词表,“意思”在词表中,将W加入到S2中,S2=” 意思/”,并将W从S1中去掉,此时S1=”计算语言学课程有”;
S1不为空,于是从S1左边取出候选子串W=”言学课程有”;
查词表,W不在词表中,将W最左边一个字去掉,得到W=”学课程有”;
查词表,W不在词表中,将W最左边一个字去掉,得到W=”课程有”;
查词表,W不在词表中,将W最左边一个字去掉,得到W=”程有”;
查词表,W不在词表中,将W最左边一个字去掉,得到W=”有”,这W是单字,将W加入到S2中,S2=“ /有 /意思”,并将W从S1中去掉,此时S1=”计算语言学课程”;
S1不为空,于是从S1左边取出候选子串W=”语言学课程”;
查词表,W不在词表中,将W最左边一个字去掉,得到W=”言学课程”;
查词表,W不在词表中,将W最左边一个字去掉,得到W=”学课程”;
查词表,W不在词表中,将W最左边一个字去掉,得到W=”课程”;
查词表,“意思”在词表中,将W加入到S2中,S2=“ 课程/ 有/ 意思/”,并将W从S1中去掉,此时S1=”计算语言学”;
S1不为空,于是从S1左边取出候选子串W=”计算语言学”;
查词表,“计算语言学”在词表中,将W加入到S2中,S2=“计算语言学/ 课程/ 有/ 意思/”,并将W从S1中去掉,此时S1=””;
S1为空,输出S2作为分词结果,分词过程结束。
相应程序示例:
准备文件:建立一个词表文件wordlexicon,格式如下
- 计算语言学
- 课程
- 意思
输入文件:test,格式如下
- 计算语言学课程有意思
编译后执行如下:SegWord.exe test,输出分词结果文件:SegmentResult.txt
源代码如下:
|
|
主程序main.cpp
|
|
补充说明:如果使用正向匹配法,请将源代码中的相关注释 “//“互换。