개요
공부 겸 패턴매칭 알고리즘을 정리해보자
문자열 t에서 패턴 p를 찾는 알고리즘.
i를 t의 index, j를 p의 index
N, M이 각각 t와 p의 길이이다.
해당 구현들은 선 비교 후 커서 이동 순이므로, 패턴 매칭이 실패하였을 때, j를 0이 아닌 -1로 초기화한다. 그래야 바로 커서이동이 되어 j=0이 된다.
1. 고지식한 패턴 검색
아이디어
본문 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식
구현
def BruteForce(pat,text):
N = len(text)
M = len(pat)
i = j = 0
anw = []
while i < N:
if pat[j] != text[i]:
i = i-j
j = -1
i = i + 1
j = j + 1
if j == M:
anw.append([i-M,text[i-M:i]])
j = 0
return anw출력
p = 'abcdabcef' # pattern
t = 'alksdabcdabcflaskjflkabcdjsaflkjasdkdsajfabcdabceflksadjabcdaksfjffsdafabcdabcef'
print(BruteForce(p,t))[[41, 'abcdabcef'], [71, 'abcdabcef']]특징
최악의 경우
t[i] 와 p[j]를 비교해가며 맞으면 i와 j를 같이 키운다.
j가 M에 도달하면 패턴을 찾은것이니 반환
t[i]와 p[j]가 다르면 패턴검색에 실패한 것이니
i = i-j+1 로 다음 문자열을 시작으로 패턴 매칭을 다시 시작
j = 0 으로 패턴 시작부터 다시 매칭하게 한다.
2. KMP 알고리즘
아이디어
불일치가 발생한 텍스트 앞 부분에 어떤 문자가 있는지 미리 알고 있으므로, 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행
패턴을 전처리하여 불일치가 발생했을 경우 이동할 다음 위치를 구해서 잘못된 시작을 최소화
예를 들어
p = abcdabce
t = abcdabcd 라면
마지막 글자 p[7] e와 t[7] d가 달라 패턴매칭이 실패하고,
고지식한 패턴 검색이라면 t[1]인 b를 시작으로 p[0]인 a부터 다시 검색을 반복하게 된다.
e와 d에서 매칭이 실패했다는 말은 그 앞까지는 p[0:6]과 t[0:6]은 다 같다는 것 그 중 abc d abc는 접미사 접두사가 같으므로,
text 좌표는 그대로 두고 (t[7]), 패턴의 d에서 부터 (p[3]) 검색을 다시 시작해도 된다.
만약 p[3]과 t[7] 같다면 i=8, j=4 로 다시 쭉 패턴매칭을 진행해도 되지만, p[3]과 t[7]이 다르다면 t[7]에서 p[0]에 대해 다시 패턴매칭을 시작하게 된다.
next[j]라는 배열을 만들어, p[j]번째에서 매칭이 실패했을 때 j를 0으로 초기화하는 것이 아닌 next[j]로 초기화한다.
이 경우 next[7]은 3이 되고 next[3] = 0 이 된다.
구현
def KMP(pat, text):
m, n = len(pat), len(text)
next = [0] * (m + 1)
# 전처리
next[0] = -1
i, j = 0, -1
while i < m:
while j >= 0 and pat[j] != pat[i]:
j = next[j]
i, j = i + 1, j + 1
next[i] = j
print(next)
# 매칭
i = j = 0
anw = []
while i < n:
while j >= 0 and pat[j] != text[i]:
j = next[j]
i, j = i + 1, j + 1
if j == m:
anw.append([i - j, text[i - j:i]])
j = 0
return anw전처리 단계에서는 next 배열을 만든다. next 배열을 만드는 것은 t = p로 놓고 i=1에서 부터 시작하여 i를 한칸씩 움직여가면서 j= next[j] 에서부터 패턴매칭을 하는 것과 비슷하다.
이해를 위해 print 로그를 찍어보자
[-1, 0, 0, 0, 0, 0, 0, 0, 0, 0] #next
1 0 abadabaef #i, j, pat
[-1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
2 0 abadabaef
[-1, 0, 0, 1, 0, 0, 0, 0, 0, 0]
3 1 abadabaef
[-1, 0, 0, 1, 0, 0, 0, 0, 0, 0]
4 0 abadabaef
[-1, 0, 0, 1, 0, 1, 0, 0, 0, 0]
5 1 abadabaef
[-1, 0, 0, 1, 0, 1, 2, 0, 0, 0]
6 2 abadabaef
[-1, 0, 0, 1, 0, 1, 2, 3, 0, 0]
7 3 abadabaef
[-1, 0, 0, 1, 0, 1, 2, 3, 0, 0]
8 0 abadabaef
[-1, 0, 0, 1, 0, 1, 2, 3, 0, 0]
9 0 abadabaef
[-1, 0, 0, 1, 0, 1, 2, 3, 0, 0]대부분의 경우 j = -1로 초기화되어서 다시 처음부터 매칭된다. 패턴 검색 단계에서는 pat[i]를 text[i]로 바꿔주고, 채워진 next 배열을 사용하여 j가 패턴길이만큼 됐을 시에만 검색이 된 것으로 하면 된다.
다시 강조하면 next[j]가 하는 일은 p[j]번째에서 매칭이 실패했을 때 j를 0으로 초기화하는 것이 아닌 next[j]로 초기화하는 것. while 문을 사용해서 j = next[j]가 된 뒤 t[i]와 p[j]의 비교를 반복한다.
따라서 i는 비교가 끝날 때마다 증가하는 것을 제외하곤 전혀 움직이지 않는다.
출력
p = 'abadabaef'
t = 'alksdabcdabcflaskjflkabadjsaflkjasdkdsajfabadabaeflksadjabadaksfjffsdafabadabaef'
print(KMP(p,t))38 0 ajfabadab
39 1 jfabadaba
40 0 fabadabae
41 0 abadabaef
42 1 badabaefl
43 2 adabaeflk
44 3 dabaeflks
45 4 abaeflksa
46 5 baeflksad
47 6 aeflksadj
48 7 eflksadja
49 8 flksadjab
50 0 lksadjaba
...
64 0 jffsdafab
65 0 ffsdafaba
66 0 fsdafabad
67 0 sdafabada
68 0 dafabadab
69 0 afabadaba
70 1 fabadabae
71 0 abadabaef
72 1 badabaef
73 2 adabaef
74 3 dabaef
75 4 abaef
76 5 baef
77 6 aef
78 7 ef
79 8 f
...
[[41, 'abadabaef'], [71, 'abadabaef']]특징
시간 복잡도
매칭 실패 시 j = 0 이 아닌 next[j]로 초기화 후 같은 i에 대해 매칭 반복. j = -1이 되면 매칭실패로 보고 다음 i로 j=0와 함께 넘어감.
next 배열을 만드는 방법만 외우거나 잘 이해하면 매칭부분 구현도 비슷해서 매우 쉽게 쓸 수 있다. 하지만 역시나 직관적으로 쓰이기가 생각보다 어렵다. 대충 구조를 외우고 있어야 구현하기 쉬운 듯...
next를 만들 때, pat[0:i] 내의 접두사와 접미사가 일치하는 문자열의 길이를 next[i+1]에 쓴다고 생각하는 게 맞긴 한데, 구현에선 또 얘기가 달라서... t = p로 놓고 i마다 패턴 매칭하여 next를 만든다고 생각하는게 편하더라.
패턴의 접두사와 접미사가 너무 많이 반복되면 (p = aaaaaaaa) 별로 좋은 방법은 아닌 듯 하다.
3. 보이어-무어 알고리즘
아이디어
패턴의 뒤에서부터 비교하는 알고리즘. 앞에 몇글자가 똑같든 마지막 글자까지 맞아야 패턴 매칭이 완료 된것이므로 마지막 글자부터 비교해보고 맞다면 뒤에서부터 계속 매칭. 틀리다면 t의 문자가 p에 있는 문자인지 판단한 뒤, 있다면 그만큼 i를 이동시켜 p[j]와 t[i]가 일치하도록 해준다.
앞 선 알고리즘과는 약간 다르게 패턴 비교를 할때 i는 문자열의 시작이 되도록 고정하고 j = m-1부터 시작하여 t[i+j]와 p[j]를 비교하며 j를 낮추어가는 과정을 거친다.
패턴 매칭이 안된다면, t[i+m-1]의 문자가 패턴에 있는 문자인지, 있다면 어느 idx인지 판단한다.
패턴에 없다면
i = i+m으로 점프한다.
패턴에 있다면 패턴 끝 기준으로 t[i+m-1] 문자가 있는 위치 x를 i+x로 더해준다.
p = ababc
t = ghjghj ababc gghgh
라면
처음 c와 h를 비교하고 없으므로 5칸 점프
i = 5, jabab 와 패턴을 비교하였을 때 일치하지 않고
마지막 글자 b가 p의 오른쪽 기준 1에 있으므로
i = 6으로 옮겨진다. i = 6에서 ababc가 되므로 패턴을 찾았고 i = 11 로 점프.
구현
def BoyerMoore(pat,text):
m, n = len(pat), len(text)
next_dict = {}
j = 0
while j < m-1:
next_dict[pat[j]] = m-1-j
j += 1
#print(text, n)
#print(pat, m)
#print(next_dict)
i = 0
anw = []
while i <= n-m:
j = m-1
#print(i,j,text[i:i+m])
#print(pat)
#print(anw)
while j >= 0 and text[i+j] == p[j]:
j -= 1
if j < 0:
anw.append([i,text[i:i+m]])
i += m
else:
i += next_dict.get(text[i+m-1],m)
return anw출력
baabbabab 9 # text, n
abab 4 # pattern, m
{'a': 1, 'b': 2} # next
0 3 baab # i j text[i:i+m]
abab # pattern
2 3 abba
abab
3 3 bbab
abab
5 3 abab
abab
[[5, 'abab']]alksdabcdabcflaskjflkabadjsaflkjasdkdsajfabadabaeflksadjabadaksfjffsdafabadabaef 80
abadabaef 9
{'a': 2, 'b': 3, 'd': 5, 'e': 1}
0 8 alksdabcd
abadabaef
5 8 abcdabcfl
abadabaef
14 8 askjflkab
abadabaef
17 8 jflkabadj
abadabaef
26 8 saflkjasd
abadabaef
31 8 jasdkdsaj
abadabaef
40 8 fabadabae
abadabaef
41 8 abadabaef
abadabaef
50 8 lksadjaba
abadabaef
52 8 sadjabada
abadabaef
54 8 djabadaks
abadabaef
63 8 fjffsdafa
abadabaef
65 8 ffsdafaba
abadabaef
67 8 sdafabada
abadabaef
69 8 afabadaba
abadabaef
71 8 abadabaef
abadabaef
[[41, 'abadabaef'], [71, 'abadabaef']]특징
앞 선 방법들과는 다르게 i를 점프하는 점에서 다른 알고리즘보다 좋은 효율을 보일 수 있다.
보다 빠를 수 있고, 최악의 경우는
아이디어만 특이하지 구현은 아이디어를 그대로 따라가므로, 어렵지 않게 구현할 수 있다.
다만 많이 헷갈리던 부분은, 패턴에 중복되는 문자가 있을 때, 왼쪽에 있는 문자 idx를 기준으로 점프를 해야하는지, 우측에 있는 문자 idx를 기준으로 점프를 해야하는지였다.
결론은 우측에 있는 문자를 기준으로 점프를 하는 것이다.
쉽게 생각하면
text[i:i+m]만 p와 비교하는 중이고, i+m 뒤의 text는 아예 모르는 상태이다.
p = a~ab 일때
t[i:i+m] = da~a , t[i+m] = b 라면
당연히 i를 보수적으로 1칸만 옮기는 것이 맞을 것이다.
패턴 기준으로 오른쪽에 있는 i가 1이므로
next_dict를 만들때 j = 0에서부터 m까지 증가시키며 next_dict를 채워 중복된 문자 중에서 우측에 있는 p[j]가 우선이 되게 해야한다. 물론 p에 중복된 문자가 없다면 상관없다.
느낀 점
문자열 패턴매칭은 직접 짜서 써볼 일이 거의 없어서 안보고 구현하려고 할 때마다 너무 어렵다. 정렬에서 쓰이는 아이디어는 분할정복, 이분탐색 등과 같이 다른 곳에서도 많이 쓰여서 금방 짜겠는데... 이 쪽 방법론은 아직까지 다른 곳에서 비슷하게 쓰이는 것을 못봤다. 특히 패턴에 중복되는 문자열이 있을 때, 반례를 찾으려고 아무 문자열이나 넣어보고 디버깅을 할 때 등등, 긴 문자열을 다룰 때 굉장히 불편하다. 눈알 빠지는 줄 ㅜㅜ
아무튼 한번 싹 정리하면서 더 이해가 잘 되는 듯 하다.
