文字列アルゴリズム

文字列検索アルゴリズム

文字列 $S$ から文字列 $T$ を検索する手法あれこれ。

ただ使うだけなら、1対1のString型の検索であれば、下手に自力実装するよりfind()など組み込み関数を使った方が一般的には高速となる。

$S$ や $T$ が複数あるのを事前計算で高速化したり、数列を文字列と見なして一致する連続箇所を検索する場合などに、以下のアルゴリズムが有用となる。

愚直(Brute Force)

計算量

$O(|S||T|)$

概要

まずは基本。マッチ位置 $i$ を1つずつずらして、そこから各 $j$ 文字目が一致するか照合していく。

   S  ABCDEABCF    ABCDEABCF    ABCDEABCF    ...
   T  ABCF          ABCF          ABCF       ...
照合  ^^^x          x             x          ...

一般的な(自然言語上意味のある)文字列であればほとんど1文字目で失敗するので、愚直といえどほぼ $O(|S|)$ で済むが、 同じ文字が多く出現する特殊な場合は、最悪 $O(|S||T|)$ かかる。

Pythonでの実装例

KMP法

計算量

前計算 $O(|T|)$、検索 $O(|S|)$

概要

1対1の検索アルゴリズム。

事前に $T$ から「$j$ 文字目で照合失敗したら次は何文字ずらすか」テーブルを作っておき、マッチ位置を試す位置を少なくする。

もう少し詳細

Pythonでの実装例

Boyer-Moore 法

1対1の検索アルゴリズム。

計算量

前計算 $O(|T|)$、検索はランダムケースならほぼ $O(\frac{|S|}{|T|})$、最悪 $O(|S||T|)$(最悪を $O(|S|)$ にする改善方法は存在)

概要

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次元にも拡張できる。

Pythonでの実装例

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+マッチ数)$

概要

$\mathbb{T}$ をTrie木化しておくことで、$S$ にどれが含まれているかを一括に検索できる。

実装としてはTrie木に戻る辺を追加して、「検索に失敗したとき、次に一致する可能性のある $T$ を探すにはどのノードから再開すればいいか」を効率化している。

もう少し詳細

Pythonでの実装例

文字列を効率的に保持するアルゴリズム

Trie木、Patricia木

複数の文字列を木構造で表現するデータ構造。

トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。(1辺を1文字と対応させる考え方もあるが、本質は一緒) 短くて似たような単語が沢山あるとき、特に効率的に保持できる。

パトリシア木は、それを複数文字も1ノードになり得るとしたもの。 実装はやや複雑になるが、長い単語がある場合でも肥大化を防ぐことができる。

Suffix tree

Burrows Wheeler Transform

検索ではなく、文字列を同じ文字が連続しやすいように可逆変換するアルゴリズム。 主に圧縮の前処理に用いる(同じ文字が連続していれば圧縮効率がよくなる)

自然言語でもデータでも、だいたいお決まりの文字(数字)の並びというのが発生しやすいことを利用している。 例えば英語では、子音の後はだいたい母音だったり、'tr', 'sh', 'ck' などが頻出しやすい。

逆に完全にランダムなデータにはあまり効かない(と思う)。

その他

Manacher

文字列 $S$ から奇数長の最長の回文を $O(|S|)$ で検索するアルゴリズム。

$S$ の各文字の間に $S$ には絶対に登場しないダミー文字を挟み込むと、偶数長の回文も見つけられる(ダミー文字が中心になったとき)。

Pythonでの実装

本WebサイトはcookieをPHPのセッション識別および左欄目次の開閉状況記憶のために使用しています。同意できる方のみご覧ください。More information about cookies
programming_algorithm/string_search.txt · 最終更新: 2020/01/17 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0