我自己设计的中文分词算法.doc-资料库

shuizimuzhongling-442324-4744302542973875860.doc.pdf-第1页.png

第1页 / 共13页

shuizimuzhongling-442324-4744302542973875860.doc.pdf-第2页.png

第2页 / 共13页

shuizimuzhongling-442324-4744302542973875860.doc.pdf-第3页.png

第3页 / 共13页

shuizimuzhongling-442324-4744302542973875860.doc.pdf-第4页.png

第4页 / 共13页

shuizimuzhongling-442324-4744302542973875860.doc.pdf-第5页.png

第5页 / 共13页

shuizimuzhongling-442324-4744302542973875860.doc.pdf-第6页.png

第6页 / 共13页

shuizimuzhongling-442324-4744302542973875860.doc.pdf-第7页.png

第7页 / 共13页

shuizimuzhongling-442324-4744302542973875860.doc.pdf-第8页.png

第8页 / 共13页

我自己设计的中文分词算法 02 月 11 日(星期六) 最近折腾毕业论文，搞得人没心情写 blog 了。于是觉得不如把毕业论文里的东西贴出来当 blog 算了。这里主要介绍了我自己的中文分词算法，我觉得它比现在开源代码比较多的中文匹配法要好多了。这里的内容没有任何背景知识啥的，毕竟论文里的背景知道我也是从网上粘贴的，呵呵！因此这篇文章的内容可能适合做搜索引擎的人。如果要了解中文分词算法在搜索引擎中的重要性，或者最大匹配法的思想与过程，请去网上搜吧，资料还是蛮多的。 1.1.1 最大匹配法分词的缺陷尽管最大匹配法分词是常用的解决的方案，但是无疑它存在很多明显的缺陷，这些缺陷也限制了最大匹配法在大型搜索系统中的使用频率。最大匹配法的问题有以下几点：一、长度限制由于最大匹配法必须首先设定一个匹配词长的初始值，这个长度限制是最大匹配法在效率与词长之间的一种妥协。我们来看一下以下两种情况：（1）词长过短，长词就会被切错。例如当词长被设成 5 时，也就意味着它只能分出长度为 5 以下词，例如当这个词为“中华人民共和国”长度为 7 的词时，我们只能取出其中的 5 个字去词库里匹配，例如“中华人民共”，显然词库里是不可能有这样的词存在的。因此我们无法下确的划分出“中华人民共和国”这样的词长大于 5 的词。

（2）词长过长，效率就比较低。也许有人会认为既然 5 个字无法满足我们的分词要求，何不将词长加大，例如加到 10 或者 100，毕竟这个世界超过 100 个字长的词还是很少见的，我们的词长问题不就解决了？然而当词长过长时，我们却要付出另一方面的代价：效率。效率是分词算法、甚至是整个算法理论体系的关键，毕竟算法书里所有的高深的查询或排序算法都是从效率出发的，否则任何笨办法都可以解决分词效率低的问题。设想到我们把字长设成 100 个词时，我们必须将词从 100 开始一直往下匹配直到找到要查的字为止，而我们大多数词的字长却只有两三个字，这意味着前 97 次的匹配算法是徒劳的。因此我们必须要在词长与效率之间进行妥协，既要求分词尽量准确，又要求我们的词长不能太长。尽管我们可能找到这样一个比较优化的字长值使两者都达到比较满足的状态，但是毕竟不管我们怎么设定，总会有些太长词分出来，或者带来效率问题。二、效率低效率低是最大匹配法分词必然会来的问题。即使我们可以将字长设成相当短，例如 5（注意，我们不能再缩短字长了，毕竟字长为 5 以上的词太多了，我们不能牺牲分词的准确），然而当我们的大数词长为 2 时，至少有 3 次的匹配算法是浪费掉的。回想一下算法书里提到的最简单的字符匹配与 KMP 算法之间天差地别的效率，我们知道通过某种方法，这些浪费的掉的匹配时间是可以补回来的。三、掩盖分词歧义中文是如此复杂的语言，它的表达方式如此之多，语法文法如此精妙，机械的电脑是很难理解这么复杂的语言，因此它必然会带来歧意性，以下是两个简单的例子：

