既存の物を超えられるか？ - 高速正規表現エンジンを１から作りたい @ 2ch

直観で行けそうだなと思いました。
根拠は？という事ですが、根拠を脳内から掘り起こす作業も１からです。

とりあえず１つ調査してみました。

 .*単語.*単語.*単語.*単語.*単語.*単語.*単語.*単語.*単語.*単語.*
 ランダムな２文字の単語が１０個並んだもの。これと１万文字とのマッチングをしてみた。
 java.util.regexとの比較で
 ５千～２万倍早くなった、これは上限に過ぎないが見込はありそうだ。
 発想は極めて幼稚で、.*のところで分割すればいいじゃないかというもの。 

指数オーダーと線形オーダーとで優劣は明白でした。
(.*で連結されたパターンというのは実用上頻繁にみられるものです）
ただしこの大差はマッチングに失敗する事が多い例だからです。
もっと簡単な例で成功する場合は１０倍程度に収まる事もあります。

以下はプログラムの一部です。
（.*で分割したパターン要素を保持するパターン要素）
とりあえずjavaで開発を進めます。HaskellやC++で書きたい欲望は今は抑えます。

---

 public class Floating implements PatternElement{
   ArrayList<PatternElement> eee=new ArrayList();
   public void add(PatternElement e){
     eee.add(e);
   }
   @Override
   public int find(String txt,int pointer){
     int ret=-1;
     for(PatternElement e: eee){
       int f=e.find(txt,pointer);
       if(f==-1)return -1;
       if(ret==-1)ret=f;
       pointer=f+e.getMod();
     }
     return ret;
   }
   @Override
   public int getMod() {
     return 1;
   }
 }

---

この実験のメインループはfind内ですが
アルゴリズムも使っておらず何の変哲もなく面白みもありませんが
１重ループなので線形オーダーです。
なおパターンからPatternElementへの字句解析は省略しています。

次に他のパターンの事も考えてみます。