문자열 패턴 매칭 알고리즘 - munjayeol paeteon maeching algolijeum

문자열 매칭 또는 패턴 매칭은 컴퓨터 과학에서 중요한 문제이다. 노트패드나 워드파일 또는 웹 브라우저 데이터베이스에서 문자열을 검색할 때 패턴 매칭 알고리즘을 사용하여 검색 결과를 표시한다.

문자열 매칭 방법의 종류는 아래와 같다.

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와 일치하는지 확인하는 것이다. 

//www.geeksforgeeks.org/naive-algorithm-for-pattern-searching/

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"와 같은 경우이다. 

참고자료:

//nlp.jbnu.ac.kr/AL/ch20.pdf

//www.geeksforgeeks.org/naive-algorithm-for-pattern-searching/