목표: 주어진 패턴의 모든 발생 위치를 반환하는 선형 시간 복잡도의 문자열 매칭 알고리즘을 Swift로 구현한다.
다시 말해, String에 indexesOf(pattern: String) 확장을 추가해 패턴 검색 결과를 나타내는 정수 배열 [Int]를 반환하거나, 문자열 내에서 패턴을 찾지 못한 경우 nil을 반환한다.
예시:
let str = "Hello, playground!"
str.indexesOf(pattern: "ground") // 출력: [11]
let traffic = "🚗🚙🚌🚕🚑🚐🚗🚒🚚🚎🚛🚐🏎🚜🚗🏍🚒🚲🚕🚓🚌🚑"
traffic.indexesOf(pattern: "🚑") // 출력: [4, 21]많은 문자열 검색 알고리즘은 후속 단계에서 사용할 테이블을 계산하기 위해 전처리 함수를 사용한다. 이 테이블은 불필요한 문자 비교를 피할 수 있게 해주어 패턴 검색 단계에서 시간을 절약한다. Z-알고리즘은 이러한 함수 중 하나다. 이 알고리즘은 원래 패턴 전처리 함수로 탄생했지만(이것이 Knuth-Morris-Pratt 알고리즘 등에서의 역할임), 여기서 보여주듯 단독 문자열 검색 알고리즘으로도 사용할 수 있다.
앞서 언급했듯이, Z-Algorithm은 주로 패턴을 처리하여 비교 건너뛰기 테이블을 계산하는 알고리즘이다. 패턴 P에 대해 Z-Algorithm을 실행하면 정수 배열 Z가 생성된다. 이 배열의 각 요소 Z[i]는 P의 i 위치에서 시작하며 P의 접두사와 일치하는 가장 긴 부분 문자열의 길이를 나타낸다. 쉽게 말해, Z[i]는 P[i...|P|]의 가장 긴 접두사가 P의 접두사와 얼마나 일치하는지 기록한다. 예를 들어, P = "ffgtrhghhffgtggfredg"일 때, Z[5] = 0 (f...h...), Z[9] = 4 (ffgtr...ffgtg...), Z[15] = 1 (ff...fr...)이다.
그렇다면 Z를 어떻게 계산할까? 알고리즘을 설명하기 전에 Z-box 개념을 이해해야 한다. Z-box는 계산 과정에서 사용되는 (left, right) 쌍으로, P의 접두사와 일치하는 가장 긴 부분 문자열을 기록한다. left와 right는 각각 이 부분 문자열의 시작과 끝 인덱스를 나타낸다.
Z-Algorithm은 귀납적으로 정의되며, 패턴의 각 위치 k에 대해 Z[k]를 계산한다. 알고리즘의 핵심은 이전에 계산된 값들을 활용해 Z[k + 1]을 빠르게 계산하는 것이다. 이는 이미 수행한 문자 비교를 건너뛰는 방식으로 동작한다. 예를 들어, k = 100일 때, Z[1]부터 Z[99]까지의 값이 이미 계산되어 있고 left = 70, right = 120이라면, 70 위치에서 시작해 120에서 끝나는 길이 51의 부분 문자열이 패턴의 접두사와 일치한다. 이 경우, 100 위치에서 시작하는 길이 21의 부분 문자열은 패턴의 30 위치에서 시작하는 부분 문자열과 일치하므로, 추가적인 문자 비교 없이 Z[30]을 사용해 Z[100]을 계산할 수 있다.
이 알고리즘의 기본 아이디어는 이렇다. 다만, 미리 계산된 값을 직접 적용할 수 없는 경우도 있으며, 이때는 추가적인 비교가 필요하다.
다음은 Z-array를 계산하는 함수의 코드다:
func ZetaAlgorithm(ptrn: String) -> [Int]? {
let pattern = Array(ptrn)
let patternLength: Int = pattern.count
guard patternLength > 0 else {
return nil
}
var zeta: [Int] = [Int](repeating: 0, count: patternLength)
var left: Int = 0
var right: Int = 0
var k_1: Int = 0
var betaLength: Int = 0
var textIndex: Int = 0
var patternIndex: Int = 0
for k in 1 ..< patternLength {
if k > right { // Z-box 외부: 문자 비교
patternIndex = 0
while k + patternIndex < patternLength &&
pattern[k + patternIndex] == pattern[patternIndex] {
patternIndex = patternIndex + 1
}
zeta[k] = patternIndex
if zeta[k] > 0 {
left = k
right = k + zeta[k] - 1
}
} else { // Z-box 내부
k_1 = k - left + 1
betaLength = right - k + 1
if zeta[k_1 - 1] < betaLength { // Z-box 내부: 이전 값 사용
zeta[k] = zeta[k_1 - 1]
} else if zeta[k_1 - 1] >= betaLength { // Z-box 외부: 추가 비교
textIndex = betaLength
patternIndex = right + 1
while patternIndex < patternLength && pattern[textIndex] == pattern[patternIndex] {
textIndex = textIndex + 1
patternIndex = patternIndex + 1
}
zeta[k] = patternIndex - k
left = k
right = patternIndex - 1
}
}
}
return zeta
}이 코드를 예제와 함께 살펴보자. 문자열 P = "abababbb"를 고려해보자. 알고리즘은 k = 1, left = right = 0으로 시작한다. 이때는 활성화된 Z-box가 없으므로 k > right 조건에 따라 P[1]과 P[0]을 비교한다.
01234567
k: x
abababbb
x
Z: 00000000
left: 0
right: 0
첫 번째 비교에서 불일치가 발생하므로 P[1]에서 시작하는 부분 문자열은 P의 접두사와 일치하지 않는다. 따라서 Z[1] = 0으로 설정하고 left와 right는 그대로 둔다. 다음으로 k = 2일 때, 2 > 0이므로 다시 P[2]와 P[0]을 비교한다. 이번에는 문자가 일치하므로 불일치가 발생할 때까지 비교를 계속한다. 불일치는 위치 6에서 발생하며, 일치한 문자는 4개이므로 Z[2] = 4로 설정하고 left = k = 2, right = k + Z[k] - 1 = 5로 설정한다. 이제 첫 번째 Z-box인 "abab"가 생성되었다. 이 부분 문자열은 P의 접두사와 일치하며, left = 2에서 시작한다.
01234567
k: x
abababbb
x
Z: 00400000
left: 2
right: 5
다음으로 k = 3일 때, 3 <= 5이므로 이전에 찾은 Z-box 내부에 위치한다. 따라서 이전에 계산된 값을 사용할 수 있다. k_1 = k - left = 1을 계산하고, Z[1] = 0을 확인한다. 0 < (right - k + 1 = 3)이므로 Z-box 내부에 정확히 위치한다. 따라서 Z[3] = Z[1] = 0으로 설정하고 left와 right는 그대로 둔다.
k = 4일 때는 외부 if의 else 분기를 실행한다. 내부 if에서 k_1 = 2이고 (Z[2] = 4) >= 5 - 4 + 1이므로, P[k...r] 부분 문자열이 P의 접두사와 right - k + 1 = 2 문자까지 일치하지만, 이후 문자는 일치하지 않을 수 있다. 따라서 r + 1 = 6 위치의 문자와 right - k + 1 = 2 위치의 문자를 비교한다. P[6] != P[2]이므로 Z[k] = 6 - 4 = 2, left = 4, right = 5로 설정한다.
01234567
k: x
abababbb
x
Z: 00402000
left: 4
right: 5
k = 5일 때는 k <= right이므로 (Z[k_1] = 0) < (right - k + 1 = 1)이므로 z[k] = 0으로 설정한다. k = 6과 k = 7일 때는 외부 if의 첫 번째 분기를 실행하지만 불일치만 발생하므로 알고리즘이 종료되고 Z = [0, 0, 4, 0, 2, 0, 0, 0]을 반환한다.
Z-Algorithm은 선형 시간에 실행된다. 즉, 크기 n의 문자열 P에 대해 Z-Algorithm의 실행 시간은 O(n)이다.
Z-Algorithm의 문자열 전처리 구현은 ZAlgorithm.swift 파일에 포함되어 있다.
앞서 설명한 Z-Algorithm은 가장 간단한 선형 시간 문자열 매칭 알고리즘을 제공한다. 이를 구현하기 위해 패턴 P와 텍스트 T를 S = P$T 형태로 연결한다. 여기서 $는 P와 T에 모두 등장하지 않는 문자이다. 그런 다음 S에 대해 Z-Algorithm을 실행해 Z-배열을 얻는다. 이제 Z-배열을 스캔하면서 n(패턴의 길이)과 같은 값을 찾는다. 해당 값을 발견하면 매칭이 발생한 위치를 보고한다.
extension String {
func indexesOf(pattern: String) -> [Int]? {
let patternLength: Int = pattern.count
/* 패턴과 텍스트를 연결한 문자열에 Z-Algorithm을 적용 */
let zeta = ZetaAlgorithm(ptrn: pattern + "💲" + self)
guard zeta != nil else {
return nil
}
var indexes: [Int] = [Int]()
/* Z-배열을 스캔해 매칭된 패턴을 찾음 */
for i in 0 ..< zeta!.count {
if zeta![i] == patternLength {
indexes.append(i - patternLength - 1)
}
}
guard !indexes.isEmpty else {
return nil
}
return indexes
}
}예제를 통해 살펴보자. 패턴 P = “CATA“와 텍스트 T = "GAGAACATACATGACCAT"이 있다고 가정한다. 이 둘을 $ 문자로 연결하면 S = "CATA$GAGAACATACATGACCAT"이 된다. S에 Z-Algorithm을 적용하면 다음과 같은 결과를 얻는다.
1 2
01234567890123456789012
CATA$GAGAACATACATGACCAT
Z 00000000004000300001300
^
Z-배열을 스캔하면 위치 10에서 Z[10] = 4 = n을 발견한다. 따라서 텍스트 위치 10 - n - 1 = 5에서 매칭이 발생했음을 알 수 있다.
앞서 언급했듯이 이 알고리즘의 복잡도는 선형이다. 패턴과 텍스트의 길이를 각각 n과 m으로 정의하면 최종 복잡도는 O(n + m + 1) = O(n + m)이 된다.
참고: 이 코드는 Dan Gusfield의 저서 "Algorithm on String, Trees and Sequences: Computer Science and Computational Biology" (Cambridge University Press, 1997)를 기반으로 작성되었다.
Swift Algorithm Club을 위해 Matteo Dunnhofer가 작성