Knuth-Morris-Pratt 문자열 검색

목표: 주어진 패턴의 모든 발생 위치를 반환하는 선형 시간 문자열 매칭 알고리즘을 Swift로 구현한다.

다시 말해, String에 indexesOf(pattern: String) 확장을 구현해 패턴이 문자열 내에서 발견된 모든 위치의 인덱스를 [Int] 배열로 반환하거나, 패턴이 발견되지 않으면 nil을 반환한다.

예시:

let dna = "ACCCGGTTTTAAAGAACCACCATAAGATATAGACAGATATAGGACAGATATAGAGACAAAACCCCATACCCCAATATTTTTTTGGGGAGAAAAACACCACAGATAGATACACAGACTACACGAGATACGACATACAGCAGCATAACGACAACAGCAGATAGACGATCATAACAGCAATCAGACCGAGCGCAGCAGCTTTTAAGCACCAGCCCCACAAAAAACGACAATFATCATCATATACAGACGACGACACGACATATCACACGACAGCATA"
dna.indexesOf(ptnr: "CATA")   // 출력: [20, 64, 130, 140, 166, 234, 255, 270]

let concert = "🎼🎹🎹🎸🎸🎻🎻🎷🎺🎤👏👏👏"
concert.indexesOf(ptnr: "🎻🎷")   // 출력: [6]

Knuth-Morris-Pratt 알고리즘은 패턴 매칭 문제를 해결하는 최고의 알고리즘 중 하나로 평가된다. 실제로는 Boyer-Moore 알고리즘이 더 선호되지만, 이 알고리즘은 더 단순하면서도 동일한 선형 시간 복잡도를 가진다.

이 알고리즘의 아이디어는 단순 문자열 검색과 크게 다르지 않다. 텍스트와 패턴을 정렬하고 왼쪽에서 오른쪽으로 문자를 비교한다. 하지만 불일치가 발생하면 한 문자씩 이동하는 대신, 더 지능적인 방식으로 패턴을 이동시킨다. 알고리즘은 패턴을 미리 처리하는 단계를 포함하며, 이 단계에서 불필요한 비교를 건너뛰고 더 큰 이동을 가능하게 하는 정보를 수집한다.

미리 처리 단계는 suffixPrefix라는 배열을 생성한다. 이 배열의 각 요소 suffixPrefix[i]는 패턴 P[0...i]의 가장 긴 접미사이면서 동시에 P의 접두사인 부분 문자열의 길이를 기록한다. 예를 들어, P = "abadfryaabsabadffg"일 때 suffixPrefix[4] = 0, suffixPrefix[9] = 2, suffixPrefix[14] = 4이다.

suffixPrefix 배열의 값을 얻는 방법은 여러 가지가 있다. 여기서는 Z-Algorithm을 기반으로 한 방법을 사용한다. 이 함수는 패턴을 입력받아 각 위치에서 시작하는 가장 긴 접두사와 일치하는 부분 문자열의 길이를 나타내는 정수 배열을 반환한다. Z[i]를 suffixPrefix[j]로 매핑하는 방법은 간단하다:

for patternIndex in (1 ..< patternLength).reversed() {
    textIndex = patternIndex + zeta![patternIndex] - 1
    suffixPrefix[textIndex] = zeta![patternIndex]
}

이 코드는 i 위치에서 시작하는 부분 문자열의 끝 인덱스를 계산하고, suffixPrefix 배열의 해당 인덱스에 부분 문자열의 길이를 설정한다.

suffixPrefix 배열이 준비되면 패턴 검색 단계를 시작한다. 알고리즘은 텍스트와 패턴의 문자를 비교한다. 일치하면 계속 비교하고, 불일치가 발생하면 패턴의 발생 여부를 확인한다. 비교가 이루어지지 않으면 텍스트 커서를 이동시키고, 그렇지 않으면 suffixPrefix 배열을 기반으로 패턴을 오른쪽으로 이동시킨다. 이 방식으로 한 번에 여러 문자를 이동시켜 많은 비교를 건너뛸 수 있다.

다음은 Knuth-Morris-Pratt 알고리즘의 코드이다:

extension String {

