石家庄经济学院本科生毕业论文
开始 获得预处理的待分句子( STR)初始化Index=0 获得子字典最大长度并将其设为最大长度MaxLength 否 比较STR长度是否大于MaxLength 是 取STR为字符串SubStr Index位取MaxLength 长字符串（SubStr） 将SubStr在字典库中按最大长度搜索 是 是否搜索成功 切分位置加SubStr 删除SubStr最后一个字 否 是 是否SubStr大于1 否 切分标志加1(Index+1) 将str在标志位Index切分，保存分词结果到list 是 判断Index是否小于STR的长度 否 返回结果集List 结束 图3-1最大正向匹配算法
- 9 -
石家庄经济学院本科生毕业论文
3.12 最大逆向匹配算法（RMM）
最大逆向匹配算法的算法思想是：最大逆向匹配的算法跟最大正向匹配类似，不同的是扫描的方向，它是从右往左取子串进行匹配。根据算法的具体的思想，我们能够很清楚的得到MM算法的流程：
1)输入经过预处理后的待切分的句子STR,并初始化Index = STR.Length； 2)获得字典数据库内各个子字典的长度；
3)获得分词单词的长度，并和字典数据库内最长的子字典比较，如果子字典的最大长度大于要分词的长度，则取剩于要分词的字符串为最大长度，否则则以最大长度切分；
4)用二分法查找与当前最大匹配长度相同的子字典，如果找到该字典则转5，否则最大长度减一转4；
5)取得要分词的字符串SubStr，在字典里找该字符串，如果找到则将该字符串添加到List内，如果没有找到则判断SubStr是否大于1，如果大于1，则删除SubStr最后一个字转5，否则置切分标志，转6；
6)判断Index是否大于1，如果小于则转3否则保存List,退出。具体的算法流程如图3-2。
- 10 -
石家庄经济学院本科生毕业论文
开始 处理的待分句子( STR)初始化Index=STR.length 获得子字典最大长度并将其设为最大长度MaxLength 否 比较STR长度是否大于MaxLength 是 取STR为字符串SubStr Index位取MaxLength 长字符串（SubStr） 将SubStr在字典库中按最大长度搜索 是 是否搜索成功 切分位置加SubStr 删除SubStr最前一个字 否 是 是否SubStr大于1 否 切分标志加1(Index-1) 将str在标志位Index切分，保存分词结果到list 是 判断Index是否大于1 否 返回结果集List 结束 图3-2最大逆向匹配算法 - 11 -
石家庄经济学院本科生毕业论文
3.13 双向匹配算法（DMM）
双向匹配算法的算法思想是：将正向匹配与逆向匹配算法相结合起来，对于待分字符串，首先分别用最大正向匹配和最大逆向匹配算法进行分词，对于分词结果进行比较， 比较正向和反向两个最大匹配，返回分词结果，当两个方向的分词结果一致，返回字符串，当不一致，返回长度小的，当长度一致，返回反向的。这是因为统计表明，统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245，显然RMM法在切分
[2]
的准确率上比MM法有很大提高。同时本算法可以分别打出正向分词和逆向分词的结果供用户实验，还能够发现出现歧义的地方，从而为将来升级系统，消除歧义打下了良好的基础。 双向匹配算法的算法步骤如下：
1）输入待切分的句子String；
2）对String 进行预处理后分别用最大正向匹配算法和最大逆向匹配算法进行分词，对分词结果进行比较，如果分词结果完全相同则转3，如果分词结果不同则转4；
3）任意选出一种分词结果，将分词结果输出算法结束；
4）比较分词数目是否相同，如果相同则选取逆向分词结果，将分词结果输出，算法结束，否则选取分词数目较小的分词结果进行输出，算法结束。双向匹配的算法流程如图3-3。
- 12 -
石家庄经济学院本科生毕业论文
开始 输入待切分的句子String 对String 进行预处理 对预处理后的String分别进行MM和RMM得到切分结果MMResult和RMMResult 是 比较分词结果是否相同 否 比较分词数目是否相同 否 任意选择一种分词结果 是 选择分词数目较小的结果 选择RMM的分词结果
将分词结果输出 结束 图3-3双向匹配算法
3.2 基于词典的分词算法的词典机制
基于词典的中文分词很大一部分上的效率取决于词典的选择，所以分词的词典设计是中文分词系统工程开发中一个重要基础部分。因为实际中文分词系统需要在词典中反复查找所需词汇，所以如何设计出高效、易于维护的词典存储，对整个分词系统的速度有很大影响。在实际工程中，时间和空间总是相互矛盾的，即很难找到一种既占用内存小同时速度很快的算法。经过30多年无数研究者的努力，提出了很多的中文词典机制。目前最常用的词典机制
- 13 -