计算机也能写宋词！

刘海明

【案例】
计算机也能写宋词！解名缰 发表于2011-12-12 21:13:35
: j! ^) F1 b# ]9 j4 w8 h, j& r

“人静风清，兰心蕙性盼如许。夜寒疏雨，临水闻娇语。佳人多情，千里独回首。别离后，泪痕衣袖，惜梦回依旧。”这首点绛唇是由一台普通的计算机写的。你是不是当时就震惊了？计算机都能写宋词，那我们能写吗？

1 D# _9 G; S5 B1 i' X, z! P, h6 o

点绛唇：人静风清，兰心蕙性盼如许。夜寒疏雨，临水闻娇语。佳人多情，千里独回首。别离后，泪痕衣袖，惜梦回依旧。

——一台计算机

计算机也能写宋词？这是怎么做到的？其实如果仔细观察，你会发现这篇大作中每个意象也经常出现在“正品宋词”中。没错，实际上它正是通过分析《全宋词》，把句子打碎成词语，并归纳出宋词中的高频词汇，再按宋词格式“创作”而成。
! D2 h# d; l9 [( V2 k  V! A4 Q显然，其中极为重要的是第一步，这种逆向操作叫做分词，分词的方法有很多，并且被广泛研究，然而它却不仅仅限于用在自动作词上。分词有哪些方法，又有什么用呢？
0 n# A5 R0 `# Y0 T: r分词：究竟有多简单？或者多难？在英语中，分词是一项相对比较简单的工作，因为词与词之间有天然的分隔符，只需要照顾到单复数（比如 apple / apples, bus / buses, woman / women ）、时态（比如 write / wrote / writing ）等词类变形，就能将有相同指代的词语汇总成同一个单元。此外要注意同形异义词，如 lay （躺下/位于/下蛋），但总的来说词与词之间还是有很明显的界限的。
而中文则有显著不同，由于汉语比较奇妙，同一个句子有可能会有不同的词语划分方式，比如 “乒乓球/拍卖/完/了” 和 “乒乓/球拍/卖/完/了”，所以中文的分词是一项艰巨而复杂的工程。
虽然如此，也存在一种简单暴力的划分办法，那就是穷举句子的所有连续二字组合，然后整体统计频率。这种办法对于宋词来说比较取巧，这是因为宋词本身句子较短，而且词语的长度有限；对于更一般化的文本，这种暴力拆解就并不适用了，一方面是计算量太大，另一方面是精度太低。
$ O/ c& T' O0 ^0 q( q% k9 O2 P: N那么，对于一般的情况而言，词语的切分都有哪些办法？在此向大家简单介绍两种较容易理解和常用的方法。
+ P5 {2 f9 Y- Y5 K
最大匹配法 在诸多复杂的分词方法中，最大匹配法（Maximum Matching，简称MM）是最简单直接的一种。它需要事先给定一个词库作为词典，然后从左到右匹配尽可能长的词语。举个例子，假设我们的词典里只有“计算机、超越、人脑”这三个词，对于“计算机会超越人脑吗”这句话，最大匹配法的计算过程是这样的：
1、 创建指针 A 并将它置于句子的最开始位置：A计算机会超越人脑吗；
5 t+ K' R, C5 w1 ^2、 由于词典中最长的词语长度为3，所以创建新指针 B，置于 A 后的三个单位：A计算机B会超越人脑吗；
" C- Z& A" b: |3 Z7 B3、 检验 A 和 B 之间的字符串是否在词典中，如果在，就将 A 移动到 B 的位置， B 相应地往后移（直至移到句子末尾）：计算机/A会超越B人脑吗；
% ~6 d3 R; b$ ^( `9 R+ Z2 s& i4、 而如果A 和 B 之间的字符串不在词典中，就将 B 不断左移，直到能够有词语匹配或与 A的距离为 1 （也就是 A、B 之间没有匹配的词语，用单字切分），我们的例子在第一次切分后就属于这种情况，所以再次操作的结果就是：计算机/A会B超越人脑吗；
1 @' k  y2 }  o7 R9 e5、 重复步骤 3 或 4，直到 A 移动到句子末尾：计算机/会/超越/人脑/吗。
这种算法非常高效和简便，同时可以避免“计算/机会/超越/人脑/吗”这种切分方式（即便计算机和机会两个词同时在词典中）。但它的缺点也是很明显的，比如之前的“乒乓球拍卖完了”，就很可能被切分成“乒乓球/拍卖/完了”。为了消除这种歧义，人们也不断提出了一些改进算法，比如逆向匹配法，双向匹配法等等。

最大概率法但是我们可以换一个角度来看待这种歧义问题。对于两种切分方式，“乒乓/球拍/卖/完/了”和“乒乓球/拍卖/完/了”，我们会认为前者更合理，因为通常乒乓球和拍卖不太可能联系在一起。也就是说，后者在语料库中出现的概率会比较小。所以，如果同一个句子出现若干种不同的划分，我们就希望找到可能出现概率最大的那个。
# j( w% I. J4 e5 P4 z为了表述简便，这里用 {A1， A2， A3， A4， A5} 和 {B1， B2， B3， B4} 来分别表示 {乒乓，球拍，卖，完，了} 和 {乒乓球，拍卖，完，了} ，我们的任务是比较 P(A1, A2, A3, A4, A5) 和 P(B1, B2, B3, B4) 的大小。
! ?6 _" G* X3 g1 u/ {; y) Y! [. Q根据条件概率公式，有
P(A1， A2， A3， A4， A5) = P(A1) P(A2|A1) P(A3|A1, A2) P(A4|A1, A2, A3) P(A5 | A1, A2, A3, A4)
其中 P(A1) 表示 A1 在语料库中出现的概率，P(A2|A1) 表示当上一个词语是A1时，在它后面 A2 出现的概率，类似的， P(A3|A1, A2) 表示当前面两个词语是 A1 和 A2 时下一个词语是 A3 的概率，等等……
% Z3 m, B2 ~+ m: c9 _% Z- A( D但是我们发现，当句子很长时，这个概率表达式的尾巴会越来越长，给计算带来很大的麻烦，所以一般采用 马尔可夫链 （Markov Chain）的假设。
# N2 S' ^: d. Q在马尔可夫链假定下，我们认为下一个词出现的概率只与前一个词有关，也就是说，在给定前文时，“卖”出现的概率只与紧接着的“球拍”有关，而与“乒乓”无关。有了这个假定，之前的概率就简化为
2 X8 x# n  ^  I" CP(A1, A2, A3, A4, A5) = P(A1) P(A2|A1) P(A3|A2) P(A4|A3) P(A5|A4)
6 l/ w' s3 i5 |8 Y9 v$ S这就大大减小了计算量。在利用这个模型时，需要先对一个很大的语料库进行分析，这被称为“训练”的过程，其意义就在于把任意两个词语之间关联的概率都计算出来。当然在实际操作中，还牵涉到很多其他非常复杂细节，在此就不一一细说了。
0 M- `; Z8 Y# q% i" U- r1 h! [2 q
- A( E6 ~) K3 T) c自动作词：离我们有多遥远？ 分词完成后，词频的统计就是小事一桩了。之前有人把宋词的高频词语统计表 发到网上 ，一时间几乎每个理科生都能写宋词了。就技术层面而言，大部分自动作诗词的尝试都是在“高频——关联”这样的框架下完成的。即给定一个词语，搜索与之关联度较大的另外一批词作为候选集合，再通过预先设定好的准则进行筛选。
7 [) T7 w4 }9 _- F& v  i) T但这样的方法显然比较简陋。相比之下，有人研究了更高级的方法，例如有一篇名为 一种宋词自动生成的遗传算法及其机器实现 的论文就采用填词的思想：给定一个词牌，就相应地给出了格律、押韵和平仄等硬性要求，将满足要求的词语填入相应的句法中，再通过一系列评价指标计算每个填词组合的“得分”，最后利用 遗传算法 计算出“得分”最高的填词方案。
1 ?" {$ b, _( S& Z6 r' j4 j以“清平乐”这个词牌为例，其填词约束为
*0 / *1, *1 / 0 / 01.    *1 / *0 / 0 / 11, *1 / *0 / *1.*0 / *1 / 00, *0 / *1 / 00.   *1 / *0 / *1, *0 / *1 / 00.其中 0 表示平声， 1 表示仄声， * 表示两者皆可， / 是词语的分割。可以看到，对于“清平乐”这个词牌，实际上就是要将 24 个词填入相应的空档中，其中第一个词以平声结尾，第二个词以仄声结尾，第四个词是一个平声单字……此外如果再考虑押韵，那么搜索的词语空间又会进一步减小。
( x2 B* n0 Q' ]) p在给定了一种填词方案后，就可以构造这种方案的评分体系。上述的论文从四个方面（句法合法性、主题相关性、词句搭配的适当性、风格和情感统一性）考虑，最后得到一个综合加权的指标。因此，自动作词的过程就抽象为了一个高维的最优化问题，即试图找到一种填词的组合，使得最终这个加权指标达到最大。
这篇论文的一个亮点在于使用了遗传算法作为主要的优化方法。遗传算法的细节比较复杂，在自动作词这一特定问题中，其主要思想是：
1、 随机生成若干个满足约束条件（格律、押韵等）的填词方案；
2、 选取其中较优的一些结果作为父代，然后利用遗传算法中的交叉和变异操作，从父代来生成子代。换言之，就是在已有的填词方案基础上生成新的填词方案；
3、 不断进行评判和迭代，直到跳出循环。
8 ]9 _% V4 f/ x* t/ S6 a) ^- w遗传算法的好处在于其算法的不确定性和可变异性，这是受生物的进化得到启发而发展起来的。虽然遗传算法作出的算词像模像样（例如本文开头的例子），但需要说明的是，遗传算法本质上是一个最优化算法，因此填词的好坏仍然与词库和评价指标直接相关。从某种意义上说，计算机作词实际上是利用已有的词库进行组合，而不是创造。
* A4 o2 I& e# q/ O无论如何，一个丰富而优秀的词库仍然是有意义的——对于电脑来说，这是它进行“创作”的基石；对于人来说，它至少能告诉读者以往词人常用的意象是什么，从而提供一些创作上的灵感（当然不应该是词作本身）。
8 N' r' r. \: @
5 B* F3 g! j, w- U  y1 F7 U词频统计：另有他用分词和词频统计的作用当然不只“自动作词”这么局限。举个简单的例子，大家几乎每天都要用到的搜索引擎就是分词的直接应用者。当你输入一串连续的词语时，搜索引擎就是先将它打碎然后再进行匹配的。
事实上，分词只是万里长征的第一步。在 数据挖掘 领域，我们经常用“文本挖掘”这个术语来指代文本数据提取、分析以及得出有用结论的过程，其操作的基本单元往往是一篇完整的文档，比如一个页面、一份报告等。在取得了文本的分词之后，我们就可以构造“文档——词频”矩阵，找出每篇文档对应的各个词语的词频，然后利用这个矩阵进行文档的分类、聚类等操作。例如，虽然Google本身不提供新闻，但是它可以从网络上自动抓取，然后根据文档的特征划分到适当的类别中。
9 R: E. h; G  m  G文档分类的另外一个应用是文本作者的鉴定。例如日本同志社大学的金明哲教授曾利用文档分类方法来辨别若干有争论的小说的作者，甚至还在日本一起刑事案件中对“匿名信是否是犯罪嫌疑人所写”为警方提供了参考证明。

本文作者半年前在 自己的博客 中就统计了宋词中常用的意象。类似有趣的统计学研究，作者和他的朋友们一直在 “统计之都” 这个网站上不断进行着，有兴趣尤其是相关专业的朋友，快来 这里 看看吧。

# m: `' ]# M& ]  ^2 l" c9 i& y% g

---

参考资料：
& Z( F$ I; d1 a, Z6 N: t' F[1] 一种宋词自动生成的遗传算法及其机器实现
[2] lewutian： 中文分词算法总结
+ E, ~6 j( h9 K6 V0 U, B[3] ICTCLAS汉语分词系统
; o) Q. X9 k& ^3 z1 c[4] 李舰，第三届R语言会议： R与文本挖掘——文本挖掘简介与系统实现
3 j9 p1 t, s5 @* ]7 U' s7 ~[5] 《文本数据统计科学的现状与展望》，金明哲，学术讲座

http://www.guokr.com/article/78894/
0 s& Y! A" @! J6 x5 N& ^6 c. r
8 l% J( t4 u% }8 _1 k
% H; }: I3 |% g3 N, E  R6 r