中文分词算法

《中文分词算法》由会员分享，可在线阅读，更多相关《中文分词算法（9页珍藏版）》请在装配图网上搜索。

1、中文分词算法（转贴）（2007-08-17 16:53:03）转载标签： 分类：计算机与Internet杂谈-作者：helpuser-发布时间：2006-9-7 16:45:00-中文分词算法作者:单翼日期:2006-08-17字体大小：小中大111最大匹配法分词的缺陷尽管最大匹配法分词是常用的解决的方案，但是无疑它存在很多明显的缺陷，这些缺陷也 限制了最大匹配法在大型搜索系统中的使用频率。最大匹配法的问题有以下几点：一、长度限制由于最大匹配法必须首先设定一个匹配词长的初始值，这个长度限制是最大匹配法在效率 与词长之间的一种妥协。我们来看一下以下两种情况：（1）词长过短，长词就会被切错。例如当

2、词长被设成5时，也就意味着它只能分出长度为 5以下词，例如当这个词为“中华人民共和国长度为7的词时，我们只能取出其中的5个字去词库里匹配，例 如“中华人民共，显然词库里是不可能有这样的词存在的。因此我们无法下确的划分出“中华人民共和国” 这样的词长大于5的词。（2）词长过长，效率就比较低。也许有人会认为既然5个字无法满足我们的分词要求，何 不将词长加大，例如加到10或者100,毕竟这个世界超过100个字长的词还是很少见的，我们的词长问题不 就解决了？然而当词长过长时，我们却要付出另一方面的代价：效率。效率是分词算法、甚至是整个算法理论 体系的关键，毕竟算法书里所有的高深的査询或排序算法都是从效

3、率出发的，否则任何笨办法都可以解决分 词效率低的问题。设想到我们把字长设成100个词时，我们必须将词从100开始一直往下匹配直到找到要査 的字为止，而我们大多数词的字长却只有两三个字，这意味着前97次的匹配算法是徒劳的。因此我们必须要在词长与效率之间进行妥协，既要求分词尽量准确，又要求我们的词长不 能太长。尽管我们可能找到这样一个比较优化的字长值使两者都达到比较满足的状态，但是毕竟不管我们怎 么设定，总会有些太长词分出来，或者带来效率问题。二、效率低 效率低是最大匹配法分词必然会来的问题。即使我们可以将字长设成相当短，例如5（注意， 我们不能再缩 短字长了，毕竟字长为5以上的词太多了，我们不能

4、牺牲分词的准确），然而当我们的大数 词长为 2 时，至少有3次的匹配算法是浪费掉的。回想一下算法书里提到的最简单的字符匹配与KMP算法之 间天差地别的效率，我们知道通过某种方法，这些浪费的掉的匹配时间是可以补回来的。三、掩盖分词歧义 中文是如此复杂的语言，它的表达方式如此之多，语法文法如此精妙，机械的电脑是很难 理解这么复杂的语言，因此它必然会带来歧意性，以下是两个简单的例子：A“有意见分歧（正向最大匹配和逆向最大匹配结果不同）有意/ 见/ 分歧/有/ 意见/ 分歧/B“结合成分子时（正向最大匹配和逆向最大匹配结果相同）结合/ 成分/ 子时/由于词的歧义性使我们在使用最大匹配法分词会产生错误的

5、结果，而且 使用正向分词与逆向分词往往会产生截然不同的结果。尽管使用回溯法或计算计算词的使用频率，可以使 出现歧义的可能性减少，但是我们知道，这样的结果是不可避免的，因为中文的变化实在太多了。四、最大匹配的并不一定是想要的分词方式 最大匹配法基于的理念是找到最大的匹配词，但有的时候除了最大匹配词外，我们也可能 只需要这个词的一部分。例如“感冒解毒胶囊”是一个完整的词，按照最大匹配法我们无法对它进行拆分了，这 样我们输入“感冒”的时候就根本搜不到我们需要的词。这是我们需要的吗？做为生产这种药的厂商，它 肯定希望用户输入“感冒”甚至“解毒”，我们都能查到对应的内容。1.2 设计自己的中文分词算法1

