解密搜索引擎技术之中文分词原理与实现

        因为中文文本中，词和词之间不像英文一样存在边界，所以中文分词是一个专业处理中文信息的搜索引擎首先面对的问题，需要靠程序来切分出词。
一、Lucene中的中文分词
        Lucene在中处理中文的常用方法有三种，以“咬死猎人的狗”为例说明之：
        单      字：【咬】 【死】 【猎】 【人】 【的】 【狗】
        二元覆盖：【咬死】 【死猎】 【猎人】 【人的】 【的狗】
        分      词：【咬】 【死】 【猎人】 【的】 【狗】
        Lucene中的StandardTokenizer采用单子分词方式，CJKTokenizer采用二元覆盖方式。
1、Lucene切分原理
        Lucene中负责语言处理的部分在org.apache.lucene.analysis包，其中，TokenStream类用来进行基本的分词工作，Analyzer类是TokenStream的包装类，负责整个解析工作，Analyzer类接收整段文本，解析出有意义的词语。
        通常不需要直接调用分词的处理类analysis，而是由Lucene内存内部来调用，其中：
        （1）在索引阶段，调用addDocument（doc）时，Lucene内部使用Analyzer来处理每个需要索引的列，具体如下图：

        
图1 Lucene对索引文本的处理

        IndexWriter index = new IndexWriter(indexDirectory,
                                                    new CnAnalyzer(),        //用于支持分词的分析器
                                                    !incremental,
                                                    IndexWriter.MaxFieldLength.UNLIMITED);
        （2）在搜索阶段，调用QueryParser.parse（queryText）来解析查询串时，QueryParser会调用Analyzer来拆分查询字符串，但是对于通配符等查询不会调用Analyzer。
        Analyzer analyzer = new CnAnalyzer();                        //支持中文的分词
        QueryParser parser = new QueryParser(Version.LUCENE_CURRENT, "title", analyzer);
        因为在索引和搜索阶段都调用了分词过程，索引和搜索的切分处理要尽量一致，所以分词效果改变后需要重建索引。
        为了测试Lucene的切分效果，下面是直接调用Analysis的例子：
        Analyzer analyzer = new CnAnalyzer();                        //创建一个中文分析器
        TokenStream ts = analyzer.tokenStream("myfield", new StringReader("待切分文本"));    //取得Token流
        while (ts.incrementToken()) {                                    //取得下一个词
                System.out.println("token: "+ ts);
        }
2、Lucene中的Analyzer
        为了更好地搜索中文，通过下图来了解一下在Lucene中通过WhitespaceTokenizer、WordDelimiterFilter、LowercaseFilter处理英文字符串的流程：

        
图2 Lucene处理英文字符串流程

二、查找词典算法
        词典格式可以是方便人工查看和编辑的文本文件格式，也可以是方便机器读入的二进制格式。词典的最基本文本文件格式就是每行一个词。在基于词典的中文分词方法中，词典匹配算法是基础。一般词典规模都在几十万词以上，所以为了保证切分速度，需要选择一个好的查找词典算法。
1、标准Trie树
        一个数字搜索Trie树的一个节点只保留一个字符，如果一个单词比一个字符长，则包含第一个字符的节点有指针指向下一个字符的节点，依次类推。这样组成一个层次结构的树，树的第一层包括所有单词的第一个字符，树的第二层包括所有单词的第二个字符，依次类推，数字搜索树的最大高度是词典中最长单词的长度。比如：如下单词序列组成的词典（as at be by he in is it of on or to）会生成如下图所示的数字搜索树：

图3 数字搜索树

        数字搜索树的结构独立于生成树时单词进入的顺序，这里，Trie树的高度是2。因为树的高度很小，在数字搜索Trie树种搜索一个单词的速度很快。但是，这是以内存消耗为代价的，树中每个节点都需要很多内存。假设每个词都是由26个小写英文字母中的一个组成的，这个节点中会有26个指针。所以不太可能直接用这样的数字搜索树来存储中文这样的大字符集。
        Trie树在实现上有一个树类（SearchTrie）和一个节点类（TrieNode）。SearchTrie的主要方法有两个：
        （1）增加单词到搜索树，方法原型是：addWord（String word）。
        （2）从文本的指定位置开始匹配单词，方法原型是：matchLong（String text, int offset）。
