[[文字列アルゴリズム]]
現在位置: トップページ » アルゴリズム » 文字列アルゴリズム
文書の表示
管理サイトマップ

差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン		前のリビジョン
次のリビジョン両方とも次のリビジョン
programming_algorithm:string_search [2020/01/17] – [Aho-Corasick 法] ikatakosprogramming_algorithm:string_search [2020/01/17] – [Manacher] 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] - はまやんはまやんはまやん]]   * [[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） ==== ==== 愚直（Brute Force） ====
 +
 +==計算量==
 +
 +$O(|S||T|)$
 +
 +==概要==
  
 まずは基本。マッチ位置 $i$ を1つずつずらして、そこから各 $j$ 文字目が一致するか照合していく。 まずは基本。マッチ位置 $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|)$ かかる。 同じ文字が多く出現する特殊な場合は、最悪 $O(|S||T|)$ かかる。
  
行 46: 行 53:
   * [[wpjp>クヌース–モリス–プラット法]]   * [[wpjp>クヌース–モリス–プラット法]]
   * [[https://youtu.be/9MphwmIsO7Q?t=7313|AtCoder Beginner Contest 150 解説]]   * [[https://youtu.be/9MphwmIsO7Q?t=7313|AtCoder Beginner Contest 150 解説]]
 +
 +==計算量==
 +
 +前計算 $O(|T|)$、検索 $O(|S|)$
 +
 +==概要==
  
 1対1の検索アルゴリズム。 1対1の検索アルゴリズム。
  
-$T$ から「$j$ 文字目で照合失敗したら次のマッチ位置は何文字飛ばせるか」テーブルを事前に作っておく。+事前に $T$ から「$j$ 文字目で照合失敗したら次は何文字ずらすか」テーブルを作っておき、マッチ位置を試す位置を少なくする。 
 + 
 +++++ もう少し詳細 |
  
 +  前計算テーブル
   j  012345             0  1  2  3  4  5   j  012345             0  1  2  3  4  5
   T  ABCABD  →  Tbl: [-1, 0, 0, 0, 1, 2]   T  ABCABD  →  Tbl: [-1, 0, 0, 0, 1, 2]
行 65: 行 81:
  
 ''Tbl[0] = -1'' となっているのは便宜的なもので、$j=0$ 文字目で失敗した際に次のマッチ位置を1つ進めるため。 ''Tbl[0] = -1'' となっているのは便宜的なもので、$j=0$ 文字目で失敗した際に次のマッチ位置を1つ進めるため。
-（基本的に照合失敗したら $T$ をずらして、失敗した $S$ 側の文字はもう一度 $T$ と照合されるが、$j=0$ の場合のみ、$S$ 側の文字も進める必要がある） 
  
-計算量は、テーブル作成 $O(|T|)$、探索 $O(|S|)$ で行える。+照合失敗したら、基本的には失敗した $S$ 側の文字はもう一度 $T$ と照合されるが、$j=0$ の場合のみ、$S$ 側の文字も進める必要がある。 
 + 
 +++++
  
 ++++ Pythonでの実装例 | ++++ Pythonでの実装例 |
行 120: 行 137:
  
 1対1の検索アルゴリズム。 1対1の検索アルゴリズム。
 +
 +===計算量===
 +
 +前計算 $O(|T|)$、検索はランダムケースならほぼ $O(\frac{|S|}{|T|})$、最悪 $O(|S||T|)$（最悪を $O(|S|)$ にする改善方法は存在）
 +
 +===概要===
  
 KMP法同様、マッチ位置をスキップしつつずらしていくのだが、文字の照合は後ろからおこなうのが特徴。 KMP法同様、マッチ位置をスキップしつつずらしていくのだが、文字の照合は後ろからおこなうのが特徴。
行 268: 行 291:
   * [[https://naoya-2.hatenadiary.org/entry/20090405/aho_corasick|Aho Corasick 法 - naoyaのはてなダイアリー]]   * [[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での実装例 | ++++ Pythonでの実装例 |
行 285: 行 356:
  
     def __init__(self, patterns):     def __init__(self, patterns):
 +        self.patterns = patterns
         self.children = [{}]         self.children = [{}]
         self.match = [[]]         self.match = [[]]
行 291: 行 363:
             self._register(pi, pattern)             self._register(pi, pattern)
  
-        self.failure = self._create_failure() +        self.failure = [0] * len(self.children) 
-        self.patterns = patterns+        self._create_failure()
  
     def _register(self, pi, pattern):     def _register(self, pi, pattern):
行 310: 行 382:
         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(): +
-            failure[k] = 0 +
-            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 +    def _next(self, k, c):
- +
-    def _get_next(self, k, c, failure):+
         while True:         while True:
             if c in self.children[k]:             if c in self.children[k]:
行 333: 行 399:
             if k == 0:             if k == 0:
                 return 0                 return 0
-            k = failure[k]+            k = self.failure[k]
  
     def search(self, target):     def search(self, target):
行 342: 行 408:
         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: 行 425:
   * [[wpjp>基数木]]   * [[wpjp>基数木]]
  
-検索手法というか、データ構造。複数の文字列を木構造で表現する。+複数の文字列を木構造で表現するデータ構造。
  
-トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。+トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。（1辺を1文字と対応させる考え方もあるが、本質は一緒）
 短くて似たような単語が沢山あるとき、特に効率的に保持できる。 短くて似たような単語が沢山あるとき、特に効率的に保持できる。
  
行 397: 行 463:
 $S$ の各文字の間に $S$ には絶対に登場しないダミー文字を挟み込むと、偶数長の回文も見つけられる（ダミー文字が中心になったとき）。 $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>
 +
 +++++
  
programming_algorithm/string_search.txt · 最終更新: 2023/06/27 by ikatakos
文書の表示
メディアマネージャー文書の先頭へ
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0