我最近學會了如何用簡單的馬可夫鏈來產生文字。產生的文字可讀，卻完全是胡言亂語；作為文章來說沒什麼價值，但若用來預測下一個詞，就像手機鍵盤的聯想字功能一樣，卻出乎意料地實用。

我是在 Kernighan 和 Pike 合著的 The Practice of Programming 第 3 章學到這個演算法的，他們在書中用多種程式語言實作這類產生器，來探討程式設計與資料結構。

要留意的是，這個演算法只是馬可夫鏈眾多用途中的一小部分，馬可夫鏈本身是一個更為通用的統計概念。

演算法

這個演算法很容易說明：先準備一份輸入文字，用其中的片語來產生輸出。對於輸入中每一對相鄰的詞，記錄下在這對詞之後可能出現的詞彙清單。

建好這個資料結構後，你就可以隨心所欲產生任意長度的輸出。先從輸入中出現的任一詞對開始，然後從可能的第三個詞中隨機挑一個。接著往前推進，讓原本詞對中的第二個詞成為新的詞對的第一個詞，再隨機挑下一個詞，以此類推。

就這麼簡單！

這個演算法使用的是詞對，也稱為 bigram。你也可以將演算法推廣為使用單一詞彙或 trigram 而非詞對。不過，正如 The Practice of Programming 所指出的：

「將前綴縮短，往往會產生較不連貫的文章；將前綴加長，則往往會逐字重現輸入的文字。對於英文來說，用兩個詞來決定第三個詞是個不錯的折衷；它似乎能在重現輸入文字風格的同時，又增添一點異想天開的趣味。」

我們來實際走一遍範例。對於較小的輸入，你會需要一些重複，演算法才跑得起來，所以我們將以《欽定版聖經》中十誡的後五誡作為輸入：

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（雖然我移除了幾個連結）。

使用 愛麗絲夢遊仙境

這是一個以 Lewis Carroll 的 愛麗絲夢遊仙境 作為輸入的例子。這本書本來就有點胡言亂語，所以這個效果幾乎像是本來就該如此：

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。這個程式並沒有什麼原創性——在此授權你對它為所欲為。

結論

我覺得很迷人的是，僅靠一個簡單的資料結構加上亂數產生器，就能產生如此有趣的輸出。

我也覺得把大小寫和標點符號一併算進所記錄的「詞」裡這個技巧相當聰明。當然，這根本不是什麼技巧，而是一個優雅的設計選擇，讓程式更簡單同時也讓輸出更好。我不禁好奇，還有多少類似的設計選擇正隱藏在現有的程式中，等待被簡化？

祝你用自己的輸入來產生文字玩得愉快！