もようの機械

あの速さの、からくり

ここまでの5つのレッスンで、あなたは何百回も、もようを打ちかえてきました。そのたびに塗りなおしは一瞬で終わり、待たされたことは一度もなかったはずです。今日は、その速さのからくりを見にいきます。

もようは、打ちかえられるたびに、裏で状態機械という小さな機械に組み立てなおされています。検索とは、その機械に本文を1文字ずつ読ませる仕事です。あなたが書いてきたのは検索の指示書であると同時に、機械の設計図でもあったのです。

機械を、見る

下の実験室には、いつもの検索のほかに、もようから組み立てられた機械の図が出ています。レッスン1の最初のもよう「ねこ」で見てみましょう。

ねこ

図の見方は3つだけです。丸が状態——「どこまで読みすすんだか」という進み具合のしるし。矢印が遷移——「この文字が来たら、次の状態へ移れる」という決まりです。

左端の何もないところから刺さっている矢印が入口で、機械はかならずここから読みはじめます。そして二重丸が受理状態——ここにたどり着けたら「当てはまった」という、あがりの場所です。

すごろくの盤だと思ってください。状態がマスで、駒は入口に置かれ、あがりのマスを目指します。

ただし、このすごろくにサイコロはありません。駒を進めるのは運ではなく、読んだ文字です。「ね」を読んだら「ね」の矢印を進む——それだけの、誠実な盤です。

もようを育てると、機械が育つ

上の実験室で、もようを ねこ から ねこ? に打ちかえてみてください。状態が4つから6つに増え、矢印も増えたはずです。もように書き足したぶんだけ、機械も組み変わります。

増えた矢印のいくつかに、ε（イプシロン）という札がついています。これは「文字を読まずに移れる」近道のしるしです。こ? の「こは無くてもよい」は、機械の上では「こを読まずに先へ抜けるεの近道がある」という形で実現されています。

つづけて ねこ* にしてみてください。状態の数は6つのままですが、「もう一周」と戻っていく ε の矢印が1本増えます。くりかえしの正体は、この戻り道です。

なお、もようを長くしすぎると状態が26個を超えて、図のかわりに注意書きが出ます。そのときは、もようを短くすれば図が戻ってきます。

1文字ずつ、読ませてみる

機械のかたちは分かりました。次は、動いているところを見ます。下の実験室は「1文字すすむ」を押すたびに機械が1文字だけ読み、いま立っている状態が図の上で点灯します。

まだ1文字も読んでいないのに、明かりが3つ灯っています。入口と、そこから ε の近道で行けるふたつの枝の先頭です。機械は文字を読む前に、ただで行ける場所へは行けるだけ行っておきます。

ふたつの道に、同時に立つ

「1文字すすむ」を押して、「ね」を読ませてください。ここがこのレッスンの核心です。

もよう ねこ|ねず には「ねこへ向かう道」と「ねずへ向かう道」のふたつがありますが、「ね」はどちらの道にもある文字です。人間なら「どっちだろう」と迷うところで、この機械は迷いません——ふたつの道の両方に、同時に立ちます。 図を見ると、ねこの枝とねずの枝の両方に明かりが灯っているはずです（ε の近道の先も点くので、明かりは4つです）。

すごろくのたとえは、ここで壊れます。すごろくの駒は分身しませんが、この機械の駒は分かれ道のたびに増え、行き止まりの道のぶんだけ消えます。もう一度「1文字すすむ」で「こ」を読ませると、ねずの道は消え、ねこの道があがり——受理状態が点灯します。

だから、速い

この読み方には、見た目以上に大きな意味があります。ぜんぶの道を同時に歩くので、選んだ道をあとで悔やむことがない。引き返して別の道を試しなおす、ということが一切起きません。

だからこの機械は、本文を先頭から末尾まで一度なぞるだけで読み終わります。かかる時間は本文の長さに比例するだけで、どんなに意地悪なもようを書いても、それ以上にはなりません。冒頭の「あの速さ」の正体は、この一方通行の読み方です。

正直に言うと、世の中の正規表現エンジンには、道を1本ずつ試してだめなら引き返す「後戻り（バックトラック）」方式のものもあります。その方式は器用なぶん、もようと本文の組み合わせによっては急に遅くなることがあります。この庭の機械は後戻りをしないので、原理的に暴走しません。

このレッスンで分かったこと

• もようは打ちかえるたびに状態機械に組み立てなおされている。もようは機械の設計図
• 丸が状態、矢印が遷移、二重丸が受理状態。ε の矢印は文字を読まずに移れる近道
• この機械は分かれ道で迷わない——ぜんぶの道に同時に立ち、行き止まりの道だけが消える
• 後戻りをしないから、本文の長さに比例した時間でかならず読み終わる