はじめに
今回はBoyer-Moore法(BM法)
を自前で実装してみようという記事になります。
BM法とは文字列検索アルゴリズムの一つで,他の文字列検索アルゴリズムと比べて優秀な部類と言われるアルゴリズムです。(最悪計算量は)
C#
をそれなりに触ったことのあるかたならString.Contains
やString.IndexOf
と表現した方がわかりやすいかもしれません。(内部的に同じアルゴリズムかは知りませんが)
今回実装する目的のイメージはこんな感じ。
static void Main(string[] args) { var text = "はなちるのマイノート"; var pattern1 = "マイ"; var pattern2 = "お金"; Console.WriteLine(text.Contains(pattern1)); // True Console.WriteLine(text.Contains(pattern2)); // False Console.WriteLine(text.IndexOf(pattern1)); // 5 Console.WriteLine(text.IndexOf(pattern2)); // -1 // 今回実装するもの Console.WriteLine(BMSerch.Execute(text, pattern1)); // 5 Console.WriteLine(BMSerch.Execute(text, pattern2)); // -1 }
早速みていきましょう。
BM法の仕組み
本当はここで細かく紹介したかったのですが、わかりやすく紹介されていたサイトがあったのでそちらを参照してみてください。
文字列検索のいろいろ from Kazuma Mikami
www.slideshare.net
実装
public static class BMSerch { public static int Execute(string text, string pattern) { var table = CreateTable(pattern); var i = pattern.Length - 1; // テキストの比較位置 var j = pattern.Length - 1; // パターンの比較位置 // パターン検出 while(i < text.Length) { if (text[i] != pattern[j]) { // ずらし表から次の比較位置を決める i += table.ContainsKey(text[i]) ? table[text[i]] : pattern.Length; j = pattern.Length - 1; } else { // 一致 if (j == 0) return i; // 文字が一致,前の文字を照合する i--; j--; } } return -1; } /// <summary> /// ずらし表作成 /// </summary> private static Dictionary<char, int> CreateTable(string pattern) { var table = new Dictionary<char, int>(); // 重複する文字列があった場合,小さい方を優先 for (int i = 0; i < pattern.Length ; i++) table[pattern[i]] = pattern.Length - i - 1; return table; } }
テスト
実際に動くか簡単なテストをしてみましょう。
static void Main(string[] args) { var text = "はなちるのマイノート"; var pattern1 = "マイ"; var pattern2 = "お金"; Console.WriteLine(BMSerch.Execute(text, pattern1)); // 5 Console.WriteLine(BMSerch.Execute(text, pattern2)); // -1 }
正しく表示されていたのでOKっぽそうですね。
さいごに
今回はBM法を紹介させていただきましたが、C#
でプログラミングするときは基本String.Contains
やString.IndexOf
を使えば事足りるでしょう。
ただこういった内部的にどんなことがなされているのかを知るのもたまには面白いかもしれませんね。
とりあえずこんなところで。
ではまた。