差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:string_search [2020/01/17] – [Aho-Corasick 法] ikatakos | programming_algorithm:string_search [2020/01/28] – [文字列アルゴリズム全体に関連することとか] ikatakos | ||
---|---|---|---|
行 3: | 行 3: | ||
執筆途中(多分永遠に) | 執筆途中(多分永遠に) | ||
+ | * [[wpjp> | ||
+ | * [[wp> | ||
* [[https:// | * [[https:// | ||
+ | |||
+ | |||
+ | 文字列に関連したアルゴリズムをメモしていく。 | ||
+ | |||
+ | 1つ1つはリンクを参照し詳しくは解説しないが、イメージ的なものと実装例は(なるべく)自分用に書いておく。 | ||
+ | 長くなりすぎたら分けるかも。 | ||
+ | |||
+ | 文字列と言いつつプログラム上は文字コードの数列なので、元から数列であるデータを処理する際にもアルゴリズムは適用できる。 | ||
+ | |||
+ | 文字列に関するアルゴリズムは、主に「検索」や「汎用的なデータ構造を構築」するものが多い。 | ||
+ | |||
+ | ===== 文字列アルゴリズム全体に関連することとか ===== | ||
+ | |||
+ | === 計算量 === | ||
+ | |||
+ | 文字列アルゴリズムに限定した話ではないが、特に文字列では「平均計算量」と「最悪計算量」に差があるものが多く、この概念を区別したい。 | ||
+ | |||
+ | 文字列比較を例に取ると、通常の言語ではだいたいすぐ失敗するのに対し、 | ||
+ | わざと一致箇所が多くなるような意地悪な入力を与えると非常に多くの比較を行わなければならない、というケースがある。 | ||
+ | |||
+ | * ' | ||
+ | * →1文字目で失敗するのですぐ No とわかる | ||
+ | * ' | ||
+ | * →先頭から10万回比較しないとわからない | ||
+ | |||
+ | 競技プログラミングではだいたいこういう意地悪ケースが入っているので最悪計算量を意識する必要があるが、実用の上では平均計算量も(というかそちらの方が)重要。 | ||
+ | |||
+ | ただ、明確に区別しづらかったり、正確な計算量の特定が難しかったりで、各アルゴリズムについて平均と最悪を必ずしも書いてはいない。 | ||
+ | |||
+ | === 記号 === | ||
+ | |||
+ | 以下、アルゴリズムの対象文字列を $S$ とする。 | ||
+ | |||
+ | 検索の場合は、被検索対象を $S$ とし、見つけ出す文字列を $T$ とする。 | ||
+ | |||
+ | それぞれが複数ある場合もあるため、それらをまとめて示す場合は $\mathbb{S}, | ||
+ | |||
+ | $S$ の $i$ 文字目を $S_i$ と表す。 | ||
+ | |||
+ | $S$ の長さを $|S|$ で表す。 | ||
===== 文字列検索アルゴリズム ===== | ===== 文字列検索アルゴリズム ===== | ||
行 10: | 行 52: | ||
ただ使うだけなら、1対1のString型の検索であれば、下手に自力実装するより'' | ただ使うだけなら、1対1のString型の検索であれば、下手に自力実装するより'' | ||
+ | (むしろ以下の内容が既に実装されているはず) | ||
$S$ や $T$ が複数あるのを事前計算で高速化したり、数列を文字列と見なして一致する連続箇所を検索する場合などに、以下のアルゴリズムが有用となる。 | $S$ や $T$ が複数あるのを事前計算で高速化したり、数列を文字列と見なして一致する連続箇所を検索する場合などに、以下のアルゴリズムが有用となる。 | ||
==== 愚直(Brute Force) ==== | ==== 愚直(Brute Force) ==== | ||
+ | |||
+ | ==計算量== | ||
+ | |||
+ | $O(|S||T|)$ | ||
+ | |||
+ | ==概要== | ||
まずは基本。マッチ位置 $i$ を1つずつずらして、そこから各 $j$ 文字目が一致するか照合していく。 | まずは基本。マッチ位置 $i$ を1つずつずらして、そこから各 $j$ 文字目が一致するか照合していく。 | ||
- | | + | S |
- | T ABCF | + | |
- | | + | 照合 |
- | ABCF | + | |
- | 一般的な(言語上意味のある)文字列であればほとんど1文字目で失敗するので、愚直といえどほぼ $O(|S|)$ で済むが、 | + | 一般的な(自然言語上意味のある)文字列であればほとんど1文字目で失敗するので、愚直といえどほぼ $O(|S|)$ で済む。 |
- | 同じ文字が多く出現する特殊な場合は、最悪 $O(|S||T|)$ かかる。 | + | |
++++ Pythonでの実装例 | | ++++ Pythonでの実装例 | | ||
行 46: | 行 93: | ||
* [[wpjp> | * [[wpjp> | ||
* [[https:// | * [[https:// | ||
+ | |||
+ | ==計算量== | ||
+ | |||
+ | 前計算 $O(|T|)$、検索 $O(|S|)$ | ||
+ | |||
+ | ==概要== | ||
1対1の検索アルゴリズム。 | 1対1の検索アルゴリズム。 | ||
- | $T$ から「$j$ 文字目で照合失敗したら次のマッチ位置は何文字飛ばせるか」テーブルを事前に作っておく。 | + | 事前に |
+ | ++++ もう少し詳細 | | ||
+ | |||
+ | 前計算テーブル | ||
j 012345 | j 012345 | ||
T ABCABD | T ABCABD | ||
- | たとえば $j=5$ 文字目の''' | + | たとえば $j=5$ 文字目の''' |
+ | さらにそのマッチ位置では既に' | ||
S ABCABCABD | S ABCABCABD | ||
行 61: | 行 118: | ||
| | ||
S ABCABCABD | S ABCABCABD | ||
- | T | + | T |
^^^^ さらに' | ^^^^ さらに' | ||
+ | |||
+ | 具体的には、$S$ の $i+j$ 文字目と $T$ の $j$ 文字目を照合しつつ $j$ 文字目で失敗した場合、次の位置は以下のようにすればよい。 | ||
+ | |||
+ | * $i ← i+j-Tbl[j]$ | ||
+ | * $j ← Tbl[j]$ | ||
'' | '' | ||
- | (基本的に照合失敗したら $T$ をずらして、失敗した $S$ 側の文字はもう一度 $T$ と照合されるが、$j=0$ の場合のみ、$S$ 側の文字も進める必要がある) | ||
- | 計算量は、テーブル作成 | + | 照合失敗したら、基本的には失敗した $S$ 側の文字はもう一度 |
+ | |||
+ | ++++ | ||
++++ Pythonでの実装例 | | ++++ Pythonでの実装例 | | ||
行 118: | 行 181: | ||
* [[wpjp> | * [[wpjp> | ||
+ | |||
+ | ==概要== | ||
1対1の検索アルゴリズム。 | 1対1の検索アルゴリズム。 | ||
- | KMP法同様、マッチ位置をスキップしつつずらしていくのだが、文字の照合は後ろからおこなうのが特徴。 | + | KMP法同様、テーブルを作ってマッチ位置をスキップするのだが、文字の照合は後ろからおこなうのが特徴。 |
- | これにより一般的な文字列検索ではスキップできる期待値が大きくなり、高速なため実用上よく使われている。 | + | |
+ | ==計算量== | ||
+ | |||
+ | 前計算 $O(|T|)$、検索はランダムケースならほぼ $O(\frac{|S|}{|T|})$、最悪 $O(|S||T|)$(最悪を $O(|S|)$ | ||
+ | |||
+ | ++++ もう少し詳細 | | ||
+ | |||
+ | 後ろから照合することで一般的な文字列ではスキップできる期待値が大きくなり、高速となる。 | ||
+ | そのため実用上よく使われている。 | ||
だが、同じ文字が多く出現するケースでは遅く、それを解決しようとすると実装が煩雑になる。 | だが、同じ文字が多く出現するケースでは遅く、それを解決しようとすると実装が煩雑になる。 | ||
行 134: | 行 207: | ||
x^ | x^ | ||
S ...AB[C]DEFGH... | S ...AB[C]DEFGH... | ||
- | T | + | T |
| | ||
S ...ABCDEFGH... | S ...ABCDEFGH... | ||
T | T | ||
- | 一般的な意味のある文字列では、ほぼ $|T|$ ずつ枠が移動し、 $O(\frac{|S|}{|T|})$ となる。 | + | 一般的な文字列では、ほぼ $|T|$ ずつ枠が移動し、 $O(\frac{|S|}{|T|})$ となる。 |
一方、$S$ や $T$ に同じ文字や並びが何度も出現する場合はスキップが有効に働かず、最悪 $O(|S||T|)$ となる。 | 一方、$S$ や $T$ に同じ文字や並びが何度も出現する場合はスキップが有効に働かず、最悪 $O(|S||T|)$ となる。 | ||
行 161: | 行 234: | ||
また、この照合では先頭の' | また、この照合では先頭の' | ||
*/ | */ | ||
+ | |||
+ | ++++ | ||
==== Rabin-Karp法(ローリングハッシュ) ==== | ==== Rabin-Karp法(ローリングハッシュ) ==== | ||
行 166: | 行 241: | ||
* [[wpjp> | * [[wpjp> | ||
- | 一定の長さの文字列をハッシュ化して1つの数字にした上で、ハッシュ値で検索するアルゴリズム。 | + | == 概要 == |
- | === 計算量 | + | 一定の長さの文字列をハッシュ化(1つの整数)にした上で、ハッシュ値で検索するアルゴリズム。 |
+ | |||
+ | 1対1でも使えるし、$T$ が複数ある場合でも、文字列長が同じであれば事前計算結果を使い回せる。 | ||
+ | |||
+ | == 計算量 == | ||
ハッシュ化に $O(|S|+|T|)$、検索に $O(|S|)$ | ハッシュ化に $O(|S|+|T|)$、検索に $O(|S|)$ | ||
- | === 概要 === | + | ++++ もう少し詳細 | |
- | KMP・BM法がマッチ位置を試す数を減らして高速化するのに対し、こちらは特定のマッチ位置における文字同士の照合を高速化する。 | + | KMP法やBM法がマッチ位置を試す回数を減らして高速化するのに対し、こちらは特定のマッチ位置における文字列同士の照合を高速化する。 |
事前計算として、$S$ から開始位置を1つずつずらしたハッシュ列 $S'$ を作成しておく。 | 事前計算として、$S$ から開始位置を1つずつずらしたハッシュ列 $S'$ を作成しておく。 | ||
$T$ も全体のハッシュ値 $T'$ を求める。 | $T$ も全体のハッシュ値 $T'$ を求める。 | ||
すると検索は、数列 $S'$ から1つの数字 $T'$ を探す処理になる。 | すると検索は、数列 $S'$ から1つの数字 $T'$ を探す処理になる。 | ||
+ | |||
+ | S a b c a b c d | ||
+ | | ||
+ | S' [ 53, 27, 38, 5 ] T' | ||
$T$ が複数ある場合、長さが同じであれば、$S' | $T$ が複数ある場合、長さが同じであれば、$S' | ||
ハッシュの計算には、1つ前の値から次のハッシュ値を高速に計算できる「ローリングハッシュ」を用いる。 | ハッシュの計算には、1つ前の値から次のハッシュ値を高速に計算できる「ローリングハッシュ」を用いる。 | ||
- | 整数 $X$ と $M$ を決め、文字列を $X$ 進法の数字とみなす。大きくなりすぎるので $M$ でmodを取る。 | + | アイデアとしては、整数 $X$ と $M$ を決め、文字列を $X$ 進法の数字とみなす感じ。大きくなりすぎるので $M$ でmodを取る。 |
比較的理解と実装が簡単だが、ハッシュ衝突(違う文字列が同じハッシュ値になってしまう)があるので、なるべく $M$ を大きい素数とし、$X$ を変えて2~3回試すのがよい。 | 比較的理解と実装が簡単だが、ハッシュ衝突(違う文字列が同じハッシュ値になってしまう)があるので、なるべく $M$ を大きい素数とし、$X$ を変えて2~3回試すのがよい。 | ||
行 191: | 行 274: | ||
* [[https:// | * [[https:// | ||
- | またこれは、2次元にも拡張できる。 | + | またこれは、2次元にも拡張できる。(ある矩形領域が特定のパターンである場所はあるか?その位置は?) |
+ | |||
+ | ++++ | ||
++++ Pythonでの実装例 | | ++++ Pythonでの実装例 | | ||
行 268: | 行 353: | ||
* [[https:// | * [[https:// | ||
- | 主に $T$ が複数ある場合に用いる。($T$ の集合を $\mathbb{T}$ で表す) | + | ==概要== |
- | ===計算量=== | + | 主に $T$ が複数ある場合に用いる($T$ の集合を $\mathbb{T}$ で表す)。 |
- | $\mathbb{T}$ の各要素の長さの合計を $m$ とすると、 | + | $\mathbb{T}$ の方を前計算するので、$\mathbb{T}$ は固定的であり、$S$ の方を様々に変更して検索する用途に向く。 |
- | 前計算の構築に | + | 前計算の実装としては、$\mathbb{T}$ からTrie木を構築、さらに「検索に失敗したとき、次に一致する可能性のある |
- | ===概要=== | + | 検索では $S$ を1文字ずつ順番に見て、前計算結果に従い遷移する。 |
- | $\mathbb{T}$ をTrie木化しておくことで、$S$ にどれが含まれているかを一括に検索できる。 | + | ==計算量== |
+ | |||
+ | $\mathbb{T}$ | ||
- | 実装としてはTrie木に戻る辺を追加して、「検索に失敗したとき、次に一致する可能性のある | + | 前計算の構築に $O(m)$、検索に $O(|S|+m+マッチ数)$ |
++++ もう少し詳細 | | ++++ もう少し詳細 | | ||
行 395: | 行 482: | ||
</ | </ | ||
++++ | ++++ | ||
+ | |||
+ | ==== Suffix Array(SA-IS法) ==== | ||
+ | |||
+ | * [[wpjp> | ||
+ | * [[https:// | ||
+ | |||
+ | ==概要== | ||
+ | |||
+ | Suffix Arrayの説明自体は上のサイトや他に溢れてるので、割愛。 | ||
+ | これを線形時間で構築するのがSA-ISと呼ばれるアルゴリズム。 | ||
+ | |||
+ | SAで文字列検索を行うには、二分探索を用いる。 | ||
+ | 辞書順に並んでいるため、$S$ の中に $T$(を接頭辞とした文字列)が出現するかどうかは二分探索で調べられる。 | ||
+ | 複数出現する場合もSA上で連続しているので、始まりと終わりの境界を探索すればよい。 | ||
+ | |||
+ | * SA-IS法について、Rubyでの実装例を追いながら、データの中身を含めて解説してくれているサイト | ||
+ | * [[https:// | ||
+ | |||
+ | ==計算量== | ||
+ | |||
+ | * 前計算 | ||
+ | * $O(|S|)$ | ||
+ | * 検索 | ||
+ | * $O(|T| \log|S|)$ | ||
+ | |||
+ | ++++ PythonでのSA-ISの実装 | | ||
+ | |||
+ | * '' | ||
+ | * aaaは数列で与える点に注意(途中でsa_is()を再帰的に呼ぶが、その際にaaaは数列の方が都合がいいため) | ||
+ | * '' | ||
+ | |||
+ | <sxh python> | ||
+ | from collections import Counter | ||
+ | from itertools import accumulate | ||
+ | from operator import itemgetter | ||
+ | |||
+ | def induced_sort(n, | ||
+ | """ | ||
+ | :param lsa: L-S Array | ||
+ | :param lmss: Leftmost S の配列(この順番により結果は変化する) | ||
+ | :return: | ||
+ | """ | ||
+ | |||
+ | sa = [-1] * n | ||
+ | |||
+ | counter = [0] * ak | ||
+ | for i in reversed(lmss): | ||
+ | di = a_dic[aaa[i]] | ||
+ | sa[a_acc[di + 1] - 1 - counter[di]] = i | ||
+ | counter[di] += 1 | ||
+ | |||
+ | counter = [0] * ak | ||
+ | for i in sa: | ||
+ | if i <= 0: | ||
+ | continue | ||
+ | if lsa[i - 1] == 0: | ||
+ | continue | ||
+ | di = a_dic[aaa[i - 1]] | ||
+ | sa[a_acc[di] + counter[di]] = i - 1 | ||
+ | counter[di] += 1 | ||
+ | |||
+ | counter = [0] * ak | ||
+ | for i in reversed(sa): | ||
+ | if i <= 0: | ||
+ | continue | ||
+ | if lsa[i - 1] == 1: | ||
+ | continue | ||
+ | di = a_dic[aaa[i - 1]] | ||
+ | sa[a_acc[di + 1] - 1 - counter[di]] = i - 1 | ||
+ | counter[di] += 1 | ||
+ | |||
+ | return sa | ||
+ | |||
+ | |||
+ | def sa_is(n: int, aaa: list, a_acc: list, a_dic: dict, ak: int): | ||
+ | """ | ||
+ | :param n: aaaの長さ | ||
+ | :param aaa: Suffix Arrayを求めたい数列 | ||
+ | | ||
+ | :param a_acc: 頭文字がa_dic[a]の要素がSA上で並び始めるindex | ||
+ | :param a_dic: aaaの各要素に昇順に割り当てる連番 | ||
+ | :param ak: aaaに出現する要素の種類数(len(a_dic)) | ||
+ | :return: | ||
+ | """ | ||
+ | |||
+ | # LS array | ||
+ | lsa = [0] * n # 0:S, 1:L | ||
+ | for i in range(n - 2, -1, -1): | ||
+ | if aaa[i] == aaa[i + 1]: | ||
+ | lsa[i] = lsa[i + 1] | ||
+ | elif aaa[i] > aaa[i + 1]: | ||
+ | lsa[i] = 1 | ||
+ | |||
+ | # LeftMost S | ||
+ | lmss = [i for i, (lsl, lsr) in enumerate(zip(lsa, | ||
+ | if lsl == 1 and lsr == 0] | ||
+ | |||
+ | sa = induced_sort(n, | ||
+ | |||
+ | lms_set = set(lmss) | ||
+ | sa = [i for i in sa if i in lms_set] | ||
+ | |||
+ | nums = [-1] * n | ||
+ | nums[sa[0]] = num = 0 | ||
+ | |||
+ | for i, j in zip(sa, sa[1:]): | ||
+ | |||
+ | for d in range(n): | ||
+ | is_id_lms = i + d in lms_set | ||
+ | is_jd_lms = j + d in lms_set | ||
+ | if aaa[i + d] != aaa[j + d] or (is_id_lms == is_jd_lms): | ||
+ | num += 1 | ||
+ | break | ||
+ | elif d > 0 and (is_id_lms or is_jd_lms): | ||
+ | break | ||
+ | |||
+ | nums[j] = num | ||
+ | |||
+ | nums = [i for i in nums if i != -1] | ||
+ | |||
+ | if num < len(nums) - 1: | ||
+ | sa = sa_is(num + 1, nums) | ||
+ | lmss2 = list(map(lmss.__getitem__, | ||
+ | else: | ||
+ | lmss2 = [lmss[i] for i, j in sorted(enumerate(nums), | ||
+ | |||
+ | sa = induced_sort(n, | ||
+ | |||
+ | return sa | ||
+ | |||
+ | def make_suffix_array(aaa): | ||
+ | n = len(aaa) | ||
+ | a_cnt = Counter(aaa) | ||
+ | a_kind = sorted(a_cnt.keys()) | ||
+ | a_dic = {a: i for i, a in enumerate(a_kind)} | ||
+ | a_acc = list(accumulate([0] + list(map(a_cnt.get, | ||
+ | ak = len(a_kind) | ||
+ | |||
+ | # [-1] はaaa内のどの要素より小さい要素(適宜変更する) | ||
+ | sa = sa_is(n + 1, aaa + [-1], a_acc, a_dic, ak) | ||
+ | return sa | ||
+ | |||
+ | </ | ||
+ | |||
+ | ++++ | ||
+ | |||
+ | ==== FM-index ==== | ||
+ | |||
+ | * [[wp> | ||
+ | * [[https:// | ||
+ | |||
+ | ==概要== | ||
+ | |||
+ | 主に $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})$ | ||
+ | |||
===== 文字列を効率的に保持するアルゴリズム ===== | ===== 文字列を効率的に保持するアルゴリズム ===== | ||
行 402: | 行 659: | ||
* [[wpjp> | * [[wpjp> | ||
- | 検索手法というか、データ構造。複数の文字列を木構造で表現する。 | + | 複数の文字列を木構造で表現するデータ構造。 |
- | トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。 | + | トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。(1辺を1文字と対応させる考え方もあるが、本質は一緒) |
短くて似たような単語が沢山あるとき、特に効率的に保持できる。 | 短くて似たような単語が沢山あるとき、特に効率的に保持できる。 | ||
行 422: | 行 679: | ||
* [[https:// | * [[https:// | ||
- | 検索ではなく、文字列を同じ文字が連続しやすいように可逆変換するアルゴリズム。 | + | 文字列を同じ文字が連続しやすいように可逆変換するアルゴリズム。 |
主に圧縮の前処理に用いる(同じ文字が連続していれば圧縮効率がよくなる) | 主に圧縮の前処理に用いる(同じ文字が連続していれば圧縮効率がよくなる) | ||
行 433: | 行 690: | ||
==== Manacher ==== | ==== Manacher ==== | ||
+ | |||
+ | * [[https:// | ||
+ | |||
+ | ==概要== | ||
文字列 $S$ から奇数長の最長の回文を $O(|S|)$ で検索するアルゴリズム。 | 文字列 $S$ から奇数長の最長の回文を $O(|S|)$ で検索するアルゴリズム。 | ||
- | * [[https:// | + | $S$ の各文字の間に $S$ には絶対に登場しないダミー文字を挟み込むと、偶数長の回文も見つけられる。 |
- | $S$ の各文字の間に $S$ には絶対に登場しないダミー文字を挟み込むと、偶数長の回文も見つけられる(ダミー文字が中心になったとき)。 | + | ++++ Pythonでの実装 | |
+ | 両端と各文字の間に' | ||
+ | |||
+ | <sxh python> | ||
+ | def manacher(s): | ||
+ | n = len(s) | ||
+ | radius = [0] * n | ||
+ | i, j = 0, 0 | ||
+ | while i < n: | ||
+ | while i - j >= 0 and i + j < n and s[i - j] == s[i + j]: | ||
+ | j += 1 | ||
+ | radius[i] = j | ||
+ | k = 1 | ||
+ | while i - k >= 0 and i + k < n and k + radius[i - k] < j: | ||
+ | radius[i + k] = radius[i - k] | ||
+ | k += 1 | ||
+ | i += k | ||
+ | j -= k | ||
+ | return radius | ||
+ | |||
+ | |||
+ | s = ' | ||
+ | s = ' | ||
+ | man = manacher(s) | ||
+ | print(man) | ||
+ | # a | ||
+ | # => [1, 2, 1, 2, 1, 4, 1, 4, 1, 2, 1, 12, 1, 2, 1, 4, 1, 4, 1, 2, 1, 2, 1] | ||
+ | |||
+ | s = ' | ||
+ | s = ' | ||
+ | man = manacher(s) | ||
+ | print(man) | ||
+ | # a | ||
+ | # => [1, 2, 1, 2, 1, 2, 7, 2, 1, 2, 1, 2, 1] | ||
+ | </ | ||
+ | |||
+ | ++++ | ||