패턴매칭
1️⃣고지식한 패턴 검색 알고리즘 (Brute Force)
def search_in_text(s, p):
n = len(s)
m = len(p)
i = 0
j = 0
while i < n and j < m:
if s[i] != p[j]:
i = i - j
j = -1
j = j+ 1
i = i + 1
if j == m: # 검색에 성공했을 때 index 반환
return i-m
else : # 검색에 실패했을 때 -1 반환
return -1
s = "This is a book!"
p = "is"
print(search_in_text(s,p)) # 22️⃣ 카프-라빈 알고리즘
3️⃣ KMP 알고리즘
kmp 알고리즘은 텍스트에서 패턴을 찾을 때 주로 쓰이는데,
특히 패턴에서 반복되는 부분이 있을 경우, 그것을 접미사-접두사 라는 개념을 이용해서 탐색하는 과정을 줄여주는 알고리즘이다.
예를 들어, ‘abxabcabcaby’ 라는 텍스트에서 ‘abcaby’ 라는 패턴을 찾는 다고 가정해보자
| text | a | b | x | a | b | c | a | b | c | a | b | y |
| pattern | a | b | c | a | b | y |
아래 붉은 부분에서 불일치가 발생한 것을 알 수 있다 .
기존의 브루트포스 탐색과정이라면 어떻게 비교하느냐?
| text | a | b | x | a | b | c | a | b | c | a | b | y |
| pattern | a | b | c | a | b | y |
바로 이렇게 패턴을 우측으로 한칸 당겨서, 다음 텍스트 값과 또 비교한다.
text 의 b 값과 pattern의 a 값이 같지 않으니 pattern을 또 한칸 당긴다.
| text | a | b | x | a | b | c | a | b | c | a | b | y |
| pattern | a | b | c | a | b | y |
이번에도 x 와 a값이 일치하지 않으니, 한칸 더 당겨서 비교한다.
잘 가다가 빨간색 칸에서 불일치가 발생했다.
| text | a | b | x | a | b | c | a | b | c | a | b | y |
| pattern | a | b | c | a | b | y |
브루트포스라면 또 다시 패턴을 한 칸 옆으로 옮기겠지만, 이 경우 패턴을 자세히 보면
패턴에서 시작하는 ‘ a b’ 값(노란색) 과 붉은색 c 이전의 ab 값(파란색) 이 일치한다!
| text | a | b | x | a | b | c | a | b | c | a | b | y |
| pattern | a | b | c | a | b | y |
바로 이렇게!!
brute force 알고리즘을 사용하면 문자열이 짧을 때는 상관없지만, 문자열이 길어진다면 탐색해야 하는 값이 길어진다. 따라서 반복횟수를 줄이기 위해 고안된 방법이 ‘kmp’라고 생각하면 되겠다.
이 kmp 알고리즘을 실행하려면 먼저 일치하는 부분이 발생하다 - 불일치 하는 부분이 생기게 되었을 때 어느 지점부터 다시 비교할 것인지(돌아갈 것인지) 저장해 두는 과정이 필요하다.
다시 위의 예시인 ‘abcaby’ 라는 pattern에서 다음과 같은 위치를 저장 할 수 있다.
아래 표를 만드는 과정은 설명이 길어지기 때문에 참고 할 유튜브 동영상을 첨부겠다.
(https://www.youtube.com/watch?v=GTJr8OvyEVQ)
| pattern | a | b | c | a | b | y |
| 위치 | 0 | 0 | 0 | 1 | 2 | 0 |
| pattern | a | b | c | d | a | b | c | a |
| 위치 | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 1 |
def index_in_pattern(pattern):
# pattern은 문자열(string) 이다.
n = len(pattern)
box = [0]*n
i = 0
j = 1
# j는 pattern을 순회하면서 돌 index 이다.
while j < n :
if 0<= j <n and pattern[i] == pattern[j]:
box[j] = i + 1
i += 1
j += 1
elif 0<= j <n and pattern[i] != pattern[j]:
i = box[i-1]
if i == 0:
j += 1
return box
print(index_in_pattern('aabaabaaa')) # [0, 1, 0, 1, 2, 3, 4, 5, 2]
print(index_in_pattern('abcaby')) # [0, 0, 0, 1, 2, 0]
돌아간 위치 표를 이용해서 어디에서 일치하게 되는지 구해보기!
세번째 요소인 text = x에서 불일치가 발생했다. 그렇다면 어디에서부터 다시 비교를 시작해야 할까?
pattern의 c 요소 이전인 b의 위치 (파란색 부분) 으로 돌아가서 다시 비교를 시작해야 한다.
| text | a | b | x | a | b | c | a | b | c | a | b | y |
| pattern | a | b | c | a | b | y |
| pattern | a | b | c | a | b | y |
| 위치 | 0 | 0 | 0 | 1 | 2 | 0 |
패턴을 한 칸 옮겨서 비교하면, x ≠ a 이기 때문에 패턴을 또 한칸 옮긴다.
| text | a | b | x | a | b | c | a | b | c | a | b | y |
| pattern | a | b | c | a | b | y |
잘 가다가 빨간색 부분에서 불일치가 발생했다.
이때 pattern의 y 요소 하나전인 b의 위치를 보면 2(파란색) 번째 인덱스로 돌아가서 비교하라고 되어있다.
| text | a | b | x | a | b | c | a | b | c | a | b | y |
| pattern | a | b | c | a | b | y |
| pattern | a | b | c | a | b | y |
| 위치 | 0 | 0 | 0 | 1 | 2 | 0 |
따라서 pattern의 2번째 인덱스인 ‘c’부터 다시 비교하게 된다.
마침내! 일치하는 것을 찾아내었다.
| text | a | b | x | a | b | c | a | b | c | a | b | y |
| pattern | a | b | c | a | b | y |
def find_pattern(text,pattern):
n = len(text)
m = len(pattern)
i = 0 # 텍스트를 순회할 인덱스를 i라고 한다.
j = 0 # 패턴을 순회할 인덱스를 j 라고 한다.
# text의 인덱스가 끝까지 돌때까지 반복한다.
while i < n:
if text[i] == pattern[j]:
j += 1
i += 1
# 텍스트의 인덱스 값과, 패턴의 인덱스 값이 일치하면 값을 1씩 증가시킨다.
elif text[i] != pattern[j] and j == 0:
i += 1
elif text[i] != pattern[j]:
# 만약 불일치 하는 지점이 발생했다면, j는 위에서 만들어둔 box의 [j-1]번째 값으로 돌아간다.
j = index_in_pattern(pattern)[j-1]
# 만약 j가 0인데, 불일치 하는 지점이라면, i를 1 증가시켜 다음 i값과 j값을 비교한다.
# 순회가 다 끝난 후에
# 만약 j가 패턴을 전부 순회하였다면 즉, 일치하는 부분이 발생했다면
# 일치가 시작되는 지점의 index를 반환한다.
if j == m:
return i-m # 끝난 부분의 i에서 패턴의 길이인 m 만큼 빼준다.
# 패턴 찾기에 실패한 경우 -1을 반환한다.
else:
return -1
print(find_pattern('abxabcabcaby','abcaby')) # 64️⃣보이어-무어 알고리즘
- 오른쪽에서 왼쪽으로 비교한다.
- 대부분 상용 소프트웨어에서 채택하고 있는 알고리즘이다
- 패턴에 오른쪽 끝에 있는 문자가 불일치 하고, 이 문자가 패턴 내에 존재하지 않는 경우, ’패턴길이’ 만큼 이동한다.
- 패턴에 오른쪽 끝에 있는 문자가 불일치하고, 문자가 패턴 내에 존재하는 경우 패턴에서 일치하는 문자를 찾아서 점프한다.
- 보이어-무어 알고리즘의 가장 큰 특징은 텍스트 문자를 다 보지 않아도 된다는 점이다
Uploaded by N2T