毕业论文 (初稿).doc

毕业论文 (初稿) 摘要在中文信息处理中，文本相似度的计算广泛应用于信息检索，机器翻译，自动问答系统，文本挖掘，论文抄袭识别，其中的中文分词环节在搜索引擎，自然语言的处理中起着至关重要的作用，长期以来一直是人们研究的热点和难点。 对于中文文本相似度计算，分词是基础和前提，采用高效的分词算法能够极大地提高文本相似度计算结果的准确性；分词中最关键的问题是消歧与未登陆词的识别，本文采用词性转换概率表来进行分词的消歧处理，使用有向拓补图的最短路径来进行分词的处理，得到了比较好的效果。 在计算相似度的过程中使用了词频与词序相结合的方法，使用TF-IDF特征法和二部图的最大匹配来计算词频的相似度，但这种方法在颠倒句子中词的顺序时也会得到相同的相似度，必须使用一种能区分词序的算法，马尔科夫模型的状态转移矩阵表示一个词转移到另一词的概率(本文把单个词语作为马尔科夫模型中的一个状态来看待)，后在文本相似度计算中，使用一种将最长公共子序列、马尔科夫状态转移矩阵和TFIDF相结合的算法得到结果。 本文使用现代汉语词典与紫光输入法中提供的文本格式词库，来制作适合本项目用的特定格式的索引词库，极大地提高了分词的效率，词性的标注使用1998年人民日报的词性标注，最后测试使用新浪，搜狐，人民网，新华网等各大新闻网站的文本新闻作为测试数据集得到了较好的效果，较准确地统计了两文本文件的相同语数，相似度，并高亮显示相同的部分数据。 在网上信息量迅速膨胀的同时，网络搜索引擎、自动分类、信息抽取等信息技术也在研究和成熟之中，为人们高效、准确地获取信息提供了有利的保证。 网络信息资源以文本、图像、视频、音频等形式存在，在我国，据中国互联网发展统计报告，文本信息占网上资源的70。 这些电子形式的数据为广大学者和师生提供丰富的信息资源和便利的交流机会，促进科学技术的发展。 与此同时，电子资源获取的便利及电子资源本身简单的“复制“粘贴功能，为学术论文的抄袭与剽窃等不道德行为提供了方便。 我国近年来，学术论文的抄袭与剽窃事件迭起，因抄袭他人论著而被曝光，甚至走上法庭被告席的案件屡有发生。 这种行为不仅侵害了作者的权益，而且严重破坏了学术发展的生态环境，损害了学术共同体的尊严，还影响到我国科研水平和科技竞争力的提高，损害了国家和公众的利益。 因此，学风问题已成为全社会众矢之的，“学术打假的呼声日甚。 当今世界以信息技术为代表的现代科技日新月异，特别是现在以新一代互联网应用为核心的科学技术，使得人们以一种以前无法想象的速度在影响着人的生活，并且正在对人类社会发展产生不可估量而深远的影响。 如何在海量的信息中迅速的查找相关信息变得异常重要，对于这个问题的研究和探索不仅会带来社会效益，同时也会带来可观的经济效益，两个最显著的例子国际上，近几年Google的股价超过了Microsoft(前者几乎是后者的20倍)；在国内，百度的影响力也是大家人所共知的事实。 这些发生在现实生活中的事情说明了目前信息检索具有多么好的前景和用途，它彻底的改变了人的生活方式。 而信息检索一个最基础和最关键的东西就是如何正确的判断网页或者文本的相似度，如果相似度判断不理想的话，就会出现一些重要信息的丢失或者遗漏，甚至错误的产生。 1.2课题研究的目的要想更好的计算文本的相似度，就需要有高效并且同时具有高准确率的文本相似度计算方法。 文本相似度是表示两个或者多个文本之间匹配程度的一个度量参数，相似度数值大，说明文本相似度高；反之文件相似程度就低。 对于文本分类、文本聚类、计算机智能问答系统以及网页去重等其他很多领域，文本相似度的精确计算问题都是进行信息处理的关键。 在信息检索中，为了提高检索的查全率和查准率，更是需要对文档进行适当的文本相似度计算，然后进行分类、聚类和相关性反馈操作，这些都需要计算文本之间的相似度。 简而言之，文本相似度研究的目的就是要更好的服务以上所提到的几个关键领域，使得它们能够提高准确率或者效率。 完全避开了诸如在欧氏空间中求相似度的大量乘法运算，因此，可以较大的提高1.3国内外文本相似度基本研究概况1.3.1国外文本相似度基本研究概况目前，国内外有很多学者在研究文本相似度计算问题并且已经有很多文档相似度模型被提出并得到广泛应用，如字符串相似度、文档结构相似度以及统计相似度等模型。 字符串相似度模型将文档构成的基本单位视为字符串，通过将一个字符串转换为另一个字符串的替换、插入和删除操作次数或最大匹配子字符串来计算相似度，如Levenshtein1距离和Likelt2方法。 Nirenberg3等也提出了两种串匹配的方法，即更规范的“切块+匹配+重组”方法和整句级匹配的方法。 这两种方法所采用的相似度衡量机制都是词组合法。 该系统的相似度计算采用罚分制，两个句子匹配所得到的总罚分值由句子中每个对应单词对的比较所得的罚分组合而成。 文档结构相似度模型45通过文档结构上的相似程度来计算文档的相似度，如Lambros6等提出同时依据句子的表层结构和内容计算相似度的方法。 在计算相似度时，系统使用了两级动态规划技术，应用动态规划算法允许在两个长度不同的句子之间计算语句相似度。 统计相似度模型如Gerard Salton和McGill78于早期提出的向量空间模型(Vector Space Model，VSM)，它的思想是把文档简化为以特征项的权重为分量的向量表示，通过词频统计与向量降维处理来计算相似度。 基于向量的文本相似度计算方法是目前主流的文本相似度计算方法，该方法将要比较相似度的文本根据文本中的词语将文本映射为n维空间向量，然后通过比较向量间的关系来确定文本间的相似度，其中最常见的方法是计算向量间的余弦值，但传统向量空间模型的缺点是模型中各词语间相互独立，无语义上的联系。 因此，广义向量空间模型(Generalized VectorSpaceModel，GVSM)就利用文本而不是用词来表示词语之间的关系。 现在研究的主流方向就是基于向量空间模型VSM)。 除了以上的模型以外还有一些其他方法被提出和发展。 如挪威Agdcr大学的Vladimir Oleshchuk9等人提出基于Ontology(本体)的文本相似度比较方法，将本体论引入了文本相似度计算，它能计算文本的语义相似度。 此外还有学者在研究句子间相似度的计算，如哥伦比亚大学的Carbon ellJ等人的最大边缘相关的MMR(Maximal MarginalRelevance)方法。 学者Chris HQDing10采用隐性语义索引模型LSI(Latent SemanticIndexing)方法，还有Belkin和Croft11于1992年提出的概率模型等。 1.3.2国内文本相似度基本研究概况在国内，国内学者潘谦红、王炬、史忠植 (1999)相似度，建立了文本属性重心剖分模型，通过坐标点与坐标点的距离计算关键词与关键词的相关性，通过坐标点与单纯形的关系计算关键词与文本的相关度，通过单纯形与单3中山大学硕士学位论文基于知网的中文文本相似度计算研究纯形的关系计算文本与文本的相似性。 张焕炯、王国胜、钟义信 (xx)于汉明距离的文本相似度计算，该方法提出了汉明码概念。 与其它的文本相似度计算公式相比较，因该方法只是利用模2加等运算，其方便性是不言而喻的，它12提出利用属性论计算文本13提出了基速度。 其次，它跳出了传统的借用空间的理念，而是用码字的方法来表征文本信息的特征，可以不仅限于关键字等孤立的信息，这为联合的描述文本的信息提供了可能。 晋耀红 (xx)内容抽象成领域(静态范畴)、情景(动态描述)、背景(褒贬、参照等)三个侧面，从概念层面入手，充分考虑了文本的领域和对象的语义角色对相似度的影响，重点针对文本中的歧义、多义、概念组合现象，以及语言中的褒贬倾向，实现了文本间语义相似程度的量化。 此外还有霍华、冯博琴 (xx)矩阵矢量相乘的文本相似度计算方法，能够减少计算和存储空间的开销。 该方法仅对非零元素存储和表示，然后用压缩稀疏矩阵矢量相乘的方法计算文本和查询的相似度，可通过给定相似度阈值来判定一个文本是否和查询相似。 各种文本相似度计算方法均在特定领域取得了良好的效果，但还都存在着缺点与不足，尚需进一步加以改进。 预计达到的目标，关键理论和技术，技术指标，完成课题的方案及主要措施。 15提出了基于语境框架的文本相似度计算方法，它把文本16提出的基于压缩稀疏1.4本文研究内容和内容安排1.4.1本文研究内容 (1)中文分词中词典的建立与存取结构的设计，分词机制的好坏决定匹配算法的时间复杂度，认真研究词典机制分析算法的时间复杂度，得到较好的词典存储机制。 (2)研究一些常用的分词算法，分析各自的优点与缺点，充分分析各算法的时空复杂度，进而设计适合于本项目的算法。 (3)文本文件的存储结构研究，以及二部图最大匹配在文本相似度中的应用。 (4)TF-IDF方法；读取分词后的文章，每一词作为一结点插入树中，若存大该结点则将其TF值加1，若无则插入结点；通过该方法结合二部图最大权值匹配可以较准备地计算词频相似度。 (5)马尔科夫模型状态转移矩阵的生成；将一个词语作为转移矩阵的一个状态来看待，继而生成状态转移矩阵，最长公共子序列的求取；马尔科夫模型与最长公共子序列的结合用于计算词序对相似度的影响。 (6)介绍本文文本相似度的计算模型，马尔科夫模型、TF-IDF方法与二部图的最大权值匹配在计算相似度的结合。 (7)项目的测试及运行结果分析。 具体的章节内容第1章为绪论部分，主要介绍本文研究的目的和意义，介绍国内外研究现状。 第2章中文分词中词典存储机制的建立。 第3章介绍常用的分词算法以及复杂度分析，最终设计实现适用于本系统的算法并分析其时间算杂度与空间复杂度。 第4章文本文件的存储结构研究，以及二部图最大匹配在文本相似度中的应用。 第5章介绍用于计算词频相似度的TF-IDF方法的原理和其算法实现。 第6章通过引入马尔科夫模型与最长公共子序列来计算词序对文本相似度的影响。 第7章介绍本文文本相似度的计算模型，马尔科夫模型、特征向量法与二部图的最大匹配在计算相似度的结合。 第8章项目的测试及运行结果分析。 2.中文分词词典机制2.1传统词典机制想要提高机械式分词算法的执行效率，就要降低匹配算法的时间复杂度，而个匹配算法的时间复杂度，从很大程度上取决于匹配数据的存储结构(在机械式分词算法中，最重要的就是分词词典的存储)下面介绍几种传统的分词词典机制； (1)基于整词二分的分词词典机制该词典的存储机制把词典分为词典正文、词索引表、首字Hash表等三级。 词典正文是以词为单位的线性表，词索引表是指向词典正文中每个词的指针表。 通过首字Hash表的散列函数和i司索引表很容易确定指定词在词典正文中的可能位置范围，进而在词典正文中通过整词二分进行定位。 23: (2)基于TRIE索引树的分词词典机制TRIE索引树是一种以多重链表形式表示的键树。 基于TRIE索引树的分词词典机制有首字散列表和TRIE索引树节点两部分组成。 TRIE索引树的优点是在对被切分语句的一次扫描过程中，不需预知待查询词的长度，沿着树链逐字匹配即可；缺点是它的构造和维护比较复杂，而且都是单词树枝(一条树枝仅代表个词)，浪费了一定的空间。 20菠菜菠罗播报播放伯父泊船驳回驳船伯爵勃然菠播伯驳泊菜罗报放父爵图21图222.2一种新的词典机制三级索引TRIE树结构在上一节介绍了几种传统的分词词典机制，通过介绍，可以了解到已有的词典机制都存在很明显的优缺点。 对于基于整词二分的词典机制，词典结构简单，维护容易，但由于采用的是全词匹配，所以速度较慢。 而对于TRIE树，采用逐字匹配，速度较快，但词典的存储数据结构复杂，较难维护。 而对于第三种相当于两种算法的折中，对两种算法的优点都不能全部发挥。 为了最大程度的提高算法的匹配效率和词典的丁维护性。 设计了种新的分词词典存储结构三级索引TRIE树结构。 通过对紫光输入法中词汇长度的统计得到如下结果图23要提高分词效率必须提高单字词，双字词，三字词的识别效率这样才能使得整个分词算法的效率，因而我们使用三级索引结构，第一级索引采用GB2312码映射，线性时间，第二级第三级索引结构可使用堆结构，查找频率较高的点较靠近堆顶结构，查找时间较快，但由于堆需要时常更新索引文件不断地读出写入将耗费大量的I/O时间。 因而使用二分查找法来代替。 半阿尔卜布价架节晶扩函德杜巴德杜体张域数夫拉尔扎尔得卡卡滋巴罗娃尔拉努扎科尔图243.中文分词算法的设计3.1中文分词概述中文分词是中文自然语言理解和处理的重要环节，也是一个比较复杂和困难的问题。 它是自动翻译、文本检索、语音识别、文本校对以及搜索技术中的重要组成部分。 分词就是将连续的字符串或序列按照一定的规范重新组合成词序列的过程1。 本文定义的分词(Text Segmentation或者Word Segmentation)就是对计算机不能直接理解的字符串或者序列按照二定的规则裁分并最终组合成计算机可以理解的词序列的过程。 西文的行文中，空格是天然的分界符。 因此，对于西文的各种处理比较直观和方便。 而中文只有最简单的旬与句之间的划界(比如标点符号之类)，词与词之间没有明显分界符。 3.2中文分词技术3.2.1中文分词主要问题 (1)分词的规范问题词的确切概念难以标准化，词的应用领域不同，使得分词规范难以统一，需要达到的分词效果也有很大区别。 核心词表问题分词需要有一个核心词表，凡属于该词表的词，在分词时就应该切分出来。 对于“琵琶”、“沙发”、“造次”这样的序列，没有人怀疑它们是一个不能切开的整体；对于“人民”、“计算”、“忽然”、“所以”等序列，绝大多数人也认为不能切开；但是，对于“铁路”、“公路”、“水路”、“海路”、“大路”、“小路”等序列，哪些应该收进核心词表，哪些是单字词组成的短语，就存在很大分歧。 词语素问题语言学家认为，现代汉语中“民”是语素而不是词。 但是“警察为民除害”如何切分呢?“民”不是词，“为民”是介词短语，中间缺了词层面，显然不合适。 把“民当作词也有问题，因为“民”与“人民不同，只能用在“为民请命“以民为本”、“亦兵亦民”等十分受限的上下文环境中。 实际上，“民”在古代汉语中是词，演变到现代汉语时成了非词语素。 但是，现代的书面汉语并非纯粹的现代汉语，其中夹杂着不少文言成分，如“为民除害”、“以逸待劳”、“帮困济穷”等等。 词缀问题“者”字单用是没有意义的，因此“成功者”、“开发者”内部不能切开。 依据这个标准，“克服许多困难而最终获得成功者”、“开发中国第一个排版软件者”也不能切开，但这样复杂的结构与词的定义相矛盾。 又如职务名“教育局长”，语义上理解为“教育局之长”，切成“教育局长”、“教育局长”、“教育局长”或不予切分，都存在语义上的问题。 此外，还有词与短语(词组)的划界问题，群众语感与语言学标准的差异，这些都对汉语切分单元的划定造成困难。 不同应用对词的需求不同研究自动分词软件系统一定要满足某种需要，而各种不同目标的应用对词的需求是不同的，甚至是有矛盾的。 因此，很难采用统一的通用的标准来评价分词系统的性能。 A以词为单位的键盘输入系统为了提高输入速度，一些高频词组(甚至只是频繁连接的两个字)也作为输入的词单位，如“这是”、“这一”、“再不”、“不够”、“不多”、“不在”等。 B检索系统检索系统的词库注重术语和专有名词，并且倾向于较小的分词单位。 比如，“并行计算机”应切成“并行计算机”，使得无论用“并行计算机”还是用“计算机”检索，都能查到。 C校对系统校对系统将含有易错字的词和词组作为词单位，如许多人“作”，“做”分不清。 计算机自动判别时，若把它们当作单字词也不好区分，但在同前后文构成的词或词组中往往可以有确定的选择，故应把有关的词和词组都收进词库，如“敢做”、“敢做敢为”、“做”、“做出”、“看作”、“作为”等。 D简繁转换系统“卤”的繁体形式有“卤”和“涵”，它的简繁转换是非确定的。 但在词和词组的层面上，它的转换常常是确定的。 比如“盐卤(滴)”、“卤水(涵)”，“卤族(卤)”“卤莽(卤)”等。 为了提高简繁转换的自动性，简繁转换系统把这类词或词组收进词表。 E.语音合成系统语音合成系统收集由多音字组成的词和词组作为分词单位如“补给(ji)”、“给(ji)水”，因为在这些词或词组中，多音字“给”的音是确定的。 对于这个问题，我们迫切希望有一个权威的核心词表供使用，使得各个系统的分词标准统一，分词准确率的测试才真正有了意义，分词系统便可进行真正的比较。 基于字位的分词方法可根据需要针对特定要求制定相应的训练数据，如果训练数据分词标准变化，分词结果便会相应的发生变化，得到用户需要的结果。 但这种方法受限性很大，没有在根本上解决个问题。 如果分词标准发生变化，必然要求修改人工标注的语料库，这要耗费很大的人力和物力。 只有得到人工标注好的语料库，基于字位的分词结果才会做出相应的改变。 由此可以看出，权威的分词词表对于分词技术的发展具有重大的意义。 (3)歧义切分对于特定的句子或字符串可能存在多种切分方法，不同的切分方法具有不同的含义，因此会导致组合型歧义和交集型歧义。 歧义切分字段指的是同样的一串汉字，按照不同的方法，可以切分成不同的结果。 在字符串“提高人民生活水平”中，“提高”、“高人、“人民、“民生”、“生活、“活水”、“水平”都是词，词和词之间交叉，怎样让没有知识的计算机将其正确地切分成“提高人民生活水平”，就是排除切分歧义的问题。 歧义字段在中文文本中是普遍存在的，据统计，在汉语文本中，歧义现象的出现概率约为1110(梁南元90)。 因此，对歧义切分字段的处理能力是影响汉语自动分词系统精度一个重要因素。 实践表明，只用词典进行机械分词，其精度不可能高，虽然有时也能满足一些标准不高的需要，但不能满足中文信息处理高标准的要求。 (梁南元，1987)最早对这个现象进行了比较系统的考察。 他定义了两种基本的切分歧义类型定义1汉字串AJB被称作交集型切分歧义，如果满足AJ，JB同时为词(A，J，B分别为汉字串)。 此时汉字串J被称作交集串。 定义2汉字串AB被称作多义组合型切分歧义，如果满足 (1)A，B，AB同时为词； (2)中文文本中至少存在一个自订后语境C，在C的约束下，A，B在语法和语义上都成立。 这两种歧义是比较典型的歧义，其中交集型歧义约占全部歧义的85以上。 如果要解决这样的歧义问题，通过在分词系统基础上提供进一步的语法、语义知识才有可能对歧义切分做出相对正确的决策。 排除歧义常常使用词频、词长、词间关系等信息，比如“真正在”中，“真”作为单字词的频率大大低于“在”作为单字词的频率，即“在”常常单独使用而“真”作为单字词使用的可能性较小，所以应切成“真J下在”。 有时切分歧义发生在小段文字中，但为了排除歧义，需要看更多的文字信息。 如“学生会”既可能是一个名词，也可能是“学生会”，这就需要观察后续的文字信息才能判断。 在“学生会主席”中前者的可能性相当大，而在“学生会去”中就倾向于后者了，在“学生会组织义演活动”中，就目前的信息是解决不了歧义问题，两种标注结果都有可能，即“学生会组织义演活动”和“学生会组织义演活动”。 这时就需要观察更多的语境信息才能真正确定下来。 早期的消歧方法主要有“松弛法，“扩充转移网络，“短语结构文法；“神经网络”，“有限状态自动机”，“隐马尔可夫模型”，“Brill式转换法”等，都对消歧的方法做了多方面的研究。 后来又有利用词频以及语素(自由抑或约束)、切分歧义表层结构等简单信息进行消歧，还有通过句法分析进行消歧。 基于相似度的消歧方法主要利用输入与训练数据中实例问的相似度来进行消歧。 典型的相似度计算方法有向量空间模型和特征距离方法。 根据词义消歧所使用的资源，可以分为基于人工智能、基于知识、基于语料库等方法。 基于人工智能的方法始于60年代初，当时主要目的在于解决自然语言理解的问题。 主要包括符号主义方法(Symbolic methods)和连接主义方法(Connectionist methods)。 进入80年代，大规模词汇资源的出现，消歧方法逐渐转为基于经验知识的方法，除了机读词典、常用词义消歧知识、还有同义词词典(Thesaurus，如叙词表)、语义词典(Computational lexicon，如WordNet)，如基于词典的词义消歧主要包括利用词义的定义消歧；利用语义词典消歧。 近年来，语料库语言学的兴起，基于语料库的消歧逐步的成为主要的方法。 其正确率在7090。 当前，国内对歧义字段切分提出多种方法，取得了一定的成效。 (3)新词识别汉字系统是一个开放性系统，可能不断有新词产生，最典型的如人名、地名以及各类术语，分词系统必须不断更新分词词典。 未登录词包括各类专有名词(人名、地名、机构名、商标名等)和术语、缩略词、新词等等。 “黄大海发明爱尔肤护肽液”需要切分成“黄大海发明爱尔肤护肤液”，并需要识别出“黄大海”是人名，“爱尔肤”是商标名，“护肤液”是术语名词。 专有名词中还包括对外国和外族名的音译名，如“斯普林菲尔德是伊罩诺州首府”，“丹增嘉措70多岁了”，其中的美国地名、藏族人名都需识别。 人类在识别未登录词时主要有两方面一方面，某几个汉字是否与某一类型的词比较相似，是否符合该类词的一般组成规律，另一方面，如果把这几个汉字当作一个未登录词，是否整个句子会更通顺，更易于理解。 现有的这一方面的研究工作多从前一方面来预测可能的某一特定类型的未登录词，如人名、地名、外语音译词等，取得了一些比较好的成果。 其实人在理解句子的时候，后一方面的因素同样起着相当重要的作用。 但这种判断不仅仅用到了词语方面的知识，更多地用到了句法、语义甚至语境方面的知识，而在计算机自动分析中，未登录词的识别往往处于词法分析阶段，还几乎没有或只引入了极少量的句法和语义知识，因此在这一阶段实现这种判断是非常困难的。 未登录词的识别对各种汉语处理系统不仅有直接的实用意义，而且起到基础性的作用。 因为各种汉语处理系统都需要使用词频关系信息，而这些信息都是计算机对大规模语料自动分词后统计出来的，如果自动分词中不识别未登录词，统计到的信息就会有很大误差。 比如，一个分词系统若不做中外人名识别，分词后进行词频统计，会发现“张”、“王”、“李”、“刘、“尔”、“斯的频率比“却”、“如”、“你”的频率还要高，用这样的统计结果作为汉语处理系统的分析依据，势必将严重影响系统的性能。 图313.2.2中文分词的处理方法 (1)基于字符串匹配的分词方法这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功。 按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大匹配和最小匹配。 常用的几种机械分词方法有，正向最大匹配法、逆向最大匹配法、逐字匹配法。 还可以将上述各种方法相互组合。 由于汉语单字成词的特点，正向最小匹配和逆向最小匹配一般很少使用。 一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。 实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过利用各种其它的语言信息来进一步提高切分的准确率。 机械分词算法简单，实现起来也比较容易。 但是由于自然语言表达方式的多样性及语句结构的复杂性，新的词汇不断出现，这使得机械分词面临诸多挑战，严重影响了分词的准确度 (2)基于理解的分词方法这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。 其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。 这种分词方法需要使用大量的语言知识和信息。 由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试验阶段。 (3)基于统计的分词方法这种方法又称无词典分词，它是通过对文本的统计，让计算机自己判断什么是词。 其主要思想是，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词，因此可以根据字符串在语料库中出现的统计频率来决定其是否构成词。 但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常用字组，并且对常用词的识别精度差，时空开销大。 到底哪种分词算法的准确度更高，目前并无定论。 对于任何一个成熟的分词系统来说，不可能单独依靠某一种算法来实现，都需要综合不同的算法，在实际应用中要根据具体的情况来选择不同的分词方案。 3.2.2本文采用的有向拓扑图的最短路径算法图32初始化拓补图算法基本思想设待分字串S=c1c2,其中ci(i=1,2,n)为单字，n为串的长度，n=1。 建立一个节点数为n+1的切分后的有向无环图，各节点的编号依次为V0V1V2Vn。 般采用贪心算法或简单扩展法求最短路径。 图33算法描述 (1)相邻结点Vk-1,Vk之间建立有向边,边对应的词默认为Ck(k=1,2,n)。 (2)如果w=cici+1cj,(0,边对应的词为w。 (3)重复上述步骤 (2),直到没有新路径产生。 (4)从产生的所有路径中，选择路径最短的作为最终分词结果。 初始化拓补图结束wordLen=2wordLen+=BufferLenIndex=0Index+adjvex与di+wipadjvex的大小关系，若前者大于后者则更新dpadjvex=di+wipadjvex;pathpath_indexparcadjvexparcadjvex=i;记录下i点以便寻找最短路径时用。 若前者等于后者，则说明到同一结点最短路径可能有多条，此时则仍将i值记下path+path_indexparcadjvexparcadjvex=i;以便后续确定最短路径时用，若小于转 (3)。 图35消歧处理输入字串他只会诊断一般的疾病。 可能的输出他/只会/诊断/一般/的/疾病。 (6个词)他/只/会诊/断/一般/的/疾病。 (7个词)最终结果他/只会/诊断/一般/的/疾病。 输入字串他说的确实在理。 可能的输出他/说/的/确实/在理。 他/说/的确/实/在理。 最终结果他/说/的/确实/在理。 此时，产生了多条路径，需要按照一定的标准来选择最终的切分路径。 最短路径算法的优劣最短路径算法的切分原则是使切分出来的词数最少，这种切分原则多数情况下符合汉语的语言规律，需要的语言资源也不多。 但是，对许多歧义字段难以区分，最短路径有多条时，选择最终的输出结果缺乏应有的标准。 字串长度较大和选取的最短路径数增大时，长度相同的路径数急剧增加，选择最终正确的结果因难越来越大。 对于切分出相同词长的若干结果可以结合最大概率分词方法来选取概率最大的一种情况作为最终的分词结果。 由于缺少相关的概率资源，在概率计算中又需要大量的查询操作与浮点数的计算操作，因而最终会使效率降低，故本文提出一种基于词性转换概率矩阵来解决这一问题。 词性转换概率矩阵是一个46行46列的矩阵，根据人民日报1998年统计的语料库中词性的标注。 利用该语料库统计出各词之间的转换概率。 （如下表3-1列出部分词的转换表）表31连词形语素数词名词形容词拟声词介词量词代词连词7944346456106207162378形语素51138110013数词12056515869123313389890108名词6685361765344073366950071981786形容词378437791606330222306118拟声词004331000介词21118689294943243002量词116327156941026027734131代词例如他说的确实在理。 这句话两种分词的结果如下他（代词）/说（动词）/的（助动词）/确实（形容词）/在理（