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

差分

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

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

両方とも前のリビジョン 前のリビジョン
次のリビジョン 		前のリビジョン
programming_algorithm:string_search [2020/01/16]
ikatakos [Aho-Corasick 法] 		programming_algorithm:string_search [2020/01/28] (現在)
ikatakos [Suffix Array(SA-IS法)]
行 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] - はまやんはまやんはまやん]]
 +
 +
 +文字列に関連したアルゴリズムをメモしていく。
 +
 +1つ1つはリンクを参照し詳しくは解説しないが、イメージ的なものと実装例は（なるべく）自分用に書いておく。
 +長くなりすぎたら分けるかも。
 +
 +文字列と言いつつプログラム上は文字コードの数列なので、元から数列であるデータを処理する際にもアルゴリズムは適用できる。
 +
 +文字列に関するアルゴリズムは、主に「検索」や「汎用的なデータ構造を構築」するものが多い。
 +
 +===== 文字列アルゴリズム全体に関連することとか =====
 +
 +=== 計算量 ===
 +
 +文字列アルゴリズムに限定した話ではないが、特に文字列では「平均計算量」と「最悪計算量」に差があるものが多く、この概念を区別したい。
 +
 +文字列比較を例に取ると、通常の言語ではだいたいすぐ失敗するのに対し、
 +わざと一致箇所が多くなるような意地悪な入力を与えると非常に多くの比較を行わなければならない、というケースがある。
 +
 +  * 'apple' と 'orange' は一致しますか？
 +    * →1文字目で失敗するのですぐ No とわかる
 +  * 'aaaaa.....aa' と 'aaaaa...ab' は一致しますか？（10万文字）
 +    * →先頭から10万回比較しないとわからない
 +
 +競技プログラミングではだいたいこういう意地悪ケースが入っているので最悪計算量を意識する必要があるが、実用の上では平均計算量も（というかそちらの方が）重要。
 +
 +ただ、明確に区別しづらかったり、正確な計算量の特定が難しかったりで、各アルゴリズムについて平均と最悪を必ずしも書いてはいない。
 +
 +=== 記号 ===
 +
 +以下、アルゴリズムの対象文字列を $S$ とする。
 +
 +検索の場合は、被検索対象を $S$ とし、見つけ出す文字列を $T$ とする。
 +
 +それぞれが複数ある場合もあるため、それらをまとめて示す場合は $\mathbb{S},\mathbb{T}$ とし、個々の1要素を $S,T$ とする。
 +
 +$S$ の $i$ 文字目を $S_i$ と表す。
 +
 +$S$ の長さを $|S|$ で表す。
  
 ===== 文字列検索アルゴリズム ===== ===== 文字列検索アルゴリズム =====
行 10: 行 52:
  
 ただ使うだけなら、1対1のString型の検索であれば、下手に自力実装するより''find()''など組み込み関数を使った方が一般的には高速となる。 ただ使うだけなら、1対1のString型の検索であれば、下手に自力実装するより''find()''など組み込み関数を使った方が一般的には高速となる。
 +（むしろ以下の内容が既に実装されているはず）
  
 $S$ や $T$ が複数あるのを事前計算で高速化したり、数列を文字列と見なして一致する連続箇所を検索する場合などに、以下のアルゴリズムが有用となる。 $S$ や $T$ が複数あるのを事前計算で高速化したり、数列を文字列と見なして一致する連続箇所を検索する場合などに、以下のアルゴリズムが有用となる。
  
 ==== 愚直（Brute Force） ==== ==== 愚直（Brute Force） ====
 +
 +==計算量==
 +
 +$O(|S||T|)$
 +
 +==概要==
  
 まずは基本。マッチ位置 $i$ を1つずつずらして、そこから各 $j$ 文字目が一致するか照合していく。 まずは基本。マッチ位置 $i$ を1つずつずらして、そこから各 $j$ 文字目が一致するか照合していく。
  
