[Algorithm] 알고리즘 - 문자열 매칭(Pattern Matching)
문자열 매칭 또는 패턴 매칭은 컴퓨터 과학에서 중요한 문제이다. 노트패드나 워드파일 또는 웹 브라우저 데이터베이스에서 문자열을 검색할 때 패턴 매칭 알고리즘을 사용하여 검색 결과를 표시한다.
문자열 매칭 방법의 종류는 아래와 같다.
1. Naive Matching (원시적인 매칭) - $O(mn)$
2. Automata Algorithm (오토마타를 이용한 매칭) - $\Theta(n + |\sum| m)$
3. Rabin-Karp Algorithm (라빈-카프 알고리즘) - $\Theta(n)$
4. Knuth-Morris-Pratt(KMP) Algorithm (KMP알고리즘) - $\Theta(n)$
5. Boyer-Moore Algorithm (보이어-무어 알고리즘) - $\Theta(n)$ Worst Case: $\Theta(nm)$
하나씩 알아보자.
Naive Matching (원시적인 매칭)
txt[0...n-1] text와 pat[0...m-1] pattern이 주어질 때 txt를 하나씩 접근하여 pat와 일치하는지 확인하는 것이다.
Best Case는 pat의 첫 번째 문자가 txt에 없는 경우이다. 이때 시간 복잡도는 $O(n)$이다.
Worst Case는 txt가 'AAAAAAAAAAAAAAAAAAAAAAA' pat이 'AAAAA'일 때 처럼 txt의 모든 문자가 pat가 같을 때 이다.
pat이 'AAAAB'처럼 pat의 마지막 글자가 달라도 최악의 경우이다.
아래는 파이썬으로 구현한 Navie Matching 알고리즘이다.
# Searching algorithm
def search(pat, txt):
M = len(pat)
N = len(txt)
# A loop to slide pat[] one by one */
for i in range(N - M + 1):
j = 0
# For current index i, check
# for pattern match */
while(j < M):
if (txt[i + j] != pat[j]):
break
j += 1
if (j == M):
print("Pattern found at index ", i)
# Driver Code
if __name__ == '__main__':
txt = "AABAACAADAABAAABAA"
pat = "AABA"
search(pat, txt)
# This code is contributed
# by PrinciRaj1992
Finite Automata Based Algorithm (오토마타를 이용한 매칭)
패턴을 전처리하고 Finite Automata를 나타내는 2차원 배열을 만든다. FA를 구성하는게 까다로운데 일단 FA를 만들고 나면 검색은 간단하게 된다. 검색할 때 txt의 첫 문자와 오토마타의 첫 번째 상태에서 시작한다. 모든 단계에서 텍스트의 다음 글자를 고려해서 만들어진 FA에서 다음 상태를 찾고 새로운 상태로 움직이면 된다.
FA의 State의 개수는 M(패턴의 길이) +1이다. FA를 구성할 때 고려해야 할 주요한 부분은 가능한 모든 문자에 대해 현재 state에서 다음 state를 얻는 것이다.
# Python program for Finite Automata
# Pattern searching Algorithm
NO_OF_CHARS = 256
def getNextState(pat, M, state, x):
'''
calculate the next state
'''
# If the character c is same as next character
# in pattern, then simply increment state
if state < M and x == ord(pat[state]):
return state+1
i=0
# ns stores the result which is next state
# ns finally contains the longest prefix
# which is also suffix in "pat[0..state-1]c"
# Start from the largest possible value and
# stop when you find a prefix which is also suffix
for ns in range(state,0,-1):
if ord(pat[ns-1]) == x:
while(i<ns-1):
if pat[i] != pat[state-ns+1+i]:
break
i+=1
if i == ns-1:
return ns
return 0
def computeTF(pat, M):
'''
This function builds the TF table which
represents Finite Automata for a given pattern
'''
global NO_OF_CHARS
TF = [[0 for i in range(NO_OF_CHARS)]\
for _ in range(M+1)]
for state in range(M+1):
for x in range(NO_OF_CHARS):
z = getNextState(pat, M, state, x)
TF[state][x] = z
return TF
def search(pat, txt):
'''
Prints all occurrences of pat in txt
'''
global NO_OF_CHARS
M = len(pat)
N = len(txt)
TF = computeTF(pat, M)
# Process txt over FA.
state=0
for i in range(N):
state = TF[state][ord(txt[i])]
if state == M:
print("Pattern found at index: {}".\
format(i-M+1))
# Driver program to test above function
def main():
txt = "AABAACAADAABAAABAA"
pat = "AABA"
search(pat, txt)
if __name__ == '__main__':
main()
# This code is contributed by Atul Kumar Rabin-Karp Algorithm (라빈-카프 알고리즘)
Naive 매칭 방법과 같이 라빈카프 알고리즘도 하나씩 문자를 이동하면서 모든 문자에 대해 패턴과 일치하는지 확인한다.
그러나 Naive 매칭과 다른 점은 패턴의 해시값을 쓴다는 것이다.
Rabin-Karp가 제안한 해시 함수는 정수값을 계산한다. 그러나 가능한 문자의 수는 10개 보다 많고 패턴 길이는 클 수 있다. 심하면 컴퓨터 레지스터의 용량이 초과될 수 있거나 오버플로우가 발생할 수 있다. 이에 대한 해결책은 modulo를 사용하는 것이다.
# Following program is the python implementation of
# Rabin Karp Algorithm given in CLRS book
# d is the number of characters in the input alphabet
d = 256
# pat -> pattern
# txt -> text
# q -> A prime number
def search(pat, txt, q):
M = len(pat)
N = len(txt)
i = 0
j = 0
p = 0 # hash value for pattern
t = 0 # hash value for txt
h = 1
# The value of h would be "pow(d, M-1)%q"
for i in range(M-1):
h = (h*d)%q
# Calculate the hash value of pattern and first window
# of text
for i in range(M):
p = (d*p + ord(pat[i]))%q
t = (d*t + ord(txt[i]))%q
# Slide the pattern over text one by one
for i in range(N-M+1):
# Check the hash values of current window of text and
# pattern if the hash values match then only check
# for characters on by one
if p==t:
# Check for characters one by one
for j in range(M):
if txt[i+j] != pat[j]:
break
j+=1
# if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]
if j==M:
print "Pattern found at index " + str(i)
# Calculate hash value for next window of text: Remove
# leading digit, add trailing digit
if i < N-M:
t = (d*(t-ord(txt[i])*h) + ord(txt[i+M]))%q
# We might get negative values of t, converting it to
# positive
if t < 0:
t = t+q
# Driver program to test the above function
txt = "GEEKS FOR GEEKS"
pat = "GEEK"
q = 101 # A prime number
search(pat,txt,q)
# This code is contributed by Bhavya Jain
Knuth-Morris-Pratt(KMP) Algorithm (KMP알고리즘)
오토마타를 이용한 매칭과 동기가 유사하지만 준비 작업이 더 단순하다. 패턴의 각 위치에 대해 매칭에 실패했을 때 돌아갈 곳을 준비해 둔다.
# Python program for KMP Algorithm
def KMPSearch(pat, txt):
M = len(pat)
N = len(txt)
# create lps[] that will hold the longest prefix suffix
# values for pattern
lps = [0]*M
j = 0 # index for pat[]
# Preprocess the pattern (calculate lps[] array)
computeLPSArray(pat, M, lps)
i = 0 # index for txt[]
while i < N:
if pat[j] == txt[i]:
i += 1
j += 1
if j == M:
print("Found pattern at index " + str(i-j))
j = lps[j-1]
# mismatch after j matches
elif i < N and pat[j] != txt[i]:
# Do not match lps[0..lps[j-1]] characters,
# they will match anyway
if j != 0:
j = lps[j-1]
else:
i += 1
def computeLPSArray(pat, M, lps):
len = 0 # length of the previous longest prefix suffix
lps[0] # lps[0] is always 0
i = 1
# the loop calculates lps[i] for i = 1 to M-1
while i < M:
if pat[i]== pat[len]:
len += 1
lps[i] = len
i += 1
else:
# This is tricky. Consider the example.
# AAACAAAA and i = 7. The idea is similar
# to search step.
if len != 0:
len = lps[len-1]
# Also, note that we do not increment i here
else:
lps[i] = 0
i += 1
txt = "ABABDABACDABABCABAB"
pat = "ABABCABAC"
KMPSearch(pat, txt)
Boyer-Moore Algorithm (보이어-무어 알고리즘)
보이어 무어 알고리즘도 패턴을 전처리한다. 그러나 이전의 매칭 알고리즘과는 다르게 텍스트 무자를 다 보지 않아도 된다.
Bad Character Heuristic 최악의 경우 시간이 O(mn) 걸릴 수 있다. 텍스트와 패턴의 모든 문자가 동일할 때 최악의 경우가 발생한다. 예를 들어 txt [] = "AAAAAAAAAAAAAAAAA" 및 pat [] = "AAAAA"와 같은 경우이다.
참고자료:
http://nlp.jbnu.ac.kr/AL/ch10.pdf
https://www.geeksforgeeks.org/naive-algorithm-for-pattern-searching/