差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:string_search [2020/01/17] – [Aho-Corasick 法] ikatakos | programming_algorithm:string_search [2020/01/17] – [Boyer-Moore 法] ikatakos | ||
---|---|---|---|
行 3: | 行 3: | ||
執筆途中(多分永遠に) | 執筆途中(多分永遠に) | ||
+ | * [[wpjp> | ||
+ | * [[wp> | ||
* [[https:// | * [[https:// | ||
行 120: | 行 122: | ||
1対1の検索アルゴリズム。 | 1対1の検索アルゴリズム。 | ||
+ | |||
+ | ===計算量=== | ||
+ | |||
+ | 前計算 $O(|T|)$、検索はランダムケースならほぼ $O(\frac{|S|}{|T|})$、最悪 $O(|S||T|)$(最悪を $O(|S|)$ にする改善方法は存在) | ||
+ | |||
+ | ===概要=== | ||
KMP法同様、マッチ位置をスキップしつつずらしていくのだが、文字の照合は後ろからおこなうのが特徴。 | KMP法同様、マッチ位置をスキップしつつずらしていくのだが、文字の照合は後ろからおこなうのが特徴。 | ||
行 268: | 行 276: | ||
* [[https:// | * [[https:// | ||
- | 主に $\mathbb{T}$ が複数ある場合に用いる。 | + | 主に $T$ が複数ある場合に用いる。($T$ の集合を $\mathbb{T}$ で表す) |
===計算量=== | ===計算量=== | ||
行 274: | 行 282: | ||
$\mathbb{T}$ の各要素の長さの合計を $m$ とすると、 | $\mathbb{T}$ の各要素の長さの合計を $m$ とすると、 | ||
- | 前計算の構築に $O(m)$、検索に最悪 | + | 前計算の構築に $O(m)$、検索に $O(|S|+m+マッチ数)$ |
===概要=== | ===概要=== | ||
- | $T$ の集合をTrie木化しておくことで、$S$ にどれが含まれているかを一括に検索できる。 | + | $\mathbb{T}$ をTrie木化しておくことで、$S$ にどれが含まれているかを一括に検索できる。 |
実装としてはTrie木に戻る辺を追加して、「検索に失敗したとき、次に一致する可能性のある $T$ を探すにはどのノードから再開すればいいか」を効率化している。 | 実装としてはTrie木に戻る辺を追加して、「検索に失敗したとき、次に一致する可能性のある $T$ を探すにはどのノードから再開すればいいか」を効率化している。 | ||
行 286: | 行 294: | ||
==failureの構築== | ==failureの構築== | ||
- | Trie木を構築後、戻る辺(failure)を構築する。 | + | Trie木を構築後、各ノードに対し、検索失敗時に戻るノード(failure)を特定する。 |
- | * ''' | + | * ''' |
* ''' | * ''' | ||
* ある→その子 | * ある→その子 | ||
- | * ない→(''' | + | * ない→''' |
* ある→その子 | * ある→その子 | ||
* ない→... | * ない→... | ||
- | * 再帰的に遡り、根まで遡っても無ければ、根 | + | * failureを再帰的に遡り、根まで遡っても無ければ、根 |
幅優先探索で根から近い方から埋めていくことで、遡る時に訪れるfailureが既に確定していることを保証できる。 | 幅優先探索で根から近い方から埋めていくことで、遡る時に訪れるfailureが既に確定していることを保証できる。 | ||
行 402: | 行 410: | ||
* [[wpjp> | * [[wpjp> | ||
- | 検索手法というか、データ構造。複数の文字列を木構造で表現する。 | + | 複数の文字列を木構造で表現するデータ構造。 |
- | トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。 | + | トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。(1辺を1文字と対応させる考え方もあるが、本質は一緒) |
短くて似たような単語が沢山あるとき、特に効率的に保持できる。 | 短くて似たような単語が沢山あるとき、特に効率的に保持できる。 | ||
行 440: | 行 448: | ||
$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 | ||
+ | # print(i, j, k, radius) | ||
+ | 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] | ||
+ | </ | ||
+ | |||
+ | ++++ | ||