【C算法】第8章 文字列処理 (その4)

こつこつ。今回はBM法。

• BM法アルゴリズムの自分なりのまとめ。
  
• テキスト"ABCXDEZCABACABAC"かパターン"ABAC"を探索する。
  
  
  
  • テキスト照合位置Tとパターン照合位置Pという2つの変数を使う。
    
  • パターンの文字列長は4文字である。そこで、テキストの4文字目以降にあらわれる最初の"C"を探す。
    
  • "C"がなければパターンは含まれていない。
    
  • "C"があったら、テキストのその位置から前へ照合をはじめる。この例の場合は、T=7, P=3となる。TとPを減算していって、パターンの文字全てが照合して同じならば探索成功。Pのインデックスまたはポインタを返す。
    
  • 照合が途中で失敗した場合は後続するテキスト内にパターンが存在するかどうか、探索を継続する。
    このケースだと、
    

    
    01234567890123456
    ABCXDEZCABACABAC\0
        ABAC
    

    
    なので、"Z"と"A"でいきなり違うので照合はストップする。ストップ時はT=6, P=2。
    
  • ここで、最後に照合に失敗した"Z"を検討対象にする。"Z"の場合はパターンにあらわれないので、パターンの最終照合時に判明した未照合文字数3だけTを進める。T=9, P=2。
    
  • ここでP=2のパターン文字は"A"なので、T=9以降の"A"を探す。するとT=10となる。
    
  • 照合再開。照合はお尻から実施するので、P=3にする。あわせて、T=11とする。
    
  
  
• う、ちょっとわかったが一般性がたりないかな。もう一度トライ。
  
  
  
  • テキストの長さをTN、パターンの長さをPNとする。
    
  • TN < PNならばマッチしないので終了。そうでなければ次へ。
    
  • テキスト照合位置TPとパターン照合位置PPという2つの変数を使う。
    
  • 初期値をTP= TN - PN, PP = PN - 1とする。
    
  • 照合ループ：
    PPがPN - 1でなければ、適量(Kとする)を加算してPN-1とする。TP += Kとする。
    TPとPPの位置にある文字が同じならば、TPとPPとを減算して比較する。
    PP=0まで同じならば、マッチ。TPの値を返して終了する。
    PP=0になるまでに不一致が発生したなら、ループを抜ける。
    
  • 次の照合位置を決める作業。
    
  • まずTPの位置にある文字を見る(不一致した文字)。その文字によってTPの移動量が異なる。例えば、その文字がパターン文字列に含まれない文字ならば、TP += PP + 1だけ移動する。逆にその文字がパターン文字列に含まれるが、この照合位置では不一致であった場合もある。この場合は、その文字にあわせた移動をする。その移動の幅の計算がなぜ本のようでいいのかがわからない。。。。それは将来Knuthをやったときとかに考えるとして、今は飲みこんでおく
    
  • さらにもう一回移動を勘案する。TP以降で現在のPPの位置の文字と一致するまでTPをインクレイメントする。一致せずTNにいたれば、一致不可能にて終了。一致した場合は、「照合ループへ」
    
  
  
• いまいちすっきりしないが、これくらいの理解でCでの実装へ。list0814を写経、上の私の理解とは違うところがあるが、大筋はあってる。
  
• おもうに、C言語を使いこなしている、というのは、このように自然言語でアルゴリズムを書いたり理解したりしようとしてくても、C言語のまま、それが自然言語であるがごとくアルゴリズムを書いたり読んだりできるようなことを言うのかもしれない。そういう感覚でもCを書いていってみたい。
  

ふー。次回はやっと線形リスト。。。