6、.2.1 设计目标 基于对分词算法的理解和对最大匹配法分词的分析，我们知道我们必须提出不同的解决方 案，使分词算法的效率、分词的长度限制甚至歧义处理上得到提高。因此我们提出了如下的设计目标：一、高效中文分词算法必须要高效，毕竟效率对于搜索引擎的重要性是不言而喻的。而且我们面对 的是海量的数据，而不是一篇几百字或几千字的文章，效率的差别的影响可能会使最后运行效率差几个小时 甚至几天。因此我希望我们设计的算法一定要比最大匹配法高，毕竟我们已经常看到最大匹配法的很多次匹 配都是浪费在无用功上了，肯定有办法把这些浪费的时间节省回来。二、无长度限制 最大匹配法的长度限制真是很讨厌的事，我们很难找到词长与

7、效率的之间的平衡。为什么 我们需要长度的限 制？为什么我们不能设计出任何词长的词（只要词库中存在）都可以分出来？三、歧义包容 我们相信长度限制的问题总是可以解决的，因为虽然长度限制这个问题很难，但是它是有 规律可循的，它是 严谨的科学。但是当我们碰到中文歧义时，我知道不管我们怎么努力，它仍然是不可能彻 底解决的。因为中 文实在太博大精深了，即使有极强的人工智能和机器学习功能，这样的错误仍然是难以避 免。既然无法避免？我们为什么不换一个角度去考虑？我们为什么不可以将出现歧义的各种可能性都包含进 去，作为分词的参考。例如上述的“有意见分歧”的两种分词方法：有意/ 见/ 分歧/ 有/ 意见/ 分歧/

8、 为什么我们不能把这样两种结果都拿来分词呢？毕竟分词的目的是为了搜索，而不是为了 教小孩读出。如果 把两种分词的可能性都告诉搜索引擎，搜索引擎会很高兴的，因为这下不管是“有意”还是“意 见”，它都可以搜到了。这就是我提出来另一个目标：歧义包容。1.2.2 算法的突破口词库 虽然我们的目标已经确定下来了，但是要想出一个更好的算法却是非常难的事。毕竟算法 需要的是灵感与突 发奇想，这与系统的架构设计和面向对象的设计与编者编码刚好是相反的，象设计模式或 重构这样的东西我 们需要的实践、总结、再实践。而算法需要的却是当我们在山重水复疑无路的时候会换个 角度思考。但是分词算法的突破口在哪里呢？我们必须要

9、有一个词库，我们必须将全文中的词与词库 去匹配，这一切都是不可避免的。 真正要改善是就是我们的匹配过程，我们要减少匹配过程中的浪费，我们要解决匹配中的 词长限制。但是我 们有什么办法呢？每次的匹配我们必须要去词库中查找一次。怎么改善这样的做法？这是几十年来关系数据库带给我们的思维：我们查找的词是数据库的某条记录，通过表格 与关系代数，我们总能找到这个词。但是正是关系数据库的这种思维束缚着我们，关系数据库让我们的数据 结构及关联表达得清楚又简单，并使某些查询的效率变得很高。但是这不适用于中文分词，有的时候退到几 十年前流行的数据库模型也许更适合。这就是层次数据库。 我们要做的是将关系数据库的词按

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

11、的句子。这算是预处理的一个步骤，目 的是让我们处理 的句子短，效率更高。毕竟中间有标点符号的词是不存在的。（注：真正实现时我们是基于 lucene 的 SimpleAnalyzer来做的，因为SimpleAnalyzer本身就是为了将全文打散成句子，因此我们没必要耗 费体力去实现这一步）。（2）我们开始将要处理的句子在树状结构中遍历，如果找到匹配的就继续，如果遇到红色 的终止符，我们就发现这个词是一个完整的词了，这样我们就可以把这个词作为一个一个分词了。（3）从分词后的下一字开始继续做步骤 2这样的遍历，如此循环往复就将词分完了。 可以看到，我们字符匹配效率几乎是线性的！我们所要做的只是取出每

12、一个字去树上找到 相应的匹配，每次的匹配代价都是0（1）（如果词库用Hash表的话），这样匹配下来的时间复杂度就是字符串 本身的长度！对于一个长度为n的字符串来说，它的分词复杂度是0（n）。而最大匹配的平均复杂度是0（n2）。 当然我们这里没有考虑歧义包容与分支处理等情况，但即使加上这些我们复杂度仍然是有 限的。1.2.4 中文分词算法的实现细节一、建立词库 有了改装词库的基本思想后，建立词库的步骤变得很简单，但是仍然会有好多的细节需要 注意。首先是词库的保存格式。现在最常用的保存数据的方式当然是关系数据库，其次是文件系 统中的二进制文件。显然关系数据库对于我们并不适用，而自定义的二进制文件则

