文字列照合アルゴリズムについて
文字列照合
BM法(BoyerーMoore algorithm）
文字列照合アルゴリズムの一つで、ポイントは文字列の照合を先頭からではなく末尾から行う事で読み飛ばしを行えるという点にあります。
BM法はgrepで用いられています。
KMP法(Knuth-Morris-Pratt Algorithm)
文字列の照合方法の一つで、予めパターン照合テーブルを作成しておくところがポイントです。
計算量は検索されるテキストをSとしたとき O(S)になります。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| def create_pattern_table(w):
""" 照合テーブルを作成する
与えられた文字の先頭部分の文字列と何文字合致しているかを配列で返す
"""
t = [-1]
for j in range(1, len(w)):
k = j - 1
while w[0:k ] != w[j-k:j] and k > 0:
k = k -1
t.append(k)
return t
def kmp(s, w, t):
""" 文字列を先頭から照合して行き、
合致しなかった場合は照合テーブルに指定された数だけずらして照合を継続する。
"""
print(t)
i, j = 0, 0
while i + j < len(s):
if w[j] == s[i + j]:
j = j + 1
if j == len(w):
return i
else:
i = i + j - t[j]
if j > 0:
j = t[j]
w = 'tested'
s = 'testehogehogtestedh'
print(kmp(s, w, create_pattern_table(w)))
|