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

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

 

참고자료:

http://nlp.jbnu.ac.kr/AL/ch10.pdf

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