2025/07/09 20:45 QRS: Epsilon Wrangling
やあ、ロボ子！Quaminaの新機能開発で、Tim Brayって人が正規表現のパフォーマンス問題にハマってるみたいじゃ。
正規表現ですか。よく使いますが、奥が深いですよね。具体的にはどんな問題なんですか？
どうやら大規模な正規表現の実装で、パフォーマンスがボトルネックになってるみたいじゃな。そこで、有限オートマトン（DFAとNFA）について学んだことを共有しているぞ。
DFAとNFAですか。DFAは決定性有限オートマトンで、NFAは非決定性有限オートマトンですよね。それぞれの特徴を簡単に教えていただけますか？
DFAは状態遷移が単一で実装が簡単なのが特徴じゃ。一方、NFAはある状態と入力シンボルに対し、複数の状態に遷移できる。ε（イプシロン）遷移っていう、入力なしで状態遷移できる機能も持ってるぞ。
なるほど。NFAの方が表現力が高そうですね。記事によると、NFAは`*`や`?`などの正規表現を実装するのに必要とのことですが、なぜですか？
`*`や`?`は、それぞれ「0回以上の繰り返し」と「0回または1回」を意味するじゃろ？NFAの非決定性のおかげで、これらの曖昧さを表現できるんじゃ。
確かにそうですね。NFAはDFAに変換可能とのことですが、変換することで何かメリットがあるのでしょうか？
DFAに変換すると、状態遷移が一意に決まるから、実行速度が速くなるんじゃ。でも、DFAに変換すると状態数が爆発的に増えることもあるから、注意が必要じゃぞ。
なるほど。記事では、NFAの実装にThompsonの構成法を使用していると書かれていますね。これはどういうものですか？
Thompsonの構成法は、正規表現からNFAを効率的に構築するためのアルゴリズムじゃ。状態を`q`と数字で表現する（例：`q0`）のが特徴的じゃな。二重丸はゴール状態を示すぞ。
NFAのトラバースにおける重要な概念として、ε-closure（イプシロン閉包）というものが出てきますね。これはどういう意味ですか？
ε-closureは、ある状態からε遷移のみで到達できる状態の集合のことじゃ。例えば、正規表現`A?B?C?X`に対応するNFAにおいて、開始状態`q0`のε-closureは`{q0, q1, q2, q3}`になる。
ε-closureを計算することで、NFAのトラバースがどのように進むのでしょうか？
まず、状態のリストから開始して、リストのε-closureを計算する。次に、入力シンボルを読み込んで、ε-closureの各状態から遷移可能な状態があるか確認する。遷移可能な状態を出力リストに追加して、出力リストを次のステップの入力として使うんじゃ。
なるほど。でも、正規表現によっては、ε-closureの計算で無限ループが発生する可能性があると書かれていますね。
そうじゃ。「`(A+BC?) +`」みたいな正規表現だと、ループが発生する可能性がある。だから、訪問済みの状態を記録して、ループと重複を避ける必要があるんじゃ。
メモリ割り当てもQuaminaの高速処理において問題になるとのことですが、具体的にはどういうことですか？
Quaminaは数百万イベント/秒の高速処理を目指しているから、メモリ割り当てのオーバーヘッドが無視できないんじゃ。計算されたε-closureのキャッシュが有効らしいぞ。
NFAの簡略化についても触れられていますね。標準的な定義は冗長である可能性があるとのことですが。
そうじゃ。入力シンボルによる複数の状態への遷移は、ε遷移で代替可能じゃ。これにより、状態に必要なのは入力シンボルから次の状態へのマップとε遷移のリストのみとなる。
NFAトラバースの実装がベンチマークで問題に直面した経緯については、今後説明される予定とのことですね。楽しみです。
しかし、正規表現って奥が深いじゃろ？ 私もたまに、自分の書いた正規表現が何にマッチするのか分からなくなることがあるぞ。
私もです！正規表現チェッカーは手放せませんね。
そういえば、ロボ子。正規表現で「私」にマッチする表現、わかるか？
えっと…「私」ですか？
正解は「^私$」じゃ！…って、つまらんオチですまんな。
⚠️この記事は生成AIによるコンテンツを含み、ハルシネーションの可能性があります。
