단순 문자열 탐색·롤링 해시·충돌

문서 편집기에서 단어를 찾으면 그 단어가 나오는 곳이 모두 표시됩니다. 이 일을 정확히 말하면, 긴 문자열 text 안에서 짧은 문자열 pattern과 똑같은 연속 구간이 시작하는 위치를 모두 찾는 것입니다. LCS가 건너뛰기를 허용하는 부분 수열을 다뤘다면, 여기서 찾는 것은 글자가 빈틈없이 이어지는 부분 문자열입니다. 이 글에서는 가장 단순한 방법이 어떤 입력에서 느려지는지 확인하고, 구간을 수 하나로 바꾸어 비교하는 Rabin–Karp 알고리즘을 만듭니다. 이 과정에서 서로 다른 문자열이 같은 수가 되는 충돌을 어떻게 다루는지가 중요합니다.

무엇을 찾는가

함수는 text와 pattern을 받아, pattern이 나타나는 모든 시작 인덱스를 작은 것부터 담은 리스트를 돌려주기로 합니다. 나타나는 구간이 서로 겹쳐도 모두 셉니다. ABABA에서 ABA는 인덱스 0과 2에서 시작하는데, 두 구간은 가운데의 A를 함께 씁니다. pattern이 text보다 길면 나타날 수 없으므로 빈 리스트를 돌려줍니다.

빈 문자열을 찾는 경우는 따로 정해 두어야 합니다. 빈 문자열은 어느 위치에나 길이 0으로 나타난다고 볼 수 있으므로, 길이 n인 text에서 글자 사이와 양 끝의 n + 1곳 모두에서 나타난다고 정하겠습니다. Python도 같은 약속을 써서 "AB".count("")는 3이고 "AB".find("")는 0입니다.

단순 탐색

가장 직접적인 방법은 pattern이 시작할 수 있는 모든 위치 i에서, text의 i번 글자부터 pattern과 한 글자씩 비교하는 것입니다. 다른 글자가 나오면 그 위치를 포기하고 다음 위치로 넘어가고, pattern의 끝까지 모두 같으면 i를 기록합니다. 시작할 수 있는 위치는 0부터 n - m까지입니다. 여기서 n은 text의 길이, m은 pattern의 길이입니다.

def naive_matches(text, pattern):
    n, m = len(text), len(pattern)
    matches, comparisons = [], 0
    for i in range(n - m + 1):
        k = 0
        while k < m:
            comparisons += 1
            if text[i + k] != pattern[k]:
                break
            k += 1
        if k == m:
            matches.append(i)
    return matches, comparisons


print(naive_matches("ABABA", "ABA"))
print(naive_matches("AAAA", "AA"))
print(naive_matches("A" * 20, "AAAB"))
print(naive_matches("AB", ""), naive_matches("AB", "ABC"))

([0, 2], 7)
([0, 1, 2], 6)
([], 68)
([0, 1, 2], 0) ([], 0)

각 결과는 찾은 위치와 글자를 비교한 횟수입니다. ABABA에서는 위치 0에서 세 글자, 위치 1에서 한 글자, 위치 2에서 세 글자를 비교해 모두 7번입니다. 빈 pattern은 비교 없이 모든 위치에서 바로 일치하고, text보다 긴 pattern은 시작할 위치가 없습니다.

세 번째 입력이 이 방법의 약점입니다. A만 20개인 text에서 AAAB를 찾으면, 시작할 수 있는 17곳 모두에서 A 세 개가 같다가 마지막 B에서야 실패하므로 17 × 4 = 68번을 비교합니다. 일반적으로 최악의 경우 (n - m + 1) × m번, 곧 O(nm)을 비교합니다. 위치 1에서 비교를 시작할 때, 위치 0에서 이미 확인한 A 세 개를 다시 읽고 있다는 점이 낭비입니다. 이 낭비를 없애는 방법은 다음 두 글의 KMP 알고리즘에서 다루고, 이 글에서는 다른 방향의 방법을 봅니다.

구간을 수로 바꾸어 비교하기

글자를 m번 비교하는 대신, 길이 m인 구간을 수 하나로 바꾸어 두 수만 비교한다면 어떨까요? 숫자로 이루어진 문자열이라면 쉽게 상상할 수 있습니다. text가 31415이고 pattern이 41이라면, 길이 2인 구간들은 31, 14, 41, 15라는 두 자리 수가 되고, 이 수들을 41과 비교하면 됩니다.

게다가 다음 구간의 수는 앞 구간의 수에서 쉽게 구할 수 있습니다. 31에서 14로 갈 때는 맨 앞 자리 3이 빠지고 뒤에 4가 붙습니다. 그래서 31에서 3 × 10을 빼서 1을 만들고, 10을 곱해 10으로 한 자리 올린 뒤, 4를 더하면 14입니다. 구간 길이가 m이라면 빠지는 맨 앞 자리의 값은 그 숫자에 10ᵐ⁻¹을 곱한 것입니다. 이렇게 한 칸 밀 때마다 빠지는 글자와 들어오는 글자만으로 새 값을 구하는 방법을 롤링 해시(rolling hash)라고 합니다. 구간 길이가 얼마든 한 칸 미는 데 드는 계산은 일정합니다.

