最近折腾毕业论文，搞得人没心情写blog了。于是觉得不如把毕业论文里的东西贴出来当blog算了。这里主要介绍了我自己的中文分词算法，我觉得它比现在开源代码比较多的中文匹配法要好多了。这里的内容没有任何背景知识啥的，毕竟论文里的背景知道我也是从网上粘贴的，呵呵！因此这篇文章的内容可能适合做搜索引擎的人。如果要了解中文分词算法在搜索引擎中的重要性，或者最大匹配法的思想与过程，请去网上搜吧，资料还是蛮多的。尽管最大匹配法分词是常用的解决的方案，但是无疑它存在很多明显的缺陷，这些缺陷也限制了最大匹配法在大型搜索系统中的使用频率。最大匹配法的问题有以下几点：
一、长度限制
由于最大匹配法必须首先设定一个匹配词长的初始值，这个长度限制是最大匹配法在效率与词长之间的一种妥协。我们来看一下以下两种情况：
（1）词长过短，长词就会被切错。例如当词长被设成5时，也就意味着它只能分出长度为5以下词，例如当这个词为“中华人民共和国”长度为7的词时，我们只能取出其中的5个字去词库里匹配，例如“中华人民共”，显然词库里是不可能有这样的词存在的。因此我们无法下确的划分出“中华人民共和国”这样的词长大于5的词。
（2）词长过长，效率就比较低。也许有人会认为既然5个字无法满足我们的分词要求，何不将词长加大，例如加到10或者100，毕竟这个世界超过100个字长的词还是很少见的，我们的词长问题不就解决了？然而当词长过长时，我们却要付出另一方面的代价：效率。效率是分词算法、甚至是整个算法理论体系的关键，毕竟算法书里所有的高深的查询或排序算法都是从效率出发的，否则任何笨办法都可以解决分词效率低的问题。设想到我们把字长设成100个词时，我们必须将词从100开始一直往下匹配直到找到要查的字为止，而我们大多数词的字长却只有两三个字，这意味着前97次的匹配算法是徒劳的。
因此我们必须要在词长与效率之间进行妥协，既要求分词尽量准确，又要求我们的词长不能太长。尽管我们可能找到这样一个比较优化的字长值使两者都达到比较满足的状态，但是毕竟不管我们怎么设定，总会有些太长词分出来，或者带来效率问题。
二、效率低
效率低是最大匹配法分词必然会来的问题。即使我们可以将字长设成相当短，例如5（注意，我们不能再缩短字长了，毕竟字长为5以上的词太多了，我们不能牺牲分词的准确），然而当我们的大数词长为2时，至少有3次的匹配算法是浪费掉的。回想一下算法书里提到的最简单的字符匹配与KMP算法之间天差地别的效率，我们知道通过某种方法，这些浪费的掉的匹配时间是可以补回来的。
三、掩盖分词歧义
中文是如此复杂的语言，它的表达方式如此之多，语法文法如此精妙，机械的电脑是很难理解这么复杂的语言，因此它必然会带来歧意性，以下是两个简单的例子：
A.“有意见分歧” （正向最大匹配和逆向最大匹配结果不同）
有意/ 见/ 分歧/
有/ 意见/ 分歧/
B.“结合成分子时” （正向最大匹配和逆向最大匹配结果相同）
结合/ 成分/ 子时/由于词的歧义性使我们在使用最大匹配法分词会产生错误的结果，而且使用正向分词与逆向分词往往会产生截然不同的结果。尽管使用回溯法或计算计算词的使用频率，可以使出现歧义的可能性减少，但是我们知道，这样的结果是不可避免的，因为中文的变化实在太多了。
四、最大匹配的并不一定是想要的分词方式
最大匹配法基于的理念是找到最大的匹配词，但有的时候除了最大匹配词外，我们也可能只需要这个词的一部分。例如“感冒解毒胶囊”是一个完整的词，按照最大匹配法我们无法对它进行拆分了，这样我们输入“感冒”的时候就根本搜不到我们需要的词。这是我们需要的吗？做为生产这种药的厂商，它肯定希望用户输入“感冒”甚至“解毒”，我们都能查到对应的内容。
基于对分词算法的理解和对最大匹配法分词的分析，我们知道我们必须提出不同的解决方案，使分词算法的效率、分词的长度限制甚至歧义处理上得到提高。因此我们提出了如下的设计目标：
一、 高效
中文分词算法必须要高效，毕竟效率对于搜索引擎的重要性是不言而喻的。而且我们面对的是海量的数据，而不是一篇几百字或几千字的文章，效率的差别的影响可能会使最后运行效率差几个小时甚至几天。因此我希望我们设计的算法一定要比最大匹配法高，毕竟我们已经常看到最大匹配法的很多次匹配都是浪费在无用功上了，肯定有办法把这些浪费的时间节省回来。
二、无长度限制
最大匹配法的长度限制真是很讨厌的事，我们很难找到词长与效率的之间的平衡。为什么我们需要长度的限制？为什么我们不能设计出任何词长的词（只要词库中存在）都可以分出来？
三、歧义包容
我们相信长度限制的问题总是可以解决的，因为虽然长度限制这个问题很难，但是它是有规律可循的，它是严谨的科学。但是当我们碰到中文歧义时，我知道不管我们怎么努力，它仍然是不可能彻底解决的。因为中文实在太博大精深了，即使有极强的人工智能和机器学习功能，这样的错误仍然是难以避免。既然无法避免？我们为什么不换一个角度去考虑？我们为什么不可以将出现歧义的各种可能性都包含进去，作为分词的参考。例如上述的“有意见分歧”的两种分词方法：
有意/ 见/ 分歧/
有/ 意见/ 分歧/
为什么我们不能把这样两种结果都拿来分词呢？毕竟分词的目的是为了搜索，而不是为了教小孩读出。如果把两种分词的可能性都告诉搜索引擎，搜索引擎会很高兴的，因为这下不管是“有意”还是“意见”，它都可以搜到了。这就是我提出来另一个目标：歧义包容。
虽然我们的目标已经确定下来了，但是要想出一个更好的算法却是非常难的事。毕竟算法需要的是灵感与突发奇想，这与系统的架构设计和面向对象的设计与编者编码刚好是相反的，象设计模式或重构这样的东西我们需要的实践、总结、再实践。而算法需要的却是当我们在山重水复疑无路的时候会换个角度思考。
但是分词算法的突破口在哪里呢？我们必须要有一个词库，我们必须将全文中的词与词库去匹配，这一切都是不可避免的。
真正要改善是就是我们的匹配过程，我们要减少匹配过程中的浪费，我们要解决匹配中的词长限制。但是我们有什么办法呢？每次的匹配我们必须要去词库中查找一次。怎么改善这样的做法？
我们总是把优化的思路定格在更好的匹配算法，更好地处理词条和全文。但是真正束缚我们的却是词库！是基于关系数据库的词库，我们需要的对词库的改造，我们要让我们的词库更适合用于匹配与分词！
这是几十年来关系数据库带给我们的思维：我们查找的词是数据库的某条记录，通过表格与关系代数，我们总能找到这个词。但是正是关系数据库的这种思维束缚着我们，关系数据库让我们的数据结构及关联表达得清楚又简单，并使某些查询的效率变得很高。但是这不适用于中文分词，有的时候退到几十年前流行的数据库模型也许更适合。这就是层次数据库。
我们要做的是将关系数据库的词按字打散，并存放到层次数据库中。以下就是一个示例：
红色的字表示树上面的字串是可以单独组成一个词的，例如“感冒”它本身是词库里可以找到的词，所有红色的表示的是终止符。而黄色则表示树上面的字串是无法单独成词的，例如“感冒解”是不存在的词。
真的很奇妙，词库经过这样的改装后，所有的匹配的思维都变掉了。任何一个句子都会打散成单字去与树状结构的单字去匹配，词的长度变成了树的高度，每一次的匹配变成了树的遍历，而这种遍历的效率竟然都是线性的！
有了以上的中文词库后，我们分词算法设计就水到渠成的。首先我们来看一下分词的步骤：
（1）首先将要分的全文按标点符号打散成一个一个的句子。这算是预处理的一个步骤，目的是让我们处理的句子短，效率更高。毕竟中间有标点符号的词是不存在的。（注：真正实现时我们是基于lucene的SimpleAnalyzer来做的，因为SimpleAnalyzer本身就是为了将全文打散成句子，因此我们没必要耗费体力去实现这一步）。
（2）我们开始将要处理的句子在树状结构中遍历，如果找到匹配的就继续，如果遇到红色的终止符，我们就发现这个词是一个完整的词了，这样我们就可以把这个词作为一个一个分词了。
（3）从分词后的下一字开始继续做步骤2这样的遍历，如此循环往复就将词分完了。
可以看到，我们字符匹配效率几乎是线性的！我们所要做的只是取出每一个字去树上找到相应的匹配，每次的匹配代价都是O(1)（如果词库用Hash表的话），这样匹配下来的时间复杂度就是字符串本身的长度！对于一个长度为n的字符串来说，它的分词复杂度是O(n)。而最大匹配的平均复杂度是O(n2)。
当然我们这里没有考虑歧义包容与分支处理等情况，但即使加上这些我们复杂度仍然是有限的。
一、建立词库
有了改装词库的基本思想后，建立词库的步骤变得很简单，但是仍然会有好多的细节需要注意。
首先是词库的保存格式。现在最常用的保存数据的方式当然是关系数据库，其次是文件系统中的二进制文件。显然关系数据库对于我们并不适用，而自定义的二进制文件则实现起来比较困难，而且读写的效率也会有问题。因为我们想到了最简单的方法是利用java的serialization的功能，把整个内存中的树状结构直接序列化成磁盘的文本文件是最方便的！而且读写的效率也会相当的高。
第二个问题是树的父子节点的导航。我们的树并不是一颗二叉树，父亲的子节点会有好多！尤其是第一层，我们会把词库中所有的首字都取出来作为根节点的子节点，这意味着如果首字有4000个的话，根节点就有4000个儿子。当然随着树层数的增多，节点的儿子数也会减少，毕竟以“感冒”开头的词在整个词库也只有四十多个，而以“感冒清”开头的词则只有两三个了。这意味着如果设计得不合理，我们树的匹配遍历过程并不完全是线性的。最坏的查找算法是O(N)（N代表儿子数）。当然如果我们建词库时将儿子有序排列，再按照二分查找的方法，则我们的复杂度会减到O(lgN)，这样的复杂度已经可以接受了。但是还有更简单又更快的存储方式，为什么不使用呢？那就是HashMap，毕竟在HashMap里查找东西时它的效率几乎是线性的，而且实现起来要比二分查询简单得多。当然用HashMap要付出存储空间变大的代价，但这样的代价来换取速度与简单性也是的。
第三个问题是找到有终结符的字后，我们必须要将它建成一个完整的词。这时我们必须能从字个往上回溯，直到找到根结点。因此我们在每个节点里都保存了父节点的指针。
有了以上的设计思想，我们就动手建立了我们的词库，词库的来源是中医药数据库的词汇表，因为我们应用一直是围绕中医药的。我们找到了两个最重要的表，这两个表几乎包含了中医药的全部词库：
一体化语言系统词库 92112个词
疾病大全、症状、证候 20879个词
最后生成的词库是java serialization的一个文件，文件的大小是16M 。当然这跟我们采用HashMap存放父子关联有关，也跟java的对象所占空间有关，虽然将词库按这种方式存放实际上也对词库进行了压缩（以“感”开头的字有数十个，关系数据库里就要保存数十个，但我们在词库只保存了一个“感”）。但文件仍然偏大，因此用oracle将这两个表导出后生成的文件大小是4M。不过这个大小仍然是可以接受的，毕竟效率才是关键。
二、 分词查询
虽然刚才对分词算法进行了描述，但实际上实现的时候我们还会碰到很多问题。
1、分支处理。
这是分词算法时歧义包容所必然碰到的问题。为了歧义包容，我们采用了与最大分词法完全不同的理念，我们的理念是将词库中存在词全部收入囊中！而且会发生重叠。例如“感冒解毒胶囊”，由于词库里存在“感冒”、“解毒”和“感冒解毒胶囊”这三个词，因此在分词的时候，我们会分别分出这三个词，这样用户无论输入“感冒”、“解毒”或“感冒解毒胶囊”搜索引擎都会找到相应的结果。
因此当遇到分支时，我们会分解成两条路线！例如当我们匹配到“感冒”的“冒”时，我们会发现一个终止符，代表“感冒”是一个完整的字，将它收录到分词中。接下来我们会分成两支，一支是继续往下走，匹配树的下一层，因为“冒”不是树的叶子，往下走可能会碰到更大的匹配词，例如“感冒解毒胶囊”。而另一支则从根开始，直接用“解”去匹配树的第一层节点，最后发现了“解毒”也是其中的一个词。
2、动态规划法
分支虽然使我们可以消除很多的歧义，但是显然它会带来副作用：导致分词的复杂度变大。如果一个句子很长时，分词的变化也许会呈指数级的增长，从一开始的两个分支变成四个、八个甚至更多。我们会发现很多句子虽然会有很多分支，但是这些分支又经常会汇聚到一个点，变成一个分支。例如：“感冒解毒胶囊可以治感冒”，我们在分词的时候可能会出现“感冒”，“解毒”，“感冒解毒”，“感冒解毒胶囊”等多个分支，但是当我们到达“囊”这个点的时候，所有的分支又会汇集到一起，因为大家接下来要处理的都是“可以治感冒”这个字符串。如果有办法让我们在汇聚以后只处理一个分支，那么算法的时间复杂度就不会象原来想象的那么坏。
而这刚好是动态规划法发挥威力的时候，动态规划要解决的问题是Overlapping sub-problem。它的处理方法就是将所有的子问题记录在公有的变量里（这里指的是类变量，它相对于某个method来说是公有变量，而不是真的全局变量）。当我遇到的子问题已经被处理过一次了，就直接跳过。这样节约的结果可以使算法复杂度得到质的改变，当然由于中文的变化多端，我们无法精确估计使用动态规划法后算法复杂度得到了多大的提高。
实际上的动态规划法的实现起来比说起来反而简单，我们只是简单地放了一个HashSet来存放已经分词过的位置：
然后判断的函数也相当的简单：
最后在分词的递归函数中加入这一句判断：
当这个位置已经被处理过了就直接返回了。
3、词库预load
在使用基于词库的方法时，我们必须要面临的一个问题是：必要将词库读到内存中，而这通常会耗费很长的时间，幸运的是这样的工作我们只需要做一次，当我们将词库load进来以后，所有的工作都会在内存中进行，分词的速度会得到极速提升。我们选择的词库预load时机是我们第一次进行分词时，这相当于lazy load，只有用到的时候我们才去初始化。
讲完算法，我们来看看分词部分的实现代码，实际上这部分的内容实现起来远比想中简单。在处理的过程中，我们对给每个句子（实际是lucene里用SimpleAnalyzer分词后的一个个Token）都新建一个ChineseSplitter，这是更加面向对象的做法，使我们处理起来更加方便简洁，因为我们会发现如果用一个Singleton的ChineseSplitter时，它的变量无法共享会导致整个Splitter里的递归方法跟上一堆的参数，容易出错，而且无法调试。代码如下：
代码简单明了，只是做了词库预load的工作后就将实际的分词工作交给了ChineseSplitter。
ChineseSplitter的核心功能实际上将句子中词典中能找到的词放到一个队列中，这中队列里提供了分词以后的所有词的信息：
下面是分词的核心算法：
它是一个递归的过程，初始时我们调用的参数里pos为0，这样它就会一级一级递归下去并将所有可能的分词放入到tokenQueue里。
1、实验1――短文分词
在第一个实验中我们选了一篇2000字的文章（是关于中医药的专业论文）。然后用三种Analyzer对它进行处理，以下是实验结果：
Analyzer | 分词算法 | 耗时 |
SimpleAnalyzer | 将文章按标点符号隔开成句子 | 47ms |
StandardAnalyzer | 将文章的中文字分成一个一个的单字 | 250ms |
ChineseAnalyzer | 我们的分词算法 | 词库没preload: 13359ms , 词库preload: 63ms |
我们没有找到最大匹配法分词可用的开源代码，因此只能用SimpleAnalyzer和StandardAnalyzer与之比较。这两种算法事实上是根本没有去查词库的，因此也不会按任何语义去分词，SimpleAnalyzer只是简单地将文章按标点符号隔开成句子，而StandardAnalyzer则只是简单地将文章的中文字分成一个一个的单字。结果确实让人惊讶，当词库preload以后，我们的分词速度竟然远超不需要查任何词库的StandardAnalyzer算法！
2、实验2――建索引
这是将分词算法应用到我们的索引系统后的效果比较，我们的数据源是来自中医药数据库的几十张表，一共有九十万条记录：
Analyzer | 分词算法 | 耗时 |
StandardAnalyzer | 将文章的中文字分成一个一个的单字 | 35分钟 |
ChineseAnalyzer | 我们的分词算法 | 31分钟 |
由于建索引时数据库的查询操作会耗费很多的时间，因此两者的差别不是太明显，但结果至少说明了我们的分词效率确实是很高。
