1 前言
两个月以来，我通过互联网自学了一些文本处理的知识，用自然语言处理和机器学习算法对《红楼梦》进行了一些分析。这个过程中我找到了一些有趣的发现，所以我想写一篇文章，既㲌与大家分享和讨论实验结果，也顺便做一个整理和总结。（其实虽说是两个月，但是中间停顿了一段时间，真正在做的时间大概是两周左右）
我开始做这件事情是因为之前看到了一篇挺好玩的文章，大概内容是，作者用“结巴分词”这个开源软件统计了红楼梦中各词汇的出现次数（也就是词频），然后用词频作为每个章回的特征，最终用“主成份分析”算法把每个章回映射到三维空间中，从而比较各个章回的用词有多么相似。（文章：用机器学习判定红楼梦后40回是否曹雪芹所写）作者的结论是后四十回的用词和前八十回有明显的差距。
看完文章之后，我觉得有两个小问题：首先，作者用的结巴分词里的词典是根据现代文的语料获得的（参见“结巴分词”开发者之前对网友的回复：模型的数据是如何生成的？ · Issue #7 · fxsjy/jieba），而《红楼梦》的文字风格是半文半白的，这样的分词方法准确性存疑；其次，虽然作者用《三国演义》做了对比，但是依然没有有力地证明用词差异没有受到情节变化的影响。于是我决定自己做一遍实验，用无字典分词的方法来分词，并且尝试剔除情节对分析的影响，看看结果会不会有所不同。
本来开始写的时候觉得 5000 字就差不多了，结果最后成文的时候竟然达到了 1.3 万字。即使这样，我也只能解释一下算法的大致工作过程，至于详细的原理，如果感兴趣的话可以找其他资料去学习，我也会附上一些资料链接。不然如果我写的面面俱到的话感觉可以出书了……至于结果如何？先卖个关子。（诶，不要直接滑到底啊！）
程序已在 GitHub 上开源，使用方法参见 README 文件：LouYu2015/analysis_on_the_story_of_a_stone。考虑到版权问题，我决定不提供《红楼梦》原文。如果想复现实验结果的话，可以去找小说网站下载。（更新：根据网友提醒，《红楼梦》因为作者去世远远超过 100 年而进入公有领域，不受版权限制。因此我把原文也补充了上去，现在按照说明运行程序即可复现结果。也可在这里获取《红楼梦》全文：紅樓夢 - 维基文库，自由的图书馆。）
2 文本预处理
这一步很基础，就不赘述了。简单来说，就是要根据标点符号，把每一个分句都切开，然后用统一的符号（这里我用的是井号）来标记切分点。这样对于后面的程序来说就好处理一些了。
虽然目标很简单，然而，有些细节还是需要额外处理一下的。比如，我找到的文本里，所有“性”啊，“露”啊之类的字都被用 『』 框了起来（可能为了过滤少儿不宜的内容？我怎么觉得框起来以后更奇怪了……），所以这种标点需要被删掉，不能当作分割符号。另外，每章开头的回目编号也需要去掉，因为这不算小说的内容。最后，文本中出现了一些电脑中没有的罕见字，不过好在文本中这些罕见字都在括号内用拆分字型的方法标了出来（比如“（左王右扁）”），所以理论上我可以把这些内容替换成一些原文中没有的字符（比如特殊符号），最后再替换回去。不过我太懒了，所以没有做这样的替换。理论上罕见字对后面的分析也不会有很大，因为后面涉及到的都是出现频率比较高的单词。
处理后的效果是这个样子：
3 构建全文索引
得到处理后的文本之后，我需要建立一个全文索引。这样是为了快速地查找原文内容，加速后面的计算。我使用了后缀树这个结构作为索引。这个数据结构比较复杂，所以我们可以先谈谈更简单的字典树。
3.1 字典树
首先，我们看看字典树的样子：
Free Image on Pixabay - Landscape, Tree, Flowers, Book
啊错了，这个才是字典树……
Trie - Wikipedia
上图中，每个圆圈是一个结点，代表着一个字符串（就是圆圈内的内容）；结点之间的连线是边，代表着一个字母。最上面的结点，也就是空着的那个结点，是根结点。如果我们从根结点不断向下走到某个结点，那么把经过的每一条边上的字母拼起来，就是这个结点代表的字符串了。这就是字典树的特点。
那么字典树是干什么用的呢？举个例子来说，假如我们想在这棵字典树里查找 “to” 这个单词，就可以先从根结点下面的边里找到第一个字母，也就是 “t” 这条边，从而找到 “t” 这个结点。然后我们再从 “t” 结点下面的边里找到第二个字母，也就是 “o” 这条边，就找到 “to” 这个结点了。假如 “to” 这个结点里储存了 “to” 的中文解释，那么我们只通过两次操作就找到了 to 的中文意思。这样比一个词一个词地找的方法快多了。这很像我们查字典的时候，先看第一个字母在字典中的位置，然后再看第二个字母……最终找到单词，因此被称为字典树。
3.2 后缀树
说完字典树，我们再说说后缀树的前身：后缀字典树。后缀字典树其实就是字典树，只不过里面的内容不是单词，而是一个字符串的所有后缀：从第一个字母到最后一个字母的内容，从第二个字母到最后一个字母的内容……以此类推。比如说，"banana" 的所有后缀就是 banana, anana, nana, ana, na 和 a。把这些内容都加到字典树里，就构成了后缀字典树。下面左图就是 banana 的后缀字典树：
https://www.slideshare.net/farseerfc/ukks-algorithm-of-suffix-tree
而后缀树和后缀字典树的区别就是，在后缀树中，我们要把下面只有一条边的结点去掉，然后把这个结点连接的两条边压缩成一条。比如，左图后缀字典树中的 b-a-n-a-n-a，在右图的后缀树中被压缩成了 banana 这一条边。此外，后缀树还使用了一个技巧，就是不储存边的内容，而是储存这些内容在原文中的位置。因为后缀树中的很多内容都是重复的，所以这个小技巧可以大大减少索引的大小（用专业的语言描述，它的空间复杂度是 O(n)）。
后缀树又有什么用呢？它最大的用途就是检索字符串中间的内容。比如，假如我想查找 an 在 banana 中哪里出现过，只需要查找代表 an 的结点，就找到了所有以 an 开头的结点： anana 和 ana。由于每次出现 an 的地方都一定会产生一个以 an 开头的后缀，而所有的后缀都在后缀树中，所以这样一定能够找到所有 an 出现的位置。后缀树的强大之处在于，即使我们把 banana 换成一篇很长很长的文章，我们也能很快地进行这样的检索。
最后，我使用了 Ukkonen 算法快速地创建了整篇《红楼梦》的后缀树（用专业的语言描述 Ukkonen 算法的速度：它的时间复杂度是 O(n)）。Ukkonen 算法比较复杂，所以这里我不会讲解 Ukkonen 算法，感兴趣的同学可以看看这些资料：
Ukkonen's suffix tree algorithm in plain English
后缀树的构造方法-Ukkonen详解 - 懒人小何的日志 - 网易博客
Ukkonen's Suffix Tree Construction - Part 6 - GeeksforGeeks
有了全文索引以后，后面的程序就好做了。
4 制作字典
等等，我们不是要无字典分词吗，为什么还要制作字典？其实无字典分词并不是完全不用字典，只是说字典是根据原文生成的，而不是提前制作的。为了进行分词，我们还是需要先找出文章中哪些内容像是单词，才能确定如何进行切分。
那么怎么确定哪些内容像单词呢？最容易想到的方法就是：把所有出现次数高的片段都当成单词。听上去很有道理，所以我们可以试一试，用后缀树查询红楼梦中的所有重复的片段，然后按出现次数排个序：
上面是出现频率前 20 的片段，括号内是出现次数。可以看到效果还不错，很多片段都是单词。然而，排在第六名的“了一”明明不是个单词，出现次数却比贾母还要高。可见这样的筛选方法还是有一定问题的。而且，这样被误当成单词的片段还有很多，例如“了的”、“的一”之类的。究其原因，是因为出现次数 TOP 5 的单字由高到低分别是“了、的、不、一、来”，所以它们的组合也会经常出现。为了排除这样的组合，我们可以用“凝固度”来进行进一步地筛选。
4.1 凝固度
凝固度的定义是：一个片段出现的频率比左右两部分分别出现的频率的乘积高出多少倍（注意，频率表示的是出现的比例，而频数表示的是出现的次数）。不过这句话太拗口了，还是用公式描述比较好。如果 P(AB) 是片段出现的频率，P(A) 是片段左边的字的出现的频率， P(B) 是右边的字出现的频率，那么凝固度 co 就是：
公式中，
对于超过两个字的片段，可以尝试每一种拆分方法（比如“贾宝玉”有“贾/宝玉”和“贾宝/玉”两种拆分方法），然后取各种方法的凝固度的最小值。
现在我选出《红楼梦》中出现次数大于 5 的片段，对它们的凝固度做个排序：
这是凝固度排名前 20 的组合，括号内是凝固度。可以看到效果还是不错的。
接着往下看，在 Top 20～100 里也基本没有不是单词的条目：
然而凝固度也有一定的局限性。再往后看的话，会发现里面还有很多片段是半个词，而它们的凝固度也挺高的。例如：“香院”（完整的词应该是“梨香院”）、“太太太太”（完整的词应该是“老太太太太”）。想想也有道理，这些片段虽然是半个词，但是它们确实也跟完整的单词一样是“凝固”在一起的。所以，光看凝固度是不够的，还要通过上下文判断这个词是否完整。
4.2 自由度
为了排除掉不完整的单词，我们可以使用自由度这个概念来继续过滤。自由度的思想是这样的：如果一个组合是一个不完整的单词，那么它总是作为完整单词的一部分出现，所以相邻的字就会比较固定。比如说，“香院”在原文中出现了 23 次，而“梨香院”出现了 22 次，也就是说“梨”在“香院”的左边一起出现的频率高达 95.7%，所以我们有把握认为”香院”不是完整的单词。而自由度描述的就是一个片段的相邻字有多么的多样、不固定。如果片段的自由度比较高，就说明这个词应该是完整的。
因为相邻字分为左侧和右侧，所以自由度也分为左右两部分。以左侧的自由度为例，计算公式就是左侧相邻字的每一种字的频率的总信息熵。也就是说，如果
是左侧自由度，
到
是每种左侧相邻字出现的频率，那么：
（对于没学过信息熵的同学来说这个公式可能很晦涩，反正记住左侧自由度体现了左侧相邻字的多样性就可以了。）
我们把左侧自由度最低的 20 个组合拿出来，可以看到确实过滤出来了很多不是单词的内容：
（括号内为左侧自由度）
右侧也同理，有些片段明显是半个单词：
（括号内为右侧自由度）
4.3 最终的单词表
有了这些明确的评判标准，我们就可以把单词筛选出来了。我最终选择的判断标准是：出现次数大于等于 5，且凝固度、左侧自由度、右侧自由度都大于 1。然而这个标准还是太宽松了。于是，我又设计了一个公式，把这些数据综合起来：
也就是说，我简单粗暴地把凝固度和自由度乘了起来，作为每个片段的分数。这样只要其中一个标准的值比较低，总分就会比较低。于是我的判断标准里又多了一条：总分还要大于等于 100。
经过层层遴选之后，单词表初步成型了。我从最终结果中随机抽取了 100 个条目，其中有 47 个是单词：
这意味单词表的正确率只有一半左右。不过，在错误的条目里，很多条目的切分其实正确的，只是有好几个词粘到了一起：
虽然正确率不高，但其实没有必要通过调高筛选标准的方法来进行更严格的过滤了。随后分词算法将会解决单词没有被切开的问题。如果继续调高标准，可能会导致很多确实是单词的条目被去除。
参考资料：
基于信息熵的无字典分词算法 - 成都笨笨 - 博客园
5 分词
之前在筛选单词的时候，思路就是用各种各样的数值标准进行判断。而对于“分词”这个看似更加困难的问题，思路也是类似的：制定一个评价切分方案的评分标准，然后找出评分最高的切分方案。评分标准是什么呢？最简单的标准就是，把切分之后每个片段是单词的概率都乘起来，作为这个切分方案正确的概率，也就是评分标准。我们假设，一个片段是单词的概率，就是这个片段在原文中的出现频率。
有了评分标准之后，还有一个问题：如何找出分数最高的切分方案呢？肯定不能一个一个地尝试每一种方案，不然速度实在是太慢了。我们可以用一个数学方法来简化计算：维特比算法。
5.1 维特比算法
维特比算法本质上就是一个动态规划算法。它的想法是这样的：对于句子的某个局部来说，这一部分的最佳切分方案是固定的，不随上下文的变化而变化；如果把这个最佳切分方案保存起来，就能减少很多重复的计算。我们可以从第一个字开始，计算前两个字，前三个字，前四个字……的最佳切分方案，并且把这些方案保存起来。因为我们是依次计算的，所以每当增加一个字的时候，我们只要尝试切分最后一个单词的位置就可以了。这个位置前面的内容一定是已经计算过的，所以通过查询之前的切分方案即可计算出分数。这就是维特比算法的工作原理。
举个例子，这是计算“宝玉黛玉”每种切分方式的得分的过程：
这样得到每种切分方式的得分之后，程序先根据最后一步的结果，把“黛玉”切分出去，剩下“宝玉”。然后程序再看“宝玉”的各种切分结果，发现不切分的得分最高，于是把“宝玉”也切分了出去。最后，程序发现没有剩下的内容了，于是切分完成了。
5.2 一些的调整
在构造单词表的时候，我计算了每个片段有多么像单词，也就是分数。然而，后面的分词算法只考虑了片段出现的频率，而没有用到片段的分数。于是，我简单粗暴地把片段的分数加入到了算法中：把片段的频率乘上片段的分数，作为加权了的频率。这样那些更像单词的片段具有更高的权重，就更容易被切分出来了。
此外，还有一个问题：如果一个片段不在字典中，怎样计算它的频率？在需要外界提供字典的分词算法中，这是一个比较棘手的问题。不过在无字典（准确的说是自动构造字典）的算法中，这反而是一个比较容易解决的问题：任何要切分的片段一定会出现在后缀树中，因为这个片段是原文的一部分！所以，我们只需要通过后缀树查询这个片段的频数，就可以计算它在原文中的频率了。
最后还有一个小优化。我们知道，一般中文单词的长度不会超过四个字，因此在程序枚举切分方法的时候，只需要尝试最后四个切分位置就可以了。这样就把最长的切分片段限制在了四个字以内，而且对于长句子来说也减少了很多不必要的尝试。
5.3 分词算法的测试
我选择了两段原文内容来测试算法的准确性。
这是第二回开头的一段叙事性片段的机器分词结果：
这是人工分词的结果：
经过统计，程序的准确率是 85.71%（意义是程序切开的位置有多少是应该切开的），召回率是 75.00%（意义是应该切开的位置有多少被程序切开了）。这个结果看上去不是很高，因为大部分开源的分词软件准确率都能达到 90% 以上，甚至能达到 97% 以上。不过，毕竟我用的是无字典的分词，而且算法也比较简单，所以我还是比较满意的。
下面再看看诗词类片段的分词效果。这是《葬花吟》的机器分词结果：
这是人工分词结果：
这下程序的准确率下降到了 74.07%，召回率也下降到了 67.04%，分别下降了将近 10%，可见诗歌的分词更难一些。这也在情理之中，因为诗词中有很多不常用词，有些词甚至只出现过一次，所以电脑很难从统计数据中发掘信息。
原文发布时间为：2017-09-17
本文作者：楼宇
本文来自云栖社区合作伙伴“Python中文社区”，了解相关信息可以关注“Python中文社区”微信公众号
