差分

このページの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>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] - はまやんはまやんはまやん]]
@@ 行 120: / 行 122: @@
 対1の検索アルゴリズム。
+===計算量===
+前計算 $O(|T|)$、検索はランダムケースなら $O(\frac{|S|}{|T|})$、最悪 $O(|S||T|)$（最悪を $O(|S|)$ にする改善方法は存在）
+===概要===
 KMP法同様、マッチ位置をスキップしつつずらしていくのだが、文字の照合は後ろからおこなうのが特徴。
@@ 行 268: / 行 276: @@
   * [[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での実装例 |
@@ 行 313: / 行 369: @@
         failure = self.failure
-        q = deque()
+        q = deque(children[0].values())
-        for k in children[0].values():
-            failure[k] = 0
-            q.append(k)
         while q:
             k = q.popleft()
@@ 行 358: / 行 410: @@
   * [[wpjp>基数木]]
-検索手法というか、データ構造。複数の文字列を木構造で表現する。
+複数の文字列を木構造で表現するデータ構造。
-トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。
+トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。（1辺を1文字と対応させる考え方もあるが、本質は一緒）
 短くて似たような単語が沢山あるとき、特に効率的に保持できる。
@@ 行 396: / 行 448: @@
 $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
+        # print(i, j, k, radius)
+        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>
+++++