目次
目的
- テキストからパターンを検索するアルゴリズムであるラビン-カープ法について理解する。
- Juliaでサンプルコードを実装・実行し、動作を確認する。
アルゴリズムの特徴と参考資料
- 見つけたいサブ文字列(パターン)とテキストの比較にハッシュ関数を利用する。
- 例えばm文字のサブ文字列をn文字のテキストから検索する事を考える場合、最も単純なアルゴリズムは全ての可能な位置からサブ文字列と比較するものである。
- これでは最悪の場合O(mn)の時間がかかるところを、ハッシュ関数で数値に変換したものを比較する事で定数時間で実行可能になり、平均検索時間を小さく保てるようになる。
- より詳細な部分については、下記の記事を参照。
ja.wikipedia.org
e-words.jp
サンプルコード
module RabinKarpSearch
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
hash_txt = get_hash(text[1:len_pat], len_pat)
hash_pat = get_hash(pattern[1:len_pat], len_pat)
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
if (i + len_pat) > len_txt
break
end
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とした場合の計算式は下記のようになる。
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
hash_txt = get_hash(text[1:len_pat], len_pat)
hash_pat = get_hash(pattern[1:len_pat], len_pat)
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
if (i + len_pat) > len_txt
break
end
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
ハッシュ値の逐次計算
- ハッシュ値が一致しない限りは、テキストからの文字列抽出とハッシュ値計算を逐次的に実行する必要がある。
- 先述したハッシュ関数を使うと、入力文字列の先頭から最後まで計算するため非効率である。
- それよりも、下記コードのように一回前の文字列のハッシュ値から先頭文字部分のハッシュ値を減算し、残った部分に基数をかけて、次に一文字ずらした後の最後の文字部分のハッシュ値を加算する方がより効率的にハッシュ値を更新できる。
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
テストケース1
- 検索するパターン: "sun"
- テキスト: "Hello sunshine"
- テキストの7文字目から9文字目で一致することを見つけられている。
テストケース2
- 検索するパターン: "GEEKS"
- テキスト: "GEEKS FOR GEEKS"
- テキストの1~5文字目、11~15文字目の2か所で一致することを見つけられている。
テストケース3
- 検索するパターン: "bbb"
- テキスト: "aaaaaaaaaaaaaaaaaaaaaaaaaaaa"
- 一致する箇所がない事を判定できている。
GitHub
- ここまでに紹介したサンプルコードは下記のGitHubリポジトリで公開済み。
github.com