    func indexesOf(ptnr: String) -> [Int]? {

        let text = Array(self.characters)
        let pattern = Array(ptnr.characters)

        let textLength: Int = text.count
        let patternLength: Int = pattern.count

        guard patternLength > 0 else {
            return nil
        }

        var suffixPrefix: [Int] = [Int](repeating: 0, count: patternLength)
        var textIndex: Int = 0
        var patternIndex: Int = 0
        var indexes: [Int] = [Int]()

        /* 미리 처리 단계: Z-Algorithm을 통해 이동 테이블 계산 */
        let zeta = ZetaAlgorithm(ptnr: ptnr)

        for patternIndex in (1 ..< patternLength).reversed() {
            textIndex = patternIndex + zeta![patternIndex] - 1
            suffixPrefix[textIndex] = zeta![patternIndex]
        }

        /* 검색 단계: 텍스트를 스캔하며 패턴 매칭 */
        textIndex = 0
        patternIndex = 0

        while textIndex + (patternLength - patternIndex - 1) < textLength {

            while patternIndex < patternLength && text[textIndex] == pattern[patternIndex] {
                textIndex = textIndex + 1
                patternIndex = patternIndex + 1
            }

            if patternIndex == patternLength {
                indexes.append(textIndex - patternIndex)
            }

            if patternIndex == 0 {
                textIndex = textIndex + 1
            } else {
                patternIndex = suffixPrefix[patternIndex - 1]
            }
        }

        guard !indexes.isEmpty else {
            return nil
        }
        return indexes
    }
}

예시로, P = "ACTGACTA"와 suffixPrefix = [0, 0, 0, 0, 0, 0, 3, 1], 그리고 T = "GCACTGACTGACTGACTAG"를 사용해보자. 알고리즘은 텍스트와 패턴을 아래와 같이 정렬하고 비교를 시작한다.

                          1       
                0123456789012345678
text:           GCACTGACTGACTGACTAG
textIndex:      ^
pattern:        ACTGACTA
patternIndex:   ^
                x
suffixPrefix:   00000031

불일치가 발생하면 T[1]과 P[0]을 비교한다. 패턴 발생이 없으므로 패턴을 오른쪽으로 이동시키고 suffixPrefix[1 - 1]을 확인한다. 값이 0이므로 T[1]과 P[0]을 다시 비교한다. 다시 불일치가 발생하면 T[2]와 P[0]을 비교한다.

                          1      
                0123456789012345678
text:           GCACTGACTGACTGACTAG
textIndex:        ^
pattern:          ACTGACTA
patternIndex:     ^
suffixPrefix:     00000031

이번에는 일치한다. 비교는 위치 8까지 계속되지만 패턴 길이와 일치하지 않아 발생 위치를 보고할 수 없다. 그러나 suffixPrefix 배열의 값을 사용할 수 있다. 일치 길이가 7이므로 suffixPrefix[7 - 1]을 확인하면 값이 3이다. 이 정보는 P의 접두사가 T[0...8]의 접미사와 일치함을 보장한다. 따라서 패턴을 한 번에 여러 문자 이동시킬 수 있다.

비교는 T[9]와 P[3]부터 다시 시작한다.

                          1       
                0123456789012345678
text:           GCACTGACTGACTGACTAG
textIndex:               ^
pattern:              ACTGACTA
patternIndex:            ^
suffixPrefix:         00000031

일치하므로 비교를 계속하다가 위치 13에서 G와 A가 불일치한다. 이전과 마찬가지로 suffixPrefix 배열을 사용해 패턴을 이동시킨다.

                          1       
                0123456789012345678
text:           GCACTGACTGACTGACTAG
textIndex:                   ^
pattern:                  ACTGACTA
patternIndex:                ^
suffixPrefix:             00000031

다시 비교를 시작하고, 결국 위치 17 - 7 = 10에서 패턴 발생을 찾는다.

                          1       
                0123456789012345678
text:           GCACTGACTGACTGACTAG
textIndex:                       ^
pattern:                  ACTGACTA
patternIndex:                    ^
suffixPrefix:             00000031

알고리즘은 T[18]과 P[1]을 비교하려고 시도하지만 실패하고 다음 반복에서 작업을 종료한다.

미리 처리 단계는 패턴만을 다룬다. Z-Algorithm의 실행 시간은 선형이며 O(n)이다. 검색 단계는 텍스트의 길이 m을 초과하지 않는다. 검색 단계의 비교 횟수는 2 * m으로 제한된다. 따라서 Knuth-Morris-Pratt 알고리즘의 최종 실행 시간은 O(n + m)이다.

참고: KnuthMorrisPratt.swift 코드를 실행하려면 Z-Algorithm 폴더에 있는 ZAlgorithm.swift 파일을 복사해야 한다. KnuthMorrisPratt.playground에는 Zeta 함수 정의가 이미 포함되어 있다.

출처: 이 코드는 Dan Gusfield의 "Algorithm on String, Trees and Sequences: Computer Science and Computational Biology"를 기반으로 작성되었다.

Swift Algorithm Club을 위해 Matteo Dunnhofer가 작성