2、三叉Trie树
        在一个三叉搜索树（Ternary Search Trie）中，每一个节点包括一个字符，但和数字搜索树不同，三叉搜索树只有三个指针：一个指向左边的树；一个指向右边的树；还有一个向下，指向单词的下一个数据单元。三叉搜索树是二叉搜索树和数字搜索树的混合体。它有和数字搜索树差不多的速度但是和二叉搜索树一样只需要相对较少的内存空间。
        树是否平衡取决于单词的读入顺序。如果按顺序后的顺序插入，则生成方式最不平衡。单词的读入顺序对于创建平衡的三叉搜索树很重要，但对于二叉搜索树就不太重要。通过选择一个排序后数据单元集合的中间值，并把它作为开始节点，我们可以创建一个平衡的三叉树。如下代码可以用来生成平衡的三叉树词典：
        /**
        * 在调用此方法前，先把词典数组k排好序
        * @param fp 写入的平衡序的词典
        * @param k 排好序的词典数组
        * @param offset 偏移量
        * @param n 长度
        * @throws Exception
        */
        void outputBalanced(BufferedWriter fp, ArrayList k, int offset, int n) {
            int m;
            if (n < 1) {
                return;
            }
            m = n >> 1;        //m=n/2

            String item = k.get(m + offset);

            fp.write(item);     //把词条写入到文件
            fp.write('\n');

            outputBalanced(fp, k, offset, m);                  //输出左半部分
            outputBalanced(fp, k, offset+m+1, n-m-1);    //输出右半部分
        }
        再次以有序的数据单元（as at be by he in is it of on or to）为例。首先把关键字“is”作为中间值并且构建一个包含字母“i”的根节点。它的直接后继节点包含字母“s”并且可以存储任何与“is”有关联的数据。对于“i”的左树，我们选择“be”作为中间值并且创建一个包含字母“b”的节点，字母“b”的直接后继节点包含“e”。该数据存储在“e”节点。对于“i”的右树，按照逻辑，选择“on”作为中间值，并且创建“o”节点以及它的直接后继节点“n”。最终的三叉树如下图所示：

图4 三叉树

         垂直的虚线代表一个父节点下面的直接后继节点。只有父节点和它的直接后继节点才能形成一个数据单元的关键字："i"和“s”形成关键字“is”，但是“i”和“b”不能形成关键字，因为它们之间仅用一条斜线相连，不具有直接后继关系。上图中带圈的节点为终止节点。如果查找一个词以终止节点结束，则说明三叉树包含这个词。以搜索单词“is”为例，向下到相等的孩子节点“s”，在两次比较后找到“is”；查找“ax”时，执行三次比较达到首字符“a”，然后经过两次比较到达第二个字符“x”，返回结果是“ax”不在树中。

三、中文分词原理
        中文分词就是对中文断句，这样能消除文字的部分歧义。除了基本的分词功能，为了消除歧义还可以进行更多的加工。中文分词可以分成如下几个子任务：
        （1）分词：把输入的标题或者文本内容等分成词。
        （2）词性标注（POS）：给分出来的词标注上名词或动词等词性。词性标注可以部分消除词的歧义，例如“行”作为量词和作为形容词表示的意思不一样。
        （3）语义标注：把每个词标注上语义编码。
        很多分词方法都借助词库。词库的来源是语料库或者词典，例如“人民日报语料库”或者《现代汉语大词典》 。
        中文分词有以下两类方法：
        （1）机械匹配的方法：例如正向最大长度匹配（Forward Maximum Match）的方法和逆向最大长度匹配（Reverse Maximum Matching）的方法。
        （2）统计的方法：例如概率语言模型分词方法和最大熵的分词方法等。
        正向最大长度品牌的分词方法实现起来很简单。每次从词典中查找和待匹配串前缀最长匹配的词，如果找到匹配词，则把这个词作为切分词，待匹配串减去该词；如果词典中没有词与其匹配，则按单字切分。例如：Trie树结构的词典中包括如下的词语：
        大 大学 大学生 活动 生活 中 中心 心
        为了形成平衡的Trie树，把词先排序，结果为：
        中 中心 大 大学 大学生 心 活动 生活
        按平衡方式生成的词典Trie树如下图所示，其中，粗黑显示的节点可以作为匹配终止节点：

