一种基于词典的正向逐次加一字最大匹配中文分词方法

摘要

本发明涉及一种基于词典的正向逐次加一字最大匹配中文分词方法，属于计算机中文文本处理技术领域。本发明包括步骤：首先读入待切分文本，根据标点、数字、西文、图表等明显的分隔符将输入的文本进行粗切分，分割成一个个短文本；将粗切分的短文本作为进一步切分对象，设定进一步分词查找长度；取粗切分后的短文本按照正向逐次加一字的方式与字典匹配分词，直到所有短文本分词结束。本发明避免了传统正向最大匹配分词速率—准确率难以平衡的缺点，在切词速度和分词准确率方面都比传统正向和逆向最大匹配分词算法有所提高。

说明书

技术领域

本发明涉及一种基于词典的正向逐次加一字最大匹配中文分词方法，属于计算机中文文 本处理技术领域。

背景技术

随着科技的发展，人类社会已经进入了信息时代。让计算机“读懂”人类的自然语言,实现自 由的人机交互已成为美好的愿景。对于人类语言来说，词是最小的、能独立活动的、有意义 的语言单位。中文和英语、法语等西方语言存在着很大差异，西文的字和字之间有明显的空 格作为分隔符，计算机很容易根据这些空格而理解一句话的含义；而中文句子中词和词紧密 排在一起，计算机理解起来就要困难的多。中文分词是汉语信息处理的关键和前提，只有处 理好中文分词，才能让计算机理解中文、进行后续的中文信息处理，并从海量的信息中提取 有用信息为人类提供服务，实现计算机智能化。随着中文信息处理的发展，中文分词技术得 到了广泛的应用，大体上主要在下面三个领域中深入应用，起着关键的作用。1)计算机和人 工智能领域：利用中文分词成果从事自然语言理解和处理研究，如语义分析，自动摘要，知 识工程，机器翻译，专家系统和智能计算机等；2)情报信息领域：在研究中文分词与自动标 引、中文分词与情报检索和搜索引擎等技术的结合上，取得了许多可喜的成绩。3)汉语语言 学研究领域：利用中文分词来促进汉语言文字研究，如研究汉语言的特点，与其它语言的比 较，汉语言的规范等。

中文分词是中文信息处理的基础环节，也是制约其发展的一个严重“瓶颈”。近年来，中 文分词技术引起了社会各界尤其是公司和高校的重视和研究，出现了各种各样的分词方法： 双向最大匹配法、逐词遍历法、设立切分标志法、词频统计法、扩充转移网络法、双向Markov 链法、模糊聚类法、专家系统法、最少分词法、神经元网络法等多种分词方法。不同分词方 法模拟了人类分词行为的不同侧面，服务于不同用途的中文信息处理系统。总的来说，这些 方法都是三个基本方法的扩展、延伸和改进。这三个基本方法分别是：基于词典的分词方法、 基于统计的分词方法和基于理解的分词方法，它们分别代表了目前分词方法的三大发展方向。

正向最大匹配法(ForwardMaximumMatchingMethod)，所谓“最大”是指该算法总是把 以某一汉字开头的尽可能长的字串看作是一个词语，即体现出“长词优先”。当在词典中找不 到该字串时(即匹配不成功时)，再去掉最后一个汉字继续查找匹配。该方法一般简称为FMM 法。其算法思想为：设D为词典，L表示D中的最大词长，S为待切分的字串。每次从S中 取出长度为L的子串M与D中的词进行匹配。若匹配成功，则将该子串M作为一个词切 分出来，同时指针后移L个字符继续匹配；否则将子串M的最后一个字去掉，再按相同的 方法进行匹配，直到切分出所有的词。传统正向和逆向最大匹配分词算法，需要事先设定一 个匹配长度M，一般以分词词典中的最大词长作为匹配长度进行分词。它强调的是“长词优 先”，每次都要从M个字符开始匹配。若M过长，要查找多次才能切分出一个词，造成不必 要的时间浪费，分词速度不高。而M过短，有一些词长超过M的长词就不能被正确的切分 出来，无法保证分词的准确率。

