はじめに
文字列検索アルゴリズムを学ぶ機会があったので、自分用にまとめます.
私自身の勉強不足や思い込みのため説明には拙い部分や飛躍のほか誤りもが多々あると思われます.
記事中に示すコード例は C# で書いています.
文字列検索とは、例えば文字列 "abcabcabcabcdabc" の中から "abcd" を探すことを考えるようなものを指します.
この記事中では探される文字列(上の例で abcabcabcabcdabc の方)をテキスト、探す文字列(上の例で abcd の方)をパターンと呼ぶこととして、
文字列検索には
- テキストがパターンを含むか？
- 含むとして、テキストの中で初めてパターンが現れるのはどこか？
- パターンは全部で何度現れるか？
- パターンの出現位置を列挙すると？
のようにいくつかケースが考えられますが、この記事でのコード例は基本的に「テキストの中で初めてパターンが現れるのはどこか？」用で、
テキストがパターンを含まない場合は -1 を返すものとしています.
また、コード例中で文字列は一次元データであることを強調する目的で、char[] を使っています.
ナイーブな方法
0: 両者の左端を揃え、左端から比較していく -> 3文字目で不一致
111111
0123456789012345
abcabcabcabcdabc
abcd
---x
1: パターンをひとつ右にずらし、パターンの左端から比較していく -> 0文字目で不一致
111111
0123456789012345
abcabcabcabcdabc
abcd
x
2: パターンをひとつ右にずらし、パターンの左端から比較していく -> 0文字目で不一致
111111
0123456789012345
abcabcabcabcdabc
abcd
x
3: パターンをひとつ右にずらし、パターンの左端から比較していく -> 3文字目で不一致
111111
0123456789012345
abcabcabcabcdabc
abcd
---x
これを繰り返せば、
9: パターンをひとつ右にずらし、パターンの左端から比較していく -> すべて一致
111111
0123456789012345
abcabcabcabcdabc
abcd
----
となり、テキストの9文字目地点でパターンが現れると分かる.
この方法はプログラムで次のように書ける:
public static int NaiveFind(char[] pattern, char[] text) {
for(int i = 0; i <= text.Length - pattern.Length; ++i) {
bool found = true;
for(int j = 0; j < pattern.Length; ++j) {
if(text[i + j] != pattern[j]) {
found = false;
}
}// loop for j
if(found) return i;
}// loop for i
return -1;// Not found
}
このアルゴリズムは機能するが非効率である.
これを注意して見ると、例えば i+j が行きつ戻りつしていることが分かる.
今回の例では同じ i+j は高々2回しか現れないが、パターンを abcabcd にすれば3度まで同じ文字を参照することになるし、
テキストを aaaaaaaaaab (10個の a と ひとつの b)、パターンを aaac (みっつの a と ひとつの c) とすれば4度まで同じ文字を参照し計32回の文字比較を要する.
一度見たテキスト内の文字を何度も参照することは無駄が多く、これをなくす、あるいは減らすことによってアルゴリズムの改良を試みるのは自然な発想だろう.
Knuth-Morris-Pratt algorithm
なぜ前述の無駄な比較が現れるのかを考えてみよう.
111111
0123456789012345
text : abcabcabcabcdabc
pattern: abcd
ナイーブな方法では不一致を見つけたとき「パターンをひとつ右にずらす」ことによって検索を進める.
しかし、上の例では「パターンの3文字目までが一致している」とき、それを「ひとつ右にずら」しても決して一致しないことが分かる.
なぜなら、パターンをひとつずらしたとき比較されるのはパターンの1文字目とパターンの0文字目であると言え、このふたつは不一致だからだ.
なので、「パターンの3文字目までが一致している」とき、パターンは一気に3文字ずらすことができるはずだ.
pattern[k] はパターンを k 文字右にずらした状態を表すものとする
111111
0123456789012345
text : abcabcabcabcdabc
pattern[0]: abcd
pattern[3]: abcd // pattern[1]、pattern[2] を考えるまでもなくこれを考えれば十分
111111
0123456789012345
text : abc????????????? // 比較で一致した部分(=既知の部分)のみ
pattern[1]: abcd // pattern[0] のときに b で一致しているのだから、pattern[1] は明らかに不一致である.
pattern[2]: abcd // pattern[0] のときに c で一致しているのだから、pattern[2] は明らかに不一致である.
これを一般化して「パターンの k-1 文字目まで一致していることが分かっていて、k 文字目が不一致であった. このときパターンをいくつまでならずらしてよいか？」
というようなことを考察してアルゴリズムの効率化を図る. これが章題の Knuth-Morris-Pratt algorithm (略して KMP アルゴリズムとも) である.
パターンを abcabcd に変えて考えてみよう:
pattern[k] はパターンを k 文字右にずらした状態を表すものとする
111111
0123456789012345
text : abcabcabcabcdabc
pattern[0]: abcabcd
最初の比較ではパターンの6文字目が不一致となるが、安直に6文字ずらすことはできない.
なぜなら、パターンの 0-2 文字目(「abc」abcd) とパターンの 3-5 文字目(abc「abc」d)が一致しているからだ.
そこで、パターンの6文字目の比較で不一致となったとき、パターンの 3-5 文字目があったところにパターンの 0-2 文字目が重なるように移動する.
ただし、ずらした後の 0-2 文字目は text に一致することが分かっているため、パターンの3文字目から比較を開始すればよい.
pattern[k] はパターンを k 文字右にずらした状態を表すものとする
111111
0123456789012345
text : abcabcabcabcdabc
pattern[0]: abcabcd
pattern[3]: abcabcd
---^ // ハイフン部分は比較しなくてよい(pattern[0] の時に調べてそこが一致することは分かっているため).
// なのでキャレット部分からの比較だけで検索を進められる.
最終的に先に挙げた問題は次のように改められる:「パターンの k-1 文字目まで一致していることが分かっていて、k 文字目が不一致であった. このときパターンをいくつまでならずらしてよいか？ また、パターンの何文字目から比較を再開すればよいか？」.
これに対する回答は「パターンの[先頭から k-1 文字目まで]と[m 文字目以降から k-1 文字目まで]、ふたつのサブ文字列に共通する先頭の文字数を c := k-m とする(m > 0). このとき、m 文字ずらすことができ、c 文字目から比較をすればよい」である.
| k | k-1 文字目まで | m | m 文字目以降から k-1 文字目まで | 共通する文字列の長さ | 補足 |
|---|---|---|---|---|---|
| 0 | - | 1 | - | - | k-1 文字目までと言うのが定義できない |
| 1 | a | 1 | - | 0 | m=1 文字目から k-1=0 文字目と言うのが定義できない |
| 2 | ab | 1 | - | 0 | ab と b(m=1) の共通部分は空である |
| 3 | abc | 1 | c | 0 | 共通部分は空 |
| 2 | bc | 0 | 共通部分は空 | ||
| 4 | abca | 1 | bca | 0 | 共通部分は空 |
| 2 | ca | 0 | 共通部分は空 | ||
| 3 | a | 1 | abca と a(m=3) の共通部分は a であり k = 4 において最長であるからこれが m,c となる | ||
| 5 | abcab | 1 | bcab | 0 | 共通部分は空 |
| 2 | cab | 0 | 共通部分は空 | ||
| 3 | ab | 2 | abcab と ab(m=3) の共通部分は ab であり k = 3 において最長であるからこれが m,c となる | ||
| 4 | b | 0 | 共通部分は空 | ||
| 6 | abcabc | 1 | bcabc | 0 | 共通部分は空 |
| 2 | cabc | 0 | 共通部分は空 | ||
| 3 | abc | 3 | abcabc と abc(m=3) の共通部分は abc であり k = 6 において最長であるからこれが m,c となる | ||
| 4 | bc | 0 | 共通部分は空 | ||
| 5 | c | 0 | 共通部分は空 |
KMP アルゴリズムはこの k, m, c に関する表を作成する手間があるものの、実際の比較が速くなる.
以下に Wikipedia にある擬似コードから起こした実装を示す:
public static int KmpFind(char[] pattern, char[] text) {
// table[k] := 上の説明中の c. m は k - c = k - table[k] で求められる.
int[] table = ConstructKmpTable(pattern);
int i = 0; int j = 0;
int k = 0;
while (i + j < text.Length) {
if (text[i + j] == pattern[j]) {
// text と pattern で一致すれば pattern の次の文字比較に移る
++j;
// パターンの全てが一致すれば終了
if (j == pattern.Length) return i;
} else {
// 不一致があれば m 文字ずらすことができる(パターンの0文字目で失敗したときは1文字だけずらす. table[0] = -1 としているため分岐不要)
i += j - table[j];
// 不一致のときパターンの c 文字目からの比較だけでよい(パターンの0文字目で失敗したときは0文字目から比較する. table[0] = -1 としているため分岐している)
if (j > 0) j = table[j];
}
}
return -1;// Not found
}// KmpFind(char[] pattern, char[] text)
private static int[] ConstructKmpTable(char[] pattern) {
// table[k] := 上の説明中の c
// m は k - c = k - table[k] で求められる.
int[] table = new int[pattern.Length];
// 実際は pattern.Length >= 2 であることを確かめてから以下の処理をするべきだが説明用なので省略
table[0] = -1;// k = 0 のとき k-1 文字目までというのが定義できないため c を定められないが、ここでは -1 として処理を書いている
table[1] = 0;// 上の表で説明した通り、k = 1 のとき c を定めることはできないが、0 とすれば都合がよい
int k = 2; int j = 0;
while (k < pattern.Length) {
if (pattern[k - 1] == pattern[j]) table[k++] = ++j;
else if (j > 0) j = table[j];
else table[k++] = 0;
}
return table;
}// ConstructKmpTable(char[] pattern)
Boyer-Moore algorithm
KMP では「パターンの何文字目で失敗したか？」だけを用いてずらし幅を決定していたが、比較に失敗した場合他にも使える情報がある. 失敗したときのテキストの文字だ.
パターンが a, b, c 3種類の文字しか含んでいないとき、テキスト内に d を見つけたとする. この d はパターンのどの位置でも不一致であるから、テキスト上 d の次の文字にパターンの左端を合わせることができる:
※これ自体はボイヤームーアのアルゴリズムではない
pattern[k] はパターンを k 文字右にずらした状態を表すものとする
111111
0123456789012345
text : abcabcdabcabcdab
pattern[0]: abcabcabc
pattern[6]: abcabcabc // テキストの 6 文字目は d であり、パターンに含まれていないから一気に6文字ずらしてよい
cf:KMPの場合
111111
0123456789012345
text : abcabcdabcabcdab
pattern[0]: abcabcabc
pattern[3]: abcabcabc // パターンの6文字目で失敗したので3文字ずらし、3文字目から比較を再開する
---^
上の例ではパターンの前方から比較しているが、失敗した際テキスト側の文字を参照できるなら後ろから比較していく方が効率的である
※これ自体はボイヤームーアのアルゴリズムではない
pattern[k] はパターンを k 文字右にずらした状態を表すものとする
o は文字が一致したことを、x は不一致であったことを表すものとする
// 前方から比較していく場合
111111
0123456789012345
text : abcabcdabcabcdab
pattern[0]: abcabcabc
oooooox
pattern[6]: abcabcabc // テキストの 6 文字目は d であり、パターンに含まれていないから一気に6文字ずらしてよい
oooooox
pattern[13]: abcabcabc // テキストの右端をはみ出したので、パターンが含まれていないことが分かる
この例では14回文字を比較している
// 後方から比較していく場合
111111
0123456789012345
text : abcabcdabcabcdab
pattern[0]: abcabcabc
x
pattern[1]: abcabcabc // テキストの 8 文字目は b であり、パターンの 7 文字目も b なのでそれらが重なるように移動する
xooo
pattern[6]: abcabcabc // テキストの 6 文字目は d であり、パターンに含まれていないから一気に5文字ずらしてよい
x
pattern[7]: abcabcabc // テキストの 15 文字目は b であり、パターンの 7 文字目も b なのでそれらが重なるように移動する
x // テキストの右端をはみ出したので、パターンが含まれていないことが分かる
この例では7回文字を比較している
上の例のように、前方から比較していくとテキストのすべての文字をなめることになるのに対して、
後方からの比較ではテキストの一部について参照するまでもなく候補から外していくことができる.
以上から文字列検索アルゴリズムを組み上げたものが Boyer-Moore algorithm (BM algorithm とも. Boyerさん、Mooreさんの二人組は他に Boyer-Moore majority vote algorithm と呼ばれるものも考案しているため、こちらは Boyer-Moore string searching algorithm と呼ぶ方が正確？)
特徴としては以下のようになる
- パターンは後方から比較していく
- 比較に失敗した場合テキストの文字が何であるかを参照する(Bad character rule、不一致文字規則)
- KMP と同様に、パターン内で繰り返しがある場合そこが重なるようなずらし量を考える(Good suffix rule、一致接尾辞規則)
- Bad character rule と Good suffix rule の内ずらし量が大きい方を採用する
以下に Wikipedia にある Java コードから起こした実装を示す:
public static int BmFind(char[] pattern, char[] text) {
// 不一致文字規則用のずらし量
// charTable[ch] := pattern 内で ch が初めて現れる位置, pattern に含まれないものは pattern.Length 番目であると考える
// Wikipedia では配列となっているが、日本語などを扱う場合を考えると連想配列の方が扱いやすいと思われる
Dictionary<char, int> charTable = ConstructBmCharTable(pattern);
// 一致接尾辞規則用のずらし量
int[] offsetTable = ConstructBmOffsetTable(pattern);
// 検索を実行する
for (int i = pattern.Length - 1, j; i < text.Length;) {
for (j = pattern.Length - 1; pattern[j] == text[i]; --i, --j) {
if (j == 0) return i;
}
// Dictionary.TryGetValue(K, out V) は幅を取るので、GetOrDefault(K key, V defaultValue) みたいな拡張メソッドを用意すべきかも
i += Math.Max(offsetTable[pattern.Length - 1 - j], charTable.TryGetValue(text[i], out int value) ? value : pattern.Length);
}
return -1;
}// BmFind(char[] pattern, char[] text)
private static Dictionary<char, int> ConstructBmCharTable(char[] pattern) {
// table[ch] := pattern 内で ch が初めて現れる位置
Dictionary<char, int> table = new();
for (int i = 0; i < pattern.Length; ++i) {
table[pattern[i]] = pattern.Length - 1 - i;
}
return table;
}// ConstructBmCharTable(char[] pattern)
private static int[] ConstructBmOffsetTable(char[] pattern) {
int n = pattern.Length;
int[] table = new int[n];
int lastPrefixPosition = n;
for (int i = n - 1; i >= 0; --i) {
if (IsPrefix(pattern, i + 1)) {
lastPrefixPosition = i + 1;
}
table[n - 1 - i] = lastPrefixPosition + n - 1 - i;
}
for (int i = 0; i < n - 1; ++i) {
int sl = SuffixLength(pattern, i);
table[sl] = sl + n - 1 - i;
}
return table;
}// ConstructBmOffsetTable(char[] pattern)
private static bool IsPrefix(char[] pattern, int pos) {
// is pattern[pos .. ] a prefix of pattern?
for (int i = pos, j = 0; i < pattern.Length; ++i, ++j) {
if (pattern[i] != pattern[j]) return false;
}
return true;
}// IsPrefix(char[] pattern, int pos)
private static int SuffixLength(char[] pattern, int pos) {
// length of common suffix between pattern[ .. pos] and pattern[ .. ]
int len = 0;
for (int i = pos, j = pattern.Length - 1; i >= 0 && pattern[i] == pattern[j]; --i, --j) {
++len;
}
return len;
}// SuffixLength(char[] pattern, int pos)
ボイヤームーアのアルゴリズムはコンセプトが単純であることもあり派生が多い.
有名なものとして、改良された不一致文字規則を適用する (Boyer-Moore-)Horspool algorithm(BMH) と、
BMH の不一致文字規則で参照する文字の位置をひとつずらした (Sunday's) quick search algorithm がある.
それぞれの改良点は些細にも見えるようなものだが、BM の発表(1977年)から BMH の発表(1980年)までが3年.
そこから Sunday さんの発表(1990年)まで10年も要したというのだから、案外他のアルゴリズムについても些細な改良で大きく性能を改善する余地があるのかもしれない.
Suffix array を用いた方法
上述のふたつ(KMP、BM) は比較に失敗した際のずらし量を大きくするものだったが、別のアプローチも考えられる.
文字列の「検索」という部分に着目すると、テキスト "abcabcabcabcdabc" の中から パターン "abcd" を探す問題は、
次の表から指定されたパターンで始まる文字列を探す問題だと書き換えられる.
| k | テキストの k 文字目以降 |
|---|---|
| 0 | abcabcabcabcdabc |
| 1 | bcabcabcabcdabc |
| 2 | cabcabcabcdabc |
| 3 | abcabcabcdabc |
| 4 | bcabcabcdabc |
| 5 | cabcabcdabc |
| 6 | abcabcdabc |
| 7 | bcabcdabc |
| 8 | cabcdabc |
| 9 | abcdabc |
| 10 | bcdabc |
| 11 | cdabc |
| 12 | dabc |
| 13 | abc |
| 14 | bc |
| 15 | c |
このような一次元配列から特定の一点を発見する問題だと考えれば、二分探索を使おうとするのは自然な発想だろう.
つまり、まず上の表を辞書順にソートして以下のようにする.
| インデックス | k | テキストの k 文字目以降 |
|---|---|---|
| 0 | 13 | abc |
| 1 | 0 | abcabcabcabcdabc |
| 2 | 3 | abcabcabcdabc |
| 3 | 6 | abcabcdabc |
| 4 | 8 | abcdabc |
| 5 | 14 | bc |
| 6 | 1 | bcabcabcabcdabc |
| 7 | 4 | bcabcabcdabc |
| 8 | 7 | bcabcdabc |
| 9 | 10 | bcdabc |
| 10 | 15 | c |
| 11 | 2 | cabcabcabcdabc |
| 12 | 5 | cabcabcdabc |
| 13 | 9 | cabcdabc |
| 14 | 11 | cdabc |
| 15 | 12 | dabc |
そうしてから二分探索を行うと、
インデックス= (0+15)/2 = 7 の文字列とパターンを比較すれば、[bcabcabcdabc の先頭] > abcd
インデックス= (0+6)/2 = 3 の文字列とパターンを比較すれば、[abcabcdabc の先頭] < abcd
インデックス= (4+6)/2 = 5 の文字列とパターンを比較すれば、[bc の先頭] > abcd
インデックス= (4+4)/2 = 4 の文字列とパターンを比較すれば、[abcdabc の先頭] == abcd
によってテキストがパターンを含んでいると分かる. この k についての配列を Suffix array(接尾辞配列)と呼ぶ.
注意しなければならない点として、この表のソートのためにいちいち文字列比較をしていては前処理が重くなりすぎてしまうことが挙げられる.
単純なアイデアとしては、基数ソート(MSD)のような、一文字ずつだけ比較していくソート方法が浮かぶだろう.
より特化した方法として、蟻本(p.336)に説明されている Manber-Myers algorithm や SA-IS 法と呼ばれるものが存在するが、ここでは文字列検索アルゴリズムのコンセプト紹介がしたいだけなので、基数ソートによる構成をコード例として示す.
public static int SuffixArrayFind(char[] pattern, char[] text) {
// 接尾辞配列を作成する
int[] suffixArray = ConstructSuffixArray(text);
// 単純な二分探索
int lo = 0;
int hi = suffixArray.Length - 1;
while(lo <= hi) {
int mid = lo + (hi - lo) / 2;
int k = suffixArray[mid];
int c = ComparePartialString(pattern, text, k);
if(c > 0) {
lo = mid + 1;
} else if(c < 0) {
hi = mid - 1;
} else /* if(c == 0) */ {
// 一致する部分を発見した時点で処理を終了する
// この実装ではこれがテキスト中最初の出現であることは保証されない
return k;
}
}
return -1;
}
private static int[] ConstructSuffixArray(char[] text) {
// 接尾辞配列を作成する
int[] arr = new int[text.Length];
for (int i = 0; i < text.Length; ++i) arr[i] = i;
MsdSortForSuffixArray(arr, text, 0, arr.Length - 1, 0);
return arr;
}
private static void MsdSortForSuffixArray(int[] arr, char[] text, int lo, int hi, int digit) {
// 基数ソート. とりあえず動きはする、程度の実装.
// マルチキークイックソートを使うべきかも.
// 特にこの例のように、作った接尾辞配列を使い捨てて一種類のパターンを検索するだけならば、
// quick select よろしく pattern[digit] をピボットにして一致した範囲だけを追いかけていけばそれが検索処理になりそう
if (lo >= hi) return;
if (digit >= text.Length) return;
// text[arr[k]..][digit] によってソートする
Array.Sort(arr, lo, hi - lo + 1, Comparer<int>.Create((lhs, rhs) => CharAt(lhs + digit, text).CompareTo(CharAt(rhs + digit, text))));
// 再帰的に text[arr[k]..][digit+1] によるソートを行う
int newLo = lo;
char ch = CharAt(arr[lo] + digit, text);
for (int i = lo + 1; i <= hi; ++i) {
char ch1 = CharAt(arr[i] + digit, text);
if (ch != ch1) {
MsdSortForSuffixArray(arr, text, newLo, i - 1, digit + 1);
newLo = i;
ch = ch1;
}
}
MsdSortForSuffixArray(arr, text, newLo, hi, digit + 1);
}
private static char CharAt(int pos, char[] text) {
// text[pos]、範囲外ならば '\0'
return pos < text.Length ? text[pos] : char.MinValue;
}
private static int ComparePartialString(char[] pattern, char[] text, int pos) {
// text の k 文字目から k + pattern.Length 文字目までと pattern 全体を比較する
int m = pattern.Length;
int j = pos;
for (int i = 0; i < m; ++i) {
// テキストの末端に達したなら、pattern > text[pos..]
if (j >= text.Length) return 1;
else if (pattern[i] > text[j]) return 1;
else if (pattern[i] < text[j]) return -1;
else ++j;
}
// パターンの末尾に達したならば一致したと言える
return 0;
}
上の実装では ComparePartialString で毎回パターン全体を使って文字列比較を行っているが、この文字の比較回数は減らすことができる.
例えば以下のような接尾辞配列が与えられ cccccacc を探すことを考えよう:
| インデックス | k | テキストの k 文字目以降 |
|---|---|---|
| 0 | 0 | acccccccacccccccb |
| 1 | 8 | acccccccb |
| 2 | 16 | b |
| 3 | 7 | cacccccccb |
| 4 | 15 | cb |
| 5 | 6 | ccacccccccb |
| 6 | 14 | ccb |
| 7 | 5 | cccacccccccb |
| 8 | 13 | cccb |
| 9 | 4 | ccccacccccccb |
| 10 | 12 | ccccb |
| 11 | 3 | cccccacccccccb |
| 12 | 11 | cccccb |
| 13 | 2 | ccccccacccccccb |
| 14 | 10 | ccccccb |
| 15 | 1 | cccccccacccccccb |
| 16 | 9 | cccccccb |
インデックス= (0+16)/2 = 8 の文字列とパターンを比較すれば、[cccb の先頭] < cccccacc (2文字目までは一致し、3文字目が b < c)
インデックス= (9+16)/2 = 12 の文字列とパターンを比較すれば、[cccccb の先頭] > cccccacc (4文字目までは一致し、5文字目が b > a)
インデックス= (9+11)/2 = 10 の文字列とパターンを比較すれば、[ccccb の先頭] < cccccacc (3文字目までは一致し、4文字目が b < c)
インデックス= (11+11)/2 = 11 の文字列とパターンを比較すれば、[cccccacccccccb の先頭] == cccccacc
のようにして目的のパターンを発見することになるが、最初に比較した[cccb の先頭]とパターンは3文字が一致しており、
かつ次の[cccccb の先頭]と[cccb の先頭]は3文字が一致している.
この情報を用いれば[cccccb の先頭]とパターンの比較は3文字目以降についてだけ比較すれば良いことが分かるだろう.
先頭の一致している部分は LCP(Longest Common Prefix) と呼ばれる.
接尾辞配列に加えて、各接尾辞の先頭が何文字まで一致しているかを保持すると次のような表が作成できる:
| インデックス | k | テキストの k 文字目以降 | 辞書順でひとつ前にある文字列との LCP の長さ |
|---|---|---|---|
| 0 | 0 | acccccccacccccccb | - |
| 1 | 8 | acccccccb | 1 |
| 2 | 16 | b | 0 |
| 3 | 7 | cacccccccb | 0 |
| 4 | 15 | cb | 1 |
| 5 | 6 | ccacccccccb | 1 |
| 6 | 14 | ccb | 2 |
| 7 | 5 | cccacccccccb | 2 |
| 8 | 13 | cccb | 3 |
| 9 | 4 | ccccacccccccb | 3 |
| 10 | 12 | ccccb | 4 |
| 11 | 3 | cccccacccccccb | 4 |
| 12 | 11 | cccccb | 5 |
| 13 | 2 | ccccccacccccccb | 5 |
| 14 | 10 | ccccccb | 6 |
| 15 | 1 | cccccccacccccccb | 6 |
| 16 | 9 | cccccccb | 7 |
この表からインデックス=8 の文字列(cccb)とインデックス=12 の文字列(cccccb)の先頭何文字が一致しているかは、
インデックス=8+1=9 の行からインデックス=12 の行までの LCP の最小値によって求められる.
なのでこの LCP を有効に活用したい場合は RMQ(Range Minimum Query) が処理できるデータ構造(e.g. セグメントツリー)が必要となる.
またこの LCP 配列の構築自体についても単純に比較していては高速化に繋がらないため、Kasai's algorithm のような特別の方法が使われる.
Rabin-Karp algorithm
KMP や BM はパターンについて前処理を施し、テキストの比較するまでもなく不一致であると分かる部分をスキップする方法であった.
Suffix Array ではテキストについて前処理を施し、二分探索を使うことで不要な比較を削り落とすものであった.
ここで紹介する Rabin-Karp algorithm はどちらとも異なるアプローチを取る. 文字列の比較そのものが重たい処理であると考えるのだ.
文字列の比較が O(1) で行えるならば、文字列検索はただの線形探索となり、テキストの長さを n として O(n) で終了する.
Rabin-Karp algorithm ではこれを実現するため、文字列の比較にローリングハッシュを使用する.
ローリングハッシュの説明
hash := ハッシュ関数として、文字列 "cake" をハッシュ化したものを hash(cake) で表すものとする.
ハッシュの計算には基数と除数(互いに素)ふたつの数値を必要とするため、基数として 7, 除数として 125 を例に用いる.
キャレット(^)は累乗を表すものとする.
簡単のため、小文字アルファベットのみを使うこととして、各文字はアルファベット順に数値化されるものとする:
11111111112222222
12345678901234567890123456
abcdefghijklmnopqrstuvwxyz
例として hash(a) = 1, hash(m) = 13, hash(u) = 21 のようにマッピングされる.
計算式だと(私が)分かりにくいため、テキスト mycakeisdelicious からパターン cake を探す場合を手計算する
0. hash(cake) の計算:
hash(cake) = ( hash(c) * 7^3
+ hash(a) * 7^2
+ hash(k) * 7^1
+ hash(e) * 7^0 ) mod 125
= ( 3 * 343
+ 1 * 49
+ 11 * 7
+ 5 * 1 ) mod 125
= 1160 mod 125
= 35
1. テキストの 0 文字目から4文字(=パターンの文字数と同じ)をハッシュ化する:
hash(myca) = ( hash(m) * 7^3
+ hash(y) * 7^2
+ hash(c) * 7^1
+ hash(a) * 7^0 ) mod 125
= ( 13 * 343
+ 25 * 49
+ 3 * 7
+ 1 * 1 ) mod 125
= 5706 mod 125
= 81
2. hash(cake) と hash(myca) を比較する:
hash(cake) = 35 != 81 = hash(myca) であるから、これは不一致であると分かる
3. テキストの 1 文字目から4文字をハッシュ化する:
ここで手順 1 と同様に計算してもよいのだが、hash(myca) と3文字分重複しているのだから、それを上手く活用する.
hash(myca) = ( hash(m) * 7^3
+ hash(y) * 7^2
+ hash(c) * 7^1
+ hash(a) * 7^0 ) mod 125
hash(ycak) = ( hash(y) * 7^3
+ hash(c) * 7^2
+ hash(a) * 7^1
+ hash(k) * 7^0 ) mod 125
のふたつを見比べ上手く変形していく(冗長なので mod 125 は省略して示す)
直感的に、hash(myca) から hash(m) 成分を抜き去り hash(k) 成分を足してやればよいと見当がつく.
hash(myca) = hash(m) * 7^3
+ ( hash(y) * 7^2
+ hash(c) * 7^1
+ hash(a) * 7^0 )
hash(ycak) = ( hash(y) * 7^2
+ hash(c) * 7^1
+ hash(a) * 7^0 ) * 7
+ hash(k) * 7^0
共通している ( hash(y) * 7^2 + hash(c) * 7^1 + hash(a) * 7^0 ) を alpha と置けば
hash(myca) = hash(m) * 7^3 + alpha
=> alpha = hash(myca) - hash(m) * 7^3
hash(ycak) = alpha * 7 + hash(k) * 7^0
より、
hash(ycak) = (hash(myca) - hash(m) * 7^3) * 7 + hash(k) * 7^0
= hash(myca) * 7 - hash(m) * 7^4 + hash(k)
となり、はじめから hash(ycak) を計算しなおさずに値が得られる.
加えて、文字列の長さによらず定数時間で次の範囲のハッシュ値を求められる.
実際に計算すると、
hash(ycak) = (hash(myca) * 7 - hash(m) * 7^4 + hash(k)) mod 125
= (81 * 7 - 13 * 26 + 11) mod 125 // 7^4 = 2401 ≡ 26 mod 125
= 240 mod 125
= 115
4. hash(cake) と hash(ycak) を比較する:
hash(cake) = 35 != 115 = hash(ycak) であるから、これは不一致であると分かる
5. テキストの 2 文字目から4文字をハッシュ化する:
手順 3 と同様に計算する.
hash(cake) = (hash(ycak) * 7 - hash(y) * 7^4 + hash(e)) mod 125
= 35 // 途中式略
6. hash(cake) と hash(cake) を比較する:
hash(cake) = 35 == 35 = hash(cake) であるから、これは一致している確率が高いと言える(まだハッシュ値が同じになることしか確かめられていない点に注意)
7. 実際に「パターン」と「テキストの 2 文字目から4文字」を比較する:
パターン(cake)とテキストの一部(cake) は文字列として一致することを確かめることによって、テキストがパターンを含んでいることが分かった
以下にコード例を示す:
public static int RabinKarpFind2(char[] pattern, char[] text) {
int n = text.Length;
int m = pattern.Length;
// パターンの方が長ければ明らかに不一致
if (n < m) return -1;
// 実際はハッシュの衝突を避けるためにより大きな d を使うべき
const int b = 7;// 基数
const int d = 125;// 除数
// pow := b^m mod d
int pow = 1;
for (int i = 0; i < m; ++i) { pow *= b; pow %= d; }
// hp := hash(pattern)
// ht := hash(text[0 .. m))
int hp = 0;
int ht = 0;
for (int i = 0; i < m; ++i) {
hp *= b; hp += pattern[i]; hp %= d;
ht *= b; ht += text[i]; ht %= d;
}
// 実際の探索処理
// for (int i = 0; i <= n - m; ++i) としてもよいのだが、
// 結局ハッシュの更新は条件(i < n - m)を満たしていなければならないので、ここでは true にしている
for (int i = 0; true; ++i) {
if (hp == ht) {
// ハッシュが一致したので実際に pattern と text[i .. i+m) を比較する
// ハッシュの性能を信じるのであればここで比較しなくともよいが、
// 厳密には衝突の可能性があるためハッシュが一致しただけでは文字列として一致したとは断言できない
// 蟻本 p.332 に示されている例では(競技プログラミングという特殊な目的のため)この比較を行っていない
bool matched = true;
for (int j = 0; j < m; ++j) {
if (pattern[j] != text[i + j]) {
matched = false;
break;
}
}
if (matched) return i;
}
// テキストの終端に達した場合は不一致
if (i == n - m) return -1;
// ハッシュを更新する
// 現在の hp は text[i .. i+m) のもの
// 新しいハッシュは text(i .. i+m] のもの
int newHash = ht * b - text[i] * pow + text[i + m];
// 単に hp = newHash % d とすると、newHash が負の場合に機能しない
ht = (int) (newHash - Math.Floor((double) newHash / d) * d);
}
}
Bitap アルゴリズム
Bitap は bit 演算を活用した approximate search (あいまい検索) のためのアルゴリズムなので、
完全一致の場合は別の名前(shift-and algorithm)を使うべきかもしれないが、ここでは完全一致検索の場合でも気にせず Bitap と呼ぶこととする.
KMP や BM では、「テキストの k 文字目とパターンの頭文字の位置を合わせてから、パターンの各文字についてカーソルを動かしていく」というスタイルで探索を進めていた.
一方 Bitap では反対に、「テキストの k 文字目と、パターンのあらゆる位置を合わせる. そして、テキストの各文字についてカーソルを動かしていく」と解釈できる.
例:
pattern[k] はパターンを k 文字右にずらした状態を表すものとする
カーソル位置=0
V
111111
0123456789012345
text : abcabcabcabcdabc
pattern[0]: abcd // カーソル位置の文字が一致しているため、pattern[0] は一致候補として残る
カーソル位置=1
V
111111
0123456789012345
text : abcabcabcabcdabc
pattern[0]: abcd // カーソル位置の文字が一致しているため、pattern[0] は一致候補として残る
pattern[1]: abcd // カーソル位置の文字が不一致であるから、pattern[1] は一致候補から外れる
カーソル位置=2
V
111111
0123456789012345
text : abcabcabcabcdabc
pattern[0]: abcd // カーソル位置の文字が一致しているため、pattern[0] は一致候補として残る
pattern[2]: abcd // カーソル位置の文字が不一致であるから、pattern[2] は一致候補から外れる
カーソル位置=3
V
111111
0123456789012345
text : abcabcabcabcdabc
pattern[0]: abcd // カーソル位置の文字が不一致であるから、pattern[0] は一致候補から外れる
pattern[3]: abcd // カーソル位置の文字が一致しているため、pattern[3] は一致候補として残る
カーソル位置=4
V
111111
0123456789012345
text : abcabcabcabcdabc
pattern[3]: abcd // カーソル位置の文字が一致しているため、pattern[3] は一致候補として残る
pattern[4]: abcd // カーソル位置の文字が不一致であるから、pattern[4] は一致候補から外れる
<中略>
カーソル位置=11
V
111111
0123456789012345
text : abcabcabcabcdabc
pattern[ 9]: abcd // カーソル位置の文字が一致しているため、pattern[9] は一致候補として残る
pattern[11]: abcd // カーソル位置の文字が不一致であるから、pattern[11] は一致候補から外れる
カーソル位置=12
V
111111
0123456789012345
text : abcabcabcabcdabc
pattern[ 9]: abcd // カーソル位置の文字が一致しているため、pattern[9] は一致候補として残る. そしてカーソル位置がパターンの終端であるから、完全一致したと言える.
pattern[12]: abcd // カーソル位置の文字が不一致であるから、pattern[12] は一致候補から外れる
Bitap では上記の処理を、bit 演算を巧みに用いて実行する.
public static int BitapFind(char[] pattern, char[] text) {
// ここではビット列の保持に uint を用いるため、それ以上に長いパターンは扱えない
if (pattern.Length > 31) throw new ArgumentException("Too long", nameof(pattern));
// pattern をビットマスクに変換する
Dictionary<char, uint> masks = new();
for (int i = 0; i < pattern.Length; ++i) {
// java の Map#compute のような処理を拡張メソッドとして用意すべきかも
char ch = pattern[i];
uint mask = masks.TryGetValue(ch, out uint val) ? val : 0u;
mask |= 1u << i;
masks[ch] = mask;
}
uint finish = 1u << (pattern.Length - 1);
// 実際の検索処理
// state := 現在残っている一致候補
uint state = 0u;
for (int i = 0; i < text.Length; ++i) {
// java の Map#getOrDefault のような処理を拡張メソッドとして用意すべきかも
// state << 1 でカーソルをひとつ進める
// | 1u が「そのカーソル位置がパターンの左端であるようなケース」に相当する
// & masks... はカーソル位置で文字が一致するパターンだけを一致候補としてふるいにかける.
state = (state << 1 | 1u) & (masks.TryGetValue(text[i], out uint val) ? val : 0u);
// 終端位置まで届いたものがあれば一致したと言える
if ((state & finish) == finish) return i - pattern.Length + 1;
}
return -1;
}
参考にしたサイトなど
- 『プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～』
- いわゆる蟻本. ローリングハッシュと接尾辞配列が説明されています.
-
Wikipedia
- 言わずと知れた大百科.
-
EXACT STRING MATCHING ALGORITHMS
- この記事で扱わなかったものも含めて色々な文字列検索アルゴリズムが紹介されています.
- Fussy's HOMEPAGE 様 > 文字列の検索 -2-
- Boyer-Moore とその派生について書かれています. (文字列の検索 -1- のページには KMP もあります)