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
啊错了，这个才是字典树……
上图中，每个圆圈是一个结点，代表着一个字符串（就是圆圈内的内容）；结点之间的连线是边，代表着一个字母。最上面的结点，也就是空着的那个结点，是根结点。如果我们从根结点不断向下走到某个结点，那么把经过的每一条边上的字母拼起来，就是这个结点代表的字符串了。这就是字典树的特点。
那么字典树是干什么用的呢？举个例子来说，假如我们想在这棵字典树里查找 “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 制作字典
等等，我们不是要无字典分词吗，为什么还要制作字典？其实无字典分词并不是完全不用字典，只是说字典是根据原文生成的，而不是提前制作的。为了进行分词，我们还是需要先找出文章中哪些内容像是单词，才能确定如何进行切分。
那么怎么确定哪些内容像单词呢？最容易想到的方法就是：把所有出现次数高的片段都当成单词。听上去很有道理，所以我们可以试一试，用后缀树查询红楼梦中的所有重复的片段，然后按出现次数排个序：
宝玉(3983)、笑道(2458)、太太(1982)、什么(1836)、凤姐(1741)、了一(1697)、贾母(1675)、一个(1520)、也不(1448)、夫人(1437)、黛玉(1370)、我们(1233)、那里(1182)、袭人(1144)、姑娘(1142)、去了(1090)、宝钗(1079)、不知(1074)、王夫人(1061)、起来(1059)
上面是出现频率前 20 的片段，括号内是出现次数。可以看到效果还不错，很多片段都是单词。然而，排在第六名的“了一”明明不是个单词，出现次数却比贾母还要高。可见这样的筛选方法还是有一定问题的。而且，这样被误当成单词的片段还有很多，例如“了的”、“的一”之类的。究其原因，是因为出现次数 TOP 5 的单字由高到低分别是“了、的、不、一、来”，所以它们的组合也会经常出现。为了排除这样的组合，我们可以用“凝固度”来进行进一步地筛选。
4.1 凝固度
凝固度的定义是：一个片段出现的频率比左右两部分分别出现的频率的乘积高出多少倍（注意，频率表示的是出现的比例，而频数表示的是出现的次数）。不过这句话太拗口了，还是用公式描述比较好。如果 P(AB) 是片段出现的频率，P(A) 是片段左边的字的出现的频率， P(B) 是右边的字出现的频率，那么凝固度 co 就是：
公式中， 
就是左右部分在完全随机组合的情况下被组合到一起的概率。凝固度的思想是：如果片段实际出现的概率比被随机组合出来的概率高出很多倍，就说明这样的组合应该不是意外产生的，而是有一些关联的。这个关联很可能就是因为这个片段是一个不可分割的整体，也就是单词。
对于超过两个字的片段，可以尝试每一种拆分方法（比如“贾宝玉”有“贾/宝玉”和“贾宝/玉”两种拆分方法），然后取各种方法的凝固度的最小值。
现在我选出《红楼梦》中出现次数大于 5 的片段，对它们的凝固度做个排序：
翡翠(171415.92)、茉莉(171415.92)、砒霜(171415.92)、逶迤(142846.60)、诽谤(142846.60)、徘徊(142846.60)、缱绻(142846.60)、乜斜(142846.60)、戥子(142846.60)、籰子(142846.60)、姽嫿(122439.94)、蝴蝶(122439.94)、囟门(122439.94)、槟榔(122439.94)、琵琶(122439.94)、娈童(119038.83)、筏子(119038.83)、牲口(119038.83)、踌躇(107134.95)、隄防(107134.95)
这是凝固度排名前 20 的组合，括号内是凝固度。可以看到效果还是不错的。
接着往下看，在 Top 20～100 里也基本没有不是单词的条目：
腼腆、隄防、甬路、趔趄、蚊子、狮子、璎珞、疗治、羔子、跛足、尧舜、嫦娥、陛见、簸箩、梆子、粳米、竭力、栗子、撺掇、葵官、芭蕉、玲珑、俞禄、妯娌、嘁嘁喳喳、玷辱、奚落、互相、譬如、腕上、祷告、攮的、钥匙、觑着、恣意、矶上、馒头、阎王、椒房、茯苓、琪官、牡丹、恒王、凹晶、翰林、畸角、淌眼、篮子、滋味、韶华、爆竹、涨了、芍药、估量、拷问、杌子、嗓子、搪塞、晦气、麒麟、玫瑰、葫芦、躬身、恳切、崽子、盹儿、皂白、谣言、凸碧、唯唯、赫赫、簌簌、荫堂、嗤的、唠叨、努嘴、吆喝、荳官、茯苓霜、艰难
然而凝固度也有一定的局限性。再往后看的话，会发现里面还有很多片段是半个词，而它们的凝固度也挺高的。例如：“香院”（完整的词应该是“梨香院”）、“太太太太”（完整的词应该是“老太太太太”）。想想也有道理，这些片段虽然是半个词，但是它们确实也跟完整的单词一样是“凝固”在一起的。所以，光看凝固度是不够的，还要通过上下文判断这个词是否完整。
4.2 自由度
为了排除掉不完整的单词，我们可以使用自由度这个概念来继续过滤。自由度的思想是这样的：如果一个组合是一个不完整的单词，那么它总是作为完整单词的一部分出现，所以相邻的字就会比较固定。比如说，“香院”在原文中出现了 23 次，而“梨香院”出现了 22 次，也就是说“梨”在“香院”的左边一起出现的频率高达 95.7%，所以我们有把握认为”香院”不是完整的单词。而自由度描述的就是一个片段的相邻字有多么的多样、不固定。如果片段的自由度比较高，就说明这个词应该是完整的。
因为相邻字分为左侧和右侧，所以自由度也分为左右两部分。以左侧的自由度为例，计算公式就是左侧相邻字的每一种字的频率的总信息熵。也就是说，如果 
是左侧自由度， 
到 
是每种左侧相邻字出现的频率，那么：
（对于没学过信息熵的同学来说这个公式可能很晦涩，反正记住左侧自由度体现了左侧相邻字的多样性就可以了。）
我们把左侧自由度最低的 20 个组合拿出来，可以看到确实过滤出来了很多不是单词的内容：
泪来(0.111)、在话(0.112)、慢的(0.116)、头们(0.117)、今我(0.121)、云笑(0.122)、以我(0.141)、王二(0.146)、里知道(0.146)、己也(0.151)、会子又(0.154)、太和(0.156)、用说(0.159)、嘻的(0.165)、今且(0.169)、么东西(0.187)、苦来(0.187)
（括号内为左侧自由度）
右侧也同理，有些片段明显是半个单词：
有什(0.034)、周瑞家(0.053)、老太(0.065)、薛姨(0.072)、也罢(0.085)、老祖(0.093)、哭起(0.100)、在话(0.112)、听下(0.113)、些东(0.118)、林之(0.121)、个婆(0.126)、我告(0.129)、老嬷(0.139)、二夫(0.144)、邢王二(0.149)、就罢(0.154)、到自(0.169)、这会(0.175)、大嫂(0.179)
（括号内为右侧自由度）
4.3 最终的单词表
有了这些明确的评判标准，我们就可以把单词筛选出来了。我最终选择的判断标准是：出现次数大于等于 5，且凝固度、左侧自由度、右侧自由度都大于 1。然而这个标准还是太宽松了。于是，我又设计了一个公式，把这些数据综合起来：
也就是说，我简单粗暴地把凝固度和自由度乘了起来，作为每个片段的分数。这样只要其中一个标准的值比较低，总分就会比较低。于是我的判断标准里又多了一条：总分还要大于等于 100。
经过层层遴选之后，单词表初步成型了。我从最终结果中随机抽取了 100 个条目，其中有 47 个是单词：
佩凤、寻常、歇下、王公、不提、仍往、亲热、之后、犯事、小戏子、现今、两三天、缝儿、弯着腰、魂飞、故典、海棠社、支使、发热、感激、压倒、一座、已到、洋漆、包勇、查抄、舅爷、石榴、报与、戥子、一匹、拐子、家里、林黛玉、法子、空门、值钱、抿嘴、未娶、秋爽斋、发誓、明日、相伴、舒服、小幺儿、李纨、仙长
这意味单词表的正确率只有一半左右。不过，在错误的条目里，很多条目的切分其实正确的，只是有好几个词粘到了一起：
赶不上、个字、料他、你快去、丫鬟婆子、无有不、抿着嘴笑、在外间睡、把我、一个小、叫我怎么、饭来、句好话、忙命人、恼的、答应了、提那、告辞了、庵里、和二奶奶、谢他、个女人、领着、急忙进、池子里、捶着、手里拿着一、五百两、之为人、和姑娘们、不知怎么样、骂一、是那里来的、家的小姐、十岁的、个眼睛、如今我、几个小、丫鬟名、省一、俗了、一一的、听了这话、撵出去、梳洗了、淡淡的、恨不能、可惜了、件大事、作诗的、与尤老、散与、究竟不
虽然正确率不高，但其实没有必要通过调高筛选标准的方法来进行更严格的过滤了。随后分词算法将会解决单词没有被切开的问题。如果继续调高标准，可能会导致很多确实是单词的条目被去除。
参考资料：
5 分词
之前在筛选单词的时候，思路就是用各种各样的数值标准进行判断。而对于“分词”这个看似更加困难的问题，思路也是类似的：制定一个评价切分方案的评分标准，然后找出评分最高的切分方案。评分标准是什么呢？最简单的标准就是，把切分之后每个片段是单词的概率都乘起来，作为这个切分方案正确的概率，也就是评分标准。我们假设，一个片段是单词的概率，就是这个片段在原文中的出现频率。
有了评分标准之后，还有一个问题：如何找出分数最高的切分方案呢？肯定不能一个一个地尝试每一种方案，不然速度实在是太慢了。我们可以用一个数学方法来简化计算：维特比算法。
5.1 维特比算法
维特比算法本质上就是一个动态规划算法。它的想法是这样的：对于句子的某个局部来说，这一部分的最佳切分方案是固定的，不随上下文的变化而变化；如果把这个最佳切分方案保存起来，就能减少很多重复的计算。我们可以从第一个字开始，计算前两个字，前三个字，前四个字……的最佳切分方案，并且把这些方案保存起来。因为我们是依次计算的，所以每当增加一个字的时候，我们只要尝试切分最后一个单词的位置就可以了。这个位置前面的内容一定是已经计算过的，所以通过查询之前的切分方案即可计算出分数。这就是维特比算法的工作原理。
举个例子，这是计算“宝玉黛玉”每种切分方式的得分的过程：
宝: p = 0.0079487991（最佳切分）
宝玉: p = 0.0079427436（最佳切分）
宝/玉: p = 0.00795 * 0.00827 = 0.0000657630
宝玉黛: p = 0.0000077623
宝/玉黛: p = 0.00795 * 0.00001 = 0.0000000511
宝玉/黛: p = 0.00794 * 0.00189 = 0.0000149872（最佳切分）
宝玉黛玉: p = 0.0000096861
宝/玉黛玉: p = 0.00795 * 0.00001 = 0.0000000617
宝玉/黛玉: p = 0.00794 * 0.00273 = 0.0000216996（最佳切分）
宝玉黛/玉: p = 0.00001 * 0.00827 = 0.0000001240（注意，这里计算时使用的是“宝玉黛”的最佳切分的分数，而不是“宝玉黛”这个片段本身的分数）
这样得到每种切分方式的得分之后，程序先根据最后一步的结果，把“黛玉”切分出去，剩下“宝玉”。然后程序再看“宝玉”的各种切分结果，发现不切分的得分最高，于是把“宝玉”也切分了出去。最后，程序发现没有剩下的内容了，于是切分完成了。
5.2 一些的调整
在构造单词表的时候，我计算了每个片段有多么像单词，也就是分数。然而，后面的分词算法只考虑了片段出现的频率，而没有用到片段的分数。于是，我简单粗暴地把片段的分数加入到了算法中：把片段的频率乘上片段的分数，作为加权了的频率。这样那些更像单词的片段具有更高的权重，就更容易被切分出来了。
此外，还有一个问题：如果一个片段不在字典中，怎样计算它的频率？在需要外界提供字典的分词算法中，这是一个比较棘手的问题。不过在无字典（准确的说是自动构造字典）的算法中，这反而是一个比较容易解决的问题：任何要切分的片段一定会出现在后缀树中，因为这个片段是原文的一部分！所以，我们只需要通过后缀树查询这个片段的频数，就可以计算它在原文中的频率了。
最后还有一个小优化。我们知道，一般中文单词的长度不会超过四个字，因此在程序枚举切分方法的时候，只需要尝试最后四个切分位置就可以了。这样就把最长的切分片段限制在了四个字以内，而且对于长句子来说也减少了很多不必要的尝试。
5.3 分词算法的测试
我选择了两段原文内容来测试算法的准确性。
这是第二回开头的一段叙事性片段的机器分词结果：
只见/封肃/方/回来，欢天喜地，众人/忙问/端的，他/乃说道，原来/本府/新/升的/太爷，姓贾名化，本/湖州人氏，曾与/女婿/旧日/相交，方才/在/咱们/前/过去，因/看见/娇杏/那/丫头/买线，所以/他/只当/女婿/移/住/于此，我一/一/将原故/回明，那/太爷倒/伤感/叹息/了一回，又问/外孙女儿，我说/看灯/丢了，太/爷说，不妨，我自/使/番役/务必/探/访/回来，说/了一回/话，临走/倒/送了/我/二两银子，甄家/娘子/听了，不免/心中/伤感，一宿无话，至/次日/早有/雨村/遣人/送了/两封/银子，四匹/锦缎，答/谢甄家娘/子，又/寄/一封/密/书与/封肃，托他/向/甄家/娘子/要/那/娇杏/作二房，封肃/喜的/屁滚尿流，巴不得/去/奉承，便在/女儿/前一/力/撺掇/成了，乘/夜/只/用一/乘小轿，便把/娇杏/送/进去/了，雨村/欢喜/自不必说，乃/封/百金/赠/封肃，外/又谢/甄家/娘子/许多/物/事，令其/好生养/赡，以待/寻访/女儿/下落，封肃/回家/无话，却说/娇杏/这/丫鬟，便是/那年/回顾/雨村/者，因/偶然/一/顾，便/弄出/这段事来，亦是/自己/意/料不/到之/奇缘，谁想/他/命运/两/济，不/承望/自/到/雨村/身边，只/一年/便/生了一子，又/半载，雨村/嫡妻/忽染疾/下世，雨村/便将他/扶/侧/作/正室/夫人/了，正是，偶因/一/着/错，便/为人/上/人
这是人工分词的结果：
只见/封肃/方/回来，欢天喜地，众人/忙问/端的，他/乃/说道，原来/本府/新升/的/太爷，姓/贾/名/化，本/湖州/人氏，曾/与/女婿/旧日/相交，方才/在/咱们/前/过去，因/看见/娇杏/那/丫头/买线，所以/他/只当/女婿/移住/于/此，我/一一/将/原故/回明，那/太爷/倒/伤感/叹息/了/一回，又/问/外孙女儿，我/说/看灯/丢了，太爷/说，不妨，我/自/使/番役/务必/探访/回来，说/了/一回话，临走/倒/送了/我/二两/银子，甄家/娘子/听了，不免/心中/伤感，一宿/无话，至/次日/早有/雨村/遣人/送了/两封/银子，四匹/锦缎，答谢/甄家/娘子，又/寄/一封/密书/与/封肃，托/他/向/甄家/娘子/要/那/娇杏/作/二房，封肃/喜的/屁滚尿流，巴不得/去/奉承，便/在/女儿/前/一力/撺掇/成了，乘夜/只用/一乘/小轿，便/把/娇杏/送/进去/了，雨村/欢喜/自/不必/说，乃/封/百金/赠/封肃，外/又/谢/甄家/娘子/许多/物事，令/其/好生/养赡，以/待/寻访/女儿/下落，封肃/回家/无话，却说/娇杏/这/丫鬟，便是/那年/回顾/雨村/者，因/偶然/一顾，便/弄出/这段/事/来，亦是/自己/意料/不到/之/奇缘，谁想/他/命运/两济，不/承望/自/到/雨村/身边，只/一年/便/生了/一/子，又/半载，雨村/嫡妻/忽/染疾/下世，雨村/便/将/他/扶侧/作/正室/夫人/了，正是，偶/因/一着/错，便/为/人上人
经过统计，程序的准确率是 85.71%（意义是程序切开的位置有多少是应该切开的），召回率是 75.00%（意义是应该切开的位置有多少被程序切开了）。这个结果看上去不是很高，因为大部分开源的分词软件准确率都能达到 90% 以上，甚至能达到 97% 以上。不过，毕竟我用的是无字典的分词，而且算法也比较简单，所以我还是比较满意的。
下面再看看诗词类片段的分词效果。这是《葬花吟》的机器分词结果：
花谢/花飞/花满/天，红/消/香/断有/谁怜，游丝/软/系飘春榭，落/絮轻沾扑/绣帘，闺中/女儿/惜春/暮，愁绪/满怀/无/释/处，手/把花锄/出/绣帘，忍/踏/落花/来/复去，柳丝榆荚/自/芳菲，不管/桃/飘/与李/飞，桃李/明年/能再/发，明年/闺中/知/有谁，三月/香/巢已垒成，梁间/燕子/太/无情，明年/花/发/虽可/啄，却不/道/人去/梁空巢/也/倾，一年/三百六十/日，风/刀霜剑严/相/逼，明/媚/鲜妍/能/几时，一朝/飘泊/难/寻觅，花开/易见/落/难寻，阶前/闷/杀/葬花/人，独/把花锄/泪/暗洒，洒/上/空/枝/见/血/痕，杜/鹃/无语/正/黄昏，荷锄归/去掩/重门，青灯/照壁/人初/睡，冷/雨敲窗被/未/温，怪/奴/底/事/倍伤/神，半/为/怜春/半/恼/春，怜春/忽至/恼/忽/去，至/又/无言/去/不闻，昨宵/庭外悲歌/发，知是/花魂/与/鸟魂，花魂/鸟魂/总难/留，鸟/自/无言/花自/羞，愿/奴/胁下/生/双翼，随/花/飞到/天尽头，天尽头，何处/有/香/丘，未/若锦/囊收艳骨，一堆/净/土掩/风流，质本洁/来/还/洁/去，强/于/污/淖陷渠沟，尔今/死去/侬收葬，未卜/侬/身/何日/丧，侬今葬/花人笑痴，他年葬侬/知是谁，试看/春/残花/渐/落，便是/红颜老/死时，一朝春尽/红颜老，花落人亡/两/不知
这是人工分词结果：
花谢/花飞/花满天，红消/香断/有/谁/怜，游丝/软系/飘/春榭，落絮/轻沾/扑/绣帘，闺中/女儿/惜/春暮，愁绪/满怀/无/释处，手/把/花/锄/出/绣帘，忍/踏/落花/来/复/去，柳丝/榆荚/自/芳菲，不管/桃飘/与/李飞，桃李/明年/能/再发，明年/闺中/知/有/谁，三月/香巢/已/垒成，梁间/燕子/太/无情，明年/花发/虽/可啄，却/不道/人去/梁空/巢/也/倾，一年/三百/六十/日，风刀/霜剑/严/相逼，明媚/鲜妍/能/几时，一朝/飘泊/难/寻觅，花开/易见/落/难寻，阶前/闷杀/葬花人，独/把/花/锄/泪/暗洒，洒上/空枝/见/血痕，杜鹃/无语/正/黄昏，荷锄/归去/掩/重门，青灯/照壁/人/初睡，冷雨/敲窗/被/未温，怪/奴/底事/倍/伤神，半为/怜春/半/恼春，怜春/忽至/恼/忽去，至/又/无言/去/不闻，昨宵/庭外/悲歌/发，知是/花魂/与/鸟魂，花魂/鸟魂/总/难留，鸟/自/无言/花/自/羞，愿/奴/胁下/生/双翼，随花/飞到/天/尽头，天/尽头，何处/有/香丘，未/若/锦囊/收/艳骨，一堆/净土/掩/风流，质/本/洁/来/还/洁/去，强/于/污淖/陷/渠沟，尔/今/死去/侬/收葬，未卜/侬身/何日/丧，侬/今/葬花/人/笑痴，他年/葬/侬/知/是/谁，试看/春残/花/渐/落，便是/红颜/老/死/时，一朝/春尽/红颜/老，花落/人亡/两/不知
这下程序的准确率下降到了 74.07%，召回率也下降到了 67.04%，分别下降了将近 10%，可见诗歌的分词更难一些。这也在情理之中，因为诗词中有很多不常用词，有些词甚至只出现过一次，所以电脑很难从统计数据中发掘信息。
6 词频统计
完成分词以后，词频统计就非常简单了。我们只需要根据分词结果把片段切分开，去掉长度为一的片段（也就是单字），然后数一下每一种片段的个数就可以了。
这是出现次数排名前 20 的单词：
宝玉(3940)、笑道(2314)、凤姐(1521)、什么(1432)、贾母(1308)、袭人(1144)、一个(1111)、黛玉(1102)、我们(1068)、王夫人(1059)、如今(1016)、宝钗(1014)、听了(938)、出来(934)、老太太(908)、你们(890)、去了(879)、怎么(867)、太太(856)、姑娘(856)
（括号内为频数）
可以跟之前只统计出现次数，不考虑切分问题的排名做个对比：
宝玉(3983)、笑道(2458)、太太(1982)、什么(1836)、凤姐(1741)、了一(1697)、贾母(1675)、一个(1520)、也不(1448)、夫人(1437)、黛玉(1370)、我们(1233)、那里(1182)、袭人(1144)、姑娘(1142)、去了(1090)、宝钗(1079)、不知(1074)、王夫人(1061)、起来(1059)
（括号内为频数）
通过分词后的词频，我们发现《红楼梦》中的人物戏份由多到少依次是宝玉、凤姐、贾母、袭人、黛玉、王夫人和宝钗。然而，这个排名是有问题的，因为”林黛玉”这个词的出现次数还有 267 次，需要加到黛玉的戏份里，所以其实黛玉的戏份比袭人多。同理，“老太太”一般是指贾母，所以贾母的戏份加起来应该比凤姐多。正确的排名应该是宝玉、贾母、凤姐、黛玉、袭人、王夫人和宝钗。
此外，我们还发现《红楼梦》中的人物很爱笑，因为除了人名以外出现次数最多的单词就是“笑道” : )
我把完整的词频表做成了一个网页，感兴趣的话可以去看一下：红楼词表 第二版
最后，我随机选择了词频表中的 200 项条目，用来估计其中有多少是真正的单词。其中有 82 条是单词：
暗地、老君、男人、匈奴、病在垂危、闻名不如、追索、气怔、神昏、照照、守着、档子、送去、下山、玉皇、菲材获谴、托他、本身、这番、大海、十载、记的、遵谕、芸哥儿、现买、专司其职、天上人间、法官、推就、阶上、所知、别物、朝阳、惧罪、入塾、前代、当地、神瑛、名利、哗喇、句句、辫梢、端上、驸马、按理、开金、以下、清官、香甜、猿背、避人、开眼、殊不知、笞杖、祭吊、药方、色红、铁锁、看见、逗蜂轩、不胜、上楼、正官禄马、国中、入会、转步、魄化、等等儿、公侯、代善、排律、只见、昼夜、外国、日月、莼噎满喉、夸奖、礼仪、自称、王妃、千秋、买棺盛殓
而 118 条不是单词：
上值日的、听我说、带的、到馆来、馀之、搛了、一两点、管这、谁先、料也、且喜、一两天、糯五十斛、命坐、杀了、在你、痛的、等都说、现吃、怔了、这金、个个是、我原、氏忙、也错不得、子本、毁僧谤、遮着、了手、眼泪直、菜已、己有、别理、凉着、遂不、仍复、的差役、们把、太爷的、你只怨、同你去、忙进去、腌脏话、在后面、又惊又、队队、名的、去睬他、与平、一个钱、没听、株枯木、正二刻、静了、已醒了、酽酽的沏、细说与、醉中、个年高有、松了、了两声、贾珍也、让至、早晚才、描鸾刺、那里肯、松的、秋闺怨、张花梨、荣宁两、待你、再多言、反吓、里调、如若、庶不、是颗、到书、当此、点上灯来、去托、又宽、又联道、你特、行一、却难、蔷大爷芸、其真、人情等、才吃了药、再拣、而诞、两手抱、便福、被劫、家大小、病就、各按、排穗褂、喝了几杯、再说、面皆、天气和暖、了对半、明日还、随往、听着、狭窄犹、没好、儿给、有说有、傍晚得、而智者忧、不留心、听着怪、不依我呢、而自、玉来
也就是说，单词的正确率只有 41 %。这比字典的准确率还低，并没有因为采用了分词算法而提高了正确率。不过这也可以理解，因为生成字典的时候我只考虑了出现次数大于 5 的片段，而分词的时候有些单词只出现了一次，所以难度确实应该更大一些。
词频表中总计有 3.99 万个条目。根据估算的词频表中正确单词的比例，我估计《红楼梦》的词汇量大约是 1.6 万。有人用其他程序估计《红楼梦》的词汇量是 0.45 万（http://bbs.creaders.net/politics/bbsviewer.php?trd_id=344894），不过作者没有描述详细的统计方法，所以我对其结果非常怀疑，因为《红楼梦》中的单字就有 0.35 万种了。
7 筛选特征词
终于做完了分词，又离目标靠近了一大步。现在，我可以用之前看到的那篇文章里提到的 PCA 算法来分析章回之间的差异了。不过在此之前，我想先反思一下，到底应该用哪些词的词频来进行分析？
在很多用 PCA 分析《红楼梦》的博文里，大家都是用出现频率最高的词来分析的。然而问题是，万一频率最高的词是和情节变化相关的呢？为了剔除情节变化的影响，我决定选出词频随情节变化最小的单词来作为每一章的特征。而我衡量词频变化的方法就是统计单词在每一回的词频，然后计算标准方差。为了消除单词的常用程度对标准方差的影响，我把标准方差除以该单词在每一回的平均频数，得到修正后的方差，然后利用这个标准来筛选特征词。
按照这个标准，与情节最无关的 20 个词是：
下回分解(0.27)、也不(0.50)、不知(0.51)、一个(0.52)、起来(0.55)、如今(0.55)、自己(0.55)、听了(0.55)、那里(0.56)、什么(0.57)、出来(0.58)、说着(0.58)、话说(0.59)、这里(0.61)、来了(0.63)、只得(0.63)、我们(0.64)、只是(0.64)、怎么(0.65)、就是(0.66)
（括号内为修正后的方差）
有趣的是，处在排名末尾的词，也就是词频变化最大的词，大部分都是人名：
丫鬟、请安、平儿、家的、薛姨妈、家人、光景、二奶奶、贾琏、贾政、李纨、林姑娘、父亲、探春、邢夫人、奴才、哥儿、母亲、女儿、妈妈、麝月、惜春、晴雯、凤姐儿、贾珍、林黛玉、鸳鸯、湘云、尤氏、迎春、林之孝、紫鹃、薛蟠、宝琴、赵姨娘、香菱、周瑞、雨村、雪雁、妙玉、莺儿、刘姥姥、芳官、秦钟、金桂、宝蟾
可见这个筛选方法确实能去掉我们不想要的特征词。
最终，我选择了词频变化最小的 50 个词作为特征，每个词的修正后标准方差都小于 0.85。这 50 个词如下：
下回分解、也不、不知、一个、起来、如今、自己、听了、那里、什么、出来、说着、话说、这里、来了、只得、我们、只是、怎么、就是、去了、进来、知道、只见、这样、出去、一时、还有、不得、都是、你们、宝玉、见他、不能、听见、不是、两个、说道、一面、咱们、这个、不敢、的人、没有、还不、又不、笑道、所以、不过、叫他
8 主成份分析(PCA)
理论上，有了特征之后，我们就可以比较各个章节的相似性了。然而问题是，现在我们有 50 个特征，也就是说现在的数据空间是 50 维的，这对于想象四维空间都难的人类来说是很难可视化的。对于高维数据的可视化问题来说，PCA 是一个很好用的数学工具。
9.1 何谓是主成份分析
因为高维的数据空间很难想象，所以我们可以先想象一下低维的情况。比如说，假设下图中的每个点都是一个数据，横坐标和纵坐标分别代表两个特征的值：
现在，如果我们让 PCA 程序把这两个特征压缩成一个特征的话，算法就会寻找一条直线，使得数据点都投影到这条直线上后损失的信息最少（如果投影不好理解的话，可以想象用两块平行于直线的板子把数据点都挤压到一条线上）。在这个例子中，这条线损失信息最少的线就是图中较长的那个箭头。这样，如果我们知道了一个数据点在直线上投影的位置，我们就能大致知道数据点在压缩之前的二维空间的位置了（比如是在左上角还是右下角）。
以上是把二维数据空间压缩到一维的情况。三维压缩到二维的情况也是类似的：寻找一个二维平面，使得数据点投影到平面后损失的信息最少，然后把所有数据点投影到这个平面上去。三维压缩到一维就是把寻找平面改成寻找直线。更高维度的情况以此类推，虽然难以想象，但是在数学上是一样的。
至于算法如何找到损失信息最少的二维平面（或者直线、三维平面等等），这会涉及到一些数学知识，感兴趣的同学可以去查找一下相关的数学公式和证明。这里只要把这个算法当成一个黑箱就可以了。
9.2 重大发现？
现在我们可以利用 PCA，把五十个词的词频所构成的五十个维度压缩到二维平面上了。我把压缩后的数据点画出来，发现是这个样子的：
（图中每个圆圈代表一个回目。圆圈内是回目编号，从 1 开始计数。红色圆圈是 1-40 回，绿色圆圈是 41-80回，蓝色圆圈是 81-120 回。）
80 回以后的内容（蓝色）大部分都集中在左下角的一条狭长的区域内，很明显地和其他章回区分开来了！莫非《红楼梦》的最后 40 回真的不是同一个作者写的？！
别着急，分析还没结束。PCA 的一个很重要的优点就是，它的分析结果具有很强的可解释性，因为我们可以知道每一个原始特征在压缩后的特征（或者说成分）中的权重。从上图中可以看到，后 40 回的主要区别在于成分二(component 2)的数值。因此我们可以看一看每一个词的词频在成分 2 中的权重排名：
笑道(0.883)、我们(0.141)、一个(0.133)、你们(0.128)、两个(0.113)、说着(0.079)、咱们(0.076)、这个(0.063)、听了(0.052)、还有(0.046)、一面(0.045)、来了(0.037)、都是(0.032)、不过(0.028)、去了(0.027)、又不(0.025)、出去(0.021)、这样(0.018)、如今(0.016)、这里(0.016)、还不(0.011)、见他(0.011)、出来(0.010)、就是(0.010)、一时(0.008)、起来(0.005)、只见(0.002)、不是(0.002)、下回分解(0.000)、不得(-0.001)、也不(-0.001)、话说(-0.002)、的人(-0.005)、不知(-0.007)、那里(-0.009)、叫他(-0.011)、不敢(-0.011)、自己(-0.011)、不能(-0.017)、什么(-0.019)、所以(-0.020)、只是(-0.023)、知道(-0.026)、进来(-0.036)、说道(-0.046)、怎么(-0.050)、只得(-0.056)、没有(-0.077)、听见(-0.092)、宝玉(-0.312)
（括号内为权重）
我发现，“笑道”这个词不仅是除了人名以外出现次数最多的单词，而且在 PCA 结果中的权重也异常地高(0.88)，甚至超过了“宝玉”的权重的绝对值(0.31)！为了搞明白这个词为什么有这么大的权重，我把“笑道”的词频变化画了出来：
（图中横坐标是章回编号，纵坐标是“笑道”的词频）
可以发现，“笑道”的词频是先增加再减少的，这不禁让我联想到了贾府兴衰的过程。莫非“笑道”的词频和贾府的发展状况有关？有趣的是，“笑道”的词频顶峰出现在第 50 回左右，而有些人从剧情的角度分析认为贾府的鼎盛时期开始于第 48、49 回，恰好重合：
《红楼梦》之“钗黛合一”带来大观园鼎盛_风之子9881198198_新浪博客
[转载]白坤峰讲红楼梦（172）贾府鼎盛：该来的都来了_史鼎说红楼_新浪博客
也许“笑道”这一看似平常的词汇确实侧面反应了贾府的兴衰史呢。虽然因果关系有待考证，不过想想也有一点道理，毕竟只有日子过的好的时候人们才会爱笑。
9.3 再次分析
在之前的分析中我们发现，“笑道”这个词似乎和情节的关系比较大，并且严重影响到了我们的分析。此外，“宝玉”作为一个人名，它的权重的绝对值也比较大，也可能是受到了情节的影响。因此，我决定把这两个词“拉黑”，用剩下的 48 个词的词频做特征，再次进行 PCA 分析。这次结果如下：
这次我需要把特征压缩到三维空间而非二维空间了。这是因为之前我们得到的两个成分的方差贡献率（可以理解为成分提供的信息量）分别为 44.6% 和 19.0 %，总贡献率 63.6%，算是比较高了。而现在，即使是三个成分，方差贡献率也只有 23.9%，10.6% 和 6.9% 了，总贡献率才 41.4%。可见去掉“笑道”和“宝玉”以后，从词频中发掘信息的难度提高了很多。
从图中可以看到，现在后 40 回已经不像之前那么聚集了，不过还是可以看出一点聚集的趋势。特别地，前 80 回和后 40 回在成分二和成分三上的区别比较明显。和之前一样，我们可以把在这两个成分中权重的绝对值比较大的词都找出来，看看它们的词频变化。
在成分三中，权重最小的五个单词是：没有(-0.41)、听见(-0.25)、如今(-0.21)、所以(-0.18)、我们(-0.14)。（括号内为权重）
而权重最大的五个单词是：听了(0.22)、两个(0.26)、说着(0.30)、只见(0.37)、一面(0.39)
成分二中，权重最小的三个单词是：什么(-0.30)、怎么(-0.26)、听见(-0.22)
权重最大三个单词是：一个(0.28)、你们(0.37)、我们(0.43)
（“听见”在排名中出现了两次。不过不知道这个发现有什么用。）
可以发现，有些词的词频确实有一些异常的变化。然而，这些变化到底有没有受到剧情影响呢？感觉很难说。此外，在 PCA 结果中，似乎前 40 回和中间 40 回也分开了一些，只是没有后 40 回那么明显而已。那么这是不是说明 PCA 的结果也是受到了剧情的影响呢？
总之，我有点把握认为《红楼梦》前 80 回和后 40 回的用词是有一些差异的，不过因为难以排除剧情的影响，所以我对于作者是不是同一个人这个问题还不敢下定论。虽然没有完全解决这个问题，不过这个过程中误打误撞产生的发现也是挺有意思的，比如“笑道”的词频变化和贾府兴衰史的有趣重合。更重要的是，看似枯燥的数学公式可以做出这些好玩的分析，Math is fun！
=======================================================
如果觉得我的文章写的不错的话，打赏一块钱鼓励一下呗～
支付宝：
微信：
（手机上可以先保存到相册，然后扫码时选择从相册中识别二维码）
未经授权禁止转载！
（已授权名单：“Python 中文社区”微信公众号，”知乎日报”，“Helloworld少儿编程”）
