差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:string_search [2020/01/16] – [Aho-Corasick 法] ikatakos | programming_algorithm:string_search [2020/01/20] – [Aho-Corasick 法] ikatakos | ||
---|---|---|---|
行 3: | 行 3: | ||
執筆途中(多分永遠に) | 執筆途中(多分永遠に) | ||
+ | * [[wpjp> | ||
+ | * [[wp> | ||
* [[https:// | * [[https:// | ||
行 14: | 行 16: | ||
==== 愚直(Brute Force) ==== | ==== 愚直(Brute Force) ==== | ||
+ | |||
+ | ==計算量== | ||
+ | |||
+ | $O(|S||T|)$ | ||
+ | |||
+ | ==概要== | ||
まずは基本。マッチ位置 $i$ を1つずつずらして、そこから各 $j$ 文字目が一致するか照合していく。 | まずは基本。マッチ位置 $i$ を1つずつずらして、そこから各 $j$ 文字目が一致するか照合していく。 | ||
- | | + | S ABCDEABCF |
- | T ABCF | + | |
- | | + | 照合 |
- | ABCF | + | |
- | 一般的な(言語上意味のある)文字列であればほとんど1文字目で失敗するので、愚直といえどほぼ $O(|S|)$ で済むが、 | + | 一般的な(自然言語上意味のある)文字列であればほとんど1文字目で失敗するので、愚直といえどほぼ $O(|S|)$ で済むが、 |
同じ文字が多く出現する特殊な場合は、最悪 $O(|S||T|)$ かかる。 | 同じ文字が多く出現する特殊な場合は、最悪 $O(|S||T|)$ かかる。 | ||
行 46: | 行 53: | ||
* [[wpjp> | * [[wpjp> | ||
* [[https:// | * [[https:// | ||
+ | |||
+ | ==計算量== | ||
+ | |||
+ | 前計算 $O(|T|)$、検索 $O(|S|)$ | ||
+ | |||
+ | ==概要== | ||
1対1の検索アルゴリズム。 | 1対1の検索アルゴリズム。 | ||
- | $T$ から「$j$ 文字目で照合失敗したら次のマッチ位置は何文字飛ばせるか」テーブルを事前に作っておく。 | + | 事前に |
+ | |||
+ | ++++ もう少し詳細 | | ||
+ | 前計算テーブル | ||
j 012345 | j 012345 | ||
T ABCABD | T ABCABD | ||
行 65: | 行 81: | ||
'' | '' | ||
- | (基本的に照合失敗したら $T$ をずらして、失敗した $S$ 側の文字はもう一度 $T$ と照合されるが、$j=0$ の場合のみ、$S$ 側の文字も進める必要がある) | ||
- | 計算量は、テーブル作成 | + | 照合失敗したら、基本的には失敗した $S$ 側の文字はもう一度 |
+ | |||
+ | ++++ | ||
++++ Pythonでの実装例 | | ++++ Pythonでの実装例 | | ||
行 118: | 行 135: | ||
* [[wpjp> | * [[wpjp> | ||
+ | |||
+ | ==概要== | ||
1対1の検索アルゴリズム。 | 1対1の検索アルゴリズム。 | ||
KMP法同様、マッチ位置をスキップしつつずらしていくのだが、文字の照合は後ろからおこなうのが特徴。 | KMP法同様、マッチ位置をスキップしつつずらしていくのだが、文字の照合は後ろからおこなうのが特徴。 | ||
- | これにより一般的な文字列検索ではスキップできる期待値が大きくなり、高速なため実用上よく使われている。 | + | |
+ | ==計算量== | ||
+ | |||
+ | 前計算 $O(|T|)$、検索はランダムケースならほぼ $O(\frac{|S|}{|T|})$、最悪 $O(|S||T|)$(最悪を $O(|S|)$ | ||
+ | |||
+ | ++++ もう少し詳細 | | ||
+ | |||
+ | 後ろから照合することで一般的な文字列ではスキップできる期待値が大きくなり、高速となる。 | ||
+ | そのため実用上よく使われている。 | ||
だが、同じ文字が多く出現するケースでは遅く、それを解決しようとすると実装が煩雑になる。 | だが、同じ文字が多く出現するケースでは遅く、それを解決しようとすると実装が煩雑になる。 | ||
行 134: | 行 161: | ||
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: | 行 188: | ||
また、この照合では先頭の' | また、この照合では先頭の' | ||
*/ | */ | ||
+ | |||
+ | ++++ | ||
==== Rabin-Karp法(ローリングハッシュ) ==== | ==== Rabin-Karp法(ローリングハッシュ) ==== | ||
行 166: | 行 195: | ||
* [[wpjp> | * [[wpjp> | ||
- | 一定の長さの文字列をハッシュ化して1つの数字にした上で、ハッシュ値で検索するアルゴリズム。 | + | == 概要 == |
- | === 計算量 | + | 一定の長さの文字列をハッシュ化(1つの整数)にした上で、ハッシュ値で検索するアルゴリズム。 |
+ | |||
+ | $T$ が複数ある場合でも、長さが同じであれば事前計算結果を使い回せる。 | ||
+ | |||
+ | == 計算量 == | ||
ハッシュ化に $O(|S|+|T|)$、検索に $O(|S|)$ | ハッシュ化に $O(|S|+|T|)$、検索に $O(|S|)$ | ||
- | === 概要 === | + | ++++ もう少し詳細 | |
- | KMP・BM法がマッチ位置を試す数を減らして高速化するのに対し、こちらは特定のマッチ位置における文字同士の照合を高速化する。 | + | KMP法やBM法がマッチ位置を試す回数を減らして高速化するのに対し、こちらは特定のマッチ位置における文字列同士の照合を高速化する。 |
事前計算として、$S$ から開始位置を1つずつずらしたハッシュ列 $S'$ を作成しておく。 | 事前計算として、$S$ から開始位置を1つずつずらしたハッシュ列 $S'$ を作成しておく。 | ||
行 183: | 行 216: | ||
ハッシュの計算には、1つ前の値から次のハッシュ値を高速に計算できる「ローリングハッシュ」を用いる。 | ハッシュの計算には、1つ前の値から次のハッシュ値を高速に計算できる「ローリングハッシュ」を用いる。 | ||
- | 整数 $X$ と $M$ を決め、文字列を $X$ 進法の数字とみなす。大きくなりすぎるので $M$ でmodを取る。 | + | アイデアとしては、整数 $X$ と $M$ を決め、文字列を $X$ 進法の数字とみなす感じ。大きくなりすぎるので $M$ でmodを取る。 |
比較的理解と実装が簡単だが、ハッシュ衝突(違う文字列が同じハッシュ値になってしまう)があるので、なるべく $M$ を大きい素数とし、$X$ を変えて2~3回試すのがよい。 | 比較的理解と実装が簡単だが、ハッシュ衝突(違う文字列が同じハッシュ値になってしまう)があるので、なるべく $M$ を大きい素数とし、$X$ を変えて2~3回試すのがよい。 | ||
行 191: | 行 224: | ||
* [[https:// | * [[https:// | ||
- | またこれは、2次元にも拡張できる。 | + | またこれは、2次元にも拡張できる。(ある矩形領域が特定のパターンである場所はあるか?その位置は?) |
+ | |||
+ | ++++ | ||
++++ Pythonでの実装例 | | ++++ Pythonでの実装例 | | ||
行 268: | 行 303: | ||
* [[https:// | * [[https:// | ||
- | 主に $T$ が複数ある場合に用いる。 | + | ==概要== |
- | $T$ の集合をTrie木化しておくことで、$S$ | + | 主に |
- | 実装としてはTrie木に辺を追加して、「検索に失敗したとき、次に一致する可能性のある | + | $\mathbb{T}$ の方を前計算するので、$\mathbb{T}$ は固定的であり、$S$ |
- | 構築の方法と何故それで上手くいくのかについては、naoya氏のブログを参照。 | + | 前計算の実装としては、$\mathbb{T}$ からTrie木を構築、さらに「検索に失敗したとき、次に一致する可能性のある $T$ を探すにはどのノードから再開すればいいか」を前計算し、有限オートマトンを生成する。 |
+ | |||
+ | 検索では $S$ を1文字ずつ順番に見て、前計算結果に従い遷移する。 | ||
+ | |||
+ | ==計算量== | ||
+ | |||
+ | $\mathbb{T}$ の各要素の長さの合計を $m$ とすると、 | ||
+ | |||
+ | 前計算の構築に $O(m)$、検索に $O(|S|+m+マッチ数)$ | ||
+ | |||
+ | ++++ もう少し詳細 | | ||
+ | |||
+ | ==failureの構築== | ||
+ | |||
+ | Trie木を構築後、各ノードに対し、検索失敗時に戻るノード(failure)を特定する。 | ||
+ | |||
+ | * ''' | ||
+ | * ''' | ||
+ | * ある→その子 | ||
+ | * ない→''' | ||
+ | * ある→その子 | ||
+ | * ない→... | ||
+ | * failureを再帰的に遡り、根まで遡っても無ければ、根 | ||
+ | |||
+ | 幅優先探索で根から近い方から埋めていくことで、遡る時に訪れるfailureが既に確定していることを保証できる。 | ||
+ | |||
+ | ==途中で出現する文字列== | ||
+ | $S=$ ''' | ||
+ | |||
+ | ○ -- a -- b -- c -- d -- z | ||
+ | `--- b -- c -- d -- e | ||
+ | `-- c -- d | ||
+ | |||
+ | ''' | ||
+ | その後''' | ||
+ | |||
+ | 実際は''' | ||
+ | |||
+ | これを捕捉するには、探索中の各ノードで | ||
+ | 「自身のfailure, | ||
+ | しかし、実際にそんなことをやっていると時間がかかるので、failureを構築する過程で前計算しておく。 | ||
+ | |||
+ | 各ノードが「自身からfailureを遡っていったときに見つかる文字列リスト」matchを持つ。 | ||
+ | |||
+ | * Trie木の構築時点では、各 $T_i$ の終端を表すノードのmatchに、$T_i$ を登録しておく | ||
+ | * failure構築時、自身のmatchに、自身のfailureのmatchを全て足す | ||
+ | * 根から近い方から構築するので、failureのmatchには、既にfailureのfailure以前のmatchが含まれている | ||
+ | |||
+ | こうしておくと、上の例では''' | ||
+ | |||
+ | ++++ | ||
++++ Pythonでの実装例 | | ++++ Pythonでの実装例 | | ||
行 284: | 行 369: | ||
class AhoCorasick: | class AhoCorasick: | ||
- | def __init__(self, | + | def __init__(self, |
+ | self.patterns = patterns | ||
self.children = [{}] | self.children = [{}] | ||
self.match = [[]] | self.match = [[]] | ||
- | for needle | + | for pi, pattern |
- | self._register(needle) | + | self._register(pi, pattern) |
- | self.failure = self._create_failure() | + | self.failure = [0] * len(self.children) |
+ | | ||
- | def _register(self, | + | def _register(self, |
k = 0 | k = 0 | ||
- | for c in needle: | + | for c in pattern: |
if c in self.children[k]: | if c in self.children[k]: | ||
k = self.children[k][c] | k = self.children[k][c] | ||
行 304: | 行 391: | ||
self.match.append([]) | self.match.append([]) | ||
k = j | k = j | ||
- | self.match[k].append(needle) | + | self.match[k].append(pi) |
def _create_failure(self): | def _create_failure(self): | ||
children = self.children | children = self.children | ||
match = self.match | match = self.match | ||
- | failure = [0] * len(children) | + | failure = self.failure |
- | + | ||
- | q = deque() | + | |
- | for k in children[0].values(): | + | |
- | | + | |
- | q.append(k) | + | |
+ | q = deque(children[0].values()) | ||
while q: | while q: | ||
k = q.popleft() | k = q.popleft() | ||
+ | b = failure[k] | ||
for c, j in children[k].items(): | for c, j in children[k].items(): | ||
- | | + | failure[j] = self._next(b, c) |
- | | + | |
match[j].extend(match[failure[j]]) | match[j].extend(match[failure[j]]) | ||
q.append(j) | q.append(j) | ||
- | return failure | + | |
- | + | ||
- | | + | |
while True: | while True: | ||
if c in self.children[k]: | if c in self.children[k]: | ||
行 332: | 行 413: | ||
if k == 0: | if k == 0: | ||
return 0 | return 0 | ||
- | k = failure[k] | + | k = self.failure[k] |
- | def search(self, | + | def search(self, |
match = self.match | match = self.match | ||
+ | patterns = self.patterns | ||
k = 0 | k = 0 | ||
matched = [] | matched = [] | ||
- | for i, c in enumerate(haystack): | + | for i, c in enumerate(target): |
- | k = self._get_next(k, c, self.failure) | + | k = self._next(k, c) |
- | | + | matched.extend((i - len(patterns[m]) + 1, i, patterns[m]) for m in match[k]) |
- | | + | |
return matched | return matched | ||
- | ahc = AhoCorasick([' | + | ahc = AhoCorasick([' |
print(ahc.search(' | print(ahc.search(' | ||
- | # => [(1, 3, ' | + | # => [(2, 3, ' |
</ | </ | ||
++++ | ++++ | ||
+ | |||
+ | ==== FM-index ==== | ||
+ | |||
+ | * [[wp> | ||
+ | * [[https:// | ||
+ | |||
+ | ==概要== | ||
+ | |||
+ | 主に $T$ が複数ある場合に用いる。(別に複数で無くてもよいが、1対1なら前処理にかかる時間を考えると他のアルゴリズムを用いた方がよい) | ||
+ | |||
+ | $S$ をBWT(Burrows Wheeler変換)しておき、$T$ の各接尾辞が出現するかをチェックする。(まだ詳しく調べてない) | ||
+ | |||
+ | ==計算量== | ||
+ | |||
+ | * 前計算 | ||
+ | * $O(|S| \log{|S|})$ | ||
+ | * $O(|S|), O(|S| \log \log{|S|})$ のアルゴリズムもあるが、自然言語に対しては実用上、上の方がよい | ||
+ | * 1回の検索 | ||
+ | * 出現する文字の種類数を $\sigma$ として、$O(|T| \log{\sigma})$ | ||
+ | |||
===== 文字列を効率的に保持するアルゴリズム ===== | ===== 文字列を効率的に保持するアルゴリズム ===== | ||
行 358: | 行 459: | ||
* [[wpjp> | * [[wpjp> | ||
- | 検索手法というか、データ構造。複数の文字列を木構造で表現する。 | + | 複数の文字列を木構造で表現するデータ構造。 |
- | トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。 | + | トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。(1辺を1文字と対応させる考え方もあるが、本質は一緒) |
短くて似たような単語が沢山あるとき、特に効率的に保持できる。 | 短くて似たような単語が沢山あるとき、特に効率的に保持できる。 | ||
行 378: | 行 479: | ||
* [[https:// | * [[https:// | ||
- | 検索ではなく、文字列を同じ文字が連続しやすいように可逆変換するアルゴリズム。 | + | 文字列を同じ文字が連続しやすいように可逆変換するアルゴリズム。 |
主に圧縮の前処理に用いる(同じ文字が連続していれば圧縮効率がよくなる) | 主に圧縮の前処理に用いる(同じ文字が連続していれば圧縮効率がよくなる) | ||
行 396: | 行 497: | ||
$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] | ||
+ | </ | ||
+ | |||
+ | ++++ | ||