일반 문자열은 글자마다 ord로 얻는 코드 번호를 숫자 하나로 보고, 10 대신 더 큰 밑 base를 씁니다. 이렇게 하면 길이 m인 문자열이 base진법으로 m자리인 수가 되는데, m이 조금만 커도 수가 너무 커집니다. 그래서 그 수를 정해 둔 수 modulus로 나눈 나머지만 저장합니다. 이렇게 문자열을 정해진 범위의 수로 바꾸는 함수를 해시 함수(hash function)라 하고, 그 결과를 해시값이라고 합니다. 리스트·배열·문자열·딕셔너리의 역할에서 딕셔너리가 키의 위치를 정할 때 쓴 것과 같은 생각입니다. 나머지를 취해도 덧셈, 뺄셈, 곱셈의 결과는 맞게 유지되므로 롤링 갱신을 그대로 쓸 수 있습니다.

충돌: 해시가 같아도 문자열은 다를 수 있다

해시값의 범위는 modulus보다 작은 수로 정해져 있지만, 가능한 문자열은 그보다 훨씬 많습니다. 그래서 서로 다른 문자열이 같은 해시값을 가질 수밖에 없는데, 이것을 충돌(collision)이라고 합니다. 밑 256, modulus 101로 계산하면 AH와 CA의 해시값은 모두 47입니다. AH는 65 × 256 + 72 = 16712이고 CA는 67 × 256 + 65 = 17217인데, 둘 다 101로 나눈 나머지가 47이기 때문입니다.

따라서 해시값이 같다는 것은 "같을 수도 있다"는 뜻일 뿐입니다. 해시값이 다르면 문자열이 확실히 다르므로 바로 건너뛰고, 해시값이 같을 때만 실제 글자를 비교해 정말 같은지 확인해야 합니다. 이 확인을 빼면, 충돌이 일어난 위치를 일치하는 위치로 잘못 보고하게 됩니다. 해시값 비교로 대부분의 위치를 빠르게 걸러 내고, 남은 후보만 정확하게 확인하는 것이 Rabin–Karp 알고리즘의 생각입니다.

def rabin_karp(text, pattern, base=256, modulus=101):
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1))
    if m > n:
        return []
    highest = pow(base, m - 1, modulus)
    pattern_hash = window_hash = 0
    for i in range(m):
        pattern_hash = (pattern_hash * base + ord(pattern[i])) % modulus
        window_hash = (window_hash * base + ord(text[i])) % modulus
    matches = []
    for i in range(n - m + 1):
        if window_hash == pattern_hash and text[i:i + m] == pattern:
            matches.append(i)
        if i < n - m:
            window_hash = ((window_hash - ord(text[i]) * highest) * base + ord(text[i + m])) % modulus
    return matches


print(rabin_karp("ABABA", "ABA"))
print(rabin_karp("XCAY", "AH"))
print(rabin_karp("ABABA", "ABA", modulus=1))
print(rabin_karp("가나다가나", "가나"))
print(rabin_karp("AB", ""), rabin_karp("AB", "ABC"))

[0, 2]
[]
[0, 2]
[0, 3]
[0, 1, 2] []

highest는 맨 앞 글자가 차지하는 자리의 크기인 base의 m - 1제곱을 modulus로 나눈 나머지입니다. pow(base, m - 1, modulus)는 큰 거듭제곱을 다 계산하지 않고 나머지만 효율적으로 구합니다. 처음 반복에서 pattern과 text의 첫 구간의 해시값을 만들고, 다음 반복에서 각 위치의 해시값을 비교한 뒤 롤링 갱신으로 한 칸 밉니다. Python의 %는 왼쪽 수가 음수여도 0 이상인 나머지를 돌려주므로, 뺄셈 때문에 값이 음수가 되어도 문제가 없습니다.

두 번째 호출에서 XCAY의 CA는 찾는 AH와 해시값이 47로 같지만, 실제 글자를 비교해 걸러 냅니다. 세 번째 호출의 modulus 1은 모든 문자열의 해시값을 0으로 만드는 극단적인 경우입니다. 모든 위치가 후보가 되지만 실제 비교 덕분에 결과는 여전히 맞습니다. 다만 모든 위치에서 글자를 비교하므로 단순 탐색과 다를 바 없이 느려집니다.

왜 맞고 왜 끝나는가

롤링 갱신이 맞는 것은 해시값이 각 글자의 코드에 그 자리의 크기를 곱해 더한 값이기 때문입니다. 맨 앞 글자의 몫인 코드 × base의 m - 1제곱을 빼면 나머지 m - 1글자의 값이 남고, base를 곱하면 각 글자가 한 자리씩 올라가며, 새 글자의 코드를 더하면 다음 구간의 해시값과 정확히 같아집니다. 모든 계산을 modulus로 나눈 나머지로 해도 이 관계는 그대로 유지됩니다.

