[문자열 검색] 한 살도 이해하는 KMP 알고리즘

KMP 알고리즘이란?

대표적인 문자열 검색 알고리즘

 

KMP 알고리즘의 핵심 원리

문자열 매칭을 하면서 텍스트(전체 문자열)와 패턴(찾는 문자열)에서 서로 다른 글자가 나왔다면,

'서로 다른 글자의 바로 전 까지는 일치했다'라는 사실과 '접두사와 접미사가 같은 만큼 비교를 덜해도 된다'는 사실 이용하기

 

즉, 바로 전 글자까지 일치했었으므로, 접미사와 접두사가  같은만큼 비교를 덜하도록 이동시켜주면 된다.

 

 

직접 하나하나 이해해보기

 

아래 그림을 보면서 이해해보자.

@ @ @ @ a b c d a b c d  @ @ @ @   인 텍스트에서, (@는 아무 글자라고 생각하자, 신경안써도 된다.)

                a b c d a b c w z                   인 패턴을 찾는다고 해보자.

 

첫 문자부터 하나 하나 비교를 시작한다.

@ @ @ @ a b c d a b c d  @ @ @ @   

@ @ @ @ a b c d a b c w z @ @ @ @                     

 

@ @ @ @ a b c d a b c d  @ @ @ @   

@ @ @ @ a b c d a b c w z@ @ @ @       

 

@ @ @ @ a b c d a b c d  @ @ @ @   

@ @ @ @ a b c d a b c w z  @ @ @ @      

 

@ @ @ @ a b c d a b c d  @ @ @ @   

@ @ @ @ a b c d a b c w z       

 

@ @ @ @ a b c d a b c d  @ @ @ @   

@ @ @ @ a b c d a b c w z       

 

@ @ @ @ a b c d a b c d  @ @ @ @   

@ @ @ @ a b c d a b c w z       

 

@ @ @ @ a b c d a b c d  @ @ @ @   

@ @ @ @ a b c d a b c w z       

 

순서대로 비교를 하다가 텍스트의 문자(d)와 패턴의 문자(w)가 다르다!

이런 상황에서 KMP 알고리즘이 빛을 발한다.

 

@ @ @ @ a b c d a b c d  @ @ @ @   

@ @ @ @ a b c d a b c w z       

 

앞서 말했던 KMP 알고리즘의 핵심 원리를 이용해보자.

 

1. '서로 다른 글자의 바로 전 까지는 일치했다'라는 사실

@ @ @ @ a b c d a b c d  @ @ @ @   

@ @ @ @ a b c d a b c w z       

앞서서 비교한 파란 부분까지는 일치했다. 즉, w의 바로 전까지는 비교하면서 다른 부분이 없었다!

이 사실을 명심한 상태에서,

 

2.  '접두사와 접미사가 같은 만큼 비교를 덜해도 된다'는 사실

@ @ @ @ a b c d a b c d  @ @ @ @   

@ @ @ @ a b c d a b c w z       

 

현재 패턴의 접두사와 접미사가 abc로 같다

바로 윗 부분에서 봤듯이, w 전까지는 모두 일치했다. 

 

그렇다면!!!!   접두사와 접미사가 같은 만큼 비교를 덜해도 되겠다

                                            =

접두사와 접미사가 같으니까(abc),

접두사(앞에 있는 abc)를 접미사(뒤에 있는 abc)가 있던 위치에 놓으면 되겠네!

 

@ @ @ @ a b c d a b c d  @ @ @ @   

@ @ @ @ a b c d a b c w z       

@ @ @ @------->   a b c d a b c w z 

 

즉, 이렇게 된다. (똑같은 상황을 그림으로 표현한 것이다)

 

이 핵심 원리를 이해했으면  KMP 알고리즘을 이해했다고 보면된다.

텍스트와 패턴의 문자가 다를 때마다 한 칸씩 이동해서 비교하는 단순 문자열 검색과는 달리