-  S  ABCDEABCF +     S  ABCDEABCF    ABCDEABCF    ABCDEABCF    ...    ABCDEABCF 
-  T  ABCF +     T  ABCF          ABCF          ABCF       ...         ABCF 
-      ABCF +  照合  ooox          x             x          ...         oooo  発見!
-       ABCF+
  
-一般的な（言語上意味のある）文字列であればほとんど1文字目で失敗するので、愚直といえどほぼ $O(|S|)$ で済むが、 +一般的な（自然言語上意味のある）文字列であればほとんど1文字目で失敗するので、愚直といえどほぼ $O(|S|)$ で済む。
-同じ文字が多く出現する特殊な場合は、最悪 $O(|S||T|)$ かかる。+
  
 ++++ Pythonでの実装例 | ++++ Pythonでの実装例 |
行 46: 行 93:
   * [[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]
  
-たとえば $j=5$ 文字目の'''D'''で失敗したら、次のマッチ位置では既に'AB'が一致していることが分かるので、2文字飛ばせることを示す。+たとえば $j=5$ 文字目の'''D'''で失敗したら、次は0,1文字目の'AB'を3,4文字目に合わせた位置で照合を行えばよい（それより左ではもはや一致しないことが $T$ だけからわかる）。 
 +さらにそのマッチ位置では既に'AB'が一致しているので、2文字飛ばせる。
  
   S  ABCABCABD   S  ABCABCABD
行 61: 行 118:
      
   S  ABCABCABD   S  ABCABCABD
-  T     ABCABD    ここまでずらせる （i ← i+j-Tbl[j], j ← Tbl[j]）+  T     ABCABD    ここまでずらせる
           ^^^^    さらに'AB'を飛ばして'C'から探索開始すればいい           ^^^^    さらに'AB'を飛ばして'C'から探索開始すればいい
 +
 +具体的には、$S$ の $i+j$ 文字目と $T$ の $j$ 文字目を照合しつつ $j$ 文字目で失敗した場合、次の位置は以下のようにすればよい。
 +
 +  * $i ← i+j-Tbl[j]$
 +  * $j ← Tbl[j]$
  
 ''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での実装例 |
行 118: 行 181:
  
   * [[wpjp>ボイヤー-ムーア文字列検索アルゴリズム]]   * [[wpjp>ボイヤー-ムーア文字列検索アルゴリズム]]
 +
 +==概要==
  
 1対1の検索アルゴリズム。 1対1の検索アルゴリズム。
  
-KMP法同様、マッチ位置をスキップしつつずらしていくのだが、文字の照合は後ろからおこなうのが特徴。 +KMP法同様、テーブルを作ってマッチ位置をスキップするのだが、文字の照合は後ろからおこなうのが特徴。 
-これにより一般的な文字列検索ではスキップできる期待値が大きくなり、高速なため実用上よく使われている。+ 
 +==計算量== 
 + 
 +前計算 $O(|T|)$、検索はランダムケースならほぼ $O(\frac{|S|}{|T|})$、最悪 $O(|S||T|)$（最悪を $O(|S|)$ にする改善方法は存在） 
 + 
 +++++ もう少し詳細 | 
 + 
 +後ろから照合することで一般的な文字列ではスキップできる期待値が大きくなり、高速となる。 
 +そのため実用上よく使われている。
 だが、同じ文字が多く出現するケースでは遅く、それを解決しようとすると実装が煩雑になる。 だが、同じ文字が多く出現するケースでは遅く、それを解決しようとすると実装が煩雑になる。
  
行 134: 行 207:
           x^           末尾から2番目で照合失敗、失敗時のS側の文字は'C'           x^           末尾から2番目で照合失敗、失敗時のS側の文字は'C'
   S  ...AB[C]DEFGH...   S  ...AB[C]DEFGH...
-  T     CA[C]ABD       失敗位置より左にはじめて出現する'C'までは飛ばせる（[]を合わせる感じ）+  T     CA[C]ABD       失敗位置より左にはじめて出現する'C'までは飛ばせる（[ ]を合わせる感じ）
                x       再度末尾から検索するが、1番目で一致しない                x       再度末尾から検索するが、1番目で一致しない
   S  ...ABCDEFGH...   S  ...ABCDEFGH...
   T           CACABD   'F'はTに出現しないので、丸ごと飛ばせる   T           CACABD   'F'はTに出現しないので、丸ごと飛ばせる
  
-一般的な意味のある文字列では、ほぼ $|T|$ ずつ枠が移動し、 $O(\frac{|S|}{|T|})$ となる。+一般的な文字列では、ほぼ $|T|$ ずつ枠が移動し、 $O(\frac{|S|}{|T|})$ となる。
  
 一方、$S$ や $T$ に同じ文字や並びが何度も出現する場合はスキップが有効に働かず、最悪 $O(|S||T|)$ となる。 一方、$S$ や $T$ に同じ文字や並びが何度も出現する場合はスキップが有効に働かず、最悪 $O(|S||T|)$ となる。
行 161: 行 234:
                         また、この照合では先頭の'BC'は一致がわかっているので比較しなくてよい                         また、この照合では先頭の'BC'は一致がわかっているので比較しなくてよい
 */ */
 +
 +++++
  
 ==== Rabin-Karp法（ローリングハッシュ） ==== ==== Rabin-Karp法（ローリングハッシュ） ====
行 166: 行 241:
   * [[wpjp>ラビン-カープ文字列検索アルゴリズム]]   * [[wpjp>ラビン-カープ文字列検索アルゴリズム]]
  
-一定の長さの文字列をハッシュ化して1つの数字にした上で、ハッシュ値で検索するアルゴリズム。+== 概要 ==
  
-=== 計算量 ===+一定の長さの文字列をハッシュ化（1つの整数）にした上で、ハッシュ値で検索するアルゴリズム。 
 + 
 +1対1でも使えるし、$T$ が複数ある場合でも、文字列長が同じであれば事前計算結果を使い回せる。 
 + 
 +== 計算量 ==
  
 ハッシュ化に $O(|S|+|T|)$、検索に $O(|S|)$ ハッシュ化に $O(|S|+|T|)$、検索に $O(|S|)$
  
-=== 概要 ===+++++ もう少し詳細 |
  
-KMP・BM法がマッチ位置を試す数を減らして高速化するのに対し、こちらは特定のマッチ位置における文字同士の照合を高速化する。+KMP法やBM法がマッチ位置を試す回数を減らして高速化するのに対し、こちらは特定のマッチ位置における文字列同士の照合を高速化する。
  
 事前計算として、$S$ から開始位置を1つずつずらしたハッシュ列 $S'$ を作成しておく。 事前計算として、$S$ から開始位置を1つずつずらしたハッシュ列 $S'$ を作成しておく。
 $T$ も全体のハッシュ値 $T'$ を求める。 $T$ も全体のハッシュ値 $T'$ を求める。
 すると検索は、数列 $S'$ から1つの数字 $T'$ を探す処理になる。 すると検索は、数列 $S'$ から1つの数字 $T'$ を探す処理になる。
 +
 +  S   a b c a b c d       T   a b c d
 +           ↓                 ↓
 +  S' [ 53, 27, 38, 5 ]    T'  5          (ハッシュ値は適当)
  
 $T$ が複数ある場合、長さが同じであれば、$S'$ を共有できる。 $T$ が複数ある場合、長さが同じであれば、$S'$ を共有できる。
  
 ハッシュの計算には、1つ前の値から次のハッシュ値を高速に計算できる「ローリングハッシュ」を用いる。 ハッシュの計算には、1つ前の値から次のハッシュ値を高速に計算できる「ローリングハッシュ」を用いる。
-整数 $X$ と $M$ を決め、文字列を $X$ 進法の数字とみなす。大きくなりすぎるので $M$ でmodを取る。+アイデアとしては、整数 $X$ と $M$ を決め、文字列を $X$ 進法の数字とみなす感じ。大きくなりすぎるので $M$ でmodを取る。
  
 比較的理解と実装が簡単だが、ハッシュ衝突（違う文字列が同じハッシュ値になってしまう）があるので、なるべく $M$ を大きい素数とし、$X$ を変えて2～3回試すのがよい。 比較的理解と実装が簡単だが、ハッシュ衝突（違う文字列が同じハッシュ値になってしまう）があるので、なるべく $M$ を大きい素数とし、$X$ を変えて2～3回試すのがよい。
行 191: 行 274:
   * [[https://qiita.com/keymoon/items/11fac5627672a6d6a9f6|安全で爆速なRollingHashの話 - Qiita]]   * [[https://qiita.com/keymoon/items/11fac5627672a6d6a9f6|安全で爆速なRollingHashの話 - Qiita]]
  
-またこれは、2次元にも拡張できる。+またこれは、2次元にも拡張できる。（ある矩形領域が特定のパターンである場所はあるか？その位置は？） 
 + 
 +++++
  
 ++++ Pythonでの実装例 | ++++ Pythonでの実装例 |
行 268: 行 353:
   * [[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$ の集合をTrie木化しておくことで、$S$ にどれが含まれているかを $O(|S|)$ で一括に検索できる。+主に $T$ が複数ある場合に用いる（$T$ の集合を $\mathbb{T}$ で表す）。
  
-実装としてはTrie木に辺を追加して、「検索に失敗したとき、次に一致する可能性のある $T$ を探すにはどのノードから再開すればいいか」を効率化している。+$\mathbb{T}$ の方を前計算するので、$\mathbb{T}$ は固定的であり、$S$ の方を様々に変更して検索する用途に向く。
  
-構築の方法と何故それで上手くいくのかについては、naoya氏のブログを参照。+前計算の実装としては、$\mathbb{T}$ からTrie木を構築、さらに「検索に失敗したとき、次に一致する可能性のある $T$ を探すにはどのノードから再開すればいいか」を前計算し、有限オートマトンを生成する。 
 + 
 +検索では $S$ を1文字ずつ順番に見て、前計算結果に従い遷移する。 
 + 
 +==計算量== 
 + 
 +$\mathbb{T}$ の各要素の長さの合計を $m$ とすると、 
 + 
 +前計算の構築に $O(m)$、検索に $O(|S|+m+マッチ数)$ 
 + 
 +++++ もう少し詳細 | 
 + 
 +==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: 行 419:
 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: 行 441:
                 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: 行 463:
             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>
 ++++ ++++
 +
 +==== Suffix Array(SA-IS法) ====
 +
 +  * [[wpjp>接尾辞配列]]
 +  * [[https://speakerdeck.com/flare/sa-is|SA-IS - Speaker Deck]]
 +
 +==概要==
 +
 +Suffix Arrayの説明自体は上のサイトや他に溢れてるので、割愛。
 +これを線形時間で構築するのがSA-ISと呼ばれるアルゴリズム。
 +
 +SAで文字列検索を行うには、二分探索を用いる。
 +辞書順に並んでいるため、$S$ の中に $T$（を接頭辞とした文字列）が出現するかどうかは二分探索で調べられる。
 +複数出現する場合もSA上で連続しているので、始まりと終わりの境界を探索すればよい。
 +
 +  * SA-IS法について、Rubyでの実装例を追いながら、データの中身を含めて解説してくれているサイト
 +    * [[https://mametter.hatenablog.com/entry/20180130/p1|SA-IS 法のメモ - まめめも]]
 +
 +==計算量==
 +
 +  * 前計算
 +    * $O(|S|)$
 +  * 検索
 +    * $O(|T| \log|S|)$
 +
 +++++ PythonでのSA-ISの実装 |
 +
 +  * ''make_suffix_array()'' を呼ぶ
 +  * aaaは数列で与える点に注意（途中でsa_is()を再帰的に呼ぶが、その際にaaaは数列の方が都合がいいため）
 +  * ''make_suffix_array()'' 内で末尾に最小のダミー要素として[-1]を加えているが、aaaの最小値に応じて適宜変更する
 +
 +<sxh python>
 +from collections import Counter
 +from itertools import accumulate
 +from operator import itemgetter
 +
 +def induced_sort(n, aaa, lsa, lmss, a_acc, a_dic, ak):
 +    """
 +    :param lsa: L-S Array
 +    :param lmss: Leftmost S の配列（この順番により結果は変化する）
 +    :return:
 +    """
 +
 +    sa = [-1] * n
 +
 +    counter = [0] * ak
 +    for i in reversed(lmss):
 +        di = a_dic[aaa[i]]
 +        sa[a_acc[di + 1] - 1 - counter[di]] = i
 +        counter[di] += 1
 +
 +    counter = [0] * ak
 +    for i in sa:
 +        if i <= 0:
 +            continue
 +        if lsa[i - 1] == 0:
 +            continue
 +        di = a_dic[aaa[i - 1]]
 +        sa[a_acc[di] + counter[di]] = i - 1
 +        counter[di] += 1
 +
 +    counter = [0] * ak
 +    for i in reversed(sa):
 +        if i <= 0:
 +            continue
 +        if lsa[i - 1] == 1:
 +            continue
 +        di = a_dic[aaa[i - 1]]
 +        sa[a_acc[di + 1] - 1 - counter[di]] = i - 1
 +        counter[di] += 1
 +
 +    return sa
 +
 +
 +def sa_is(n: int, aaa: list, a_acc: list, a_dic: dict, ak: int):
 +    """
 +    :param n: aaaの長さ
 +    :param aaa: Suffix Arrayを求めたい数列
 +               （初回呼び出し時は末尾に最小ダミー要素を1つ追加すること）
 +    :param a_acc: 頭文字がa_dic[a]の要素がSA上で並び始めるindex
 +    :param a_dic: aaaの各要素に昇順に割り当てる連番
 +    :param ak: aaaに出現する要素の種類数（len(a_dic)）
 +    :return:
 +    """
 +
 +    # LS array
 +    lsa = [0] * n  # 0:S, 1:L
 +    for i in range(n - 2, -1, -1):
 +        if aaa[i] == aaa[i + 1]:
 +            lsa[i] = lsa[i + 1]
 +        elif aaa[i] > aaa[i + 1]:
 +            lsa[i] = 1
 +
 +    # LeftMost S
 +    lmss = [i for i, (lsl, lsr) in enumerate(zip(lsa, lsa[1:]), start=1)
 +            if lsl == 1 and lsr == 0]
 +
 +    sa = induced_sort(n, aaa, lsa, lmss, a_acc, a_dic, ak)
 +
 +    lms_set = set(lmss)
 +    sa = [i for i in sa if i in lms_set]
 +
 +    nums = [-1] * n
 +    nums[sa[0]] = num = 0
 +
 +    for i, j in zip(sa, sa[1:]):
 +
 +        for d in range(n):
 +            is_id_lms = i + d in lms_set
 +            is_jd_lms = j + d in lms_set
 +            if aaa[i + d] != aaa[j + d] or (is_id_lms != is_jd_lms):
 +                num += 1
 +                break
 +            elif d > 0 and (is_id_lms or is_jd_lms):
 +                break
 +
 +        nums[j] = num
 +
 +    nums = [i for i in nums if i != -1]
 +
 +    if num < len(nums) - 1:
 +        sa = sa_is(num + 1, nums)
 +        lmss2 = list(map(lmss.__getitem__, sa))
 +    else:
 +        lmss2 = [lmss[i] for i, j in sorted(enumerate(nums), key=itemgetter(1))]
 +
 +    sa = induced_sort(n, aaa, lsa, lmss2, a_acc, a_dic, ak)
 +
 +    return sa
 +
 +def make_suffix_array(aaa):
 +    n = len(aaa)
 +    a_cnt = Counter(aaa)
 +    a_kind = sorted(a_cnt.keys())
 +    a_dic = {a: i for i, a in enumerate(a_kind)}
 +    a_acc = list(accumulate([0] + list(map(a_cnt.get, a_kind))))
 +    ak = len(a_kind)
 +
 +    # [-1] はaaa内のどの要素より小さい要素（適宜変更する）
 +    sa = sa_is(n + 1, aaa + [-1], a_acc, a_dic, ak)
 +    return sa
 +
 +</sxh>
 +
 +++++
 +
 +==== FM-index ====
 +
 +  * [[wp>FM-index]]
 +  * [[https://www.slideshare.net/kujira16/fmindex|FM-indexによる全文検索]]
 +
 +==概要==
 +
 +主に $T$ が複数ある場合に用いる。（別に複数で無くてもよいが、1対1なら前処理にかかる時間を考えると他のアルゴリズムを用いた方がよい）
 +
 +$S$ を前計算するので、$S$ が固定的であり、$T$ を様々に変えて検索する用途に向く。
 +
 +前計算では $S$ をBWT(Burrows Wheeler変換)しておき、検索で $T$ の各接尾辞が出現するかをチェックする。
 +
 +これまでのアルゴリズムと比べて新しく、性能はいいが理解・実装も複雑。
 +
 +==計算量==
 +
 +  * 前計算
 +    * 理解しやすいが低速 $O(|S|^2 \log{|S|})$
 +    * 難しいが高速 $O(|S| \log{|S|})$
 +    * $O(|S|)$ などのアルゴリズムもあるが、自然言語に対しては実用上、上の方がよいらしい
 +  * 1回の検索
 +    * 出現する文字の種類数を $\sigma$ として、$O(|T| \log{\sigma})$
 +
 ===== 文字列を効率的に保持するアルゴリズム ===== ===== 文字列を効率的に保持するアルゴリズム =====
  
行 358: 行 659:
   * [[wpjp>基数木]]   * [[wpjp>基数木]]
  
-検索手法というか、データ構造。複数の文字列を木構造で表現する。+複数の文字列を木構造で表現するデータ構造。
  
-トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。+トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。（1辺を1文字と対応させる考え方もあるが、本質は一緒）
 短くて似たような単語が沢山あるとき、特に効率的に保持できる。 短くて似たような単語が沢山あるとき、特に効率的に保持できる。
  
行 378: 行 679:
   * [[https://naoya-2.hatenadiary.org/entry/20081016/1224173077|Burrows Wheeler Transform と Suffix Array - naoyaのはてなダイアリー]]   * [[https://naoya-2.hatenadiary.org/entry/20081016/1224173077|Burrows Wheeler Transform と Suffix Array - naoyaのはてなダイアリー]]
  
-検索ではなく、文字列を同じ文字が連続しやすいように可逆変換するアルゴリズム。+文字列を同じ文字が連続しやすいように可逆変換するアルゴリズム。
 主に圧縮の前処理に用いる（同じ文字が連続していれば圧縮効率がよくなる） 主に圧縮の前処理に用いる（同じ文字が連続していれば圧縮効率がよくなる）
  
行 389: 行 690:
  
 ==== Manacher ==== ==== Manacher ====
 +
 +  * [[https://snuke.hatenablog.com/entry/2014/12/02/235837|文字列の頭良い感じの線形アルゴリズムたち２ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ]]
 +
 +==概要==
  
 文字列 $S$ から奇数長の最長の回文を $O(|S|)$ で検索するアルゴリズム。 文字列 $S$ から奇数長の最長の回文を $O(|S|)$ で検索するアルゴリズム。
  
-  * [[https://snuke.hatenablog.com/entry/2014/12/02/235837|文字列の頭良い感じの線形アルゴリズムたち２ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ]]+$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