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

🔎 KMP

문자열 검색에서 널리 사용되는 알고리즘 KMP를 알아보자. 우선 이름이 KMP인 이유는 개발자인 Knuth, Morris, Pratt의 이름을 따왔다고 한다. 이름에 큰 의미는 없다! 한번 알아보자!

Algoritmo di Knuth-Morris-Pratt - Wikipedia

🔡 문자열을 검색한다면?

만약에 "ABC ABCDAB ABCDABCDABDE" 라는 텍스트에서 "ABCDABD" 패턴이 어디에 있는지를 찾고 싶다면 어떻게 해야 할까? 가장 단순한 방법은 텍스트의 첫 번째부터 순서대로 "ABCDABD" 가 되는지 체크해보는 것이다.

이렇게 된다면 텍스트의 길이가 n이고, 패턴의 길이가 m이라면 O(nm)의 시간복잡도를 가지게 된다. 모든 텍스트에서 m의 길이만큼 비교해줘야 하니까!

😤 좀더 효율적인 방법이 없을까?

대충 300페이지 책이 60만자의 글자가 있다고 친다면(한페이지당 300~500단어 한단어에 5자 계산 가정) 만약에 1,000자의 패턴만 구하게 되어도 6억번의 연산이 필요하고, 더 긴글은 검색한번하는데 몇초가 걸릴 수 있다. 분명 개선할 방법이 필요하다.

 

"ABC ABCDAB ABCDABCDABDE" 라는 텍스트에서 "ABCDABD" 패턴을 찾을때 첫번째부터 출발해서 패턴을 하나하나 비교했는데 이전에 비교하면서 사용안하고 넘어간 게 있다. 바로 아래의 경우는 ABC까지는 확실히 비교가 되었고 동일하다는 것! 이 뜻은 B와 C로 시작하는 것은 비교할 필요도 없다는 것이다.

불일치한 시점에서 그 바로 뒤인 B와 C로 시작해봤자 A로 시작하는 패턴과 안맞을게 뻔하다. 그렇다면 바로 건너뛸 수 있다.

이것은 바로 일치하지 않기 때문에 다음으로 넘어간다.

아쉽게도 마지막 D가 일치하지 않았다. 그렇다면 적어도 우린 A로 시작한 곳으로 옮겨야 하니 아래와 같이 다시 비교가 가능하다.

이것도 마찬가지로 AB로 비교를 이미 했기 때문에 넘어가준다. 바로 불일치하기 때문에 다음으로 넘어간다.

오 넘어가니 이번에도 아쉽게 D에서 불일치가 일어났다. 우리는 여기서 최소 A로는 시작해야함을 알 수 있다.

A로 시작한 곳으로 옮겼더니 일치하게 되었다! 그 뒤는 어자피 길이가 부족하기 때문에 탐색을 종료한다.

🔖 부분 일치 테이블

사실 여기서 단순하게 최소 A로 시작해야한다고 했는데 사실은 AB로 시작해야 한다는 기준을 가지고 움직이면 된다. 어떻게 건너뛰고 이것을 판단할 수 있을까? 이것이 KMP의 핵심이다. "ABCDABD" 에서 어떻게 활용이 가능할까? 바로 패턴 안에서 "AB" 가 반복된다는 것이다.

이것을 부분 일치 테이블을 생성하여 나타낼 수 있다. 맨 아래 T[i] 배열이 핵심이다. 실패 했을때 어디로 가서 다시 비교할 것인가를 나타낸다.

이러한 테이블을 구하는 알고리즘은 아래와 같다. 위키피디아의 의사코드를 보고 작성했다.

func kmpTable(_ pattern: String) -> [Int] {
    let word = Array(pattern)
    
    var table = [Int](repeating: 0, count: pattern.count + 1)
    table[0] = -1
    
    var pos = 1 /// 현재 위치
    var cnd = 0 /// 접두사 접미사 일치 후보 인덱스 (candidate)

    while pos < pattern.count {
        if word[pos] == word[cnd] {
            table[pos] = table[cnd]
        } else {
            table[pos] = cnd
            /// 다를 때 사용할 수 있는 반복되는 부분 찾음
            while cnd >= 0 && word[pos] != word[cnd] {
                cnd = table[cnd]
            }
        }
                
        pos += 1
        cnd += 1
    }
    
    table[pos] = cnd
    
    return table
}

