プログラミング作法　第３章　設計と実装　３．２　データ構造の選択

入力テキストが100,000語だとｎが非常に大きくなるので、プログラムを高速に動かしたければ、あまりに多順素朴なアルゴリズムを採用するわけにはいかない。

入力語の記憶方法と出力について

入力全体を１個の長大な文字列に読み込む方法もあるだろうが、入力を単語単位に分割しなければならないことは最初からわかっているので、単語を指すポインタの配列として入力を保持しておけば出力の生成作業が単純になる。個々の単語を出力するときには、入力テキストを走査して、出力したばかりのプレフィクスに続くサフィックスの候補を調べ、どれかをランダムに出力すればいいのだ。しかし、それだと1語出力するたびに、100,000語の入力をすべて走査しなければならないことになる。

　もうひとつ考えられる手法は、ユニークな入力単語だけを記憶し、その単語の入力中の出現位置を示すリストを管理することによって後続の単語をもっと高速に見つけられるようにすることだ。２章で紹介したような形のハッシュテーブルを使うのも可能だが、あのバージョンはマルコフアルゴリズムの必要条件（ある特定のプレフィクスのサフィックス全部を高速に見つけなければならない）に直接合致しているとは言えない。
　そこで、プレフィクスとそれに対応するサフィックスをもっとうまく表現するデータ構造が必要になる。このプログラムは２つのパスを実行する。入力パスではフレーズを表現するデータ構造を作成し、出力パスではそのデータ構造を利用してランダムな出力を生成する。どちらのパスでも、特定のプレフィクスを（高速に）ルックアップする必要がある。入力パスの場合にはそのプレフィクスに対応するサフィックスを更新しなければならないし、出力パスではサフィックスの候補からアットランダムに選択しなければならないからだ。このことから、プレフィクスをキーとして、そのプレフィクスに対応するサフィックス集合を値とするハッシュテーブルが必要になってくる。

プレフィクスとすべてのサフィックス候補の集合を状態と呼ぶ。これはマルコフアルゴリズムの標準的な用語だ。

　あるプレフィクスが与えられたら、それに続くすべてのサフィックスを記憶して、あとでアクセスできるようにする必要がある。サフィックスはソートされずに一度に１語ずつ追加される。サフィックスが何個存在するかは予測できないので、リストや動的な配列のように簡単に効率よく伸張できるデータ構造が必要だ。出力を生成するときには、特定のプレフィクスに対応するサフィックス集合からアットランダムに１個のサフィックスを選択できなければならない。項目は一切削除されない。

　ここまでの話をまとめておこう。それぞれの状態はプレフィクスとサフィックスのリストで構成される。この情報は、プレフィクスをキーとするハッシュテーブルに記憶される。個々のプレフィクスは固定サイズの単語集合であり、あるサフィックスが特定のプレフィックスについて複数回出現する場合には、それが出現するたびに別々にリストに入れられる。