13、实现起来比较困难，而且 读写的效率也会有问题。因为我们想到了最简单的方法是利用java的serialization的功能，把整个内存中的树状结构直接序列化成磁盘的文本文件是最方便的！而且读写的效率也会相当的高。第二个问题是树的父子节点的导航。我们的树并不是一颗二叉树，父亲的子节点会有好多! 尤其是第一层，我们会把词库中所有的首字都取出来作为根节点的子节点，这意味着如果首字有4000个的 话，根节点就有4000 个儿子。当然随着树层数的增多，节点的儿子数也会减少，毕竟以“感冒”开头的词在整 个词库也只有四十多个，而以“感冒清”开头的词则只有两三个了。这意味着如果设计得不合理，我们树的匹 配遍历过

14、程并不完全是线性的。最坏的査找算法是O(N)(N代表儿子数)。当然如果我们建词库时将儿子 有序排列，再按照二分查找的方法，则我们的复杂度会减到O(lgN)，这样的复杂度已经可以接受了。但是 还有更简单又更快的存储方式，为什么不使用呢？那就是HashMap,毕竟在HashMap里查找东西时它的效率 几乎是线性的，而且实现起来要比二分查询简单得多。当然用HashMap要付出存储空间变大的代价，但这样的 代价来换取速度与简单性也是的。第三个问题是找到有终结符的字后，我们必须要将它建成一个完整的词。这时我们必须能 从字个往上回溯，直到找到根结点。因此我们在每个节点里都保存了父节点的指针。有了以上的设计

15、思想，我们就动手建立了我们的词库，词库的来源是中医药数据库的词汇 表，因为我们应用一直是围绕中医药的。我们找到了两个最重要的表，这两个表几乎包含了中医药的全部词 库：一体化语言系统词库92112个词疾病大全、症状、证候20879个词最后生成的词库是java serialization的一个文件，文件的大小是16M。当然这跟我们采用HashMap 存放父子关联有关，也跟 java 的对象所占空间有关，虽然将词库按这种方式存放实际上也对词库 进行了压缩(以“感”开头的字有数十个，关系数据库里就要保存数十个，但我们在词库只保存了一个“感”)。 但文件仍然偏大，因此用oracle将这两个表导出后生成的

16、文件大小是4M。不过这个大小仍然是可以接 受的，毕竟效率才是关键。二、分词查询 虽然刚才对分词算法进行了描述，但实际上实现的时候我们还会碰到很多问题。1、分支处理。 这是分词算法时歧义包容所必然碰到的问题。为了歧义包容，我们采用了与最大分词法完 全不同的理念，我们的理念是将词库中存在词全部收入囊中！而且会发生重叠。例如“感冒解毒胶囊”，由于词 库里存在“感 冒”、“解毒”和“感冒解毒胶囊”这三个词，因此在分词的时候，我们会分别分出这三个词， 这样用户无 论输入“感冒”、“解毒”或“感冒解毒胶囊”搜索引擎都会找到相应的结果。因此当遇到分支时，我们会分解成两条路线！例如当我们匹配到“感冒”的“冒”

17、时，我们会发 现一个终止 符，代表“感冒”是一个完整的字，将它收录到分词中。接下来我们会分成两支，一支是继续 往下走，匹配 树的下一层，因为“冒”不是树的叶子，往下走可能会碰到更大的匹配词，例如“感冒解毒胶 囊”。而另一 支则从根开始，直接用“解”去匹配树的第一层节点，最后发现了“解毒”也是其中的一个词。2、动态规划法分支虽然使我们可以消除很多的歧义，但是显然它会带来副作用：导致分词的复杂度变大。 如果一个句子很 长时，分词的变化也许会呈指数级的增长，从一开始的两个分支变成四个、八个甚至更多。 我们会发现很多 句子虽然会有很多分支，但是这些分支又经常会汇聚到一个点，变成一个分支。例如： “感

18、冒解毒胶囊可以 治感冒”，我们在分词的时候可能会出现“感冒”， “解毒”， “感冒解毒”， “感冒解毒胶囊”等 多个分 支，但是当我们到达“囊”这个点的时候，所有的分支又会汇集到一起，因为大家接下来要处 理的都是“可 以治感冒”这个字符串。如果有办法让我们在汇聚以后只处理一个分支，那么算法的时间复 杂度就不会象原 来想象的那么坏。而这刚好是动态规划法发挥威力的时候， 动态规划要解决的问题是 Overlapping sub-problem。它的处理方法就是将所有的子问题记录在公有的变量里（这里指的是类变量，它相对于某个method来 说是公有变量，而不是真的全局变量）。当我遇到的子问题已经被处理