1. '서로 다른 글자의 바로 전 까지는 일치했다'라는 사실
2.  '접두사와 접미사가 같은 만큼 비교를 덜해도 된다'는 사실

이 사실들을 이용해 비교하는 횟수를 획기적으로 줄이게 된다.

 

---

그러면 핵심 원리를 바탕으로 문자열 검색을 풀버전으로 감상해보자. (아니 감상만하지 말고 따라가면서 생각해보자.)

텍스트 "a b a c a a b a c c a b a c a b a a "  에서

패턴 "a b a c a b"를 찾아보자

 

그림 1

 

그림 2: 접두사와 접미사가 겹치지 않으므로 뒤로 한 칸 이동

 

그림 3

 

그림 4: 접두사와 접미사가 겹치지 않으므로 뒤로 한 칸 이동

 

---

코드로 구현하려면 어떻게 해야할까?

사람은 위의 그림들 처럼 옆으로 옮겨 가면서 생각할 수 있지만, 컴퓨터는 이 방식으로 이해할 수는 없을 것이다.

그래서 코드로 구현할 때는 텍스트와 패턴에 각각 포인터를 두고, 포인터를 옮겨 가면서 비교하는 방식으로 진행한다.

코드로 보기 전에 그림으로 컴퓨터가 이해하는 방식을 이해해보자.

 

텍스트의 포인터와 패턴의 포인터로 문자를 비교하면서, 서로 다른 문자가 나오면

패턴의 포인터가 가리키는 지점의 바로 전 문자가 가리키는 실패함수 값(주황색 숫자)을 이용해,  그 값을 인덱스로 갖는 문자로 이동한다.

실패 함수에 대해 포스팅을 따로 할 예정인데, 실패 함수는 주황색 숫자들이며 해당 문자까지 나오는 접두사와 접미사가 같은 최대 길이이다.

 

그림 2-1

---

그림 2-2

---

그림 2-3

---

그림 2-4

---

그림 2-5, 최종적으로 패턴의 포인터가 끝까지 도착했다면 문자열을 찾은 것이다.

 

이제 이 방식을 코드로 구현한 코드를 보자. (makeTable은 실패 함수를 만드는 코드인데, 이 부분은 곧 추가로 포스팅 할 예정.)

 

def makeTable(pattern):
    patternSize = len(pattern)
    table = [0 for i in range(patternSize)]
    j = 0
    for i in range (1, patternSize):
        while(j >0 and pattern[i] != pattern[j]):
            j = table[j-1]
        if(pattern[i] == pattern[j]):
            table[i] = j+1
            j += 1
    return table

def KMP(parent, pattern):
    table = makeTable(pattern)
    parentSize = len(parent)
    patternSize = len(pattern)
    parentPointer = 0
    patternPointer = 0
    count = 0
    for parentPointer in range(0, parentSize):
        while(patternPointer > 0 and parent[parentPointer] != pattern[patternPointer]):
            patternPointer = table[patternPointer - 1]
        if(parent[parentPointer] == pattern[patternPointer]):
            if(patternPointer == patternSize - 1):
                print(pattern, "을", parent,"에서 찾았습니다.")
                count += 1
                print("총", count, " 번 나옵니다")
                patternPointer = table[patternPointer]
            else:
                patternPointer += 1
    if count == 0:
      print("해당 문자열이 없습니다.")
    
    return count
    
KMP("abacaabaccabacabaa", "abacab")

 

구현 결과

 

abacab 을 abacaabaccabacabaa 에서 찾았습니다.
총 1  번 나옵니다

---

시간 복잡도

 

텍스트(부모)의 길이를 N, 찾는 문자열(패턴)의 길이를 M이라 할 때 

문자열을 한 칸씩 이동하면서 모두 비교하는 '단순 문자열 검색 알고리즘'이 시간 복잡도가 O(NM)인 것에 비해

'KMP 알고리즘'은 O(N+M)에 문자열 검색이 가능하다.