图5 三叉树

        输入“大学生活动中心”，首先匹配出“大学生”，然后匹配出“活动”，最后匹配出“中心”，切分过程如下表所示：

已匹配上的结果	待匹配串
NULL	大学生活动中心
大学生	活动中心
大学生/活动	中心
大学生/活动/中心	NULL

        最后分词结果为“大学生/活动/中心”。
        在最大长度匹配的分词方法中，需要用到从指定字符串返回指定位置的最长匹配词的方法。例如：当输入串是“大学生活动中心”，则返回“大学生”这个词，而不是返回“大”或者“大学”。

四、中文分词流程与结构
        中文分词总体流程与结构如下图所示：

图6 中文分词结构图

        简化版的中文分词切分过程说明如下：
        （1）生成全切分词图：根据基本词库对句子进行全切分，并且生成一个邻接链表表示的词图。
        （2）计算最佳切分路径：在这个词图的基础上，运用动态规划算法生成切分最佳路径。
        （3）词性标注：可以采用HMM方法进行词性标注。
        （4）未登录词识别：应用规则识别未登录词。
        （5）按需要的格式输出结果。
        复杂版本的中文分词切分过程说明如下：
        （1）对输入字符串切分成句子：对一段文本进行切分，依次从这段文本中切分出一个句子，然后对这个句子再进行切分。
        （2）原子切分：对于一个句子的切分，首先是通过原子切分，将整个句子切分成一个个的原子单元（即不可再切分的形式，例如ATM这样的英文单词可以看成不可再切分的）。
        （3）生成全切分词图：根据基本词库对句子进行全切分，并且生成一个邻接链表表示的词图。
        （4）计算最佳切分路径：在这个词图的基础上，运用动态规划算法生成切分最佳路径。
        （5）未登录词识别：进行中国人名、外国人名、地名、机构名等未登录名词的识别。
        （6）重新计算最佳切分路径。
        （7）词性标注：可以采用HMM方法或最大熵方法等进行词性标注。
        （8）根据规则调整切分结果：根据每个分词的词形以及词性进行简单地规则处理，如日期分词的合并。
        （9）按需要的格式输出结果：例如输出成Lucene需要的格式。

五、形成切分词图
        为了消除分词中的歧异，提高切分准确度，需要找出一句话所有可能的词，生成全切分词图。
        如果待切分的字符串有m个字符，考虑每个字符左边和右边的位置，则有m+1个点对应，点的编号从0到m。把候选词看成边，可以根据词典生成一个切分词图。切分词图是一个有向正权重的图。“有意见分歧”这句话的切分词图如下图所示：

图7 中文分词切分路径

        在“有意见分歧”的切分词图中：“有”这条边的起点是0，终点是1；“有意”这条边的起点是0，终点是2，以次类推。切分方案就是从源点0到终点5之间的路径，共存在两条切分路径：
        路径1:0——1——3——5    对应切分方案S1：有/    意见/    分歧/
        路径2:0——2——3——5    对应切分方案S2：有意/    见/    分歧/
        切分词图中的边都是词典中的词，边的起点和终点分别是词的开始和结束位置。
        邻接表表示的切分词图由一个链表表示的数组组成。首先需要实现一个单向链表，为了方便动态规划的方法计算最佳前驱词，在此单向链表的基础上形成逆向邻接表，然后从词典中形成以某个字符串的前缀开始的词集合，比如以”中华人民共和国成立了“这个字符串前缀开始的词集合是”中“、”中华“、”中华人民共和国“，一共三个词。在匹配的过程中，需要对英文和数字等进行特殊处理。

