正規表現のベンチマークの一つにRust Leipzigのベンチマークというものがあります。正確には「Leipzigに拠点を置くRust（プログラミング言語）ユーザーの集まりが公開している正規表現のベンチマーク比較ページ」とでも言い表すべきものなのでしょうが、長いので以下単に「Rust Leipzigベンチマーク」または略してRLBと呼ぶことにします。
Rustユーザのページですので、本来は「Rustの正規表現ライブラリはC/C++など他言語のライブラリに比べてどんなものか。どのぐらい速いかあるいは遅いか」を明らかにすることを目的としたページなのであろうと想像しますが、結果として現行の正規表現ライブラリの速度を見比べるのに便利なページになっています。
上記ページの一番下に、各ライブラリの成績が一覧表画像として埋め込まれています。2023年8月現在、2022年10月に行われた結果がトップページに掲載されていますが、この画像を見ますとHyperscanとRustのregex crateとが2強で、その少し後ろにRE2やPCREのJIT版などが続いているというのが2022～3年にかけての状況のようです。
PCREはJITを使う使わないでかなり速度に違いが出るようで、JITを使えば最速クラスとなる一方、JITを使わないPCREはC++のstd::regexと並んで下位スコア常連となっています。std::regexよりは速いとされるBoost.Regexでさえも、Rustのregex crateの作者に言わせると「horribly slow（恐ろしく遅い）」そうです。
Boostがワーストスコアを出してしまったのは1項目だけですのでちょっと手厳しいようにも感じられますが、上位陣の主戦場がもはや1～2桁ミリ秒となっている中、テスト項目の半分で3桁ミリ秒の数値を出しているうえに最後のテストは完走できずn/aになってしまっているあたりがこのような評価につながっているのかもしれません。
ところでこの表を見て「なら、これを使ってみよう」と思っても、実際にはそれが叶わないケースもあります。理由としては次のようなものが挙げられます。
昨今のライブラリはほぼ例外なくUnicodeベースですので、例えばShift_JISに対応したライブラリを使いたいというような場合には選択の余地はなく、事実上鬼車の一択となります。
またUnicodeベースでもHyperscan, RE2などはUTF-8のみの対応ですので、UTF-16やUTF-32での検索を行いたい場合には選択肢から外さざるを得ません。
必要とする機能がライブラリに実装されていないため選択肢から外さざるを得ないケースというのもあります。
実は先ほど名前を挙げたHyperscan, RE2, Rustのregex crateなどは「検索が遅くなる原因となる機能、および検索を速くするための最適化の邪魔になる機能」を除外しています。具体的にはlookaround（lookahead［先読み］とlookbehind［戻り読み］とを合わせた言い方）、backreference/後方参照などです。
Hyperscanにいたってはさらに、正規表現中の括弧がキャプチャしたものを取り出す機能さえ除外しています。例えば日時にマッチする表現 /(\d{4})[\/-](\d{1,2})[\/-](\d{1,2})/ にマッチする箇所を見つけても、年月日に相当する部分を取り出すことがHyperscan単体では出来ません。
ではどうすれば良いのかと言いますと、「マッチした部分を別の正規表現ライブラリに渡して、そちらに括弧の部分を取り出してもらってください」というのがHyperscanの考え方です。実際これを実現するために、HyperscanとPCREとを組み合わせたChimeraというライブラリが用意されています。
ずいぶんと割り切った考え方ではありますが、先のベンチマーク比較表でも他のライブラリと比べてHyperscanは文字通り桁が違うスコアを出していますので、マッチを見つけた後、別のライブラリに括弧内を取り出してもらうという二度手間を取ったとしても充分使いものになるという判断なのかもしれません。
Lookaroundに関しても「速いライブラリ」でマッチする箇所を見つけた後、別のライブラリでlookaroundの条件を満たしているか確認するという方法を採れなくもありませんが、「速いライブラリ」にlookaroundを含む正規表現をそのまま渡すとエラーが発生してしまいますので、lookaroundの部分だけ取り除いた正規表現を別に用意するような一手間が必要になってきてしまいます。
Hyperscanは開発元がIntelということもあり、SIMDを活用しています。そのためIntelのCPU以外では動きません（ARMのNEONに対応させようとする強者がいたようですが、さすがにIntelが断ったようです）。
またPCREのJIT版も実行時に直接マシン語/機械語を生成するという性質から利用できるCPUが限られます。
※2024/08/16追補：Hyperscanはversion 5.5以降、proprietary化（closed-source化）してしまったそうです（ソース1、その2）。
同ソースによると、open source最終版である5.4.2からのforkとしてVectorscanというものがあり、ARMのNEON対応など独自に改良が続けられているようです。
正規表現ライブラリを作っている立場から見て「うまいな」と思うのはRE2です。Rustが使える環境ならregex crateも良さそうです。このregex crateについては作者（焼き寿司さん？）が色んなところで語っていますが、RE2に触発されて作ったそうですので、これもRE2の系譜上にあるライブラリと言えます。
先のベンチマーク比較表においてRE2に特徴的なのは、大半のテストを21ミリ秒前後で終えているという点です。その結果、最速の座を逃しているテストもありますが、ワーストになったテストは一つもありません。N/A（その表現に対応していない）になった項目がない「完走組」の中で、全テストを100ミリ秒未満で終えているのはRE2とHyperscanだけです。
「どんな正規表現であれ、検索対象テキストの長さが同じならだいたい同じ時間で検索できる」というのがRE2の最大の魅力です。Lookaroundなどを必要としないのであれば、現時点では最善の選択なのではないかと思われます。
Lookaroundなど新しめの機能が必要であれば、これというお勧めはありません。現状では「お好みで」ということになろうかと思います。
ではなぜRE2系の実装はだいたい同じ時間で検索が出来るのでしょうか。逆に、なぜそれが出来ないライブラリもあるのでしょうか。またlookaroundや後方参照に対応しないとどうして高速化できるのでしょうか。
RE2の秘密に迫る前にまずは、そもそも正規表現ライブラリというものはどのように実装されているかについて簡単にご説明します。
正規表現の仕組みについて検索しますと、難しい用語やら数式やらが色々出てきたりもしますが、現代のライブラリの実装を分類する上でもっとも重要なのは「Backtracking系かそれ以外か」という点です。
Backtrackというのは「来た道を引き返す」という意味で、正規表現においては「既に調べた箇所へ戻ってもう一度調べることもある方式」のことを指します。この用語は頻出するので以下では「BT」と略します。
BTによる実装はだいたい次のような感じです。例として文字列 "ac" に対して、正規表現 /ab|ac/ で検索する場合を示します。
正規表現文字列をパーズして内部表現（ここではstateと呼びます）に変換してゆく。
/ab|ac/の内部表現の一例：
以下、0番stateのことはS0、1番stateはS1のように表記します。
以下、検索対象文字列 (target string, haystack) については、先頭文字をT0、その次のものをT1のように表記します。
BT方式では「現在のstate番号を保持する変数」「現在のtarget文字列中の位置を保持する変数」「state番号とtarget位置番号とのペアをpush/popするスタック」を使いますので、検索に先立ってこれらを用意しておきます。
"ac"のうちの [T0, T2) をマッチ範囲として呼出元に報告する。
この例では、T0の位置にある文字との照合→T1との照合失敗→T0に巻き戻す→T1というふうに照合位置が行きつ戻りつしています。このように「既に一度調べた位置へ戻って別の可能性を調べる」ということが起こり得るのが、BT式の正規表現検索が遅くなる原因です。この例ではたった1文字戻るだけですが、正規表現パターンによっては数十文字、数百文字単位で戻ることも起こり得ます。
BTの持つこの性質が最悪の形で現れるのが /(a+)+b/ のような例です。この正規表現で文字列 "aa" に対して検索をかけた場合の挙動を次に示します。
a+ が "aa" のすべてにマッチ。この際BTスタックに「先頭1文字だけにマッチした状態 (ST0a)」がpushされる。+のところでBTスタックに「次のstateである b へ進む選択肢 (ST1a)」をpushした上で2周目に進む。(a+) との照合が試みられるが、もう残っている文字がないので照合失敗。BTスタックからST1aがpopされる。+のところで2周目に行かず b との照合を試みるルートが選択されるが、残っている文字がないので照合に失敗。BTスタックからST0aがpopされる。スタックは空に。(a+) が "aa" の最後1文字を諦めて最初の "a" にだけマッチしている状態で再開。1周目=[T0, T1). 残り=[T1, T2).+で「b へ進む選択肢 (ST0b)」をpushした上で2周目に入る。"a" に対して (a+) がマッチする。1周目=[T0, T1), 2周目=[T1, T2).+で「b へ進む選択肢 (ST1b)」をpushした上で3周目に入る。(a+) との照合失敗。ST1bがpopされる。+で3周目に行かず b との照合が試みられるも、残っている文字がないので失敗。ST0bがpopされる。スタックは空に。+で2周目に行かず b との照合が試みられるも、残っている文字がないので失敗。スタックが空なので選択肢が尽きたと判断し、呼出元に対してマッチング失敗をreturnする。
たった2文字に対する検索でさえこれだけの手順を踏んで、ようやく「マッチしない」という結論に至ります。余談ですが上の文章は当初、 "aaa" の3文字に対する照合手順を示すつもりで書き始めました。ところが手順20を超えてもまだ終わりが見えなかったので、2文字に短縮して書き直したという経緯があります。
文字列が長くなるとその分だけ「前回以前のループから1文字譲ってもらえる回数」が増えるため、1周目が1文字譲る → 2周目がそれを全部消化する → 3周目でマッチするものがない → 2周目が一文字譲る → 3周目がそれを全部消化する → 4周目でマッチするものがない → …… → 3周目が譲れなくなる → …… → 2周目も譲るものが尽きる → ……というループがどんどん長く深くなってゆき、それにつれて同じところをなぞる回数も増えていってしまうのです。これが悪名高い「Backtrackingによる照合回数の指数的爆発 (exponential explosion)」です。
この問題を回避する方法もいくつか考案されてはいるものの、どの方法も制約があり、万能の解決策というのは私が知る限り今のところ見つかっていません。
Perl 5.10で導入されたpossessiveなquantifer、/a++/ のような表現も指数的爆発への対策の一つで、「1文字ずつ譲るのをやめてしまえばそもそも指数的爆発は起こりようがない」という発想に基づくものです。ですのでこの表現は、BTを使わない方法で実装されている正規表現エンジンではサポートしてもパフォーマンス上の恩恵はありません（BTの使用を前提とした機能ですので、非BT系の実装ではそもそもエミュレートするのが難しいはずです）。
このような問題を抱えているにもかかわらず、なぜBTを使った正規表現エンジンがなくならないのかと言いますと、それはひとえにPerl 5互換のためです。Perl 5の正規表現エンジンはBTベースで実装され、BTが使われていることを前提に次々と新しい機能を導入してゆきました。
Lookaroundもその一つで、「検索対象文字列中の同じ箇所を何度もなぞることが出来る」というBTの特性を利用した機能と言えます。Perl 5以降登場した機能の多くは、BT以外の方法で実装するのが困難なのです。
Perl 5互換の正規表現が使えるようにするためにはBTを使って実装せざるを得ず、その結果照合回数の指数的爆発という爆弾を抱え込んでしまう、でもPerl 5互換にするためにはそれも仕方ない、このような考え方が幅を利かせる中、「いや、照合回数の指数的爆発は看過して良い問題ではない。BTの使用をやめることで回避できるならそうすべし。結果としてPerl 5の正規表現に完全に倣うことが出来なくなるとしても」という考えから生み出されたのが、HyperscanやRE2の系譜と言えます。
RE2ではいくつかの方式が併用されているのですが、その根幹となるのはThompsonのNFAと呼ばれる方法です。最新どころか1960年代に編み出された手法です。RE2の作者さんが詳しい仕組みを公開されています。
先ほどの「文字列 "ac" に対して、正規表現 /ab|ac/ で検索する例」はこのように照合されます。
先ほどのstatesがそのまま流用できます。以下再掲。
BT式ではスタック（最初にpushしたものが最後に出てくる）を使いましたが、Thompson NFAでは2つのキュー（最初にpushしたものが最初に出てくる）を使います。それぞれQ0, Q1と呼ぶことにします。
対象文字列は今回も "ac" で、先頭から順にT0の位置、T1の位置と呼ぶのも同じです。
この例ではキューからAcceptedが出てきたらすぐにマッチング成功と判断していますが、最長一致優先ならアクティヴなキューにstateが残っている限りは続ける必要があります。また左方優先であれば、Acceptedを示すstateがアクティヴなキューの先頭に来るまで続けてゆくようにします（優先度の高い選択肢ほどキューの前のほうに来るのでそれらの結果を確定させる必要がある）。
この2つのスレッドキューを使う方法であれば、BT方式なら指数的爆発を起こしてしまう先ほどのような表現も難なく処理できます。
/(a+)+b/は次のようなstatesで表せます。なお説明を単純にするためキャプチャについては無視します（/(?:a+)+b/相当）。
対象文字列は先ほど同様に "aa" を使います。
同じキューの中に同じstateが重複して存在することがないようにしているのがポイントで、既に調べたことのある「stateと文字との組み合わせ」を何度も調べることになるのを防いでいます。また同じキューの中に同じstateが複数存在しえないということは、キューの要素数はstateの総数を超えないということでもありますので、必要となるメモリの量が検索開始前の時点で予め分かるというメリットもあります。
なお上では省略しましたが、括弧によるキャプチャも「現在位置を保存するstate」を設けることで対応できます。
この方式のようにBTを使わない実装の場合、{n,m}のような回数指定は*, +, ?を使った表記法に置き換えて処理するのが一般的です。例えば a{2,4} は aa(?:a(?:a)?)? 相当に変換されます。そのためa{100000000}のような簡単な表記で、膨大な数のstatesが容易に作れてしまいますので、大抵は繰り返し回数に上限が設けられています（RE2は1000まで、Hyperscanは単体の文字や文字クラスについては32767まで、括弧については小さな数（詳細不明）か無限であること）。
検索対象テキスト中の文字についてはどれとも一期一会の関係で、一度通り過ぎてしまった文字のところまで戻ってもう一度照合を試みることはしません。そのためlookbehindのように逆方向に文字列を照合したり、lookaheadのように一定の位置までのマッチが成功したらまた元の位置に戻って続けたりするような、読み込み位置を行ったり来たりさせる必要がある機能は効率よく実装できません（Lookaroundの部分だけ再帰呼出を使ったりBT方式を使ったりすれば対応させること自体は出来なくもないのですが、これをすると「検索対象テキストの長さに比例した照合時間」が保証できなくなり、BTを排除した意味がなくなるのでしないのが普通です）。
このThompson NFA方式は指数的爆発を起こさないので著しく遅くなることこそありませんが、BT方式に比べると「概して遅い」結果になりがちです。理由は明確で、常にすべての可能性を同時に調べるためです。
BTなら「1つのstate対1つの文字」の比較で済みますので、他のどの方式よりも早くマッチを見つけられるケースさえあります。しかし見つからない場合は、行きつ戻りつするので「マッチしない」という結果が確定するまで時間が掛かる傾向にあります。このように検索時間にムラがあるのもBT方式の特徴です（余談ですが、RLBの一番下のテストはマッチする箇所が見つからない例です。BT系のエンジンはどれもボロボロなスコアを出しています）。
それに対してこの2つのキュー方式は、「1つの文字対複数のstates」という比較を行うことで、すべての可能性を同時並行的に調べてゆきますので、マッチが見つかる場合も見つからない場合も同じぐらいの時間が掛かる傾向にあります。
しかしThompsonのNFA方式がBT方式に対して速度的に不利なのだとしたら、RE2はどうしてあれだけのスピードが出せるのでしょうか。
先に「すべての可能性を同時に調べるせいで遅くなる」と書きましたが、実はRE2ではこの辺りの処理を高速化するためにDFAを採用しているのです。
DFAというのは、ものすごく大雑把な言い方をしますと「読み込んだ文字によって次に進むべきstateが自動的に決まる」という仕組みです。struct state { state *next[256]; };がチェーン状につながっているものを想像していただければだいたい合っています。
ちなみにこれまで見てきたBT法や2つのキュー方式などは、DFA (Deterministic Finite Automaton) に対してNFA (Non-deterministic Finite Automaton) といいます。
純粋なDFAの例を示します。/abc|bcd/を検索するには、次のような配列を用意します。表中のs0, s1などはすべて前記state型です。
| state→ ↓添え字 | s0.next[256] | s1.next[256] | s2.next[256] | s3.next[256] | s4.next[256] |
|---|---|---|---|---|---|
| 'a' 0x61 | s1への ポインタ | NULL | NULL | NULL | NULL |
| 'b' 0x62 | s3への ポインタ | s2への ポインタ | NULL | NULL | NULL |
| 'c' 0x63 | NULL | NULL | 受理を表す値 | s4への ポインタ | NULL |
| 'd' 0x64 | NULL | NULL | NULL | NULL | 受理を表す値 |
s0.next['a']には&s1が、s0['b']には&s3がセットされているという状態です。表に出てくる4文字以外の文字、0x00-0x60及び0x65-0xffの範囲の文字を添え字とする要素にはすべてNULLが入っています。例えばs0.next['0']やs4.next['_']などの値はどれもNULLです。
state *nextstate = &s0; という状態で検索を始め、nextstate = nextstate->next[T0の文字]とした結果、nextstateがNULLになったらマッチング失敗、受理を表す値（例えば1）が出てきたらマッチング成功、それ以外ならtarget側の現在位置を+1してまた nextstate = nextstate->next[Tnの文字] に戻るというのを繰り返してゆくだけの簡単な検索方法です。配列からポインタを読み出して次の配列へと渡り歩いてゆくだけですので動作も高速です。
RE2はこのような配列を持ったDFA用statesをキャッシュとして利用しています。そのため「この文字が来たら次に行けるstateは何番と何番」と即座に判断できるので、高速な検索が行えるのです。
純粋なDFAエンジンではこのような遷移先テーブルをコンパイル時に作ってしまうのですが、RE2は検索時に動的に作ります。例えば検索対象文字列から 'a' が出てきたら現在のstateのnext_['a']に有効な値が入っているか調べ、入っていたら（過去にも 'a' に遭遇したことがある場合）その値が示すstateへ移行、入っていなければ（過去に 'a' に遭遇したことがない場合）前記の手順を踏んで次に行くべきstateを調べ、その値をnext_['a']に書き込んでから当該stateへジャンプします。こうすることで2回目以降は「文字を比較してnextを読み出す」という手順を飛ばして、すぐに次のstateへ飛ぶことが出来るようになっています。
（※実際には、stateごとに256個のポインタテーブルを持たせるとメモリの使用量が増えるため［64bit環境なら256*8=2048でstateごとに2KB必要］、RE2の実装ではbytemapという仕組みを使って0x00-0xFFをグループ分けして、そのグループ番号をnext_[]の添え字にするようになっています）
DFAを使う場合、RE2は括弧によるキャプチャ位置どころか検索開始位置すら保存しません。括弧については、マッチ範囲が確定したらその範囲に対してNFAによる照合を行って取り出します。この辺りの考え方はHyperscanと同じで、「とにかくマッチを見つけることが最優先。細かいことはその後で」というわけです。
しかし開始位置を保存しないのであれば、マッチする箇所が見つかっても範囲を確定させることが出来ないはずですが、その辺りはどうしているのでしょうか。
答えは「前後反転させた正規表現を作り、それを使ってマッチが成立した位置から逆方向に照合してゆく」です。冗談のように聞こえるかもしれませんが本当の話で、re2.cc内のRE2::Match()函数内を順に見てゆきますと、SearchDFA()が成功したらReverseProg()を呼んで内部表現を逆向きにしたものを生成し、それを使ってもう一度SearchDFA()を呼んでいるのが確認できます。
RE2はlookbehindに対応していないのに、逆方向に照合する機能が実装されているのです。
ところでRE2はなぜコンパイル時ではなく検索時に遷移先テーブルを作るのでしょうか。その理由は明言されていないようですので推測になりますが、おそらくDFAの持つデメリットを考慮した結果ではないかと思われます。
先にBT法における指数的爆発について取り上げましたが、実はDFAも爆発します。BTで爆発するのは照合回数でしたが、DFAの場合はstate数が爆発を起こします。State数の爆発とは言い換えれば使用メモリ量が爆発的に増えるということです。
ではどういう時にstate数は爆発するのでしょうか。
/[a-e]+[b-f]*/ という表現を例とします。この表現の1つ目の正規表現要素（atomといいます）である[a-e]と、2つ目のatomである[b-f]とは、どちらも[b-e]の4文字にマッチします。つまりマッチする範囲が互いに一部重なり合っています。
そのためDFAの遷移表を作ろうとした時、検索対象文字列の2文字目以降に現れる[b-e]の4文字は、1つ目の[a-e]にマッチしていると考えれば良いのか、それとも2つ目の[b-f]にマッチしているとすべきか判断がつかなくなってしまいます。
このような場合どうするのかといいますと、「1つ目の[a-e]の一部かもしれないし、2つ目の[b-f]の一部かもしれない」という、いわば1.5番目とも言えるstateを作って対応します。
| state→ ↓添え字 | s0.next[256] | s1.next[256] | s2.next[256] |
|---|---|---|---|
| 'a' 0x61 | s1への ポインタ | s1自身への ポインタ | 受理 |
| 'b'-'e' 0x62-0x65 | s1への ポインタ | s1自身への ポインタ | s2自身への ポインタ |
| 'f' 0x66 | NULL | s2への ポインタ | s2自身への ポインタ |
| 上記以外の 文字 0x00-0x60 0x67-0xff | NULL | 受理 | 受理 |
この表のs1が「1.5番目のstate」に相当します。現在位置が1番目のatomなのか2番目のatomなのかはっきりしないうちはs1自身をループし続け、2番目のatomのみがマッチする'f'が出てきた時点で初めて明確に[b-f]*へ遷移し、以後は'a'にはマッチしなくなります。NFAのstatesをDFAで使えるよう変換すると、このようにNFAの時点では存在しなかったstateが新たに発生するのです。
この例は単純ですが、隣り合うatom同士のマッチする文字がoverlapしている状態（atomの境界がはっきりしない状態）が3連、4連と増えてゆくと中間state同士の中間stateなるものまで発生するようになり、どんどん複雑な状況になってゆきます。これがstate数の爆発につながります。
Regex crateの作者曰く、/[01]*1[01]{N}/という表現（Nは回数指定）をDFAにコンパイルするとだいたい2のN乗個のstatesになるそうです。
これを検証してみましょう。あまり表が大きくなっても困りますので、Nの部分は3とし、/[01]*1[01][01][01]/ に展開して考えます。2^3ですので、8 statesほどになるはずです。
| 添え字→ ↓state | '0' 0x30 | '1' 0x31 | 左記2字以外 | 備考 |
|---|---|---|---|---|
| s0 | &s0 | &s1 | NULL | /[01]*1[01][01][01]/ の下線部分に相当するstate。0が出てくるうちは自分自身をloopし続ける。1が出てきたら「 /[01]*1[01][01][01]/ の 1 にマッチしたのかもしれないし、/[01]*1[01][01][01]/ の 1 にマッチしたのかもしれない」というstate、s1に移行する。
|
| s1 | &s2 | &s3 | NULL | /[01]*1[01][01][01]/ の下線部のどちらかのatomにマッチした直後の状態。0が出てきたら「 /[01]*1[01][01][01]/ の下線部にある 0 のどちらかにマッチした状態」というstate、s2に移行する。1が出てきたら「 /[01]*1[01][01][01]/ の下線部にある 1 のどれかにマッチした状態」というstate、s3に移行する。
|
| s2 | &s4 | &s5 | NULL | /[01]*1[01][01][01]/ の下線部のどちらかにマッチした直後の状態。0が出てきたら「 /[01]*1[01][01][01]/ の下線部にある 0 のどちらかにマッチした状態」というstate、s4に移行する。1が出てきたら「 /[01]*1[01][01][01]/ の下線部にある 1 のどれかにマッチした状態」というstate、s5に移行する。
|
| s3 | &s6 | &s7 | NULL | /[01]*1[01][01][01]/ の下線部のどこかにマッチした直後の状態。0が出てきたら「 /[01]*1[01][01][01]/ の下線部にある 0 のどれかにマッチした状態」というstate、s6に移行する。1が出てきたら「 /[01]*1[01][01][01]/ の下線部にある 1 のどれかにマッチした状態」というstate、s7に移行する。
|
| s4 | &s0? | &s1? | NULL | /[01]*1[01][01][01]/ の下線部のどこかにマッチした直後の状態。0が出てきたら「 /[01]*1[01][01][01]/ の下線部にある 0 のどちらかにマッチした状態」を意味するが、最終atomにマッチしたということは照合成功を意味するので、ここで終わることも出来る。現在位置を保存して他の可能性を追い掛けるなら「最終atomにマッチした状態」を外して「/[01]*1[01][01][01]/ の 0 にマッチした状態」というstate、s0に移行する。1が出てきたら「 /[01]*1[01][01][01]/ の下線部にある 1 のどれかにマッチした状態」を意味するが、こちらも照合成功と考えられる状態なのでここで終わることも出来る。続けるなら「最終atomにマッチした状態」を外して「/[01]*1[01][01][01]/ の下線部にある 1 のどちらかにマッチした状態」というstate、s1に移行する。
|
| s5 | &s2? | &s3? | NULL | /[01]*1[01][01][01]/ の下線部のどこかにマッチした直後の状態。0が出てきたら「 /[01]*1[01][01][01]/ の下線部にある 0 のどれかにマッチした状態」を意味するが、上と同じ理由によりここで終わることも出来る。続けるなら「/[01]*1[01][01][01]/ の下線部にある 0 のどちらかにマッチした状態」というstate、s2に移行する。1が出てきたら「 /[01]*1[01][01][01]/ の下線部にある 1 のどれかにマッチした状態」を意味するが、これも上と同じく続けるなら「/[01]*1[01][01][01]/ の下線部にある 1 のどれかにマッチした状態」というstate、s3に移行する。
|
| s6 | &s4? | &s5? | NULL | /[01]*1[01][01][01]/ の下線部にある 0 の下線部のどこかにマッチした直後の状態。0が出てきたら「 /[01]*1[01][01][01]/ の下線部にある 0 のどれかにマッチした状態」を意味するが、上と同じく最終atomにマッチしたと見なしてここで終わることも出来る。続けるなら「/[01]*1[01][01][01]/ の下線部にある 0 のどちらかにマッチした状態」というstate、s4に移行する。1が出てきたら「 /[01]*1[01][01][01]/ の下線部にある 1 のどれかにマッチした状態」を意味するが、これもここで終わることが出来る。続けるなら「/[01]*1[01][01][01]/ の下線部にある 1 のどれかにマッチした状態」というstate、s5に移行する。
|
| s7 | &s6? | &s7? | NULL | /[01]*1[01][01][01]/ の下線部のどこかにマッチした直後の状態。0が出てきたら「 /[01]*1[01][01][01]/ の下線部にある 0 のどれかにマッチした状態」を意味するが、ここで終わることも出来る。続けるなら「/[01]*1[01][01][01]/ の下線部にある 0 のどれかにマッチした状態」というstate、s6に移行する。1が出てきたら「 /[01]*1[01][01][01]/ の下線部にある 1 のどれかにマッチした状態」を意味するが、ここで終わることも出来る。続けるなら「/[01]*1[01][01][01]/ の下線部にある 1 のどれかにマッチした状態」というstate、s7自身を繰り返す。
|
途中から気づかれたかもしれませんが、最後3つのatomが[01][01][01]となるパターン、[01][01][01]となるパターン、[01][01][01]となるパターン、[01][01][01]となるパターンの4種類があります。つまり最後の[01]を除くその前の2つはすべての組み合わせ (2^2=4) が現れます。
そして4パターンそれぞれに、その前が [01]*1であるパターンと[01]*1とがあるので、2通りの3乗で合計8パターン存在することとなります。焼き寿司さんの言うように、2^N個のstate数です。
ちなみに焼き寿司さんが「だいたい」と付けているのは、実際にはs0の前にセットアップ用のstateが来たり、s7の後に「上がり」であることを示すstateが来たりするからではないかと思われます。
RE2はNFA用statesから変換して作ったDFAのstatesをずっとは保持し続けず、キャッシュという形で管理します。キャッシュには上限（既定では1MB）が設定されていて、それを超えるstateをキャッシュ化しようとすると、キャッシュ全体がクリアされます。その状態で今一度キャッシュの追加を試みて、なおも失敗するようならstate数の爆発が起きたと考え、呼出元に対して「うちでは手に負えません」と通知します。
遷移表をコンパイル時に作るということは、全statesに対して「この文字が現れたら次はこのstateへ行く」というのを事前にすべて調べなければならないということですので、state数が増えればその分パターンコンパイルに要する時間も長くなってゆくというデメリットもあります。前もって作っておいても検索対象文字列から該当する文字が現れないため通過することがないstateというのもあることでしょう。
RE2がコンパイル時ではなく検索時にDFAの遷移表を作ってゆくのは、このようなデメリットを避けて、メモリ使用量と遷移先を調べる時間との両方を極力抑えたいということなのではないかと考えられます。
DFAエンジンから「うちでは扱えません」と断られたら、RE2はNFAでの検索を試みます。RE2には3種類のNFAエンジンが搭載されています。
次善策として最初に試すのはOnePass検索エンジンです。ここで云う one-pass とは「BTなしで検索できる」という意味です。BTなしで検索できるというのは、先に見た「隣り合うatom同士がoverlapしている」箇所が皆無ということです。
例えば ".*" という表現は .* とその次の " とがoverlapしています。どちらも " にマッチする表現だからです。しかしこれを "[^"]*" のように改めるとoverlapしていない表現となり、OnePassエンジンが使えるようになります。
ちなみに「隣り合う」というのは照合する順番が隣という意味です。例えば /(aba*)*/ のような表現もone-passではないと判断されます。a*の部分が次のループ先頭の a とoverlapしているからです。
OnePassエンジンが使えない場合、第3の策としてBitState検索エンジンの使用が検討されます。これは巨大なbitset（262144ビット分）を用意して、既に試したことのある「内部表現位置と検索対象文字列中の位置との組み合わせ」を記録してゆくことで、同じ組み合わせを何度も試すことになるのを防ぐという方式です。
262144÷正規表現から変換された内部表現のサイズ=対応可能な文字列の長さですので、事実上、短い正規表現と短いテキストとの組み合わせの場合しか出番はありません。
BitStateエンジンもダメとなったらいよいよ最後の頼みの綱、ThompsonのNFAによる検索が行われます。これまで見てきたDFA, OnePass, BitStateと違い、このエンジンには何の制約もありませんので、マッチするしないが確実に判明します。
なおDFAでの検索に成功した場合でも括弧の中身を取り出す必要がある時は、マッチした箇所に対して上述の順番でNFAエンジンの呼び出しを試します。そのため括弧の中身を取り出そうとするとベンチマークのスコアも幾分か落ちます（著しく長いテキストにマッチしない限りはOnePassかBitStateが担当することになるはずです。BitStateエンジンの存在理由はこの処理の高速化ではないかと思われます）。
昨今の正規表現ライブラリ事情について記すはずが、終わってみれば半分以上はRE2の話になってしまいました。
以下は、本文中に入らなかった雑多な余談です。
/[a-q][^u-z]{13}x/ で著しく数字を落としていますが、RE2はそれほど遅くありません。この辺りにヒントが潜んでいる気もします。
\p{RGI_Emoji}のように、NFAの段階で数千statesにもなる表現もあることや、DFAでは正規表現中に同じ文字クラスが複数回出てきても、そのクラス用の内部表現を使い回すということができない（次の行き先が違う）ので、例えば\p{Ll}{10}のような表現は文字通り\p{Ll}用のstatesを10個分配置する必要があったりすることなどを踏まえますと、RE2既定の1MBを超えるメモリが必要になる状況も現実に発生しうるのではないかと思われます。
/(...),\1/ という表現は、括弧が cat をキャプチャしている時は /cat,cat/ と等価ですが、dog をキャプチャしている時は /dog,dog/ と等価になります。このように検索の最中に正規表現パターンに変化されると、DFAやThompson NFAでは対応するのが難しいのです。/(.*)b\1$/ という表現で "aaba" を検索した場合、最初の 'a' から検索するとマッチングは失敗に終わりますが、2文字目の 'a' から検索するとマッチングは成功します。しかし2文字目の 'a' と .* との組み合わせは、最初の 'a' から検索した時にも調査します。そのため先述のBitStateのような方法で調査済みの組み合わせは弾くような仕組みを導入していると、マッチすべきものがマッチしないということが起こってしまいます。