为了解决上述传统正向匹配算法出现的不足，本文基于正向匹配算法提出了正向逐次加 一字最大匹配算法，较好地完善了传统算法的不足。

发明内容

本发明提供了一种基于词典的正向逐次加一字最大匹配中文分词方法，以用于解决传统 正向最大匹配分词方法造成的分词速度慢，分词结果不精确等问题，本方法不需要预先设定 最大匹配词长，避免了传统的最大匹配法因设定的最大匹配词长过长，而进行多次无用匹配， 分词速度较慢；最大匹配词长过短，又无法正确切分的情况。

本发明的技术方案是：一种基于词典的正向逐次加一字最大匹配中文分词方法的具体步 骤如下：

Step1、读入待切分文本，根据标点、数字、西文、图表等明显的分隔符将输入的文本进 行粗切分，分割成一个个短文本；

Step2、将粗切分的短文本作为进一步切分对象，设定进一步分词查找长度L，其中L取 小于词典里最大词长的长度；

Step3、取粗切分后的一个短文本的起始两个字，在词典里查找匹配；

若不存在当前输入的两个字，则表示第一个字是单字，将其切分出去；

若存在当前输入的两个字，则将查找文本的长度指针往后增加一个字，增加到三个字， 继续在词典里进行匹配；

若此三字词不存在，则表明前两个字是一个词，将其切分出去，作为一次切分的结果； 接着分词查找指针后移，取后面两个词进行新一轮的查找匹配；

若此三字词存在，则继续往后增加一个字，构成四字词，查找此四字词是否存在于词典 里，以此类推，进行匹配查找，从而进行分词；

Step4、当查找到查找长度为L时，从L的下一个字符开始，重新按照步骤Step3中以此 类推的方法进行查找匹配以及分词，直到所有短文本分词结束。

本发明的有益效果是：

1、本方法基于词典的匹配查找机制，对输入的待切分文本进行查找匹配，来确定分词 结果。分词时不预先设定最大匹配词长，而是根据词典里最大词条长度来设定一个略小于最 大词长的相应的查找长度L，避免了传统的最大匹配法因设定的最大匹配词长过长，而进行 多次无用匹配，分词速度较慢；最大匹配词长过短，又无法正确切分的情况；

2、本方法在分词响应时间以及分词准确性方面得到很好的改进。对于测试文本，利用本 发明的正向逐次加一字匹配分词方法与传统的基于词典的正向最大匹配分词，以及逆向最大 匹配分词方法在分词性能方面进行了比较，无论是准确度还是分词时间都得展现出了很好的 优势。

附图说明

图1为本发明的流程图；

图2为本发明中实施例1正向逐次加一字匹配分词方法流程图；

图3为本发明中基于词典的正向逐次加一字匹配分词方法与传统基于词典的分词方法的 精确度对比图。

具体实施方式

实施例1：如图1-3所示，一种基于词典的正向逐次加一字最大匹配中文分词方法，所述 方法的步骤为：

步骤一、粗切分；对待切分的文本进行剔除标点符号、空格、日期、数字、英文字母等 标记，将待处理的文本设为A，分成N个短文本序列S_i的集合(0＜i≤N)，即切分为S_i个短 文本，A＝{S₁,S₂,S₃,...S_N}；

步骤二、如图2所示，依次按顺序读入一个个粗切分后的短文本，记为S_i，设每个句子 序列S_i由m个字W_ij(0＜j≤m)组成，即S_i＝<W_i1W_i2W_i3...W_im>；

步骤三、将粗切分后的文本S_i进行分词。如图2所示，将文本进行分词处理。

1)设定一个略小于词典里最大词长的分词查找长度L，L一般略小于词典里最大词长；

2)在短文本S_i中顺序取起始前两个相邻的字符W_ijW_i(j+1)，初始时为W_i1W_i2，在词典中查 找匹配，若当前输入的两个字W_ijW_i(j+1)不是词典中的词，则转(3)；否则，转(4)；

