基于一种粗切分的最短路径中文分词研究

《基于一种粗切分的最短路径中文分词研究》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、基于一种粗切分的最短路径中文分词研究摘要本论文在分析现有的分词算法并比较各种算法优缺点的基础上，提出了将正向匹配算法与逆向匹配算法所得到的结果集进行叠加，生成粗分结果集的新观点，再对生成的粗分结果集构造非负权有向图，然后应用最短路径算法求解有向图。本文提出的叠加算法着重考虑粗分结果的准确性、包容性以及粗分结果的长度。经过实验验证，该算法有效提高了汉语切分的准确性以及切分速度，同时部分解决了交集型歧义切分问题。关键字中文分词；最短路径；叠加运算1引言中文分词是中文自然语言理解和处理的重要环节，也是一个比较复杂和困难的问题。它是自动翻译、文本检索、

2、语音识别、文本校对以及搜索技术中的重要组成部分。分词就是将连续的字符串或序列按照一定的规范重新组合成词序列的过程[1]。本论文定义的分词(textsegmentation或者entation)就是对计算机不能直接理解的字符串或者序列按照一定的规则裁分并最终组合成计算机可以理解的词序列的过程。西文的行文中，空格是天然的分界符。因此，对于西文的各种处理比较直观和方便。而中文只有最简单的句与句之间的划界（比如标点符号之类），词与词之间没有明显分界符。例如一个最简单的例子，英语：Icallhersister；译文：我叫她姐姐。在西文处理中，计算机可以通

3、过空格和标点符号确定“sister”为一个独立语意单位，独自构成一个词。但是在译文中，由于没有明显标点符号分界，在没有一定规则的前提下，计算机很难理解“姐”和“姐”共同构成一个语意单位。2中文分词技术概述2.1中文分词技术中存在的难题如引言中所述，中文自然语言的理解和处理远比西文语言复杂得多，主要体现在以下几个方面[1]：(1)分词的规范问题：词的确切概念难以标准化，词的应用领域不同，使得分词规范难以统一，需要达到的分词效果也有很大区别。(2)歧义切分：对于特定的句子或字符串可能存在多种切分方法，不同的切分方法具有不同的含义，因此会导致组合型歧

4、义和交集型歧义。(3)新词识别：汉字系统是一个开放性系统，可能不断有新词产生，最典型的比如：人名、地名以及各类术语，分词系统必须不断更新分词词典。(4)分词理解的先与后：由于计算机需要靠词的信息来理解文章，因此它只能采用先分词后理解的方法，而分词需要以理解为基础，理解必须先分词。由此产生的逻辑问题决定了不可能有百分之百正确的分词方法。2.2中文分词技术发展现状目前，已经有很多比较成熟的汉语分词技术。邹海山等在现有分词技术的基础上提出了一种基于词典的正向最大匹配和逆向最大匹配相结合的汉语分词方案，可以高效准确的实现中文文档的主题词条抽取和词频统计

5、；应志伟等基于一个实际的文语转换系统，改进最大匹配算法，从实用角度解决多音字的异读问题和中文姓名自动识别问题；欧振猛、余顺争采用基于自动建立词库的最佳匹配方法进行中文分词；韩客松等主要从知识的自动获取出发，介绍了研究中的汉语语言无词典分词模型系统[4]。2.3中文分词算法综述中文词语分词采取的主要步骤是：先采取最大匹配、最短路径、概率统计、全切分等方法，得到一个相对较好的粗分结果，然后进行排歧、未登录词识别，最后标注词性。例如：北大计算语言所分词系统采用了统计方法进行词语粗分，北航1983年的CDN”，其中每一个字母代表一个字。采用正向匹配算法

6、的切分结果为：AB/CD/EF/GH/I/JKL/MN；采用逆向匹配算法的切分结果为：ABC/DE/F/GH/IJ/KLM/N。如果按照常规方法叠加，可能在有向图的顶点中同时存在AB与ABC，这样构成的有向图会严重影响整个切分效率和准确性。本文采用的叠加方法避免了上述情况的发生，如下描述：正向切分按照切分结果顺序排列Lz，逆向切分按照切分结果倒序排列Lr。对于Lz与Lr，从某一个切分词in{length（Lz），length（Lr）}）开始比较，保留词W应该是两者中长度最大的。根据保留词从Lz和Lr中取得下一个比较词的开始字符，重复上述过程直到

7、Lz与Lr中长度最小的结果集比较完毕。这样就能保证有向图中的顶点唯一，顶点个数最少。3.2构造非负权图用给定的字符串构造非负权图的方法如下所述：①对于给定语句S（从构成来看由许多单字组成，而表达的意义是由多个语义单位构成）；②根据提供的统一分词词典，按照正向最大匹配算法找出字符串中所有可能的语意对象或者词，求得构词集Vd={vd1,vd2,…,vdn}；③如同②，按照反向最大匹配算法找出字符串中所有可能的语意对象或者词；求得构词集Vr={vr1,vr2,…,vrn}；④对②与③的构词集Vd与Vr按照本论文算法进行叠加运算，连同语句中所有的单字集

8、Vs取得无负权图所有构词集V={v1,v2,…,vn}，边权值定义为.权图如图1所示。3.3求解非负权图的算法描述[1]假设P(i,j)是顶点集N中n