ハッシュは文字列の検索にも使えます。ローリングハッシュは文字列A(m文字)から、互いに素な基数bとmodの除数hを用いて以下の式でハッシュ値を求めます。
hash(A) = ( A_0*b^(m-1) + A_1*b^(m-2) + … + A_(m-1)*b^0 ) mod h
ハッシュ値が一致する場合は高確率で同じ文字列なのである文字列のなかに探している文字列があるかどうかを調べることができます。
ローリングハッシュで計算量を減らすには？
m文字の文字列のハッシュ値の計算にはO(m)がかかります。なので普通の方法で計算していると時間がかかります。しかし合同式の性質を使うと計算量を減らすことができます。
まず文字列の1文字目からｎ文字目までのハッシュ値を求めてしまいましょう。
1文字目は文字コード×Bの0乗（＝1）なので文字コードと同じになります。2文字目以降のハッシュ値は先に求めた（n-1）文字目までの文字列のハッシュ値にBを掛けて文字コードを足したものをmodで割った剰余となります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Program { public static List<long> CreateHashTable(string str, long B, long mod) { List<long> hashes = new List<long>(); long l = (long)str[0]; hashes.Add(l); for (int i = 1; i < str.Length; i++) { l *= B; l += (long)str[i]; l %= mod; hashes.Add(l); } return hashes; } } |
1文字目からｎ文字目までのハッシュ値がわかれば、これをつかってa文字目からb文字分の文字列のハッシュも求めることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Program { public static long GetHashFromTable(List<long> hashes, int start, int length, long B, long mod) { long a = hashes[start + length - 1]; long b = 0; if(start - 1 >= 0) b = hashes[start - 1]; long ret = (a - b * PowMod(B, length, mod)) % mod; if(ret < 0) // このとき ret が負数だと正しい値が取得できないので modを加算して正の数にする ret += mod; return ret; } } |
これは検索しようとしている文字列のハッシュ値を取得するメソッドです。同時に複数の文字列の検索をする場合、PowModメソッドが一度取得した値を辞書に記録してすぐに取得できるようにしました。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
class Program { static Dictionary<long, long> valuePairs = new Dictionary<long, long>(); public static long PowMod(long x, long y, long mod) { if (valuePairs.ContainsKey(y)) return valuePairs[y]; long ret = 1; for (int i = 0; i < y; i++) { ret *= x; ret %= mod; if (!valuePairs.ContainsKey(i + 1)) valuePairs.Add(i+1, ret); } return ret; } public static long GetHash(string str, long B, long mod) { long hash = 0; for (int i = 0; i < str.Length; i++) { hash += str[i] * PowMod(B, str.Length - 1 - i, mod); hash %= mod; } return hash; } } |
あとはMainメソッド内でこれらを呼び出します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
class Program { public static void Main() { long B = (long)Math.Pow(10, 8) + 7; long mod = (long)Math.Pow(10, 9) + 7; string str = "鳩でもわかるC#"; List<long> hashes = CreateHashTable(str, B, mod); // ハッシュテーブルを表示 for (int i = 1; i <= str.Length; i++) Console.WriteLine(str.Substring(0, i) + " => " + hashes[i - 1]); string[] strings = { "C#", "わかる", "Java" }; foreach (string s in strings) { long hash2 = GetHash(s, B, mod); Console.WriteLine(s + " を探す（ハッシュは " + hash2 + "）"); bool find = false; for (int i = 0; i < str.Length - s.Length + 1; i++) { long hash = GetHashFromTable(hashes, i, s.Length, B, mod); string judge = ""; if (hash == hash2) { judge = " => 一致"; find = true; } Console.WriteLine(str.Substring(i, s.Length) + " => " + hash + judge); } if(find) Console.WriteLine(s + " は 存在する"); else Console.WriteLine(s + " は 存在しない"); } } } |
実行結果
JavaScriptで実装する
JavaScriptでも実装してみることにします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
<!DOCTYPE html> <html lang="ja"> <head> <meta charset="UTF-8"> <title>鳩でもわかるローリングハッシュ</title> <meta name = "viewport" content = "width=device-width, initial-scale = 1.0"> </head> <body> <div id = "container"> <p>被検索文字列</p> <textarea rows = "4" cols = "32" id = "source"></textarea> <p>検索文字列（改行区切り）</p> <textarea rows = "6" cols = "32" id = "search-words"></textarea> <p>B:<input type="number" id = "B"></p> <p>mod:<input type="number" id = "mod"></p> <p><button onclick="search()">検索</button></p> <p>ここに計算結果が表示されます</p> <textarea rows = "6" cols = "32" id = "result"></textarea> </div> <script src= "./index.js"></script> </body> </html> |
定数を示します。
index.js
|
1 2 3 4 5 6 7 8 9 10 |
const $B = document.getElementById('B'); const $mod = document.getElementById('mod'); const $source = document.getElementById('source'); const $searchWords = document.getElementById('search-words'); const $result = document.getElementById('result'); window.onload = () => { $B.value = Math.pow(10, 8) + 7; $mod.value = Math.pow(10, 9) + 7; } |
ハッシュテーブルを生成する処理を示します。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
function createHashTable(str, B, mod){ const hashes = []; let hash = BigInt(str.charCodeAt(0)); hashes.push(hash); for (let i = 1; i < str.length; i++){ hash *= B; hash += BigInt(str.charCodeAt(i)); hash %= mod; hashes.push(hash); } return hashes; } |
ハッシュテーブルからハッシュを求める処理を示します。
|
1 2 3 4 5 6 7 8 9 10 11 |
function getHashFromTable(table, start, length, pows, mod){ const a = table[start + length - 1]; let b = 0; if(start - 1 >= 0) b = table[start - 1]; let ret = (BigInt(a) - BigInt(b) * pows[length]) % mod; if(ret < 0) // このとき ret が負数だと正しい値が取得できないので modを加算して正の数にする ret += mod; return ret; } |
ボタンがクリックされたら検索をおこないます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
function search(){ const B = BigInt($B.value); const mod = BigInt($mod.value); const str = $source.value; // ハッシュテーブルを生成 const table = createHashTable(str, B, mod) // ハッシュテーブルを表示 let result = ''; result = 'ハッシュテーブル\n'; for (let i = 1; i <= str.length; i++) result += str.substring(0, i) + '\t' + table[i-1] + '\n'; // 改行区切りで配列に変換して空白要素を取り除く let searchWords = $searchWords.value.split('\n'); searchWords = searchWords.filter(word => word != ''); // 事前に B ^ n % mod を計算するが、nの値は？ let maxLength = 1; for(let i = 0; i < searchWords.length; i++){ if(maxLength < searchWords[i].length) maxLength = searchWords[i].length; } // B ^ n % mod を計算する const pows = []; pows.length = maxLength + 1; let pow = BigInt(1); pows[0] = pow; for(let i = 1; i < maxLength; i++){ pow *= B; pow %= mod; pows[i] = pow; } // 文字列のなかからハッシュが一致する部分があるか調べる for(let num = 0; num < searchWords.length; num++){ // 検索しようとしている文字列のハッシュを求める const word = searchWords[num]; const hash2 = getHash(word, pows, mod); result += word + ' を探す（ハッシュは ' + hash2 + '）\n'; let find = false; for (let i = 0; i < str.length - word.length + 1; i++) { const hash = getHashFromTable(table, i, word.length, pows, mod); let judge = ''; // 一致する部分があるなら表示 if (hash == hash2) { judge = ' => 一致'; find = true; } result += str.substring(i, i + word.length) + ' => ' + hash + judge + '\n'; } // 検索結果を表示する if(find) result += word + ' は 存在する\n'; else result += word + ' は 存在しない\n'; } $result.value = result; } // 前回の記事（「ハッシュ関数とマークル木」）と同じ function getHash(str, pows, mod){ let hash = BigInt(0); for (let i = 0; i < str.length; i++){ hash += BigInt(str.charCodeAt(i)) * pows[str.length - 1 - i]; hash %= mod; } return hash; } |
