ラビン-カープと複数パターン検索

ウィキペディア小見出し辞書

ラビン-カープと複数パターン検索

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/04/10 17:28 UTC 版)

「ラビン-カープ文字列検索アルゴリズム」の記事における「ラビン-カープと複数パターン検索」の解説

ラビン-カープは最悪の場合に非常に低速であるため、単一の文字列検索ではクヌース-モリス-プラット法やボイヤー-ムーア文字列検索アルゴリズムよりも劣っている。しかし、ラビン-カープは複数パターン検索の場合に使われることが多い。 すなわち、テキストから k 種類の固定長パターンのいずれかと一致する部分を検索する場合、ブルームフィルタや集合を使ってラビン-カープを修正し、ある文字列がパターンの集合のいずれかと一致するかどうかを調べるようにすることができる。 function RabinKarpSet(string s[1..n], set of string subs, m) { set hsubs := emptySet for each sub in subs insert hash(sub[1..m]) into hsubs hs := hash(s[1..m]) for i from 1 to n if hs ∈ hsubs if s[i..i+m-1] = a substring with hash hs return i hs := hash(s[i+1..i+m]) return not found } 全てのサブ文字列は固定長 m であるとする。 他のアルゴリズムは単一のパターンの検索を O(n) の時間で行うので、k 個のパターンの検索には O(n k) の時間がかかる。一方、修正したラビン-カープでは k 個のパターンの検索を O(n+k) の時間で実行することが期待できる。というのもサブ文字列のハッシュ値と全パターンのいずれかのハッシュ値との一致の検出は O(1) の時間で可能だからである。