BM法のスキップテーブル

Question

BM法を用いた文字列検索のプログラムを書いています。

参考にしているテキストがあるのですが、スキップテーブルの説明で疑問を持ったので質問致します。
例としてdoremifasorashidoというテキストに対して、スキップテーブルではoの値が7になると書かれています。
右端からの文字数だと認識しているので、oの値は0になると思うのですが、認識が間違っているのでしょうか。

テキストが違うような気がしますが、初めてこのアルゴリズムを使うので、何が正しいのか今いちよくわかりません。
ご回答よろしくお願い致します。

Answer 1

BM法の本質は、一致しない文字が出たとき、その文字が一致しうる場所に移動させるということです。
例えば後ろから2文字目にoが出て不一致になった場合、このoが一致しうる場所として、soのoに合わせるために検索文字列を後ろにスライドさせるといったことをするのです。
この方法をとる際、先述のoは最後のoに一致させるということは不可能です。つまり、スキップテーブル作成に当たって末尾のoに関してはないものとして扱わなければならないのです。

Comments

[programming]

無限ループになることを確かめました(^^;)
確かに、移動先が末尾のままでは、いつまでもパターンが移動せず、無限に移動量0の移動をしてしまいますね。

パターン側の末尾の文字とテキスト側の文字を比較した時に一致しなければ、パターンをテキスト側の比較した文字がある位置まで移動して比較してみる、ということで理解しました（うまく言えていないですが）。そのようにして無駄な比較を省いているのですね。

BM法に対して理解を深めることができました。
ご回答ありがとうございます。