19、过一次了，就直接跳过。这样节约的结 果可以使算法复杂度得到质的改变，当然由于中文的变化多端，我们无法精确估计使用动态规划法后算法 复杂度得到了多大的提高。实际上的动态规划法的实现起来比说起来反而简单，我们只是简单地放了一个HashSet来存 放已经分词过的 位置：然后判断的函数也相当的简单：最后在分词的递归函数中加入这一句判断： 当这个位置已经被处理过了就直接返回了。3、词库预 load 在使用基于词库的方法时，我们必须要面临的一个问题是：必要将词库读到内存中，而这 通常会耗费很长的时间，幸运的是这样的工作我们只需要做一次，当我们将词库load进来以后，所有的工作 都会在内存中进行，分词的速度

20、会得到极速提升。我们选择的词库预load时机是我们第一次进行分词时，这 相当于 lazy load，只有用到的时候我们才去初始化。讲完算法，我们来看看分词部分的实现代码，实际上这部分的内容实现起来远比想中简单。 在处理的过程中，我们对给每个句子（实际是lucene里用SimpleAnalyzer分词后的一个个Token）都新建一 个 ChineseSplitter，这是更加面向对象的做法，使我们处理起来更加方便简洁，因为我们会发现如果用一个Singleton 的 ChineseSplitter时，它的变量无法共享会导致整个Splitter里的递归方法跟上一堆的参数，容易 出错，而且无法调试。代

21、码如下：代码简单明了，只是做了词库预load的工作后就将实际的分词工作交给了 ChineseSplitter。 ChineseSplitter 的核心功能实际上将句子中词典中能找到的词放到一个队列中，这中队列里 提供了分词以后的所有词的信息：下面是分词的核心算法：它是一个递归的过程，初始时我们调用的参数里pos为0，这样它就会一级一级递归下去并 将所有可能的分词放入到tokenQueue里。1.2.5 中文分词的实验结果1、实验1短文分词在第一个实验中我们选了一篇 2000 字的文章（是关于中医药的专业论文）。然后用三种Analyzer 对它进行处理，以下是实验结果：Analyzer分词算法耗

22、时SimpleAnalyzer将文章按标点符号隔开成句子47msStandardAnalyzer将文章的中文字分成一个一个的单字250msChineseAnalyzer我们的分词算法词库没 preload: 13359ms , 词库 preload: 63ms我们没有找到最大 匹配法分词可用的开 源代码，因此只能用 SimpleAnalyzer 和 StandardAnalyzer 与之比较。这两种算法事实上是根本没有去査词库的，因此也不会按任何语义去分词，SimpleAnalyzer 只是简单地将文章按标点符号隔开成句子，而StandardAnalyzer则只是简单地将文章的中文字分成一个一

23、个 的单字。结果确实让人惊讶，当词库 preload 以后，我们的分词速度竟然远超不需要查任何词库的 StandardAnalyzer 算法！2、实验 2建索引 这是将分词算法应用到我们的索引系统后的效果比较，我们的数据源是来自中医药数据库 的几十张表，一共有九十万条记录：Analyzer分词算法耗时StandardAnalyzer将文章的中文字分成一个一个的单字35分钟ChineseAnalyzer我们的分词算法31分钟由于建索引时数据库的查询操作会耗费很多的时间，因此两者的差别不是太明显，但结果 至少说明了我们的分词效率确实是很高。反思：但是没有谈到人名地名等问题的解决方法特殊符号处理网址

24、识别类型识别转发识别符号识别中文分词的主要困难在于分词歧义。“结婚的和尚未结婚的”应该分成结婚/的/ 和/尚未/结婚/的”，还是“结婚/的/和尚/未/结婚/的”？人来判断很容易，要交 给计算机来处理就麻烦了。问题的关键就是，“和尚未”里的“和尚”也是一个词，“尚未” 也是一个词，从计算机的角度看上去，两者似乎都有可能。对于计算机来说，这样的分词 困境就叫做“交集型歧义”。有时候，交集型歧义的“歧义链”有可能会更长。“中外科学名著”里，“中外”、“外科”、 “科学”、“学名”、“名著”全是词，光从词库的角度来看，随便切几刀下去，得出的切分 都是合理的。类似的例子数不胜数，“提高产品质量”、“鞭炮声响彻夜空”、“努力学习语法 规则”等句子都有这样的现象。在这些极端例子下，分词算法谁优谁劣可谓是一试便知。因此没有解决这样的交集型歧义问题。