文書の過去の版を表示しています。
文字列アルゴリズム
文字列検索アルゴリズム
文字列 $S$ から文字列 $T$ を検索する手法あれこれ。
ただ使うだけなら、1対1のString型の検索であれば、下手に自力実装するよりfind()など組み込み関数を使った方が一般的には高速となる。
$S$ や $T$ が複数あるのを事前計算で高速化したり、数列を文字列と見なして一致する連続箇所を検索する場合などに、以下のアルゴリズムが有用となる。
愚直（Brute Force）
計算量
概要
まずは基本。マッチ位置 $i$ を1つずつずらして、そこから各 $j$ 文字目が一致するか照合していく。
S ABCDEABCF ABCDEABCF ABCDEABCF ...
T ABCF ABCF ABCF ...
照合 ^^^x x x ...
一般的な（自然言語上意味のある）文字列であればほとんど1文字目で失敗するので、愚直といえどほぼ $O(|S|)$ で済むが、
同じ文字が多く出現する特殊な場合は、最悪 $O(|S||T|)$ かかる。
Pythonでの実装例
def brute_force(s, t):
matched_indices = []
n = len(s)
m = len(t)
for i in range(n - m + 1):
for j in range(m):
if s[i + j] != t[j]:
break
else:
matched_indices.append(i)
return matched_indices
KMP法
計算量
概要
1対1の検索アルゴリズム。
事前に $T$ から「$j$ 文字目で照合失敗したら次は何文字ずらすか」テーブルを作っておき、マッチ位置を試す位置を少なくする。
もう少し詳細
前計算テーブル
j 012345 0 1 2 3 4 5
T ABCABD → Tbl: [-1, 0, 0, 0, 1, 2]
たとえば $j=5$ 文字目の'D'で失敗したら、次のマッチ位置では既に'AB'が一致していることが分かるので、2文字飛ばせることを示す。
S ABCABCABD
T ABCABD
^^^^^x ここで失敗 （i=0, j=5）
S ABCABCABD
T ABCABD ここまでずらせる （i ← i+j-Tbl[j], j ← Tbl[j]）
^^^^ さらに'AB'を飛ばして'C'から探索開始すればいい
Tbl[0] = -1 となっているのは便宜的なもので、$j=0$ 文字目で失敗した際に次のマッチ位置を1つ進めるため。
照合失敗したら、基本的には失敗した $S$ 側の文字はもう一度 $T$ と照合されるが、$j=0$ の場合のみ、$S$ 側の文字も進める必要がある。
Pythonでの実装例
1つ見つかったら終了ではなく一致箇所全てを求めるため、テーブルサイズを1つ長くし、最後まで一致した後に次に合わせるべき位置も計算している。
def make_kmp_table(t):
i = 2
j = 0
m = len(t)
tbl = [0] * (m + 1)
tbl[0] = -1
while i <= m:
if t[i - 1] == t[j]:
tbl[i] = j + 1
i += 1
j += 1
elif j > 0:
j = tbl[j]
else:
tbl[i] = 0
i += 1
return tbl
def kmp(s, t):
matched_indices = []
tbl = make_kmp_table(t)
i = 0
j = 0
n = len(s)
m = len(t)
while i + j < n:
if t[j] == s[i + j]:
j += 1
if j == m:
matched_indices.append(i)
i += j - tbl[j]
j = tbl[j]
else:
i += j - tbl[j]
if j > 0:
j = tbl[j]
return matched_indices
Boyer-Moore 法
計算量
前計算 $O(|T|)$、検索はランダムケースならほぼ $O(\frac{|S|}{|T|})$、最悪 $O(|S||T|)$（最悪を $O(|S|)$ にする改善方法は存在）
概要
KMP法同様、マッチ位置をスキップしつつずらしていくのだが、文字の照合は後ろからおこなうのが特徴。
これにより一般的な文字列検索ではスキップできる期待値が大きくなり、高速なため実用上よく使われている。
だが、同じ文字が多く出現するケースでは遅く、それを解決しようとすると実装が煩雑になる。
あらかじめ $T$ からテーブルを作成する。
ただ、テーブルの作り方も複数あって、「不一致文字規則」「一致suffix規則」「両方計算してスキップできる距離の大きい方」が存在する。
不一致文字規則は実装は簡単だが、文字の種類が少ない場合に効果が少ない。一致suffix規則はちょっと複雑。
不一致文字規則の例
S ...ABCDEFGH...
T CACABD
x^ 末尾から2番目で照合失敗、失敗時のS側の文字は'C'
S ...AB[C]DEFGH...
T CA[C]ABD 失敗位置より左にはじめて出現する'C'までは飛ばせる（[]を合わせる感じ）
x 再度末尾から検索するが、1番目で一致しない
S ...ABCDEFGH...
T CACABD 'F'はTに出現しないので、丸ごと飛ばせる
一般的な意味のある文字列では、ほぼ $|T|$ ずつ枠が移動し、 $O(\frac{|S|}{|T|})$ となる。
一方、$S$ や $T$ に同じ文字や並びが何度も出現する場合はスキップが有効に働かず、最悪 $O(|S||T|)$ となる。
Horspoolのアルゴリズム、Sundayのアルゴリズムでは、不一致となったときに参照する文字を変えることで、実用上の平均計算時間が改善する。
線形時間を保証するには、移動量テーブル作成時、「不一致となった所までは一致していた」という情報を使う Galil 規則というものを導入すればよい。
Rabin-Karp法（ローリングハッシュ）
一定の長さの文字列をハッシュ化して1つの数字にした上で、ハッシュ値で検索するアルゴリズム。
計算量
ハッシュ化に $O(|S|+|T|)$、検索に $O(|S|)$
概要
KMP・BM法がマッチ位置を試す数を減らして高速化するのに対し、こちらは特定のマッチ位置における文字同士の照合を高速化する。
事前計算として、$S$ から開始位置を1つずつずらしたハッシュ列 $S'$ を作成しておく。
$T$ も全体のハッシュ値 $T'$ を求める。
すると検索は、数列 $S'$ から1つの数字 $T'$ を探す処理になる。
$T$ が複数ある場合、長さが同じであれば、$S'$ を共有できる。
ハッシュの計算には、1つ前の値から次のハッシュ値を高速に計算できる「ローリングハッシュ」を用いる。
整数 $X$ と $M$ を決め、文字列を $X$ 進法の数字とみなす。大きくなりすぎるので $M$ でmodを取る。
比較的理解と実装が簡単だが、ハッシュ衝突（違う文字列が同じハッシュ値になってしまう）があるので、なるべく $M$ を大きい素数とし、$X$ を変えて2～3回試すのがよい。
その際、Hackのある競プロサイトでは撃墜されるのを防ぐため、ランダム化するのを推奨されている。
またこれは、2次元にも拡張できる。
Pythonでの実装例
1対1の検索なら、まず $T$ をハッシュ化し、その後 $S$ をずらしてハッシュ化する過程で照合すればよい。僅かだがリスト化などの生成コストが抑えられる。
Pythonは多倍長整数を扱えるので、特別な書き方をしなくても $X,M$ に比較的大きな値を設定できる。
def rabin_karp(s, t):
def exe(x, m):
th = 0
for c in tt:
th = (th * x + c) % m
sh = 0
for c in st[:l]:
sh = (sh * x + c) % m
xl = pow(x, l - 1, m)
matched = set()
if sh == th:
matched.add(0)
for i, (c0, c1) in enumerate(zip(st, st[l:]), start=1):
sh = ((sh - c0 * xl) * x + c1) % m
if sh == th:
matched.add(i)
return matched
l = len(t)
st = list(map(ord, s))
tt = list(map(ord, t))
# Xはなるべくst,ttの最大要素より大きくする
# Mはとりあえず2^61-1(素数)を設定する
xs = random.sample(range(10 ** 9, 10 ** 10), 3)
ans = exe(xs[0], 2305843009213693951)
ans.intersection_update(exe(xs[1], 2305843009213693951))
ans.intersection_update(exe(xs[2], 2305843009213693951))
return sorted(ans)
Bitap法
1対1の検索アルゴリズム。
照合状態をbit列であらわし、$S$ を1文字ずつ進めながらbit演算で遷移させていく。
下から $i$ 桁目が'1'であれば、$T$ の先頭から $i$ 番目までは一致していることを表す。
またこれはあいまい検索にも対応し、「'?'は何の文字が入ってもいい」「レーベンシュタイン距離が $N$ 以下」などの検索が可能となる。
Z-algorithm
これ自体は検索ではなく、文字列 $S$ の各開始位置 $i$ に対して、「$S$ と $S[i:]$ が先頭何文字まで一致するか？（最長共通接頭辞数）」を構築するアルゴリズム。
i 0123456789012
S ABCABCZABCABC
Z 13003000600300
愚直にやると最悪 $O(|S|^2)$ かかるところ、一度見たところを飛ばして $O(|S|)$ でできる。
これを文字列検索に生かすには、$S$ と $T$ を、$S$ の中に絶対存在しない文字（$\$$ とする）でつなぎ、$T\$S$ とする。
$S$ の開始位置よりZ-algorithmを適用すれば、値が $|T|$ と等しくなる箇所が、$S$ 上で $T$ が出現する位置である。
Aho-Corasick 法
主に $T$ が複数ある場合に用いる。（$T$ の集合を $\mathbb{T}$ で表す）
計算量
$\mathbb{T}$ の各要素の長さの合計を $m$ とすると、
前計算の構築に $O(m)$、検索に $O(|S|+m+マッチ数)$
概要
$\mathbb{T}$ をTrie木化しておくことで、$S$ にどれが含まれているかを一括に検索できる。
実装としてはTrie木に戻る辺を追加して、「検索に失敗したとき、次に一致する可能性のある $T$ を探すにはどのノードから再開すればいいか」を効率化している。
もう少し詳細
failureの構築
Trie木を構築後、各ノードに対し、検索失敗時に戻るノード(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を持つ。
こうしておくと、上の例では'bcd'のノードのmatchに'cd'が登録されており、見つけることが出来る。
Pythonでの実装例
from collections import deque
class AhoCorasick:
def __init__(self, patterns):
self.patterns = patterns
self.children = [{}]
self.match = [[]]
for pi, pattern in enumerate(patterns):
self._register(pi, pattern)
self.failure = [0] * len(self.children)
self._create_failure()
def _register(self, pi, pattern):
k = 0
for c in pattern:
if c in self.children[k]:
k = self.children[k][c]
else:
j = len(self.children)
self.children[k][c] = j
self.children.append({})
self.match.append([])
k = j
self.match[k].append(pi)
def _create_failure(self):
children = self.children
match = self.match
failure = self.failure
q = deque(children[0].values())
while q:
k = q.popleft()
b = failure[k]
for c, j in children[k].items():
failure[j] = self._next(b, c)
match[j].extend(match[failure[j]])
q.append(j)
def _next(self, k, c):
while True:
if c in self.children[k]:
return self.children[k][c]
if k == 0:
return 0
k = self.failure[k]
def search(self, target):
match = self.match
patterns = self.patterns
k = 0
matched = []
for i, c in enumerate(target):
k = self._next(k, c)
matched.extend((i - len(patterns[m]) + 1, i, patterns[m]) for m in match[k])
return matched
ahc = AhoCorasick(['bc', 'd', 'ababcde', 'bababcde', 'ab'])
print(ahc.search('xbababcdex'))
# => [(2, 3, 'ab'), (4, 5, 'ab'), (5, 6, 'bc'), (7, 7, 'd'), (1, 8, 'bababcde'), (2, 8, 'ababcde')]
文字列を効率的に保持するアルゴリズム
Trie木、Patricia木
複数の文字列を木構造で表現するデータ構造。
トライ木は、文字列の集合を1文字を1ノードとした木構造に変換したもの。（1辺を1文字と対応させる考え方もあるが、本質は一緒）
短くて似たような単語が沢山あるとき、特に効率的に保持できる。
パトリシア木は、それを複数文字も1ノードになり得るとしたもの。
実装はやや複雑になるが、長い単語がある場合でも肥大化を防ぐことができる。
Suffix tree
検索ではなく、文字列を同じ文字が連続しやすいように可逆変換するアルゴリズム。
主に圧縮の前処理に用いる（同じ文字が連続していれば圧縮効率がよくなる）
自然言語でもデータでも、だいたいお決まりの文字（数字）の並びというのが発生しやすいことを利用している。
例えば英語では、子音の後はだいたい母音だったり、'tr', 'sh', 'ck' などが頻出しやすい。
逆に完全にランダムなデータにはあまり効かない（と思う）。
その他
Manacher
文字列 $S$ から奇数長の最長の回文を $O(|S|)$ で検索するアルゴリズム。
$S$ の各文字の間に $S$ には絶対に登場しないダミー文字を挟み込むと、偶数長の回文も見つけられる（ダミー文字が中心になったとき）。
Pythonでの実装
両端と各文字の間に'$'を挿入すると、各要素の「最大値-1」がそこを中心とした回文の長さとなる。
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]