六、概率语言模型的分词方法
        从统计思想的角度来看，分词问题的输入是一个字串C=C_1,C₂,...,C_n，输出是一个词串S=W₁,W₂,...,W_m，其中m<=n。对于一个特定的字符串C，会有多个切分方案S对应，分词的任务就是在这些S中找出概率最大的一个切分方案，也就是对输入字符串切分出最有可能的词序列。
        概率语言模型分词的任务是：在全切分所得的所有结果中求某个切分方案S，使得P(S)最大。那么，如何来表示P(S)呢？为了容易实现，假设每个词之间的概率是上下文无关的，则：
        P(S) = P(W₁,W₂,...,W_m)  ~= P(W₁)xP(W₂)x...xP(W_m)
        P(S)一般是通过很多小数值的连乘积算出来的，对于不同的S，m的值是不一样的，一般来说m越大，P(S)会越小，即分出的词越多，概率越小。
        这个计算P(S)的公式也叫做基于一元概率语言模型的计算公式，这种分词方法简称一元分词。它综合考虑了切分出的词数和词频。一般来说，词数少，词频高的切分方案概率更高。考虑一种特殊的情况，所有词的出现概率相同，则一元分词退化成最小词切分方法。
        计算任意一个词出现的概率如下：
        P(W_i) = W_i在语料库中的出现词数n/语料库中的总词数N
        因此，logP(W_i) = log(Freq_w) - logN
        如果词概率的对数值事前已经算出来了，则结果直接用加法就可以得到logP(S)，而加法比乘法速度更快。
        从另外一个角度来看，计算最大概率等于求切分词图的最短路径。但是这里不采用Dijkstra算法，而采用动态规划的方法求解最短路径。

七、N元分词方法
        为了切分更准确，要考虑一个词所处的上下文。例如：“上海银行间的拆借利率上升”。因为“银行”后面出现了“间”这个词，所以把“上海银行”分成“上海”和“银行”两个词。
        一元分词假设前后两个词的出现概率是相互独立的，但实际不太可能。比如，沙县小吃附件经常有桂林米粉，所以这两个词是正相关。但是很少会有人把“沙县小吃”和“星巴克”相提并论。【羡慕】【嫉妒】【恨】这三个词有时候会连续出现。切分出来的词序列越通顺，越有可能是正确的切分方案。N元模型主要主要用来衡量词序列搭配的合理性。

八、新词发现
        词典中没有的，但是结合紧密的字或词有可能组成一个新词，比如：“水立方”如果不在词典中，可能会切分成两个词“水”和“立方”，如果在一篇文档中“水”和“立方”结合紧密，则“水立方”可能是一个新词。可以用信息熵来度量两个词的结合紧密程度。信息熵的一般公式是：
        I(X,Y) = log₂P(X,Y)/P(X)P(Y)
        如果X和Y的出现互相独立，则P(X,Y)的值和P(X)P(Y)的值相等，I(X,Y)为0.如果X和Y密切相关，P(X,Y)将比P(X)P(Y)大很多，I(X,Y)值也就远大于0。如果X和Y几乎不会相邻出现，而它们各自出现的概率又比较大，那么I(X,Y)将取负值，这时候X和Y负相关。
        此外，可以用Web信息挖掘的方法辅助发现新词：网页锚点上的文字可能是新词，例如“美甲”。可以考虑先对文档集合聚类，然后从聚合出来的相关文档中挖掘新词。

九、未登录词识别
        在分词时即时发现词表中没有的词叫做未登录词识别。未登录词在英文中叫做Out Of Vocabulary（简称OOV）词。常见的未登录词包括人名、地名、机构名。可以通过匹配规则来识别未登录词，可以用二元模型或三元模型来整合未登录词本身的概率和未登录词所在的上下文这两种信息。

十、词性标注
        词性用来描述一个词在上下文中的作用，相同的词在不同的上下文中会有不同的词性，比如：“中国开始对计划经济体制进行改革”和“医药卫生改革中经济问题”，“改革”一词，前者是动词，后者是名词，给词准确滴标注词性并不容易。
        隐马尔科夫模型（Hidden Markov Model, HMM）和基于转换的学习方法（Transformation Based Learning, TBL）是两种常用的词性标注方法。这两种方法都整合了频率和上下文两方面的特征来取得好的标注结果。具体来说，隐马尔科夫模型同时考虑到了词的生成概率和词性之间的转移概率。基于转换的学习方法先把每个词标注上最可能的词性，然后通过转换规则修正错误的标注，提高标注精度。

十一、平滑算法
        语料是有限的，不可能覆盖所有的词汇。由于训练模型的语料库规模有限且类型不同，许多合理的搭配关系在语料库中不一定出现，因此会造成模型出现数据稀疏现象。数据稀疏在统计自然语言处理中的一个表现就是零概率问题。
        有各种平滑算法来解决零概率问题。平滑有黑盒方法和白盒方法两种。黑盒平滑方法把一个项目作为不可分割的整体，而白盒平滑方法把一个项目作为可拆分的，可用于N元模型。加法平滑算法是最简单的一种平滑。