3)若当前输入的两个字W_ijW_i(j+1)在词典中不存在，则表明前两个字中的第一个字是一个 词，将W_ij从句子S_i中切分出去。判断是否到S_i句尾，若是，则S_i分词结束；否则j＝j+1， 再转(2)；

4)若存在当前输入的两个字W_ijW_i(j+1)，则将查找文本的长度指针往后增加一个字，即 W_ijW_i(j+1)后加一字，增加到三个字，得到S_k＝W_ijW_i(j+1)W_ik(o＜k≤L)，继续在词典里进行匹 配，判断新读入的词是否存在于词典中。若存在，则转(5)，否则，转(6)；

5)若此三字词S_k＝W_ijW_i(j+1)W_ik存在，若此三字词存在，则继续将指针往S_k＝W_ijW_i(j+1)W_ik后增加一个字，构成四字词S_k+1＝W_ijW_i(j+1)...W_ikW_i(k+1)，查找此四字词S_k+1＝W_ijW_i(j+1)...W_ikW_i(k+1)是 否存在于词典里，若是，则继续往后逐次加一字再判断，转(7)；若不是，则把S_k切分出 去，放入分词结果；

6)若此三字词S_k＝W_ijW_i(j+1)W_ik不存在，则表明前两个字W_ijW_i(j+1)是一个词，将W_ijW_i(j+1)从 S_i中其切分出去，接着分词查找指针后移，使指针j＝j+2，再取后面两个词进行新一轮的 查找匹配。若j≤m，表明当前短文本还未完全切分，转(2)，若指针j＝m，则短文本S_i分 词结束；

7)依此类推，每次移动分词指针时判断移动之后读入的当前词数k≤L是否成立，若成 立，则继续在S_k+1＝W_ijW_i(j+1)...W_ikW_i(k+1)后逐次加一字进行判断；否则从W_i(k+1)处开始取两字字 符进行下一轮查找匹配。

步骤四、判断读入文本数i≤N是否成立，若成立，表明当前文本还未分词结束，则分词 指针增加一，i＝i+1，读入下一个句子重新按照上面的程序进行查找匹配以及分词，进行分 词直到整个输入文本分词结束；否则，说明整个文本分词结束。

实施例2：如图1-3所示，一种基于词典的正向逐次加一字最大匹配中文分词方法，所述 方法的步骤为：

设定一个略小于词典里最大词长的分词查找长度L；设待切分字符串为S＝s₁s₂s₃s₄...s_i。 从句头开始，取前两个字符s₁s₂，判断s₁s₂是否是词典里的一个词，若不是，则说明s₁是单字 词，将其切分出去，则将查找文本的长度指针往后增加一个字，增加到第三个字，取在词典 中s₂s₃进行新一轮的查找匹配；若s₁s₂是词典中的词，则往后增加一个字，判断s₁s₂s₃是否成 词，若s₁s₂s₃不是词典里的词，则表明s₁s₂是一个词，将其切分出去；若s₁s₂s₃是词典里的一个 词，则继续往后增加一个字，查找s₁s₂s₃s₄是否是词典里的词，若不是词，则将s₁s₂s₃作为一个 词切分出去，若是词典里的词，则继续往后增加一个词再来匹配。依此类推，直到整个句子 S＝s₁s₂s₃s₄...s_i切分完毕。

实施例3：如图1-3所示，一种基于词典的正向逐次加一字最大匹配中文分词方法，所述 方法的步骤为：

Step1、读入待切分文本，根据标点、数字、西文、图表等明显的分隔符将输入的文本进 行粗切分，分割成一个个短文本；例如分成一个文本“今天天气特别的好”；

Step2、将粗切分的短文本作为进一步切分对象，设定进一步分词查找长度L＝7，其中L 取小于词典里最大词长的长度，其中最大词长为12；

