【C#】Boyer-Moore法(BM法)を使って文字列の照合を行う

はじめに

今回はBoyer-Moore法(BM法)を自前で実装してみようという記事になります。

BM法とは文字列検索アルゴリズムの一つで，他の文字列検索アルゴリズムと比べて優秀な部類と言われるアルゴリズムです。(最悪計算量は $o(m+n)$ )

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法の仕組み
実装
テスト
さいごに

BM法の仕組み

本当はここで細かく紹介したかったのですが、わかりやすく紹介されていたサイトがあったのでそちらを参照してみてください。

文字列検索のいろいろ from Kazuma Mikami

www.slideshare.net

qiita.com

実装

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っぽそうですね。