最近我学会了如何用一个简单的马尔可夫链来生成文本。生成的文本读起来很通顺，却完全不知所云；作为文章没什么价值，但在预测下一个词方面——比如手机键盘的联想输入——它却出奇地有用。

我是从 Kernighan 和 Pike 合著的《程序设计实践》第 3 章中学到这个算法的，书中用多种编程语言实现了这样一个生成器，以此来探讨程序设计与数据结构。

当然，这个算法只是马尔可夫链众多用途中很小的一个，马尔可夫链本身是一个要通用得多的统计学概念。

算法

这个算法很容易解释：先准备一份输入文本，用其中的词组来生成输出。遍历输入文本中的每一对相邻单词，记录下所有可能跟在这对词后面的单词列表。

建好这个数据结构之后，你想生成多少输出都可以。先从输入文本中出现过的任意一对词开始，随机挑选一个可能跟在它后面的第三个词。然后向前滑动一步，用原来的第二个词和刚刚生成的新词组成新的一对，再随机挑选下一个词，如此循环往复。

就是这么简单！

这个算法使用的是单词对，也就是所谓的二元组。你也可以把它推广到用单个词或三元组来代替单词对。不过，正如《程序设计实践》所指出的：

前缀越短，生成的文本往往越不连贯；前缀越长，则越容易逐字复现输入文本。对于英文文本来说，用两个词来决定第三个词是一个不错的折中：既能重现输入文本的风格，又能增添几分奇妙的随意感。

我们来看一个具体例子。对于篇幅很小的输入，文本中需要有一定的重复才能奏效，所以我们就以《钦定版圣经》中十诫的最后五条作为输入：

Thou shalt not kill.

Thou shalt not commit adultery.

Thou shalt not steal.

Thou shalt not bear false witness against thy neighbour.

Thou shalt not covet thy neighbours house, thou shalt not covet thy neighbours wife, nor his manservant, nor his maidservant, nor his ox, nor his ass, nor any thing that is thy neighbours.

“可能的第三个词”这个数据结构看起来是这样的，下面展示了前几项，左边是单词对，右边是用 | 分隔的候选词：

shalt not         kill. | commit | steal. | bear | covet | covet
Thou shalt        not | not | not | not | not
nor his           manservant, | maidservant, | ox, | ass,
not covet         thy | thy
covet thy         neighbours | neighbours
thy neighbours    house, | wife,
not kill.         Thou
kill. Thou        shalt
not commit        adultery.
...

所以如果你从“shalt not”开始，下一个词就会从“kill.”、“commit”、“steal.”、“bear”或“covet”中随机选一个。因为“covet”在候选列表中出现了两次，它被选中的概率就是其他词的两倍。

可以看到，我们把大小写和标点都当成了单词的一部分。这样不仅让分词变得更简单，还意味着生成的输出会自动带上输入文本中出现过的大小写和标点，形成“句子”。这是个相当巧妙的技巧！

生成的输出是什么样的呢？我们就用上面的十诫文本来试一下：

Thou shalt not bear false witness against thy neighbour. Thou shalt not commit adultery. Thou shalt not steal. Thou shalt not covet thy neighbours house, thou shalt not commit adultery. Thou shalt not covet thy neighbours house, thou shalt not steal. Thou shalt not commit adultery. Thou shalt not steal. Thou shalt not covet thy neighbours…

可以看到，使用这么小的输入文本时，输出往往就是输入文本的逐字复制——或者与之非常接近的随机组合。

如果使用更大的输入文本，输出就会有趣得多。

更精彩的示例

下面是使用更大输入文本生成的一些更有趣的输出。每个输入我们都生成 100 个词。这些书籍的文本均来自Project Gutenberg。

以我写的文章作为输入

以我写的文章作为输入：

Especially if you need to return a value, but are now very flat – almost 5x as fast. Still, if you need a custom exception; use built-in exceptions if appropriate. Only break backwards compatibility if you’re on Linux, this uses the x86’s SSE/SIMD instructions to process CSV using AWK, such as NF are read-only in AWKGo. What does “Pythonic” mean? That’s a lot of fun. My recommendation: roll your own type-safe OrderedMap<int>. But because Lox strings don’t support escape sequences, there’s no null or undefined, and you have it! A minimalist Make in one of its revenue comes from the…

我很喜欢它捕捉到了我大部分的技术兴趣：性能、优雅的代码、向后兼容、AWK、CSV、小型语言等等。它当然比不上 ChatGPT，但眯起眼睛一看，生成的文本还挺像那么回事！

注意，输出中甚至包含了来自输入的有效 Markdown（不过我删掉了几个链接）。

以《爱丽丝梦游仙境》作为输入