결과가 맞는 이유는 두 가지입니다. 모든 시작 위치를 검사하고, 실제로 일치하는 위치는 해시값도 반드시 같으므로 놓치는 위치가 없습니다. 또 기록하기 전에 실제 글자를 비교하므로 일치하지 않는 위치를 기록하는 일도 없습니다. 반복은 시작 위치를 한 칸씩 오른쪽으로 옮기다가 n - m에서 끝납니다.

비용과 쓰임

해시값을 처음 만드는 데 O(m), 위치마다 해시값을 비교하고 미는 데 O(1)이 들므로, 실제 글자 비교를 빼면 전체가 O(n + m)입니다. 실제 글자 비교는 해시값이 같은 위치에서만 하며, 충돌이 드물고 일치하는 위치가 많지 않다면 전체 비용도 O(n + m)에 가깝습니다. 하지만 AAAA…에서 AA…를 찾는 것처럼 일치하는 위치가 많거나 충돌이 많으면 위치마다 m글자를 비교해 최악의 경우 O(nm)이 됩니다.

Rabin–Karp 알고리즘이 특히 쓸모 있는 것은 같은 길이의 pattern 여러 개를 한꺼번에 찾을 때입니다. pattern들의 해시값을 딕셔너리나 집합에 넣어 두면, text를 한 번 훑으며 구간마다 해시값이 그 안에 있는지만 확인하면 되기 때문입니다. 두 문서에서 같은 길이의 구간이 얼마나 겹치는지 세어 표절을 찾는 도구들이 이 방법을 응용합니다. Python의 str.find와 in은 이보다 정교한 방법들을 섞어 C로 구현해서, 하나의 pattern을 찾을 때는 직접 만든 함수보다 훨씬 빠릅니다.

더 깊이: 충돌은 얼마나 자주 일어날까

이 글의 modulus 101은 충돌을 쉽게 보여 주려고 일부러 작게 고른 값입니다. 해시값이 0부터 modulus - 1까지 고르게 퍼진다고 하면, 서로 다른 두 구간이 우연히 같은 해시값을 가질 확률은 대략 1/modulus입니다. 그래서 실제로는 modulus를 10억 정도 되는 소수나 그보다 큰 소수로 정합니다. 그러면 구간이 100만 개인 text에서 거짓 후보는 평균 0.001개 정도라, 실제 글자 비교는 거의 진짜 일치에서만 일어납니다.

다만 이 계산은 입력이 해시 함수와 상관없이 주어진다는 가정 위에 있습니다. base와 modulus가 알려져 있으면 일부러 충돌하는 문자열을 만들어 탐색을 느리게 할 수 있습니다. 그래서 그런 입력이 걱정되는 프로그램에서는 실행할 때마다 base를 무작위로 고릅니다. 딕셔너리에서 Python이 문자열의 해시값을 실행할 때마다 섞는 것도 같은 이유입니다.

정리

• 문자열 탐색은 text 안에서 pattern과 같은 연속 구간이 시작하는 모든 위치를 찾는 문제이며, 겹치는 구간도 세고 빈 pattern은 n + 1곳에서 나타난다고 정했습니다.
• 단순 탐색은 시작 위치마다 글자를 비교해, 거의 일치하다 끝에서 실패하는 입력에서 O(nm)이 듭니다.
• 롤링 해시는 구간을 base진법의 수로 보고, 한 칸 밀 때 맨 앞 글자의 몫을 빼고 한 자리 올린 뒤 새 글자를 더해 O(1)에 다음 해시값을 구합니다.
• 서로 다른 문자열이 같은 해시값을 갖는 충돌이 있으므로, 해시값이 같을 때 실제 글자를 비교해야 정확합니다.
• Rabin–Karp 알고리즘은 충돌이 드물면 O(n + m)에 가깝지만 최악은 O(nm)이며, 같은 길이의 pattern 여러 개를 한꺼번에 찾을 때 특히 쓸모 있습니다.

연습 문제

1. 겹치는 일치

text가 AAAA이고 pattern이 AA일 때 함수가 돌려주는 위치를 모두 쓰세요.

2. 실제 비교를 빼면

rabin_karp에서 and text[i:i + m] == pattern을 빼고 modulus를 1로 하면, ABABA에서 ABA를 찾을 때 어떤 위치가 잘못 추가될까요?

3. 손으로 롤링하기

밑 10을 쓰고 나머지는 취하지 않는다고 할 때, 2718에서 길이 3인 구간의 값을 첫 구간부터 롤링 갱신으로 구하세요.

다음 글 접두·접미·LPS 배열 만들기에서는 단순 탐색이 이미 읽은 글자를 다시 읽는 낭비를 없애기 위해, pattern 자신 안에서 앞부분과 뒷부분이 겹치는 정도를 미리 계산합니다.