롤링 해시: 문자열 창의 지문을 빠르게 갱신하는 방법
롤링 해시는 연속된 문자열 구간의 해시값을 조금씩 이동하며 빠르게 갱신하는 기법이다. 매번 구간 전체를 읽지 않고 빠져나가는 문자와 새 문자를 반영한다. 문자열 검색이나 부분문자열 비교에 쓰이지만 해시 일치는 문자열의 동일성을 보장하지 않는다.
이동한 부분 문자열의 해시는 갱신할 수 있지만 해시가 같다고 문자열이 반드시 같은 것은 아니다.
다항식으로 문자를 압축하기
길이 m 문자열의 문자 코드를 c₀,…,cₘ₋₁이라 할 때 h=c₀bᵐ⁻¹+c₁bᵐ⁻²+…+cₘ₋₁을 모듈러 p로 계산할 수 있다. 창을 옮길 때 첫 문자의 기여 c₀bᵐ⁻¹을 빼고, 남은 부분에 b를 곱한 뒤 새 문자를 더한다.
def rolling_hashes(text, width, base=257, modulus=1000000007):
if not 1 <= width <= len(text):
return []
leading_power = pow(base, width - 1, modulus)
fingerprint = 0
for character in text[:width]:
fingerprint = (fingerprint * base + ord(character)) % modulus
result = [fingerprint]
for right in range(width, len(text)):
outgoing = ord(text[right - width])
incoming = ord(text[right])
fingerprint = (fingerprint - outgoing * leading_power) % modulus
fingerprint = (fingerprint * base + incoming) % modulus
result.append(fingerprint)
return result
이 코드는 모든 해시를 목록에 보관해 O(n) 결과 공간을 쓴다. 한 번에 현재 값만 소비하는 스트리밍 방식이라면 상태는 일정하게 유지할 수 있다. 첫 구간 계산은 O(m), 이후 각 이동은 모듈러 연산 비용을 일정하다고 보면 O(1)이다.
숫자로 이동 과정을 따라가기
문자 코드를 A=1,B=2,C=3으로 단순화하고 b=10이면 AB의 해시는 12다. BC로 이동할 때 A의 기여 10을 빼 2를 얻고, 10을 곱해 20, 새 C의 3을 더해 23이 된다. 실제 구현은 값이 계속 커지지 않도록 모듈러를 적용한다.
p개의 해시값으로 더 많은 문자열을 표현하므로 다른 문자열이 같은 값을 갖는 충돌은 필연적으로 존재한다. 패턴 해시와 창 해시가 같으면 실제 문자를 비교하여 확인할 수 있다. 서로 다른 모듈러 두 개를 쓰면 우연 충돌을 줄일 수 있지만 논리적으로 없애지는 못한다.
Rabin–Karp 검색은 이 원리로 후보를 빠르게 거른다. 일반적인 좋은 분포에서 효율적이지만 충돌마다 전체 패턴을 검사하면 최악 O(nm)이 될 수 있다. 선형 해시 계산과 전체 검색의 최악 비용을 구분해야 한다.
접두 해시와 미리 계산한 거듭제곱을 이용하면 임의 부분문자열의 지문도 빠르게 얻을 수 있다. 양쪽 구간의 길이와 지수 위치를 정규화하지 않으면 같은 문자열도 다른 값이 나온다.
롤링 해시는 암호학적 무결성이나 비밀번호 저장에 적합한 해시를 뜻하지 않는다. 빠른 갱신이라는 성질은 교육용 문자열 알고리즘의 목적에 맞춘 것이다. 충돌 허용 여부, 확인 방식, 수치 오버플로, 입력 단위를 명시해야 정확한 도구가 된다.