自然语言理解初步
-
1
-
自然语言理解初步
——中文分词实验报告
自然语言理解初步
-
2
-
中文分词实验报告
一、实验目的
通过本实验了解中文分词的意义，在实现正向、逆向最大匹配分词算法
的过程中，加深对自然语言理解原理的探讨兴趣。
二、实验环境
Windows7 旗舰版 64 位
C-Free5.0 编译器
三、实验设计思路
目前较为成熟的中文分词方法主要有基于词典的（正向、逆向，双向）
最大匹配法、基于确定文法的分词法、基于统计的分词方法等，其中最大匹
配法是中文分词的一个最基础算法，由于是自然语言理解初步，更加高深的
算法尚需要时间，所以本文着重选取了基于词典的正向最大匹配法和逆向最
大匹配法来进行文本的切割。
词典选取： 算法词典的词源主要来自人民日报 199801 语料库，另外结
合了一些自选训练语料，构建了排好序的中文词典。（构建方法包括取词，去
重，排序，java 提供了相关类库，很容易便可提取）
除了分词结果的准确性，程序的性能也是至关重要的。由于本程序采用
了词典法来分词，执行过程需要检索大量数据，因此查找效率成为程序性能
的决定性因素。目前比较成熟的查找算法主要有顺序查找 O(n)、二分查找
O(logn)、哈希表查找等 O(1)。 但是若词条数目太多，导致哈希表冲突经常
发生，复杂度就不是 O(1)了。因此，本程序采用效率较优的二分查找算法，
自然语言理解初步
-
3
-
其中事先排序则采用了快速排序法。
中文处理和英文处理的一个很大不同就在于编码格式的复杂性。同样的
中文字符，在不同的汉字编码格式中，可能有不同的二进制表示。因此编程
做字符串匹配时，通常要求统一的编码格式。本程序拟采用 ANSI 格式。
四、算法设计（源代码及详细注释详见附件）
1、主函数操作流程：
N
进入中文分词系统
选择最大匹配方式（有正向，逆
向可选）
输入您所选的备用字典
选择正向最大匹配方式
输入待测语料名称
选择逆向最大匹配方式
分词结果输出到（文件名）_forward.txt
分词结果输出到（文件名）_reverse.txt
是否选择结束分词
分词结束
逆向分词
正向分词
Y
自然语言理解初步
-
4
-
2、<PosCut()>正向最大分词算法
2.1、 令i=0,当前指针pi指向输入字串的初始位置,执行下面的操作:
2.2、 计算当前指针pi到字串末端的字数(即未被切分字串的长度)n,如果n=1,
转(2.4),结束算法。否则,令m=词典中最长单词的字数, 如果n<m 令m=n;
2.3、从当前pi起取m个汉字作为词wi,判断:
(a) 如果wi确实是词典中的词,则在wi后添加一个切分标志,转(c);
(b) 如果wi不是词典中的词且wi的长度大于1,将wi从右端去掉一个字,转(a)
步;否则（wi的长度等于1）,则在wi后添加一个切分标志,将wi作为单字词添
加到词典中,执行 (c)步;
(c) 根据wi的长度修改指针pi 的位置,如果pi指向字串末端,转2.4,否则,
i=i+1,返回 2.2
2.4、输出切分结果,结束分词程序。
3、<NegCut()>逆向最大分词算法：
3.1、选取某种方式，将文章分成子句；
3.2、从语料中循环的读入每一个句子 S,保存为字符串，设定最大词长（一
般选取词典中最长词的长度为最大词长）；
3.3、如果字符串长度大于设定最大词长，则取字符串最右边的最大词长个中
文字符，作为候选词；否则取出整个字符串作为候选词；
3.4、在词典中查找这个候选词，如果查找失败，则去掉这个候选词的最左字，
重复这步进行查找，直到候选词为 1 个中文字符；
3.5、将候选词从字符串中取出、删除，回到第 3.3 步直到字符串为空；
3.6、回到第 3.2 步直到语料已读完。
