文字列アルゴリズム

執筆途中(多分永遠に)

文字列に関連したアルゴリズムをメモしていく。

1つ1つはリンクを参照し詳しくは解説しないが、イメージ的なものと実装例は(なるべく)自分用に書いておく。 長くなりすぎたら分けるかも。

文字列と言いつつプログラム上は文字コードの数列なので、元から数列であるデータを処理する際にもアルゴリズムは適用できる。

文字列に関するアルゴリズムは、主に「検索」や「汎用的なデータ構造を構築」するものが多い。

文字列アルゴリズム全体に関連することとか

計算量

文字列アルゴリズムに限定した話ではないが、特に文字列では「平均計算量」と「最悪計算量」に差があるものが多く、この概念を区別したい。

文字列比較を例に取ると、通常の言語ではだいたいすぐ失敗するのに対し、 わざと一致箇所が多くなるような意地悪な入力を与えると非常に多くの比較を行わなければならない、というケースがある。

  • 'apple' と 'orange' は一致しますか?
    • →1文字目で失敗するのですぐ No とわかる
  • 'aaaaa…..aa' と 'aaaaa…ab' は一致しますか?(10万文字)
    • →先頭から10万回比較しないとわからない

競技プログラミングではだいたいこういう意地悪ケースが入っているので最悪計算量を意識する必要があるが、実用の上では平均計算量も(というかそちらの方が)重要。

ただ、明確に区別しづらかったり、正確な計算量の特定が難しかったりで、各アルゴリズムについて平均と最悪を必ずしも書いてはいない。

記号

以下、アルゴリズムの対象文字列を $S$ とする。

検索の場合は、被検索対象を $S$ とし、見つけ出す文字列を $T$ とする。

それぞれが複数ある場合もあるため、それらをまとめて示す場合は $\mathbb{S},\mathbb{T}$ とし、個々の1要素を $S,T$ とする。

$S$ の $i$ 文字目を $S_i$ と表す。

$S$ の長さを $|S|$ で表す。

文字列検索アルゴリズム

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

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

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

愚直(Brute Force)

計算量

$O(|S||T|)$

概要

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

   S  ABCDEABCF    ABCDEABCF    ABCDEABCF    ...    ABCDEABCF
   T  ABCF          ABCF          ABCF       ...         ABCF
照合  ooox          x             x          ...         oooo  発見!

一般的な(自然言語上意味のある)文字列であればほとんど1文字目で失敗するので、愚直といえどほぼ $O(|S|)$ で済む。

Pythonでの実装例

KMP法

計算量

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

概要

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

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

もう少し詳細

Pythonでの実装例

Boyer-Moore 法

概要

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

KMP法同様、テーブルを作ってマッチ位置をスキップするのだが、文字の照合は後ろからおこなうのが特徴。

計算量

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

もう少し詳細

Rabin-Karp法(ローリングハッシュ)

概要

一定の長さの文字列をハッシュ化(1つの整数)にした上で、ハッシュ値で検索するアルゴリズム。

1対1でも使えるし、$T$ が複数ある場合でも、文字列長が同じであれば事前計算結果を使い回せる。

計算量

ハッシュ化に $O(|S|+|T|)$、検索に $O(|S|)$

もう少し詳細

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}$ の方を前計算するので、$\mathbb{T}$ は固定的であり、$S$ の方を様々に変更して検索する用途に向く。

前計算の実装としては、$\mathbb{T}$ からTrie木を構築、 さらに「検索に失敗したとき、次に一致する可能性のある $T$ を探すにはどのノードから再開すればいいか」を前計算し、 オートマトンを生成する。

検索では $S$ を1文字ずつ順番に見て、前計算結果に従い遷移する。

計算量

$\mathbb{T}$ の各要素の長さの合計を $m$ とすると、

前計算の構築に $O(m)$、検索に $O(|S|+m+マッチ数)$

もう少し詳細

Pythonでの実装例

Suffix Array(SA-IS法)

概要

Suffix Arrayの説明自体は上のサイトや他に溢れてるので、割愛。 これを線形時間で構築するのがSA-ISと呼ばれるアルゴリズム。

SAで文字列検索を行うには、二分探索を用いる。 辞書順に並んでいるため、$S$ の中に $T$(を接頭辞とした文字列)が出現するかどうかは二分探索で調べられる。 複数出現する場合もSA上で連続しているので、始まりと終わりの境界を探索すればよい。

  • SA-IS法について、Rubyでの実装例を追いながら、データの中身を含めて解説してくれているサイト
計算量
  • 前計算
    • $O(|S|)$
  • 検索
    • $O(|T| \log|S|)$

PythonでのSA-ISの実装

FM-index

概要

主に $T$ が複数ある場合に用いる。(別に複数で無くてもよいが、1対1なら前処理にかかる時間を考えると他のアルゴリズムを用いた方がよい)

$S$ を前計算するので、$S$ が固定的であり、$T$ を様々に変えて検索する用途に向く。

前計算では $S$ をBWT(Burrows Wheeler変換)しておき、検索で $T$ の各接尾辞が出現するかをチェックする。

これまでのアルゴリズムと比べて新しく、性能はいいが理解・実装も複雑。

計算量
  • 前計算
    • 理解しやすいが低速 $O(|S|^2 \log{|S|})$
    • 難しいが高速 $O(|S| \log{|S|})$
    • $O(|S|)$ などのアルゴリズムもあるが、自然言語に対しては実用上、上の方がよいらしい
  • 1回の検索
    • 出現する文字の種類数を $\sigma$ として、$O(|T| \log{\sigma})$

FFT(畳み込み)

概要

畳み込みは別に文字列に限定したアルゴリズムでは無いのだが、少し応用の利いた一致箇所の列挙に使える。

$T$ を反転させたものを $U$ とし、$S,U$ の各文字を対応する何らかの数値に置き換える。

すると、$S,U$ の畳み込み結果の数列は、 「$S_i$ と $T_1$ の位置を合わせた時の $S_iT_1+S_{i+1}T_2+...+S_{i+|T|-1}T_{|T|}$」をそれぞれ表す。

結果の値から、両者が一致しているかどうかを特定できるような数値への置き換えをしておけば、一致箇所を列挙できる。

計算量
  • $N=|S|+|T|$ として、$O(N \log{N})$

もう少し詳細

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

Trie木、Patricia木

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

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

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

Suffix tree

Burrows Wheeler Transform

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

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

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

その他

Manacher

概要

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

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

Pythonでの実装

programming_algorithm/string_search.txt · 最終更新: 2023/06/27 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0