目次
文書の過去の版を表示しています。
文字列アルゴリズム
文字列検索アルゴリズム
文字列 $S$ から文字列 $T$ を検索する手法あれこれ。
ただ使うだけなら、1対1のString型の検索であれば、下手に自力実装するよりfind()
など組み込み関数を使った方が一般的には高速となる。
$S$ や $T$ が複数あるのを事前計算で高速化したり、数列を文字列と見なして一致する連続箇所を検索する場合などに、以下のアルゴリズムが有用となる。
愚直(Brute Force)
まずは基本。マッチ位置 $i$ を1つずつずらして、そこから各 $j$ 文字目が一致するか照合していく。
S ABCDEABCF T ABCF ABCF ABCF
一般的な(言語上意味のある)文字列であればほとんど1文字目で失敗するので、愚直といえどほぼ $O(|S|)$ で済むが、 同じ文字が多く出現する特殊な場合は、最悪 $O(|S||T|)$ かかる。
KMP法
1対1の検索アルゴリズム。
$T$ から「$j$ 文字目で照合失敗したら次のマッチ位置は何文字飛ばせるか」テーブルを事前に作っておく。
j 012345 0 1 2 3 4 5 T ABCABD → Tbl: [-1, 0, 0, 0, 1, 2]
たとえば $j=5$ 文字目の'D
'で失敗したら、次のマッチ位置では既に'AB'が一致していることが分かるので、2文字飛ばせることを示す。
S ABCABCABD T ABCABD ^^^^^x ここで失敗 (i=0, j=5) S ABCABCABD T ABCABD ここまでずらせる (i ← i+j-Tbl[j], j ← Tbl[j]) ^^^^ さらに'AB'を飛ばして'C'から探索開始すればいい
Tbl[0] = -1
となっているのは便宜的なもので、$j=0$ 文字目で失敗した際に次のマッチ位置を1つ進めるため。
(基本的に照合失敗したら $T$ をずらして、失敗した $S$ 側の文字はもう一度 $T$ と照合されるが、$j=0$ の場合のみ、$S$ 側の文字も進める必要がある)
計算量は、テーブル作成 $O(|T|)$、探索 $O(|S|)$ で行える。
Boyer-Moore 法
1対1の検索アルゴリズム。
KMP法同様、マッチ位置をスキップしつつずらしていくのだが、文字の照合は後ろからおこなうのが特徴。 これにより一般的な文字列検索ではスキップできる期待値が大きくなり、高速なため実用上よく使われている。 だが、同じ文字が多く出現するケースでは遅く、それを解決しようとすると実装が煩雑になる。
あらかじめ $T$ からテーブルを作成する。 ただ、テーブルの作り方も複数あって、「不一致文字規則」「一致suffix規則」「両方計算してスキップできる距離の大きい方」が存在する。 不一致文字規則は実装は簡単だが、文字の種類が少ない場合に効果が少ない。一致suffix規則はちょっと複雑。
不一致文字規則の例 S ...ABCDEFGH... T CACABD x^ 末尾から2番目で照合失敗、失敗時のS側の文字は'C' S ...AB[C]DEFGH... T CA[C]ABD 失敗位置より左にはじめて出現する'C'までは飛ばせる([]を合わせる感じ) x 再度末尾から検索するが、1番目で一致しない S ...ABCDEFGH... T CACABD 'F'はTに出現しないので、丸ごと飛ばせる
一般的な意味のある文字列では、ほぼ $|T|$ ずつ枠が移動し、 $O(\frac{|S|}{|T|})$ となる。
一方、$S$ や $T$ に同じ文字や並びが何度も出現する場合はスキップが有効に働かず、最悪 $O(|S||T|)$ となる。
Horspoolのアルゴリズム、Sundayのアルゴリズムでは、不一致となったときに参照する文字を変えることで、実用上の平均計算時間が改善する。
線形時間を保証するには、移動量テーブル作成時、「不一致となった所までは一致していた」という情報を使う Galil 規則というものを導入すればよい。
Rabin-Karp法(ローリングハッシュ)
一定の長さの文字列をハッシュ化して1つの数字にした上で、ハッシュ値で検索するアルゴリズム。
計算量
ハッシュ化に $O(|S|+|T|)$、検索に $O(|S|)$
概要
KMP・BM法がマッチ位置を試す数を減らして高速化するのに対し、こちらは特定のマッチ位置における文字同士の照合を高速化する。
事前計算として、$S$ から開始位置を1つずつずらしたハッシュ列 $S'$ を作成しておく。 $T$ も全体のハッシュ値 $T'$ を求める。 すると検索は、数列 $S'$ から1つの数字 $T'$ を探す処理になる。
$T$ が複数ある場合、長さが同じであれば、$S'$ を共有できる。
ハッシュの計算には、1つ前の値から次のハッシュ値を高速に計算できる「ローリングハッシュ」を用いる。 整数 $X$ と $M$ を決め、文字列を $X$ 進法の数字とみなす。大きくなりすぎるので $M$ でmodを取る。
比較的理解と実装が簡単だが、ハッシュ衝突(違う文字列が同じハッシュ値になってしまう)があるので、なるべく $M$ を大きい素数とし、$X$ を変えて2~3回試すのがよい。 その際、Hackのある競プロサイトでは撃墜されるのを防ぐため、ランダム化するのを推奨されている。
またこれは、2次元にも拡張できる。
Bitap法
1対1の検索アルゴリズム。
照合状態をbit列であらわし、$S$ を1文字ずつ進めながらbit演算で遷移させていく。
下から $i$ 桁目が'1'であれば、$T$ の先頭から $i$ 番目までは一致していることを表す。
またこれはあいまい検索にも対応し、「'?'は何の文字が入ってもいい」「レーベンシュタイン距離が $N$ 以下」などの検索が可能となる。
Z-algorithm
これ自体は検索ではなく、文字列 $S$ の各開始位置 $i$ に対して、「$S$ と $S[i:]$ が先頭何文字まで一致するか?(最長共通接頭辞数)」を構築するアルゴリズム。
i 0123456789012 S ABCABCZABCABC Z 13003000600300
愚直にやると最悪 $O(|S|^2)$ かかるところ、一度見たところを飛ばして $O(|S|)$ でできる。
これを文字列検索に生かすには、$S$ と $T$ を、$S$ の中に絶対存在しない文字($\$$ とする)でつなぎ、$T\$S$ とする。 $S$ の開始位置よりZ-algorithmを適用すれば、値が $|T|$ と等しくなる箇所が、$S$ 上で $T$ が出現する位置である。
Aho-Corasick 法
主に $T$ が複数ある場合に用いる。($T$ の集合を $\mathbb{T}$ で表す)
計算量
$\mathbb{T}$ の各要素の長さの合計を $m$ とすると、
前計算の構築に $O(m)$、検索に最悪 $O(|S|+m)$(ただし一般的な自然言語ならほぼ $O(|S|)$)
概要
$\mathbb{T}$ をTrie木化しておくことで、$S$ にどれが含まれているかを一括に検索できる。
実装としてはTrie木に戻る辺を追加して、「検索に失敗したとき、次に一致する可能性のある $T$ を探すにはどのノードから再開すればいいか」を効率化している。
文字列を効率的に保持するアルゴリズム
Trie木、Patricia木
検索手法というか、データ構造。複数の文字列を木構造で表現する。
トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。 短くて似たような単語が沢山あるとき、特に効率的に保持できる。
パトリシア木は、それを複数文字も1ノードになり得るとしたもの。 実装はやや複雑になるが、長い単語がある場合でも肥大化を防ぐことができる。
Suffix tree
Burrows Wheeler Transform
検索ではなく、文字列を同じ文字が連続しやすいように可逆変換するアルゴリズム。 主に圧縮の前処理に用いる(同じ文字が連続していれば圧縮効率がよくなる)
自然言語でもデータでも、だいたいお決まりの文字(数字)の並びというのが発生しやすいことを利用している。 例えば英語では、子音の後はだいたい母音だったり、'tr', 'sh', 'ck' などが頻出しやすい。
逆に完全にランダムなデータにはあまり効かない(と思う)。
その他
Manacher
文字列 $S$ から奇数長の最長の回文を $O(|S|)$ で検索するアルゴリズム。
$S$ の各文字の間に $S$ には絶対に登場しないダミー文字を挟み込むと、偶数長の回文も見つけられる(ダミー文字が中心になったとき)。