A.“有意见分歧” （正向最大匹配和逆向最大匹配结果不同）有意/ 见/ 分歧/ 有/ 意见/ 分歧/ B.“结合成分子时” （正向最大匹配和逆向最大匹配结果相同）结合/ 成分/ 子时/由于词的歧义性使我们在使用最大匹配法分词会产生错误的结果，而且使用正向分词与逆向分词往往会产生截然不同的结果。尽管使用回溯法或计算计算词的使用频率，可以使出现歧义的可能性减少，但是我们知道，这样的结果是不可避免的，因为中文的变化实在太多了。四、最大匹配的并不一定是想要的分词方式最大匹配法基于的理念是找到最大的匹配词，但有的时候除了最大匹配词外，我们也可能只需要这个词的一部分。例如“感冒解毒胶囊”是一个完整的词，按照最大匹配法我们无法对它进行拆分了，这样我们输入“感冒”的时候就根本搜不到我们需要的词。这是我们需要的吗？做为生产这种药的厂商，它肯定希望用户输入“感冒”甚至“解毒”，我们都能查到对应的内容。 1.2 设计自己的中文分词算法 1.2.1 设计目标基于对分词算法的理解和对最大匹配法分词的分析，我们知道我们必须提出不同的解决方案，使分词算法的效率、分词的长度限制甚至歧义处理上得到提高。因此我们提出了如下的设计目标：一、高效中文分词算法必须要高效，毕竟效率对于搜索引擎的重要性是不言而喻的。而且我们面对的是海量的数据，而不是一篇几百字或几千字的文章，效率的差别的影响可能会使最后运行效率差几个小时甚至几天。因此我希望我们设计的算法一定

要比最大匹配法高，毕竟我们已经常看到最大匹配法的很多次匹配都是浪费在无用功上了，肯定有办法把这些浪费的时间节省回来。二、无长度限制最大匹配法的长度限制真是很讨厌的事，我们很难找到词长与效率的之间的平衡。为什么我们需要长度的限制？为什么我们不能设计出任何词长的词（只要词库中存在）都可以分出来？三、歧义包容我们相信长度限制的问题总是可以解决的，因为虽然长度限制这个问题很难，但是它是有规律可循的，它是严谨的科学。但是当我们碰到中文歧义时，我知道不管我们怎么努力，它仍然是不可能彻底解决的。因为中文实在太博大精深了，即使有极强的人工智能和机器学习功能，这样的错误仍然是难以避免。既然无法避免？我们为什么不换一个角度去考虑？我们为什么不可以将出现歧义的各种可能性都包含进去，作为分词的参考。例如上述的“有意见分歧”的两种分词方法：有意/ 见/ 分歧/ 有/ 意见/ 分歧/ 为什么我们不能把这样两种结果都拿来分词呢？毕竟分词的目的是为了搜索，而不是为了教小孩读出。如果把两种分词的可能性都告诉搜索引擎，搜索引擎会很高兴的，因为这下不管是“有意”还是“意见”，它都可以搜到了。这就是我提出来另一个目标：歧义包容。 1.2.2 算法的突破口—词库虽然我们的目标已经确定下来了，但是要想出一个更好的算法却是非常难的事。毕竟算法需要的是灵感与突发奇想，这与系统的架构设计和面向对象的设计与编

者编码刚好是相反的，象设计模式或重构这样的东西我们需要的实践、总结、再实践。而算法需要的却是当我们在山重水复疑无路的时候会换个角度思考。但是分词算法的突破口在哪里呢？我们必须要有一个词库，我们必须将全文中的词与词库去匹配，这一切都是不可避免的。真正要改善是就是我们的匹配过程，我们要减少匹配过程中的浪费，我们要解决匹配中的词长限制。但是我们有什么办法呢？每次的匹配我们必须要去词库中查找一次。怎么改善这样的做法？我们总是把优化的思路定格在更好的匹配算法，更好地处理词条和全文。但是真正束缚我们的却是词库！是基于关系数据库的词库，我们需要的对词库的改造，我们要让我们的词库更适合用于匹配与分词！这是几十年来关系数据库带给我们的思维：我们查找的词是数据库的某条记录，通过表格与关系代数，我们总能找到这个词。但是正是关系数据库的这种思维束缚着我们，关系数据库让我们的数据结构及关联表达得清楚又简单，并使某些查询的效率变得很高。但是这不适用于中文分词，有的时候退到几十年前流行的数据库模型也许更适合。这就是层次数据库。我们要做的是将关系数据库的词按字打散，并存放到层次数据库中。以下就是一个示例：

