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

先日.* で単語を分割して効率が良くなる実験をしました。
そんな安易な発想で行けるわけねーだろｗｗｗｗｗｗと切り捨てた方もいたと思いますｗ
自分も安易だと思いましたが愚直に延長線上を進みます。
ではアスタリスク * がついているところで分割すればいいのか？それともダメなのか？
と考えてみます。結論を先に言えばＹＥＳ＆ＮＯです。
具体的には .* では良かったが w* ではダメっぽい。
これら２つは長さに対する出現頻度の傾向が違うように感じます。
つまりパターン w* は以下とマッチしますが

 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww

wが連続するほどこの単語は出現頻度は低くなる。
w* は単語として扱った方が良く分割には適さないと思えます。

別の正規表現も考えてみます [^w]* というのは .* と似た傾向があるように感じます。

 [^w]*はwを検索して無い事を調べる操作が加わった .* と見なせる。

こう考えることで[^w]*の部分で分割でき、線形オーダーへの効率化が期待できます。

以上説明のために出現頻度という言葉を用いましたが、マッチする組み合わせの数で説明する方法もあったでしょう。
何か名称を与えた方がいいかもしれません。

 R( .*)=0
 R(a*)=1

仮にこうしておきます。