差分

この文書の現在のバージョンと選択したバージョンの差分を表示します。

--- programming_algorithm:string_search [2020/01/16]
ikatakos [Aho-Corasick 法]
+++ programming_algorithm:string_search [2020/01/17] (現在)
ikatakos [Manacher]
@@ ライン 3: / ライン 3: @@
 執筆途中（多分永遠に）
+  * [[wpjp>文字列探索]]
+  * [[wp>String-searching_algorithm]]
   * [[https://www.hamayanhamayan.com/entry/2017/03/25/005452|競技プログラミングにおける文字列アルゴリズム問題まとめ [ローリングハッシュ,Suffix Array,LCP,KMP,Aho-Corasick,Z-algorithm,Palindromic Tree, Manacher, Suffix Tree] - はまやんはまやんはまやん]]
@@ ライン 14: / ライン 16: @@
 ==== 愚直（Brute Force） ====
+==計算量==
+$O(|S||T|)$
+==概要==
 まずは基本。マッチ位置 $i$ を1つずつずらして、そこから各 $j$ 文字目が一致するか照合していく。
-  S  ABCDEABCF
+     S  ABCDEABCF    ABCDEABCF    ABCDEABCF    ...
-  T  ABCF
+     T  ABCF          ABCF          ABCF       ...
-      ABCF
+  照合  ^^^x          x             x          ...
-       ABCF
-一般的な（言語上意味のある）文字列であればほとんど1文字目で失敗するので、愚直といえどほぼ $O(|S|)$ で済むが、
+一般的な（自然言語上意味のある）文字列であればほとんど1文字目で失敗するので、愚直といえどほぼ $O(|S|)$ で済むが、
 同じ文字が多く出現する特殊な場合は、最悪 $O(|S||T|)$ かかる。
@@ ライン 46: / ライン 53: @@
   * [[wpjp>クヌース–モリス–プラット法]]
   * [[https://youtu.be/9MphwmIsO7Q?t=7313|AtCoder Beginner Contest 150 解説]]
+==計算量==
+前計算 $O(|T|)$、検索 $O(|S|)$
+==概要==
 対1の検索アルゴリズム。
-$T$ から「$j$ 文字目で照合失敗したら次のマッチ位置は何文字飛ばせるか」テーブルを事前に作っておく。
+事前に $T$ から「$j$ 文字目で照合失敗したら次は何文字ずらすか」テーブルを作っておき、マッチ位置を試す位置を少なくする。
+++++ もう少し詳細 |
+  前計算テーブル
   j  012345             0  1  2  3  4  5
   T  ABCABD  →  Tbl: [-1, 0, 0, 0, 1, 2]
@@ ライン 65: / ライン 81: @@
 ''Tbl[0] = -1'' となっているのは便宜的なもので、$j=0$ 文字目で失敗した際に次のマッチ位置を1つ進めるため。
-（基本的に照合失敗したら $T$ をずらして、失敗した $S$ 側の文字はもう一度 $T$ と照合されるが、$j=0$ の場合のみ、$S$ 側の文字も進める必要がある）
-計算量は、テーブル作成 $O(|T|)$、探索 $O(|S|)$ で行える。
+照合失敗したら、基本的には失敗した $S$ 側の文字はもう一度 $T$ と照合されるが、$j=0$ の場合のみ、$S$ 側の文字も進める必要がある。
+++++
 ++++ Pythonでの実装例 |
@@ ライン 120: / ライン 137: @@
 対1の検索アルゴリズム。
+===計算量===
+前計算 $O(|T|)$、検索はランダムケースならほぼ $O(\frac{|S|}{|T|})$、最悪 $O(|S||T|)$（最悪を $O(|S|)$ にする改善方法は存在）
+===概要===
 KMP法同様、マッチ位置をスキップしつつずらしていくのだが、文字の照合は後ろからおこなうのが特徴。
@@ ライン 268: / ライン 291: @@
   * [[https://naoya-2.hatenadiary.org/entry/20090405/aho_corasick|Aho Corasick 法 - naoyaのはてなダイアリー]]
-主に $T$ が複数ある場合に用いる。
+主に $T$ が複数ある場合に用いる。（$T$ の集合を $\mathbb{T}$ で表す）
-$T$ の集合をTrie木化しておくことで、$S$ にどれが含まれているかを $O(|S|)$ で一括に検索できる。
+===計算量===
-実装としてはTrie木に辺を追加して、「検索に失敗したとき、次に一致する可能性のある $T$ を探すにはどのノードから再開すればいいか」を効率化している。
+$\mathbb{T}$ の各要素の長さの合計を $m$ とすると、
-構築の方法と何故それで上手くいくのかについては、naoya氏のブログを参照。
+前計算の構築に $O(m)$、検索に $O(|S|+m+マッチ数)$
+===概要===
+$\mathbb{T}$ をTrie木化しておくことで、$S$ にどれが含まれているかを一括に検索できる。
+実装としてはTrie木に戻る辺を追加して、「検索に失敗したとき、次に一致する可能性のある $T$ を探すにはどのノードから再開すればいいか」を効率化している。
+++++ もう少し詳細 |
+==failureの構築==
+Trie木を構築後、各ノードに対し、検索失敗時に戻るノード(failure)を特定する。
+  * '''abcd''' のfailureは、
+    * '''abc''' のfailureの子に '''d''' が
+      * ある→その子
+      * ない→'''abc'''のfailureのfailureの子に '''d''' が
+        * ある→その子
+        * ない→...
+        * failureを再帰的に遡り、根まで遡っても無ければ、根
+幅優先探索で根から近い方から埋めていくことで、遡る時に訪れるfailureが既に確定していることを保証できる。
+==途中で出現する文字列==
+$S=$ '''abcde''' の中から $T=$''{'cd', 'bcde', 'abcdz'}'' を探すことを考える。
+  ○ -- a -- b -- c -- d -- z
+   `--- b -- c -- d -- e
+    `-- c -- d
+'''abcd''' のノードまで辿った後、次の'''e'''が無いのでfailureを辿って'''bcd'''のノードに移り、
+その後'''bcde'''が見つかって終わりになる。
+実際は'''cd'''も含まれるのに、'''cd'''のノードは一回も訪れられない。
+これを捕捉するには、探索中の各ノードで
+「自身のfailure, failureのfailure, failureのfailureのfailure, ...」を根まで遡って調べると見つけることが出来る。
+しかし、実際にそんなことをやっていると時間がかかるので、failureを構築する過程で前計算しておく。
+各ノードが「自身からfailureを遡っていったときに見つかる文字列リスト」matchを持つ。
+  * Trie木の構築時点では、各 $T_i$ の終端を表すノードのmatchに、$T_i$ を登録しておく
+  * failure構築時、自身のmatchに、自身のfailureのmatchを全て足す
+    * 根から近い方から構築するので、failureのmatchには、既にfailureのfailure以前のmatchが含まれている
+こうしておくと、上の例では'''bcd'''のノードのmatchに'cd'が登録されており、見つけることが出来る。
+++++
 ++++ Pythonでの実装例 |
@@ ライン 284: / ライン 355: @@
 class AhoCorasick:
-    def __init__(self, needles):
+    def __init__(self, patterns):
+        self.patterns = patterns
         self.children = [{}]
         self.match = [[]]
-        for needle in needles:
+        for pi, pattern in enumerate(patterns):
-            self._register(needle)
+            self._register(pi, pattern)
-        self.failure = self._create_failure()
+        self.failure = [0] * len(self.children)
+        self._create_failure()
-    def _register(self, needle):
+    def _register(self, pi, pattern):
         k = 0
-        for c in needle:
+        for c in pattern:
             if c in self.children[k]:
                 k = self.children[k][c]
@@ ライン 304: / ライン 377: @@
                 self.match.append([])
                 k = j
-        self.match[k].append(needle)
+        self.match[k].append(pi)
     def _create_failure(self):
         children = self.children
         match = self.match
-        failure = [0] * len(children)
+        failure = self.failure
-        q = deque()
-        for k in children[0].values():
-            failure[k] = 0
-            q.append(k)
+        q = deque(children[0].values())
         while q:
             k = q.popleft()
+            b = failure[k]
             for c, j in children[k].items():
-                b = failure[k]
+                failure[j] = self._next(b, c)
-                failure[j] = self._get_next(b, c, failure)
                 match[j].extend(match[failure[j]])
                 q.append(j)
-        return failure
+    def _next(self, k, c):
-    def _get_next(self, k, c, failure):
         while True:
             if c in self.children[k]:
@@ ライン 332: / ライン 399: @@
             if k == 0:
                 return 0
-            k = failure[k]
+            k = self.failure[k]
-    def search(self, haystack):
+    def search(self, target):
         match = self.match
+        patterns = self.patterns
         k = 0
         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)
-            for m in match[k]:
+            matched.extend((i - len(patterns[m]) + 1, i, patterns[m]) for m in match[k])
-                matched.append((i - len(m) + 1, i, m))
         return matched
-ahc = AhoCorasick(['ab', 'bc', 'bab', 'd', 'ababcde', 'bababcde'])
+ahc = AhoCorasick(['bc', 'd', 'ababcde', 'bababcde', 'ab'])
 print(ahc.search('xbababcdex'))
-# => [(1, 3, 'bab'), (2, 3, 'ab'), (3, 5, 'bab'), (4, 5, 'ab'), (5, 6, 'bc'), (7, 7, 'd'), (1, 8, 'bababcde'), (2, 8, 'ababcde')]
+# => [(2, 3, 'ab'), (4, 5, 'ab'), (5, 6, 'bc'), (7, 7, 'd'), (1, 8, 'bababcde'), (2, 8, 'ababcde')]
 </sxh>
 ++++
@@ ライン 358: / ライン 425: @@
   * [[wpjp>基数木]]
-検索手法というか、データ構造。複数の文字列を木構造で表現する。
+複数の文字列を木構造で表現するデータ構造。
-トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。
+トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。（1辺を1文字と対応させる考え方もあるが、本質は一緒）
 短くて似たような単語が沢山あるとき、特に効率的に保持できる。
@@ ライン 396: / ライン 463: @@
 $S$ の各文字の間に $S$ には絶対に登場しないダミー文字を挟み込むと、偶数長の回文も見つけられる（ダミー文字が中心になったとき）。
+++++ Pythonでの実装 |
+両端と各文字の間に'$'を挿入すると、各要素の「最大値-1」がそこを中心とした回文の長さとなる。
+<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 = 'abcbcdcbcba'
+s = '$' + '$'.join(s) + '$'
+man = manacher(s)
+print(man)
+#        a     b     c     b     c      d     c     b     c     b     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 = 'abccba'
+s = '$' + '$'.join(s) + '$'
+man = manacher(s)
+print(man)
+#        a     b     c     c     b     a
+# => [1, 2, 1, 2, 1, 2, 7, 2, 1, 2, 1, 2, 1]
+</sxh>
+++++