Step3、取粗切分后的一个短文本的起始两个字“今天”，在词典里查找匹配；经匹配“今 天”存在于词典中，那么查找文本的长度指针往后增加一个字，增加到三个字“今天天”，继 续在词典里进行匹配；经匹配“今天天”不存在，则表明“今天”是一个词，那么把“今天” 切分出去，作为一次切分的结果；接着分词查找指针后移，取后面两个词“天气”进行新一 轮的查找匹配；经匹配“天气”存在，那么查找文本的长度指针往后增加一个字，增加到三 个字“天气特”，继续在词典里进行匹配；经匹配“天气特”不存在，则表明“天气”是一个 词，那么把“天气”切分出去，作为一次切分的结果；依次类推，进行匹配查找，从而进行 分词，分词的结果为/今天/天气/特别/的/好/；具体分词的过程见表1所示；

表1正向逐次加一字最大匹配分词过程

匹配字段 匹配经过 匹配结果 今天 词典中存在 今天 天气 词典中存在 天气 特别 词典中存在 特别 的好 词典中不存在 的 单字词 的 好 单字词 好

为了验证本方法的有益效果，用本方法与传统的正向最大匹配分词方法、逆向最大匹配 分词方法(一次最大匹配字符长度为4)进行对比，传统的正向最大匹配分词方法、逆向最 大匹配分词方法的分词过程如表2、表3所示；

1)正向最大匹配分词方法：

表2正向最大匹配分词过程

匹配字段 匹配经过 匹配结果 今天天气 词典中不存在 今天天 词典中不存在 今天 词典中存在 今天 天气特别 词典中不存在 天气特 词典中不存在 天气 词典中存在 天气 特别的好 词典中不存在 特别的 词典中不存在 特别 词典中存在 特别 的好 词典中不存在 的 单字词 的 好 单字词 好

正向最大匹配的结果是：/今天/天气/特别/的/好/

2)逆向最大匹配分词方法:由右至左从待切分字符串中取子串进行匹配；

表3逆向最大匹配分词过程

匹配字字段 匹配经过 匹配结果 特别的好 词典中不存在 别的好 词典中不存在 的好 词典中不存在 好 单字词 好 气特别的 词典中不存在 特别的 词典中不存在 别的 词典中不存在 的 单字词 的 天气特别 词典中不存在 气特别 词典中不存在 今天天气 词典中不存在 天天气 词典中不存在 天气 词典中存在 天气 今天 词典中存在 今天

逆向最大匹配的结果是：/今天/天气/特别/的/好/

从上述三种方法的分词过程可以看出，虽然最终的分词结果都是相同的、正确的，但是 从分词的过程上可以清楚的看到传统的基于词典的正向、逆向最大匹配方法的分词过程都出 现了读入词不存在的重复匹配步骤，浪费了分词的时间，造成分词后词典匹配、歧义判断的 工作量。而本发明提出的正向逐次加一字最大匹配方法，几乎每个两字词都得到了一步分词 的快速、准确分词，这样分词的整体效率就得到了很大的提高，试验仿真的结论也证明了这 一点，如下表4所示。

表4三种分词方法的平均切分速率比较

分词方法 平均切分速度(字/s) 传统的正向最大匹配法 52000 传统的逆向最大匹配法 103000 正向逐次加一字匹配法 113000

将三种方法应用到本发明的试验环境中去，以一个完整的包含27万个词条的词库作为分 词词典，在硬件采用计算机内存1G及以上，软件为Windows7，使用JAVA开发语言，My Eclipse8.5开发工具的运行环境下进行模拟实验。选取了经济、科技、社会新闻、军事四个 方面大小均为0.02M左右的文章，利用三种不同的分词算法进行分词，得到的结果如图3所 示，纵坐标表示分词准确率，横坐标表示分词的领域，可以看到在这三种分词方法中，本文 提出的正向逐次加一字匹配方法和传统的正向、逆向最大匹配分词方法相比，准确率均得到 了提高。

以上实施例的实验结论表4，图3均能表明本发明的一种基于词典的正向逐次加一字最 大匹配分词方法较传统的基于词典的分词方法在分词切分速度，分词准确率方面都有很显著 的改进。

上面结合附图对本发明的具体实施方式作了详细说明，但是本发明并不限于上述实施方 式，在本领域普通技术人员所具备的知识范围内，还可以在不脱离本发明宗旨的前提下作出 各种变化。