깃허브: https://github.com/PSLeon24/DataStructure-Algorithms/blob/main/KMP_Algorithm.ipynb
KMP 문자열 검색 알고리즘(Knuth-Morris-Pratt Algorithm)
문자열 검색의 가장 기초가 되는 알고리즘이 지난 포스팅에서 학습한 브루트 포스법(https://psleon.tistory.com/53)이었다.
하지만 브루트 포스법의 경우, 검색하고자 하는 패턴과 검색 대상인 텍스트가 동일한지 검사하는 과정에서 만약 하나라도 일치하지 않는 경우 이미 검사한 위치를 기억하지 못해 현재 검색하고 있는 텍스트의 첫 문자의 바로 다음 텍스트 문자부터 검색하게 되어 시간 복잡도가 O(n·m)가 되는 비효율적인 알고리즘이라고 설명하였다. 따라서 이를 개선하고자 나온 방법 중 하나가 바로 검사했던 결과를 버리지 않고 효율적으로 활용하는 'KMP 알고리즘'이다.
오늘은 구체적으로 아래의 순서로 학습을 진행해보고자 한다.
- 정의(definition)
- 알고리즘의 역사(history of the algorithm)
- KMP 알고리즘 알아보기(learning KMP algorithm)
- KMP 알고리즘에서 사용하는 표 만들기(making a table using KMP algorithm)
- Python으로 KMP 알고리즘의 구현(implementation of KMP algorithm with Python)
1. 정의(definition)
KMP 알고리즘은 텍스트와 패턴 안에서 겹치는 문자열을 찾아내 검사를 다시 시작할 위치를 구하여 패턴의 이동을 되도록이면 크게 하는 알고리즘이고 이를 위해 '몇 번째 문자부터 다시 검색할지'의 값을 건너뛰기 표로 만들어서 문제를 해결한다.
- 이 알고리즘의 시간복잡도는 선형 시간인 O(m + n)이라고 알려져 있다.
- 왼쪽에서부터 오른쪽으로 비교한다.
- 검사를 시작하는 위치는 한 칸 또는 한 칸 이상씩 이동한다.
2. 알고리즘의 역사(history of the algorithm)
이 알고리즘은 D. E. 크누스(D. E. Knuth), J. H. 모리스(J. H. Morris), V. R. 프래트(V. R. Pratt)이 함께 고안했고, 이들 이름의 앞글자를 따와 KMP 알고리즘이라고 한다.
이들은 브루트 포스법을 분석하여, 세계 최초로 선형 시간의 복잡도를 가진 문자열 검색 알고리즘을 발견하였다.
이 알고리즘은 문자열을 검사하는 동안 얻어지는 브루트 포스법의 결과를 버리지 않고 기억한다. 이를 통해 정보의 낭비를 피하고, '몇 번째 문자부터 다시 검색할지' 값을 건너뛰기 표를 만들어서 문제를 해결하며 시간 복잡도는 O(m + n)에 도달하게 된다.
따라서, 이러한 KMP 알고리즘의 구현을 통해 텍스트 문자열과 패턴의 비교를 최소화하기 때문에 효율적인 알고리즘이다. 다만, 이 알고리즘은 복잡하고 성능 면에서 보이어·무어법이랑 같거나 낮은 수준이므로 차후 배울 보이어·무어법이 실제 문자열 검색에서 널리 사용된다.
3. KMP 알고리즘 알아보기(learning KMP algorithm)
예를 들어 텍스트 'ACBACCBBAC'에서 패턴 'CBB'를 찾는다고 가정해보자.
| A | C | B | A | C | C | B | A | A | C |
| C(X) | B | B | A | A | C |
위 표와 같이 텍스트와 패턴의 첫 문자인 'C'부터 차례로 검사를 수행한다. 하지만 이때 텍스트의 첫 문자인 'A'는 패턴에 포함되지 않으므로 일치하지 않는다. 이제 패턴을 오른쪽으로 1칸 민다.
| A | C | B | B | C | C | B | A | A | C |
| C(O) | B(O) | B(O) | C(O) | C(O) | C(X) |
패턴의 앞쪽부터 차례대로 검사를 수행해 가면 패턴의 마지막 문자인 'C'가 텍스트의 'B'와 일치하지 않는다.
이때, 텍스트 안의 'CB'(suffix: 접미사)와 패턴 안의 'CB'(prefix: 접두사)가 일치하는 것에 주목한다.
그러면, 이 부분을 검사를 마친 위치라고 간주한다면, 텍스트에서 'CB' 다음에 나오는 'A' 이후 부분이 패턴의 'BCCC'와 일치하는지 검사하면 된다.
즉, 검사하는 과정 중 검사를 마친 위치를 스킵하여 아래의 표와 같이 오른쪽으로 오른쪽으로 4칸 밀어 패턴의 3번째 문자 'B'부터 검사를 시작하면 된다.
| A | C | B | B | C | C | B | A | A | C | C |
| C | B | B(O) | C(X) | C | C |
KMP 알고리즘은 위의 과정과 같이 텍스트와 패턴 안에서 겹치는 문자열을 찾아내 검사를 다시 시작할 위치를 구해 겹치는 부분은 스킵하여 효율적으로 검색하는 알고리즘인데, 몇 번째 문자부터 검사를 다시 시작할지 패턴을 이동할 때마다 계산한다면 좋은 효율을 기대할 수 없다. 따라서, 정의에서 설명한 것과 같이 '몇 번째 문자부터 다시 검색할지'의 값을 건너뛰기 표로 만들어서 문제를 해결한다.
이러한 과정은 <Do it! 자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편>의 311 페이지에 자세히 묘사되어 있다.
위 그림에서 왼쪽은 텍스트와 패턴이 불일치한 경우를 나타내고, 오른쪽은 몇 번째 문자부터 검사를 다시 시작할지를 나타낸다.
e와 f를 자세히 살펴보면, 다른 과정에서는 모두 패턴의 첫번째 문자부터 검사를 다시 시작하지만, e와 f에서는 각각 검사를 다시 시작하는 위치가 2번째와 3번째로 다름을 알 수 있다.
e의 경우, 패턴의 5번째 문자인 'B'에서 검사가 실패하는데 이 경우에는 패턴을 이동하면 텍스트의 4번째 문자인 'A'와 패턴의 1번째 문자인 'A'가 일치하므로, 패턴의 2번째 문자인 'B'부터 검사를 다시 시작할 수 있다.
f의 경우, 패턴의 6번째 문자인 'D'에서 검사를 실패하는 경우에도 위와 같이 패턴의 3번째 문자인 'C'부터 검사를 다시 시작할 수 있다.
4. KMP 알고리즘에서 사용하는 표 만들기(making a table using KMP algorithm)
KMP 알고리즘에서 사용하는 표를 작성할 때는 패턴에서 겹치는 문자열을 찾는다.
즉, 접미사(패턴의 끝 부분)이기도 한 접두사(패턴의 시작 부분)를 찾는다.
패턴의 각 위치에 대해 가장 긴 겹치는 접두사(prefix)와 접미사(suffix)의 길이를 기록합니다.
예를 들어 패턴이 'ABCABD'라고 가정하자.
이 경우, 패턴 'ABCABD' 22개를 위아래로 나란히 놓고 아래쪽 패턴을 아래의 표와 같이 오른쪽으로 1칸 밀어 서로 겹친다.
| A | B | C | A | B | D | |||||
| A | B | C | A | B | D | |||||
| 0 | 0 |
위 과정에서 위쪽의 패턴의 'B'문자와 아래쪽 패턴의 'A'가 일치하는지 비교하여 일치하는 접두사와 접미사가 있는지 확인한다.
이 경우에는 없기 때문에 아래쪽 패턴을 이동하면 첫 문자부터 검사를 다시 시작해야 하므로 위쪽의 패턴에서 2번째 문자 'B'는 다시 시작하는 값을 0으로 한다.
그런 다음 세 번째 문자 'C'로 이동한다.
| A | B | C | A | B | D | |||||
| A | B | C | A | B | D | |||||
| 0 | 0 | 0 |
이 경우에도 마찬가지로 문자가 일치하지 않으므로 위쪽의 패턴에서 3번째 문자 'C'는 다시 시작하는 값을 0으로 작성한다.
| A | B | C | A | B | D | |||||
| A | B | C | A | B | D | |||||
| 0 | 0 | 0 | 1 | 2 |
패턴을 오른쪽으로 1칸 밀면, 'AB'가 일치한다. 여기서 아래와 같은 2가지 사실을 알 수 있따.
- 패턴의 4번째 문자 'A'까지 일치하는 경우: 패턴 이동 후 'A'를 건너뛰고(skip) 2번째 문자인 'B'부터 검사할 수 있다.
- 패턴의 5번째 문자 'B'까지 일치하는 경우: 패턴 이동 후 'AB'를 건너뛰고(skip) 3번째 문자인 'C'부터 검사할 수 있다.
따라서, 'A'와 'B'는 다시 시작하는 값을 표에서 각각 1과 2로 작성한다.
| A | B | C | A | B | D | |||||
| A | B | C | A | B | D | |||||
| 0 | 0 | 0 | 1 | 2 | 0 |
마지막으로 패턴을 오른쪽으로 2칸 밀면 문자가 일치하지 않으므로 패턴의 끝 문자 'D'는 다시 시작하는 값을 0으로 작성한다.
그러면 최종적으로 아래와 같은 표가 완성되어 '건너뛰기 표(skip table)'가 된다.
| A | B | C | A | B | D |
| 0 | 0 | 0 | 1 | 2 | 0 |
5. Python으로 KMP 알고리즘 구현(implementation of KMP algorithm with Python)
def kmp_match(text, pattern):
cursor_text = 1 # 텍스트를 따라가는 커서
cursor_pattern = 0 # 패턴을 따라가는 커서
skip_table = [0] * (len(pattern) + 1) # 건너뛰기 표
# 건너뛰기 표 만들기
print(f'건너뛰기 표')
skip_table[cursor_text] = 0 # 건너뛰기 표에서 패턴의 첫 부분은 항상 0
while cursor_text != len(pattern):
if pattern[cursor_text] == pattern[cursor_pattern]:
cursor_text += 1
cursor_pattern += 1
skip_table[cursor_text] = cursor_pattern
elif cursor_pattern == 0:
cursor_text += 1
skip_table[cursor_text] = cursor_pattern
else:
cursor_pattern = skip_table[cursor_pattern]
print(skip_table)
print()
# 문자열 검색하기
cursor_text = cursor_pattern = 0
while cursor_text != len(text) and cursor_pattern != len(pattern):
if text[cursor_text] == pattern[cursor_pattern]:
cursor_text += 1
cursor_pattern += 1
elif cursor_pattern == 0:
cursor_text += 1
else:
cursor_pattern = skip_table[cursor_pattern]
return cursor_text - cursor_pattern if cursor_pattern == len(pattern) else -1
def kmp_checker(idx):
if idx == -1:
print('텍스트 안에 패턴이 존재하지 않음')
else:
print(f'{(idx + 1)}번째 문자가 일치함')
if __name__ == "__main__":
str_txt1 = 'ZABCABXACCADEF'
str_pat = 'ABCABD'
str_txt2 = 'ZABCABDACCADEF'
idx1 = kmp_match(str_txt1, str_pat)
idx2 = kmp_match(str_txt2, str_pat)
print(f'텍스트 "{str_txt1}"에서 패턴 "{str_pat1}" 문자열 검사 - 1')
kmp_checker(idx1)
print()
print(f'텍스트 "{str_txt2}"에서 패턴 "{str_pat2}" 문자열 검사 - 2')
kmp_checker(idx2)
패턴 'ABCABD'에 대해서 2개의 텍스트의 문자열을 검사해 보았다.
첫 번째 텍스트의 문자열은 'ZABCABXACCADEF'이고 두 번째 텍스트의 문자열은 'ZABCABDACCADEF'이다.
패턴은 둘다 같으므로 건너뛰기 표는 동일하게 생성된다.
그 후, 문자열 검색을 진행하면, 아래와 같은 결과가 출력된다.
참고로 텍스트를 스캔하는 커서인 cursor_text는 앞으로 나아갈 뿐 뒤로 되돌아오지 않는데, 이것은 브루트 포스법에는 없는 특징이다.
이 과정이 쉽게 와닫지 않는다면 코드를 디버깅해서 확인할 수 있는 파이썬 튜터를 확인해 동작 과정 살펴보면 이해가 쉬울 것이다.
* 참고로 파이썬 튜터의 링크는 https://pythontutor.com/ 이다.
+ 필자는 추가로 아래와 같이 손 로직(hand-logic)을 돌려보았다.
txt = 'ABCDABBCABCDABCDABCAB'
pat = 'ABCDABC'
kmp(txt, pat)
pt = 1
pp = 0
skip = [0] * len((pat) + 1)
# [0, 0, 0, 0, 0, 0, 0, 0]
# 건너뛰기 표 만들기
skip[pt] = 0 # [0, 0, 0, 0, 0, 0, 0, 0] ~ 건너뛰기 표에서 패턴의 두 번째 문자의 인덱스에 해당하는 값을 0으로 초기화
while pt != len(pat) # O
# 1
if pat[pt: 1] == pat[pp: 0]: # X: B != A
elif pp == 0: # O
pt += 1 # pt = 2
skip[2] = pp # 0
# [0, 0, 0, 0, 0, 0, 0, 0]
# 2
if pat[pt: 2] == pat[pp: 0] # X: C != A
elif pp == 0:
pt += 1 # pt = 3
skip[3] = pp # 0
# [0, 0, 0, 0, 0, 0, 0, 0]
# 3
if pat[pt: 3] == pat[pp: 0] # X: D != A
elif pp == 0:
pt += 1 # pt = 4
skip[4] = pp # 0
# [0, 0, 0, 0, 0, 0, 0, 0]
# 4
if pat[pt: 4] == pat[pp: 0] # O: A == A
pt += 1 # pt = 5
pp += 1 # pp = 1
skip[5] = pp # 1
# [0, 0, 0, 0, 0, 1, 0, 0]
# 5
if pat[pt: 5] == pat[pp: 1] # O: B == B
pt += 1 # pt = 6
pp += 1 # pp = 2
skip[6] = pp # 2
# [0, 0, 0, 0, 0, 1, 2, 0]
# 6
if pat[pt: 6] == pat[pp: 2] # O: C == C
pt += 1 # pt = 7
pp += 1 # pp = 3
skip[7] = pp # 3
# [0, 0, 0, 0, 0, 1, 2, 3]
# pt == len(pat): 7 == 7이므로 while문 탈출
# 문자열 검색
pt = pp = 0
while pt != len(txt) and pp != len(pat):
# 1: pt = 0, pp = 0
if txt[pt] == pat[pp]: # O: A == A
pt += 1 # pt = 1
pp += 1 # pp = 1
# 2: pt = 1, pp = 1
if txt[pt] == pat[pp]: # O: B == B
pt += 1 # pt = 2
pp += 1 # pp = 2
# 3: pt = 2, pp = 2
if txt[pt] == pat[pp]: # O: C == C
pt += 1 # pt = 3
pp += 1 # pp = 3
# 4: pt = 3, pp = 3
if txt[pt] == pat[pp]: # O: D == D
pt += 1 # pt = 4
pp += 1 # pp = 4
# 5: pt = 4, pp = 4
if txt[pt] == pat[pp]: # O: A == A
pt += 1 # pt = 5
pp += 1 # pp = 5
# 6: pt = 5, pp = 5
if txt[pt] == pat[pp]: # O: B == B
pt += 1 # pt = 6
pp += 1 # pp = 6
# 7: pt = 6, pp = 6
if txt[pt] == pat[pp]: # X: B != C
elif pp == 0: # X: pp(=6) != 0
else: # O
pp = skip[pp] # skip[6] = 2
# 8: pt = 6, pp = 2
if txt[pt] == pat[pp]: # X: B != C
elif pp == 0: # X: pp(=2) != 0
else: # O
pp = skip[pp] # skip[2] = 0
# 9: pt = 6, pp = 0
if txt[pt] == pat[pp]: # X: B != A
elif pp == 0: # O: pp(=0) == 0
pt += 1 # pt = 7
# 10: pt = 7, pp = 0
if txt[pt] == pat[pp]: # X: C != A
elif pp == 0: # O: pp(=0) == 0
pt += 1 # pt = 8
# 11: pt = 8, pp = 0
if txt[pt] == pat[pp]: # O: A == A
pt += 1 # pt = 9
pp += 1 # pp = 1
# 12: pt = 9, pp = 1
if txt[pt] == pat[pp]: # O: B == B
pt += 1 # pt = 10
pp += 1 # pp = 2
# 13: pt = 10, pp = 2
if txt[pt] == pat[pp]: # O: C == C
pt += 1 # pt = 11
pp += 1 # pp = 3
# 14: pt = 11, pp = 3
if txt[pt] == pat[pp]: # O: D == D
pt += 1 # pt = 12
pp += 1 # pp = 4
# 15: pt = 12, pp = 4
if txt[pt] == pat[pp]: # O: A == A
pt += 1 # pt = 13
pp += 1 # pp = 5
# 16: pt = 13, pp = 5
if txt[pt] == pat[pp]: # O: B == B
pt += 1 # pt = 14
pp += 1 # pp = 6
# 17: pt = 14, pp = 6
if txt[pt] == pat[pp]: # O: B == B
pt += 1 # pt = 15
pp += 1 # pp = 7
if pp == len(pat): # O: 7 == 7(검색 성공)
return pt - pp # 15-7 = 8
print(f'(idx+1)번째 문자와 일치') # 9번째(8+1)
'Algorithms & Data Structure' 카테고리의 다른 글
| [Data Structure] 원형 이중 연결 리스트(Circular Doubly Linked List) (0) | 2023.05.30 |
|---|---|
| [Algorithms] 4퀸 문제 및 8퀸 문제 (4-Queen problem & 8-Queen problem) (0) | 2023.05.23 |
| [Algorithms] 하노이의 탑(Tower of Hanoi) (0) | 2023.05.19 |
| [Algorithms] 브루트 포스법(Brute Force Method) (2) | 2023.05.17 |
| [Algorithms] 문자열 검색(String Searching) (0) | 2023.05.17 |