差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:string_search [2020/01/17] – [Aho-Corasick 法] ikatakos | programming_algorithm:string_search [2020/01/17] – [文字列アルゴリズム] ikatakos | ||
|---|---|---|---|
| 行 3: | 行 3: | ||
| 執筆途中（多分永遠に） | 執筆途中（多分永遠に） | ||
| + | * [[wpjp> | ||
| + | * [[wp> | ||
| * [[https:// | * [[https:// | ||
| 行 268: | 行 270: | ||
| * [[https:// | * [[https:// | ||
| - | 主に $T$ が複数ある場合に用いる。 | + | 主に $T$ が複数ある場合に用いる。（$T$ の集合を $\mathbb{T}$ で表す） |
| - | $T$ の集合をTrie木化しておくことで、$S$ にどれが含まれているかを $O(|S|)$ で一括に検索できる。 | + | ===計算量=== |
| - | 実装としてはTrie木に辺を追加して、「検索に失敗したとき、次に一致する可能性のある | + | $\mathbb{T}$ の各要素の長さの合計を $m$ とすると、 |
| - | 構築の方法と何故それで上手くいくのかについては、naoya氏のブログを参照。 | + | 前計算の構築に $O(m)$、検索に $O(|S|+m+マッチ数)$ |
| + | |||
| + | ===概要=== | ||
| + | |||
| + | $\mathbb{T}$ をTrie木化しておくことで、$S$ にどれが含まれているかを一括に検索できる。 | ||
| + | |||
| + | 実装としてはTrie木に戻る辺を追加して、「検索に失敗したとき、次に一致する可能性のある $T$ を探すにはどのノードから再開すればいいか」を効率化している。 | ||
| + | |||
| + | ++++ もう少し詳細 | | ||
| + | |||
| + | ==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での実装例 | | ||
| 行 285: | 行 335: | ||
| def __init__(self, | def __init__(self, | ||
| + | self.patterns = patterns | ||
| self.children = [{}] | self.children = [{}] | ||
| self.match = [[]] | self.match = [[]] | ||
| 行 291: | 行 342: | ||
| self._register(pi, | self._register(pi, | ||
| - | self.failure = self._create_failure() | + | self.failure = [0] * len(self.children) |
| - | self.patterns = patterns | + | self._create_failure() |
| def _register(self, | def _register(self, | ||
| 行 310: | 行 361: | ||
| 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] | b = failure[k] | ||
| for c, j in children[k].items(): | for c, j in children[k].items(): | ||
| - | failure[j] = self._get_next(b, c, failure) | + | 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]: | ||
| 行 333: | 行 378: | ||
| if k == 0: | if k == 0: | ||
| return 0 | return 0 | ||
| - | k = failure[k] | + | k = self.failure[k] |
| def search(self, | def search(self, | ||
| 行 342: | 行 387: | ||
| matched = [] | matched = [] | ||
| for i, c in enumerate(target): | 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]) | matched.extend((i - len(patterns[m]) + 1, i, patterns[m]) for m in match[k]) | ||
| return matched | return matched | ||
| 行 359: | 行 404: | ||
| * [[wpjp> | * [[wpjp> | ||
| - | 検索手法というか、データ構造。複数の文字列を木構造で表現する。 | + | 複数の文字列を木構造で表現するデータ構造。 |
| - | トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。 | + | トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。（1辺を1文字と対応させる考え方もあるが、本質は一緒） |
| 短くて似たような単語が沢山あるとき、特に効率的に保持できる。 | 短くて似たような単語が沢山あるとき、特に効率的に保持できる。 | ||
| 行 397: | 行 442: | ||
| $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] | ||
| + | </ | ||
| + | |||
| + | ++++ | ||
