最近、シンプルなマルコフ連鎖を使って文章を生成する方法を学びました。生成された文章は一見読めるのですが、内容は完全なナンセンスです。文章として読む分には大した価値はありませんが、スマホのキーボードの予測変換のように次の単語を予測する用途では、驚くほど役に立ちます。

このアルゴリズムは、カーニハンとパイクの著書The Practice of Programmingの第3章で知りました。同書では、プログラム設計やデータ構造について論じるために、さまざまなプログラミング言語でこのようなジェネレータを実装しています。

なお、このアルゴリズムはマルコフ連鎖のごく小さな応用例にすぎず、マルコフ連鎖自体はもっと一般的な統計的概念です。

アルゴリズム

アルゴリズムの説明は簡単です。まず、出力の生成元となる入力テキストを用意します。入力テキストに含まれるすべての単語ペアについて、そのペアの後に続く可能性のある単語のリストを記録します。

このデータ構造ができれば、好きな長さの出力を生成できます。入力テキストに存在する任意の単語ペアから始め、その後に続く候補の中からランダムに1つを選びます。次に1つずらして、先ほど生成した単語をペアの2番目の単語とし、またランダムに次の単語を選ぶ、というのを繰り返します。

これだけです！

このアルゴリズムでは単語のペア、すなわちバイグラムを使います。単語1つやトライグラムを使うように一般化することもできます。ただし、The Practice of Programmingでは次のように指摘されています。

接頭辞（prefix）を短くすると一貫性のない文章になりがちで、長くすると入力テキストをそのまま再現する傾向があります。英語のテキストでは、3つ目の単語を選ぶのに2つの単語を使うのが良い妥協点で、入力の雰囲気を再現しつつ、独自の気まぐれな味わいを加えることができるようです。

例で見てみましょう。小さな入力ではうまく機能させるためにある程度の繰り返しが必要なので、入力として欽定訳聖書（King James Bible）の十戒のうち最後の5つを使います。

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」は候補リストに2回登場するため、他の単語の2倍の確率で選ばれます。

ここでは大文字・小文字や句読点をそのまま単語に含めていることが分かります。これにより単語の分割がシンプルになるだけでなく、生成される出力でも、入力に実際に現れた大文字や句読点を使った「文」が自動的に生成されることになります。なかなか巧妙な工夫です！

生成される出力はどのようなものになるでしょうか。上記の十戒を入力として試してみましょう。

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さえ含まれていることに注目してください（ただしリンクは2つほど削除しました）。

不思議の国のアリスを入力として使う

次は、ルイス・キャロルの不思議の国のアリスを入力として使った例です。元々がほぼナンセンスな本なので、これはほとんど違和感がありません。

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・ウェルズのThe War of the Worlds（宇宙戦争）を使った例です。

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…

「insane resolve（狂気の決意）」に駆られたところで、この実装に使った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。このプログラムは決して独創的なものではありません — どうぞご自由にお使いください。

おわりに

シンプルなデータ構造と乱数生成器だけで、こんなにも面白い出力が生まれるというのは、本当に魅力的だと思います。

また、記録する「単語」に大文字や句読点を含めるという工夫も、とても巧妙だと思います。もちろんこれは小手先のトリックではなく、プログラムをシンプルにしつつ出力の質も高める、エレガントな設計上の選択です。既存のプログラムの中に、シンプルにできるのを待っている同様の設計上の選択が、どれほど隠れていることでしょうか。

ぜひご自身の入力テキストでも、文章生成を楽しんでみてください！