下面是用刘易斯·卡罗尔的《爱丽丝梦游仙境》作为输入生成的一段。这本书本身就有点荒诞不经，所以效果倒还不错：

A large rose-tree stood near the entrance of the cakes, and was delighted to find that her flamingo was gone in a great hurry; “and their names were Elsie, Lacie, and Tillie; and they can’t prove I did: there’s no use denying it. I suppose Dinah’ll be sending me on messages next!” And she opened the door began sneezing all at once. The Dormouse had closed its eyes again, to see what was going off into a large fan in the pool, “and she sits purring so nicely by the hand, it hurried off, without waiting for the limited right of replacement…

以《旧约》（钦定版圣经）作为输入

注意，输出中包含了（毫无意义的）章节编号，这些编号本就是输入的一部分。

看看巴比伦王被怎样“烤”了一把！

Benjamin, Jaasiel the son of Berachiah, the son of Jehoiakim king of Gomorrah, and toward the holy gods is in your own will. 22:30 On the south in the porch of the sea, over against the mount out of the LORD shall smite the waves thereof. 107:26 They mount up to mount up to bury them, them, their children, shewing to the priest; 13:17 And the king of Babylon roasted in the name of the dust. 18:1 Then answered one of them, did Joshua take, and put his hand over the servants of Saul my father nor my life from perishing by…

以《新约》（钦定版圣经）作为输入

有点好笑的是，《新约》生成的文本竟然以“Moses”开头——这位可是《旧约》的关键人物（不过他的名字在《新约》中也出现了 80 次）。

我的电脑似乎还有点离经叛道：“we have preached the word of the body is the will of man”。

还有，“throughly”确实是一个（古语）单词。

Moses, ye would that we dwell in them. 2:11 Wherefore remember, that by my voice against them. 20:20 And they said, Is not this he that humbleth himself shall be given, and he will throughly purge his floor, and gather the wheat into the sea, and get victuals: for we have preached the word of the body is the will of man, it shall be: but we have sent for me? 10:30 And Jesus went into the kingdom of God. 5:6 Let no man may say, Thou fool, that he was nigh to Joppa, and the other side. 10:33 But whosoever shall…

以《世界大战》作为输入

再来一个作为收尾。这是使用 H. G. Wells 的《世界大战》生成的：

At Halliford I had the appearance of that blackness looks on a Derby Day. My brother turned down towards the iron gates of Hyde Park. I had seen two human skeletons—not bodies, but skeletons, picked clean—and in the pit—that the man drove by and stopped at the fugitives, without offering to help. The inn was closed, as if by a man on a bicycle, children going to seek food, and told him it would be a cope of lead to him, therefore. That, indeed, was the dawn of the houses facing the river to Shepperton, and the others. An insane resolve possessed…

怀着“疯狂的决心”，我们来看看我是如何用 Python 实现它的。

Python 实现

首先，这是完整的程序——算上空行和注释共 24 行，去掉之后是 16 行：

import collections, random, sys, textwrap

# Build possibles table indexed by pair of prefix words (w1, w2)
w1 = w2 = ''
possibles = collections.defaultdict(list)
for line in sys.stdin:
    for word in line.split():
        possibles[w1, w2].append(word)
        w1, w2 = w2, word

# Avoid empty possibles lists at end of input
possibles[w1, w2].append('')
possibles[w2, ''].append('')

# Generate randomized output (start with a random capitalized prefix)
w1, w2 = random.choice([k for k in possibles if k[0][:1].isupper()])
output = [w1, w2]
for _ in range(int(sys.argv[1])):
    word = random.choice(possibles[w1, w2])
    output.append(word)
    w1, w2 = w2, word

# Print output wrapped to 70 columns
print(textwrap.fill(' '.join(output)))

大家可以自行评判，但我觉得它的可读性还不错。

程序通过命令行参数（sys.argv[1]）接收要生成的单词数，并从标准输入读取输入文本。运行方式如下：

$ python3 markov.py 100 <AliceInWonderland.txt 
A large rose-tree stood near the entrance of the cakes, and was
...

代码也已作为 GitHub Gist 发布：markov.py。这个程序算不上什么原创——在此授权你可以随意使用它。

结语

我觉得，一个简单的数据结构加上一个随机数生成器就能产生如此有趣的输出，这实在令人着迷。

我也觉得，把大小写和标点直接包含在记录的“单词”中的做法非常巧妙。当然，这与其说是技巧，不如说是一个优雅的设计选择，它既让程序更简单，又让输出效果更好。不禁让人好奇，现有的程序中还藏着多少这样等待被简化的设计选择？

祝你用自己的输入文本玩得开心！