大雑把な発想 - 高速正規表現エンジンを１から作りたい @ 2ch

単純な発想でパターンをアスタリスク*で分割する方法に可能性を見出しました。

 R（パターン)の値が十分に小さいならば分割できる

しかしアスタリスクの他に*? *+ + +? ++ {n} {n}? {n}+ {n,} {n,}? {n,}+ {m,n} {m,n}? {m,n}+などが有る事を忘れていました。
ですが工夫すればアスタリスクに還元できるとおおざっぱに考えます。
以上で本エンジンの性能が指数オーダーから線形オーダーになった気になりました。
え？そんな安直な！というご批判には答えていくつもりです。

次に分割されたパターンの事を考えます。前回の実験では簡単な単語を用いましたが、
実際のパターンのバリエーションは無限なので困ってしまいます。
具体的に考えていきます。

 (?:(?:abc)|(?:edfg))

パターンのＯＲですが、これは合成して１つの単語にする方法がありそうです。

 [a-z]

なども同様の合成方法がありそうです。

 (?:(?:\s*abc)|(?:(?:\s*cde)*))

あまり複雑なときは場合分けするのが妥当ですが、
この程度ならabcとcdeを合成したものを検索して先に現れた方から調べるという工夫ができそうです。
なおR((?:\s*cde)*)の値は十分大きいので分割は考えなくて良さそうです。

 (?:abc)?(?:def)?(?:ghi)?

これもabc　def　ghiを合成して検索することができそうです。
これらの例の合成方法はバケットを用いれば簡単に実装できますが、
もっと複雑なパターンには別の方法を組み合わせます
、これも明らかにしていきます。

パターンを合成して扱う考え方はオートマトンと等価なんじゃないか？という感じもしますが、無かったことにします。
かわりに検索アルゴリズムの拡張版を使う予定です。

おおざっぱなままですが、明日から調査用のプログラムを作り始めます。