ボイヤ・ムーア法のアルゴリズムがよくわかりません。

ボイヤ・ムーア法のアルゴリズムがよくわかりません。

テストで

kouhou-ni-jouhou-ga-aru.(-はスペースです。)
というテキストをjouhouで検索した場合のパターンの移動の様子をかけという問題で
先生の答えは
kouhou-ni-jouhou-ga-aru.
jouhou
-jouhou
-------jouhou
----------jouhou
となるらしいんですが、自分は
kouhou-ni-jouhou-ga-aru.
jouhou
---jouhou
---------jouhou
----------jouhou
だと思いました。
一行目のkouhouのuから比較してjで一致しなかったら
次は三文字目のuに合わせるのではないのでしょうか？

どういう考え方をすればいいのかをご教授いただきたいです。
よろしくお願いします。

No.2 ベストアンサー 回答者： mtaka2 回答日時： 2010/07/24 23:03

とりあえず、ちょっとだけ補足しておきます。

ます、Wikipedia のBM法の説明は理解できますでしょうか。
http://goo.gl/HJ8N
私の説明は、ほぼこれに沿ったものとして、テーブルの作り方を具体的に書き下したものとなっています。
結果だけ書くと、

★第一のテーブル

文字 シフト
u 0
o 1
h 2
j 5
他のあらゆる文字 6


★第二のテーブル

N パターン シフト
0 _____X 1
1 ____Xu 6
2 ___Xou 3
3 __Xhou 6
4 _Xuhou 6
5 Xouhou 6

となります。

No.1 回答者： mtaka2 回答日時： 2010/07/24 22:13

どちらの回答も間違えてます。

まずはテーブルの算出について説明すると

★右から一文字目がいきなり不一致の場合についての、移動量テーブルの算出

a)不一致文字がoの場合
?????o
-jouho ○一致可能性あり
--jouh ×一致可能性なし
---jou ×一致可能性なし
----jo ○一致可能性あり
-----j ×一致可能性なし
→次は1文字ずらす
-jouhou


b)不一致文字がhの場合
?????h
-jouho ×一致可能性なし
--jouh ○一致可能性あり
---jou ×一致可能性なし
----jo ×一致可能性なし
-----j ×一致可能性なし
→次は2文字ずらす
--jouhou

c)不一致文字がjの場合
?????j
-jouho ×一致可能性なし
--jouh ×一致可能性なし
---jou ×一致可能性なし
----jo ×一致可能性なし
-----j ○一致可能性あり
→次は5文字ずらす
-----jouhou

d)不一致文字がそれ以外の時は6文字ずらす


★右から二文字以降で不一致の場合についての、移動量テーブルの算出

A)右から5文字目までは一致、6文字目で不一致の場合
Xouhou (Xはj以外)
-jouho ×一致可能性無し
--jouh ×一致可能性無し
---jou ×一致可能性無し
----jo ×一致可能性無し
-----j ×一致可能性無し
→次は6文字ずらす
------jouhou

B)右から4文字目までは一致、5文字目で不一致の場合
?Xuhou (Xはo以外)
-jouho ×一致可能性無し(質問者さんが挙げられた回答1つ目)
--jouh ×一致可能性無し
---jou ×一致可能性無し(質問者さんが挙げられた回答2つ目)
----jo ×一致可能性無し
-----j ×一致可能性無し
→次は6文字ずらす
------jouhou

C)右から3文字目までは一致、4文字目で不一致の場合
??Xhou (Xはu以外)
-jouho ×一致可能性無し
--jouh ×一致可能性無し
---jou ×一致可能性無し
----jo ×一致可能性無し
-----j ×一致可能性無し
→次は6文字ずらす
------jouhou

D)右から2文字目までは一致、3文字目で不一致の場合
???Xou (Xはh以外)
-jouho ×一致可能性無し
--jouh ×一致可能性無し
---jou ○一致可能性アリ
----jo ×一致可能性無し
-----j ×一致可能性無し
→次は3文字ずらす
---jouhou

E)右から1文字目までは一致、2文字目で不一致の場合
????Xu (Xはo以外)
-jouho ×一致可能性無し
--jouh ×一致可能性無し
---jou ×一致可能性無し
----jo ×一致可能性無し
-----j ×一致可能性無し
→次は6文字ずらす
------jouhou

となります。
このようなテーブルに基づいて処理しますから、検索実行の結果は、

kouhou-ni-jouhou-ga-aru.
jouhou →右から6文字目で不一致、パターンA、6文字ずらし
------jouhou →右から1文字目で不一致、パターンa、1文字ずらし
-------jouhou →右から3文字目で不一致、パターンD、3文字ずらし
----------jouhou →全文字一致

となります。

この回答へのお礼

とても詳しい回答ありがとうございます。

先生の言っていたことや教科書、また自分の考えていたやりかたとmtaka2さんのやりかたが
違いすぎて一体何が正しいのかよくわからなくなってしまいました。

mtaka2さんの回答を参考にしながらもっと調べてみようと思います。

ありがとうございました。

お礼日時：2010/07/24 22:41