差分

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

この比較画面にリンクする

両方とも前のリビジョン 前のリビジョン
次のリビジョン
前のリビジョン
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] - はまやんはまやんはまやん]]   * [[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での実装例 |
ライン 284: ライン 355:
 class AhoCorasick:​ class AhoCorasick:​
  
-    def __init__(self, ​needles):+    def __init__(self, ​patterns): 
 +        self.patterns = patterns
         self.children = [{}]         self.children = [{}]
         self.match = [[]]         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         k = 0
-        for c in needle:+        for c in pattern:
             if c in self.children[k]:​             if c in self.children[k]:​
                 k = self.children[k][c]                 k = self.children[k][c]
ライン 304: ライン 377:
                 self.match.append([])                 self.match.append([])
                 k = j                 k = j
-        self.match[k].append(needle)+        self.match[k].append(pi)
  
     def _create_failure(self):​     def _create_failure(self):​
         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]
             for c, j in children[k].items():​             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]])                 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]:​
ライン 332: ライン 399:
             if k == 0:             if k == 0:
                 return 0                 return 0
-            k = failure[k]+            k = self.failure[k]
  
-    def search(self, ​haystack):+    def search(self, ​target):
         match = self.match         match = self.match
 +        patterns = self.patterns
  
         k = 0         k = 0
         matched = []         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         return matched
  
  
-ahc = AhoCorasick(['​ab', ​'​bc',​ 'bab', 'd', 'ababcde', 'bababcde'])+ahc = AhoCorasick(['​bc',​ 'd', 'ababcde', 'bababcde', 'ab'])
 print(ahc.search('​xbababcdex'​)) 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>​ </​sxh>​
 ++++ ++++
ライン 358: ライン 425:
   * [[wpjp>​基数木]]   * [[wpjp>​基数木]]
  
-検索手法というか、データ構造。複数の文字列を木構造で表現する。+複数の文字列を木構造で表現するデータ構造
  
-トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。+トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。(1辺を1文字と対応させる考え方もあるが、本質は一緒)
 短くて似たような単語が沢山あるとき、特に効率的に保持できる。 短くて似たような単語が沢山あるとき、特に効率的に保持できる。
  
ライン 396: ライン 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.1579178520.txt.gz · 最終更新: 2020/01/16 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0