用 Python 分析《红楼梦》（1）

1 前言

两个月以来，我通过互联 自学了一些文本处理的知识，用自然语言处理和机器学习算法对《红楼梦》进行了一些分析。这个过程中我找到了一些有趣的发现，所以我想写一篇文章，既?与大家分享和讨论实验结果，也顺便做一个整理和总结。（其实虽说是两个月，但是中间停顿了一段时间，真正在做的时间大概是两周左右）

本来开始写的时候觉得 5000 字就差不多了，结果最后成文的时候竟然达到了 1.3 万字。即使这样，我也只能解释一下算法的大致工作过程，至于详细的原理，如果感兴趣的话可以找其他资料去学习，我也会附上一些资料链接。不然如果我写的面面俱到的话感觉可以出书了……至于结果如何卖个关子。（诶，不要直接滑到底啊！）

2 文本预处理

这一步很基础，就不赘述了。简单来说，就是要根据标点符 ，把每一个分句都切开，然后用统一的符 （这里我用的是井 ）来标记切分点。这样对于后面的程序来说就好处理一些了。

虽然目标很简单，然而，有些细节还是需要额外处理一下的。比如，我找到的文本里，所有“性”啊，“露”啊之类的字都被用 『』 框了起来（可能为了过滤少儿不宜的内容怎么觉得框起来以后更奇怪了……），所以这种标点需要被删掉，不能当作分割符 。另外，每章开头的回目编 也需要去掉，因为这不算小说的内容。最后，文本中出现了一些电脑中没有的罕见字，不过好在文本中这些罕见字都在括 内用拆分字型的方法标了出来（比如“（左王右扁）”），所以理论上我可以把这些内容替换成一些原文中没有的字符（比如特殊符 ），最后再替换回去。不过我太懒了，所以没有做这样的替换。理论上罕见字对后面的分析也不会有很大，因为后面涉及到的都是出现频率比较高的单词。

处理后的效果是这个样子：

Free Image on Pixabay – Landscape, Tree, Flowers, Book

啊错了，这个才是字典树……

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 20～100 里也基本没有不是单词的条目：

（括 内为左侧自由度）

右侧也同理，有些片段明显是半个单词：

也就是说，我简单粗暴地把凝固度和自由度乘了起来，作为每个片段的分数。这样只要其中一个标准的值比较低，总分就会比较低。于是我的判断标准里又多了一条：总分还要大于等于 100。

经过层层遴选之后，单词表初步成型了。我从最终结果中随机抽取了 100 个条目，其中有 47 个是单词：

虽然正确率不高，但其实没有必要通过调高筛选标准的方法来进行更严格的过滤了。随后分词算法将会解决单词没有被切开的问题。如果继续调高标准，可能会导致很多确实是单词的条目被去除。

参考资料：

基于信息熵的无字典分词算法 – 成都笨笨 – 博客园

5 分词

之前在筛选单词的时候，思路就是用各种各样的数值标准进行判断。而对于“分词”这个看似更加困难的问题，思路也是类似的：制定一个评价切分方案的评分标准，然后找出评分最高的切分方案。评分标准是什么呢简单的标准就是，把切分之后每个片段是单词的概率都乘起来，作为这个切分方案正确的概率，也就是评分标准。我们假设，一个片段是单词的概率，就是这个片段在原文中的出现频率。

有了评分标准之后，还有一个问题：如何找出分数最高的切分方案呢定不能一个一个地尝试每一种方案，不然速度实在是太慢了。我们可以用一个数学方法来简化计算：维特比算法。

5.1 维特比算法

维特比算法本质上就是一个动态规划算法。它的想法是这样的：对于句子的某个局部来说，这一部分的最佳切分方案是固定的，不随上下文的变化而变化；如果把这个最佳切分方案保存起来，就能减少很多重复的计算。我们可以从第一个字开始，计算前两个字，前三个字，前四个字……的最佳切分方案，并且把这些方案保存起来。因为我们是依次计算的，所以每当增加一个字的时候，我们只要尝试切分最后一个单词的位置就可以了。这个位置前面的内容一定是已经计算过的，所以通过查询之前的切分方案即可计算出分数。这就是维特比算法的工作原理。

举个例子，这是计算“宝玉黛玉”每种切分方式的得分的过程：

这是人工分词的结果：

这是人工分词结果：

这下程序的准确率下降到了 74.07%，召回率也下降到了 67.04%，分别下降了将近 10%，可见诗歌的分词更难一些。这也在情理之中，因为诗词中有很多不常用词，有些词甚至只出现过一次，所以电脑很难从统计数据中发掘信息。

原文发布时间为：2017-09-17

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34518 人正在系统学习中 相关资源：蓝梦软件BestRecoveryForOracle碎片级数据恢复软件-Oracle工具类…