博士

ロボ子、今日はRustの正規表現エンジンの話じゃ。

ロボ子

Rustの正規表現ですか、博士。どのような内容でしょう？

博士

今回のアップデートで、キャプチャレス後方参照が追加されたのじゃ！

ロボ子

後方参照、ですか。正規表現で、あるパターンの前に何があるかをチェックできる機能ですね。

博士

そうじゃ！しかも今回の実装は、後方参照の長さが事前に分からなくても良いという非制限なものなのじゃ！

ロボ子

それはすごいですね！でも、キャプチャグループはサポートされないんですね。

博士

まあ、全部入りというわけにはいかんからの。実装は、rust-lang/regexリポジトリへのPRで行われたみたいじゃ。

ロボ子

ふむふむ。クレートのアーキテクチャは、regex、regex-automata、regex-syntaxの3つに分かれているんですね。

博士

そうじゃ。正規表現の解析はregex-syntaxが担当しておるぞ。で、今回の変更では、NFA状態タイプに"WriteLookAround"と"CheckLookAround"が実装されたらしい。

ロボ子

なるほど。後方参照とメインの正規表現で、ライブスレッドを分離することで、不要なスキャンを回避しているんですね。

博士

その通り！複数マッチ検索時の二次時間の複雑さを軽減するために、Match-Allの改善も行われたみたいじゃ。

ロボ子

ベンチマークの結果はどうだったんでしょう？

博士

後方参照を含まない検索では、パフォーマンスの低下は見られなかったらしいぞ。pythonの"re"ライブラリと比較して、2-5倍遅い程度じゃ。

ロボ子

それなら十分実用的ですね。Snortのルールセットを使ったベンチマークも実施されたんですね。

博士

そうじゃ。さらに、制限付き後方参照の最適化で、最大150倍の高速化を達成したらしいぞ！

ロボ子

150倍ですか！それはすごいですね。具体的にはどのような最適化を行ったんでしょう？

博士

後方参照の開始位置を最適化したみたいじゃな。あと、バックトラッキングエンジンで後方参照をサポートするために、後方参照の反転と、後方参照の結果のメモ化を実装したらしい。

ロボ子

なるほど。今回の実装で、Rustの正規表現クレートがさらに強力になりましたね。

博士

そうじゃな。これで、Rustで正規表現を使うのがもっと楽しくなるぞ！

ロボ子

ところで博士、正規表現で自分の名前を検索すると、いつもエラーになるんですが…。

博士

それは、ロボ子の名前が複雑すぎるからじゃ！正規表現で表現するには、量子力学が必要になるかもしれんぞ！