红色的字表示树上面的字串是可以单独组成一个词的，例如“感冒”它本身是词库里可以找到的词，所有红色的表示的是终止符。而黄色则表示树上面的字串是无法单独成词的，例如“感冒解”是不存在的词。真的很奇妙，词库经过这样的改装后，所有的匹配的思维都变掉了。任何一个句子都会打散成单字去与树状结构的单字去匹配，词的长度变成了树的高度，每一次的匹配变成了树的遍历，而这种遍历的效率竟然都是线性的！ 1.2.3 中文分词算法设计有了以上的中文词库后，我们分词算法设计就水到渠成的。首先我们来看一下分词的步骤：

（1）首先将要分的全文按标点符号打散成一个一个的句子。这算是预处理的一个步骤，目的是让我们处理的句子短，效率更高。毕竟中间有标点符号的词是不存在的。（注：真正实现时我们是基于 lucene 的 SimpleAnalyzer 来做的，因为 SimpleAnalyzer 本身就是为了将全文打散成句子，因此我们没必要耗费体力去实现这一步）。（2）我们开始将要处理的句子在树状结构中遍历，如果找到匹配的就继续，如果遇到红色的终止符，我们就发现这个词是一个完整的词了，这样我们就可以把这个词作为一个一个分词了。（3）从分词后的下一字开始继续做步骤 2 这样的遍历，如此循环往复就将词分完了。可以看到，我们字符匹配效率几乎是线性的！我们所要做的只是取出每一个字去树上找到相应的匹配，每次的匹配代价都是 O(1)（如果词库用 Hash 表的话），这样匹配下来的时间复杂度就是字符串本身的长度！对于一个长度为 n 的字符串来说，它的分词复杂度是 O(n)。而最大匹配的平均复杂度是 O(n2)。当然我们这里没有考虑歧义包容与分支处理等情况，但即使加上这些我们复杂度仍然是有限的。 1.2.4 中文分词算法的实现细节一、建立词库有了改装词库的基本思想后，建立词库的步骤变得很简单，但是仍然会有好多的细节需要注意。首先是词库的保存格式。现在最常用的保存数据的方式当然是关系数据库，其次是文件系统中的二进制文件。显然关系数据库对于我们并不适用，而自定义的二

进制文件则实现起来比较困难，而且读写的效率也会有问题。因为我们想到了最简单的方法是利用 java 的 serialization 的功能，把整个内存中的树状结构直接序列化成磁盘的文本文件是最方便的！而且读写的效率也会相当的高。第二个问题是树的父子节点的导航。我们的树并不是一颗二叉树，父亲的子节点会有好多！尤其是第一层，我们会把词库中所有的首字都取出来作为根节点的子节点，这意味着如果首字有 4000 个的话，根节点就有 4000 个儿子。当然随着树层数的增多，节点的儿子数也会减少，毕竟以“感冒”开头的词在整个词库也只有四十多个，而以“感冒清”开头的词则只有两三个了。这意味着如果设计得不合理，我们树的匹配遍历过程并不完全是线性的。最坏的查找算法是 O(N)（N 代表儿子数）。当然如果我们建词库时将儿子有序排列，再按照二分查找的方法，则我们的复杂度会减到 O(lgN)，这样的复杂度已经可以接受了。但是还有更简单又更快的存储方式，为什么不使用呢？那就是 HashMap，毕竟在 HashMap 里查找东西时它的效率几乎是线性的，而且实现起来要比二分查询简单得多。当然用 HashMap 要付出存储空间变大的代价，但这样的代价来换取速度与简单性也是的。第三个问题是找到有终结符的字后，我们必须要将它建成一个完整的词。这时我们必须能从字个往上回溯，直到找到根结点。因此我们在每个节点里都保存了父节点的指针。有了以上的设计思想，我们就动手建立了我们的词库，词库的来源是中医药数据库的词汇表，因为我们应用一直是围绕中医药的。我们找到了两个最重要的表，这两个表几乎包含了中医药的全部词库：一体化语言系统词库 92112 个词疾病大全、症状、证候 20879 个词

资料库

我自己设计的中文分词算法.doc

相关推荐

开发技术

热门标签

最新资料