正規表現でlookbehindやlookaheadがある場合でも効率良く(線形時間で)マッチしたい、という論文3つ:

Efficient Matching of Regular Expressions with Lookaround Assertions

https://dl.acm.org/doi/10.1145/3632934

NFAにオラクルを追加する。

オラクルは各位置でlookaroundの正規表現にマッチするかどうかを示す。

オラクルはlookaroundの正規表現ごとに作られる。

純粋な正規表現に任意のpositive/negative lookaroundを追加した正規表現を扱う(正規表現は反転できる必要がある)。キャプチャは無し。

文字列wの範囲[i, j)が正規表現にマッチするかどうかを判定する。

Linear Matching of JavaScript Regular Expressions

https://dl.acm.org/doi/10.1145/3656431

NFAにオラクルを追加する。

JavaScriptの正規表現のサブセット(バックリファレンス以外?)をサポートする(キャプチャや、JavaScriptの正規表現の細かい仕様をサポートする)。

lookaroundでキャプチャがある場合は前の論文と方針は同じで、キャプチャの処理のために1パスさらに追加される。

キャプチャの無いlookbehindの場合は順方向のスキャン1回のみにできる。

RE#: High Performance Derivative-Based Regex Matching with Intersection, Complement, and Restricted Lookarounds

https://dl.acm.org/doi/10.1145/3704837

Derivativeベース。lookaroundに制限あり。

lookaroundはネストできない。その代わりに&と否定が使える。lookbehindは最初に1つのみ存在できる。lookaheadは最後に1つのみ存在できる。キャプチャはなし。

後ろから逆方向に最長マッチした後にそこから順方向に最長マッチすることで最左最長マッチを計算する。

正規表現の最適化とかベクトル化とかいろいろやってすごい速度が出るしメモリもそんなに消費しないって書いてあるけど本当? 数百MB/秒出るなら毎回最後から検索しても問題ない感じなんだろうか。