[Python] KMP 알고리즘 (문자열 검색 알고리즘)

글에 앞서, "알고리즘 문제 해결 전략"에서 공부한 내용을 정리한 글임을 알려드립니다

 

---

 

문자열 검색

우리는 수많은 문자열 자료를 다룬다

이는 문서 파일, 웹페이지, 이메일 등에서 쓰이고,

정보 검색(information retrieval)이나 생물 정보학(bioinformatices) 분야에서 유용하게 사용된다

 

긴 문자열 H에서 짧은 문자열 N을 부분 문자열로 포함하는지, 그 시작 위치는 어디인지 문제를 해결해보자

가장 단순한 방법으로는 한 칸씩 옮겨 확인하는 방법이 있다

 

더 효율적인 방법은 없을까 ?

 

---

 

KMP 알고리즘

우리는 검색 과정에서 얻는 정보를 잘 활용하면 많은 시간을 절약할 수 있다

 

[그림 1] 답이 될 수 없는 시작 위치들 걸러내기

그림 1에서 확인할 수 있듯이, 우리는 시도조차 피할 수 있는 "시작 위치 후보"가 있음을 알 수 있다

이 때 우리는 H에 대한 정보는 관계 없이, "현재 위치에서 H와 N을 비교했을 때 몇 글자나 일치했는가"만 이용하였다

이와 같은 정보를 전처리 과정으로 미리 계산해 저장해 둔다면 아주 효율적일 것이다

 

이를 KMP 알고리즘, 커누스-모리스-프랫(Knuth-Morris-Pratt) 알고리즘이라고 한다

이는 여러 문자열 문제에 응용될 수 있어 아주 중요하다

 

---

 

어떻게 ?

다음 그림 2를 보자

 

[그림 2] 다음 시작 위치 i+k 찾기

matched 글자까지 일치하고 다음 글자가 불일치하는 상황이다

k만큼 넘어간다고 가정해보자

 

회색으로 색칠된 문자열은 일치된 문자열이므로, A-B는 일치함을 알 수 있다

그런데 시작 위치 i+k가 답이 되기 위해서는 B-C가 같아야 하므로

A-C 역시 같음을 알 수 있다

 

여기서 A와 C는 N의 접두사이기도 하고 접미사이기도 하다

따라서 시작위치 i+k에서 답을 찾기 위해,

N에서의 길이가 matched-k인 접두사와 접미사가 같아야 한다

 

그렇다면 우리는 N의 각 접두사에 대해 접두사도 되고 접미사도 되는 문자열의 최대 길이를 계산하면 될 것이다

→ pi[i]  :  N[~i]의 접두사도 되고 접미사도 되는 문자열의 최대 길이

 

[그림 3] 부분 일치 테이블의 계산

 

---

 

구현은 어떻게 ?

시작 위치 0에서부터 시작해서 H와 N을 비교한다

만약 matched 글자가 일치한 후 불일치가 발생했다고 하자

그림 2에서 A의 길이는 pi[matched-1]이다. 따라서 시작 위치를 matched-pi[matched-1]만큼 증가시키면 된다

더불어서 중요한 점은 새로운 위치에서 비교를 시작하더라도,

대응되었던 문자열을 이용하여 matched를 pi[matched-1]으로 변경하고 비교를 계속하면 된다는 것이다

 

코드는 다음과 같다

 

def kmpSearch(H, N):
    n = len(H)
    m = len(N)
    # 결과값 리스트
    ret = []
    # pi[i]는 N[~i]의 접두사도 되고 접미사는 되는 문자열의 최대 길이
    pi = getPartialMatch(N)

    begin = 0
    matched = 0
    while begin <= n - m:
        # 글자가 일치한다면
        if matched < m and H[begin + matched] == N[matched]:
            matched += 1
            # m글자가 모두 일치한다면
            if matched == m:
                ret.append(begin)
        else:
            # matched가 0인 경우 다음 칸에서 시작
            if matched == 0:
                begin += 1
            else:
                begin += matched - pi[matched - 1]
                matched = pi[matched - 1]

    return ret

 

시간 복잡도인 반복문의 전체 수행 횟수는 H의 길이에 비례함을 알 수 있다

 

---

 

부분 일치 테이블의 구현은 어떻게 ?

사실 이 역시도 KMP 알고리즘으로 구현할 수 있다

일치가 일어날 때마다 pi[]를 갱신하는 것만 제외한다면 거의 흡사하다

pi[]의 각 원소는 최대 한 번만 변경된다는 사실에 주목하여 다음 코드를 보자

 

def getPartialMatch(N):
    m = len(N)
    pi = [0] * m
    # KMP로 N에서 N을 찾는다 (begin은 1부터)
    begin = 1
    matched = 0
    # 비교할 문자가 N의 끝에 도달할 때까지 부분 일치를 모두 기록
    while begin + matched < m:
        if N[begin + matched] == N[matched]:
            matched += 1
            pi[begin + matched - 1] = matched
        else:
            if matched == 0:
                begin += 1
            else:
                begin += matched - pi[matched - 1]
                matched = pi[matched - 1]

    return pi

 

시간 복잡도는 역시 N의 길이에 비례함을 알 수 있다

따라서 전체의 시간 복잡도는 O( M의 길이 + N의 길이 ) 가 된다

 

---

 

전체 코드는 다음과 같다

 

def kmpSearch(H, N):
    n = len(H)
    m = len(N)
    # 결과값 리스트
    ret = []
    # pi[i]는 N[~i]의 접두사도 되고 접미사는 되는 문자열의 최대 길이
    pi = getPartialMatch(N)

    begin = 0
    matched = 0
    while begin <= n - m:
        # 글자가 일치한다면
        if matched < m and H[begin + matched] == N[matched]:
            matched += 1
            # m글자가 모두 일치한다면
            if matched == m:
                ret.append(begin)
        else:
            # matched가 0인 경우 다음 칸에서 시작
            if matched == 0:
                begin += 1
            else:
                begin += matched - pi[matched - 1]
                matched = pi[matched - 1]
    return ret


def getPartialMatch(N):
    m = len(N)
    pi = [0] * m
    # KMP로 N에서 N을 찾는다 (begin은 1부터)
    begin = 1
    matched = 0
    # 비교할 문자가 N의 끝에 도달할 때까지 부분 일치를 모두 기록
    while begin + matched < m:
        if N[begin + matched] == N[matched]:
            matched += 1
            pi[begin + matched - 1] = matched
        else:
            if matched == 0:
                begin += 1
            else:
                begin += matched - pi[matched - 1]
                matched = pi[matched - 1]
    return pi

H = "aflkjsklfaabaabacdsfwdsfaba"
N = "aabaabac"

print(kmpSearch(H, N)) # output : [9]

 

이 이외의 보이어-무어 알고리즘, 접미사 배열 등 여러가지 문자열 검색 알고리즘이 있다

snupi.tistory.com/2

[C code] 보이어-무어 알고리즘 (Boyer-Moore Algorithm)