위 코드를 돌려보면 아래와 같이 테이블이 나오게 된다. 테이블이 뜻하는 것은 현재 인덱스에서 틀렸을 때 다음 비교위치를 해당 인덱스로 바꾸면 된다는 뜻이다. 예를들면 ABCDABD에서 D에서 틀렸을 때 앞에 index 2인 C부터 다시 비교하시면 됩니다. 라는 뜻이다.

print(kmpTable("ABCDABD")) // [-1, 0, 0, 0, -1, 0, 2, 0]
print(kmpTable("ABABAC")) // [-1, 0, -1, 0, -1, 3, 0]

🧮 알고리즘 구현

테이블은 O(m), 검색 알고리즘은 O(n)이므로 결국 O(m+n)의 효율적인 시간복잡도로 알고리즘을 구현 할 수 있다.

func kmpSearch(text: String, pattern: String) -> [Int] {
    let table = kmpTable(pattern)

    let text = Array(text)
    let pattern = Array(pattern)
    
    var i = 0  // 텍스트 인덱스
    var j = 0  // 패턴 인덱스
    var result = [Int]()  // 매칭 위치 저장
    
    while i < text.count {
        if text[i] == pattern[j] {
            i += 1
            j += 1
            
            if j == pattern.count {
                // 전체 패턴이 일치하면 시작 인덱스 저장
                result.append(i - j)
                j = table[j]  // 다음 비교 위치
            }
        } else {
            j = table[j]  // 실패시 점프
            if j < 0 {
                // 처음부터 다시 비교
                i += 1
                j += 1
            }
        }
    }
    
    return result
}

🥸 테이블을 구하는 다른 방법

사실 KMP 알고리즘을 알고 있다면 위의 테이블을 보면 이상함을 느꼈을 수도 있다. 흔히 아는 π 배열을 만드는 과정이 아니었기 때문이다. 위키에서는 테이블을 활용하여 설명이 되어있지만 보통 KMP 알고리즘 설명을 보면 π 배열로 설명이 되어있다. 구현은 아래와 같다.

func prefixTable(_ pattern: String) -> [Int] {
    let word = Array(pattern)
    var table = [Int](repeating: 0, count: word.count)
    var j = 0

    for i in 1..<word.count {
        while j > 0 && word[i] != word[j] {
            /// 일치하지 않을 경우, 이전 접두사, 접미사 길이 정보를 이용해 j를 줄임
            j = table[j - 1]
        }
        if word[i] == word[j] {
            j += 1
            table[i] = j
        }
    }

    return table
}

기존의 kmpTable은 실패 시 점프할 인덱스를 나타내는데, 위의 함수는 겹치는 접두사와 접미사의 길이를 나타낸다. 예를들면 ABCDAB에서는 AB가 겹치기 때문에 2인것이고, ABCDA에서는 A가 겹치기 때문에 1이다.

print(prefixTable("ABCDABD"))  // [0, 0, 0, 0, 1, 2, 0]

이것으로 kmpSearch를 구현해보면 아래와 같다.

func kmpSearch(text: String, pattern: String) -> [Int] {
    let table = prefixTable(pattern)
    
    let text = Array(text)
    let pattern = Array(pattern)

    var result: [Int] = []
    var j = 0  // 패턴 인덱스

    for i in 0..<text.count {
        // 불일치, 테이블을 이용해 j 줄이기
        while j > 0 && text[i] != pattern[j] {
            j = table[j - 1]
        }

        // 일치, j 증가
        if text[i] == pattern[j] {
            j += 1
        }

        // 패턴 끝까지 다 일치한 경우
        if j == pattern.count {
            result.append(i - j + 1)  // 일치한 시작 위치 저장
            j = table[j - 1]          // 다음 일치 후보로 이동
        }
    }

    return result
}