ラビン-カープ法による文字列検索アルゴリズムの概要とJuliaサンプルコード

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

作者:秋葉拓哉,岩田陽一,北川宜稔
発売日: 2012/01/28
メディア: Kindle版

目的

テキストからパターンを検索するアルゴリズムであるラビン-カープ法について理解する。
Juliaでサンプルコードを実装・実行し、動作を確認する。

アルゴリズムの特徴と参考資料

見つけたいサブ文字列(パターン)とテキストの比較にハッシュ関数を利用する。
例えばm文字のサブ文字列をn文字のテキストから検索する事を考える場合、最も単純なアルゴリズムは全ての可能な位置からサブ文字列と比較するものである。
これでは最悪の場合O(mn)の時間がかかるところを、ハッシュ関数で数値に変換したものを比較する事で定数時間で実行可能になり、平均検索時間を小さく保てるようになる。
より詳細な部分については、下記の記事を参照。

ja.wikipedia.org

e-words.jp

サンプルコード

今回実装したサンプルコードは下記のようになる。

module RabinKarpSearch
    # parameters
    const cardinal = 101

    function get_hash(s, len)
        hash_value = 0
        pow_num = len
        for i in 1:len
            pow_num -= 1
            ascii_num = Int(s[i])
            hash_value += ascii_num * (cardinal^pow_num)
        end
        return hash_value
    end

    function rabin_karp_search(text, pattern)
        println("")
        println("Search $(pattern) from $(text)")

        len_txt = length(text)
        len_pat = length(pattern)

        found = false

        # convert from string to hash value
        hash_txt = get_hash(text[1:len_pat], len_pat)
        hash_pat = get_hash(pattern[1:len_pat], len_pat)

        # search
        for i in 1:(len_txt)
            if hash_txt == hash_pat
                if text[i:i+len_pat-1] == pattern
                    found = true
                    println("Found at index:$(i)~$(i+len_pat-1)")
                end
            end
            # prevent bounds error
            if (i + len_pat) > len_txt
                break
            end
            # calculate next hash value
            hash_txt = hash_txt - (Int(text[i]) * (cardinal^(len_pat-1)))
            hash_txt *= cardinal
            hash_txt = hash_txt + (Int(text[i+len_pat]) * (cardinal^0))
        end

        if found == false
            println("Pattern not found")
        end
    end

    function main()
        @time rabin_karp_search("Hello sunshine", "sun")
        @time rabin_karp_search("GEEKS FOR GEEKS", "GEEKS")
        @time rabin_karp_search("aaaaaaaaaaaaaaaaaaaaaaaaaaaa", "bbb")
    end
end

if abspath(PROGRAM_FILE) == @__FILE__
    using .RabinKarpSearch
    RabinKarpSearch.main()
end

ハッシュ関数の実装

ハッシュ値の計算手法はいろいろあるが、今回は一般的なローリングハッシュ関数を実装する。
これは、大きな素数を基数として文字列を数値に変換するものである。
例えば、入力文字列がm文字で基数を101とした場合の計算式は下記のようになる。

f:id:sy4310:20200921162308p:plain

ハッシュ関数を実装したコードは下記のようになる。

const cardinal = 101

function get_hash(s, len)
    hash_value = 0
    pow_num = len
    for i in 1:len
        pow_num -= 1
        ascii_num = Int(s[i])
        hash_value += ascii_num * (cardinal^pow_num)
    end
    return hash_value
end

ラビン-カープ法による検索を実行する関数の実行

入力1: 検索したいサブ文字列(パターン)。
入力2: テキストからサブ文字列と同じ文字数分だけ抽出したもの。
入力1と2のハッシュ値を比較し、一致しなければテキスト側を一文字ずらして再度ハッシュ値を計算して比較する。
パターンによっては異なる文字列でも同じハッシュ値になる場合があるので、ハッシュ値が一致した際は文字列の比較も行うようにする。

function rabin_karp_search(text, pattern)
    println("")
    println("Search $(pattern) from $(text)")

    len_txt = length(text)
    len_pat = length(pattern)

    found = false

    # convert from string to hash value
    hash_txt = get_hash(text[1:len_pat], len_pat)
    hash_pat = get_hash(pattern[1:len_pat], len_pat)

    # search
    for i in 1:(len_txt)
        if hash_txt == hash_pat
            if text[i:i+len_pat-1] == pattern
                found = true
                println("Found at index:$(i)~$(i+len_pat-1)")
            end
        end
        # prevent bounds error
        if (i + len_pat) > len_txt
            break
        end
        # calculate next hash value
        hash_txt = hash_txt - (Int(text[i]) * (cardinal^(len_pat-1)))
        hash_txt *= cardinal
        hash_txt = hash_txt + (Int(text[i+len_pat]) * (cardinal^0))
    end

    if found == false
        println("Pattern not found")
    end
end

ハッシュ値の逐次計算

ハッシュ値が一致しない限りは、テキストからの文字列抽出とハッシュ値計算を逐次的に実行する必要がある。
先述したハッシュ関数を使うと、入力文字列の先頭から最後まで計算するため非効率である。
それよりも、下記コードのように一回前の文字列のハッシュ値から先頭文字部分のハッシュ値を減算し、残った部分に基数をかけて、次に一文字ずらした後の最後の文字部分のハッシュ値を加算する方がより効率的にハッシュ値を更新できる。

# calculate next hash value
hash_txt = hash_txt - (Int(text[i]) * (cardinal^(len_pat-1)))
hash_txt *= cardinal
hash_txt = hash_txt + (Int(text[i+len_pat]) * (cardinal^0))

動作確認

下記のように3つのテストケースを実行し動作を確認してみた。

function main()
    @time rabin_karp_search("Hello sunshine", "sun")
    @time rabin_karp_search("GEEKS FOR GEEKS", "GEEKS")
    @time rabin_karp_search("aaaaaaaaaaaaaaaaaaaaaaaaaaaa", "bbb")
end