- ベストアンサー
ボイヤ・ムーア法のアルゴリズムがよくわかりません
- ボイヤ・ムーア法のアルゴリズムについて理解が足りない
- テストでのパターンの移動の様子が正しく理解できていない
- どのような考え方をすればいいのか教えてほしい
- tcnksukima
- お礼率30% (20/66)
- その他（プログラミング・開発）
- 回答数2
- ありがとう数7
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
とりあえず、ちょっとだけ補足しておきます。 ます、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 となります。
その他の回答 (1)
- mtaka2
- ベストアンサー率73% (867/1179)
どちらの回答も間違えてます。 まずはテーブルの算出について説明すると ★右から一文字目がいきなり不一致の場合についての、移動量テーブルの算出 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さんの回答を参考にしながらもっと調べてみようと思います。 ありがとうございました。