문자열 비교를 빠르게 만들기 위해 문자열 전체를 매번 읽지 않고 짧은 숫자 지문(fingerprint)을 비교할 수 있습니다. 다항식 rolling hash는 prefix hash를 미리 계산해 임의의 같은 길이 구간을 일정한 산술 연산으로 비교하게 해 줍니다. 하지만 숫자가 같다는 사실은 원문이 같다는 증명이 아닙니다. 알고리즘이 허용하는 확률적 오탐인지, 아니면 후보만 빠르게 줄이고 마지막에 정확 비교를 할 것인지가 구현의 핵심 계약입니다.
비교 키와 입력 표현
먼저 무엇을 같은 문자열로 볼지 고정해야 합니다. 바이트 배열을 비교하는지, 유니코드 코드 포인트를 비교하는지, 화면에 보이는 문자열을 비교하는지는 서로 다른 문제입니다. 예를 들어 é를 하나의 코드 포인트 U+00E9로 표현한 입력과 e 뒤에 combining acute를 둔 입력은 화면에서 비슷하게 보일 수 있어도 코드 포인트와 UTF-8 바이트 열이 다릅니다. 정규화를 적용한다면 모든 입력에 같은 정규화 형식, 대소문자 정책, 인코딩 단위를 적용한 뒤 hash를 계산해야 합니다.
해시는 키를 테이블에 배치하는 해시 테이블의 bucket collision과도 다릅니다. 문자열 rolling hash의 충돌은 서로 다른 구간이 같은 fingerprint를 갖는 현상이고, 해시 테이블에서는 같은 bucket에 들어간 뒤 키 동등성 비교로 해결합니다. 문자열 비교에서도 마지막에 실제 원문 비교를 하면 같은 원리로 거짓 양성을 제거할 수 있습니다. 반대로 hash만으로 승인하면 충돌에 대한 확률적 계약을 사용자에게 떠넘기는 셈입니다.
Prefix hash와 부분 구간 계산
정규화된 문자열의 각 문자를 숫자 value[i]로 매핑하고 base p, modulus m을 정합니다. 한 가지 인덱싱으로 H[0]=0, H[i+1]=(H[i]*p + value[i]) mod m을 두면 구간 [l,r)의 hash를
raw = H[r] - H[l] * p^(r-l) mod m
으로 계산할 수 있습니다. H[l]의 앞부분을 길이 r-l만큼 밀어 주고 빼는 이유는 prefix에서 구간 앞까지의 기여를 제거하기 위해서입니다. 음수 나머지는 언어 규칙이 제각각이므로 ((raw % m) + m) % m처럼 canonical residue를 만들거나 정수 타입의 범위를 확인합니다.
abracadabra에서 구간 [0,3)인 abr와 [7,10)인 abr를 비교한다고 해 보겠습니다. 두 구간의 hash를 각각 계산해 같은 값이 나오면 실제 비교 대상은 이제 a, b, r 세 글자로 좁혀집니다. prefix 배열에서 구간을 읽는 연산은 문자 수와 무관하지만, prefix 자체 H와 p의 거듭제곱 배열은 텍스트 길이에 비례합니다. 문자가 바뀌는 동적 문자열은 이 단순 전처리를 그대로 유지할 수 없으므로 Fenwick tree나 블록 구조 같은 별도 모델이 필요합니다.
Rabin-Karp 후보 탐색
Rabin-Karp는 패턴 길이 K의 hash와 텍스트의 모든 길이 K 윈도우 hash를 비교해 후보 위치를 찾습니다. prefix hash를 사용하면 각 윈도우를 [i,i+K)로 계산하고, rolling 갱신을 사용하면 이전 윈도우의 가장 오래된 항을 제거한 뒤 나머지를 한 자리 밀고 새 문자를 더합니다. 이 단계는 후보를 빠르게 거르는 필터이며, 일치 결과 자체가 아닙니다.
예를 들어 hash(ab)와 hash(ba)가 선택한 modulus에서 우연히 같은 값이 되었다고 가정하겠습니다. 텍스트에서 ba를 발견했을 때 hash만 보고 ab의 match라고 반환하면 거짓 양성이 됩니다. 정확한 결과가 필요한 검색에서는 후보마다 길이 K 원문을 다시 비교합니다. 충돌이 거의 없더라도 최악의 입력에서는 후보 검증이 반복되어 O(textLength * patternLength)까지 커질 수 있으므로, 공격 가능한 입력에서 rolling hash를 유일한 방어로 삼지 않습니다.
다음 수식은 길이 K=3인 abc에서 bcd로 옮기는 설명용 형태입니다. 문자를 왼쪽이 가장 높은 자리로 두면
h_next = ((h - a*p^(K-1)) * p + d) mod m
입니다. a의 기여를 제거하지 않고 이동하면 abc의 정보와 bcd의 정보가 같은 자리 체계에 놓이지 않습니다. p^(K-1)을 매번 다시 계산하지 않고 미리 보관하며, overflow가 발생할 수 있는 언어에서는 곱셈 전 wider integer나 안전한 모듈러 곱셈을 사용합니다. 이 계산은 설명용이며 특정 언어에서 실제로 실행한 결과가 아닙니다.
그림을 글로 읽기
- 정규화된 입력: 같은 인코딩·정책 · 문자열 → 값
- prefix hash: H와 power 전처리 · 구간 fingerprint
- hash 후보: 같은 값이면 후보 · 충돌 가능성 유지
- 원문 검증: 문자별 비교 · 정확 결과 확정
- 정규화된 입력 → prefix hash: 누적 계산
- prefix hash → hash 후보: O(1) 구간 hash
- hash 후보 → 원문 검증: 충돌 제거
단일 해시와 double hash
서로 다른 두 modulus 또는 base를 사용해 두 fingerprint가 모두 같을 때만 후보로 삼으면 우연한 충돌 가능성을 보통 크게 줄일 수 있습니다. 그러나 “두 해시가 독립이고 입력이 무작위다” 같은 가정을 포함한 확률적 필터일 뿐, 모든 서로 다른 문자열을 반드시 분리한다는 증명은 아닙니다. 같은 입력 모델에서 adversary가 modulus와 알고리즘을 알고 있거나, 두 해시 조건을 동시에 만족하는 입력을 만들 수 있다면 확률을 0이라고 기록할 수 없습니다.
따라서 판단은 결과의 정확성 비용으로 나눕니다. 일반적인 비적대적 데이터에서 후보를 빠르게 만들고 최종 검증 비용을 줄이는 목적이라면 double hash가 실용적인 필터가 될 수 있습니다. 파일 무결성, 인증, 접근 제어, 금액 정산처럼 false positive가 허용되지 않는 판정에서는 원문 비교, 암호학적 MAC·서명 등 목적에 맞는 구조를 선택해야 합니다. 암호학적 용도가 아닌 rolling hash를 보안 증거로 포장하지 않습니다.
누적 값과 실제 중간 상태
짧은 예를 두어 p=3, m=101, 문자값 a=1, b=2, c=3으로 계산해 보겠습니다. H[0]=0에서 H[1]=1, H[2]=1*3+2=5, H[3]=5*3+3=18입니다. abc의 prefix hash는 18입니다. 구간 [1,3)인 bc는 H[3] - H[1]*3^2 = 18 - 9 = 9이고, 이는 2*3+3=9와 같습니다. 같은 길이 구간은 같은 위치 체계로 정규화되어야 하므로, 단순히 H[r]-H[l]만 빼는 것은 뒤 문자의 자릿값을 다시 맞추지 않아 잘못된 결과를 냅니다.
text=abca, K=3에서 abc의 hash는 18입니다. 한 칸 이동할 때 오래된 a의 기여 1*9를 빼면 9, 남은 값을 base 3으로 이동하면 27, 새 문자 a=1을 더하면 28입니다. 직접식 bca=2*9+3*3+1=28과 일치합니다. 따라서 갱신 경로는 18 -> 9 -> 27 -> 28로 추적해야 합니다. 구현 전에 어느 문자가 p^0에 놓이는지 결정하지 않으면 이 식과 반대 방향의 prefix 식을 섞어 같은 문자열도 다른 hash로 만들 수 있습니다.
Unicode와 비교 키의 정규화
정규화는 해시 충돌을 해결하는 기능이 아니라 hash 입력의 동일성 정책을 고정하는 단계입니다. NFC를 쓰기로 했다면 원문을 NFC로 바꾼 뒤 UTF-8 byte sequence를 값으로 매핑합니다. NFD나 locale별 대소문자 접기는 다른 결과를 만들 수 있으므로 요청마다 임의로 고르면 캐시 키가 안정되지 않습니다. 원문 보존이 필요한 시스템은 표시용 원문과 비교용 canonical key를 분리하고, offset을 반환할 때 canonical byte offset을 원문 문자열 offset으로 바로 오인하지 않도록 매핑을 보관해야 합니다.
같은 화면 문자열을 동일하게 볼 필요가 없다면 정규화를 하지 않고 byte identity를 그대로 hash하는 것이 오히려 정확합니다. 중요한 점은 “보이는 모양이 같다”와 “비교 계약상 같다”를 구분하는 것입니다. 해시 테이블의 불변 키와 마찬가지로 hash 계산에 사용한 필드를 삽입 뒤 바꾸면 기존 위치에서 항목을 찾지 못할 수 있으므로 canonical key는 생성 후 불변으로 두는 편이 안전합니다.
구현 선택과 실패 경계
prefix hash는 정적 텍스트의 많은 구간 비교에 적합하고, rolling window는 길이 K가 고정된 스트리밍 탐색에 적합합니다. 긴 패턴 전체를 후보마다 다시 비교하면 worst-case가 커지므로, exact 결과가 필요하면 suffix array나 KMP처럼 결정적 구조를 검토합니다. double hash는 비교 비용과 충돌 위험 사이의 절충이지 검증 제거가 아닙니다.
검증 항목은 다음과 같이 구성합니다. 같은 문자열의 두 위치가 동일 hash인지 확인하고, 서로 다른 짧은 문자열을 열거해 hash 충돌이 있어도 원문 검증이 false positive를 제거하는지 확인합니다. 빈 패턴·패턴이 텍스트보다 긴 경우, K=1, K=텍스트 길이, Unicode canonical equivalent 입력을 별도로 둡니다. arithmetic overflow, 음수 나머지, power 인덱스 범위도 실패 입력입니다. 본문 계산은 설명용 산술이며 이 환경에서 코드 실행을 수행했다고 주장하지 않습니다.
참고자료와 근거의 한계
확인한 cp-algorithms의 String Hashing 문서는 prefix hash로 부분 문자열 hash를 일정 시간에 계산하는 방식, 같은 hash가 같은 문자열을 증명하지 않는다는 점, double hash가 위험을 낮추되 제거하지는 않는다는 점을 다룹니다. 해당 페이지는 입력 모델별 정확한 충돌 확률이나 특정 언어의 정수 overflow 계약을 정하지 않으므로, 이 노트는 확률을 수치로 단정하지 않고 정책·공격 모델을 명시해야 한다고 제한했습니다. 해시 테이블 노트와 달리 이 글의 최종 단위는 bucket이 아니라 문자열 구간의 후보 동일성입니다.
참고 URL
- https://cp-algorithms.com/string/string-hashing.html — prefix hash, 부분 문자열 계산, 동일 hash가 동일 문자열의 증명이 아니라는 범위를 확인했습니다(알고리즘 참고 문서, 특정 언어 계약 아님).
- https://unicode.org/reports/tr15/ — 정규화 주장을 사용할 때의 표준 출발점입니다. 이 노트는 해당 문서의 세부 구현 규칙을 재현하지 않고, 입력 표현 정책을 고정해야 한다는 범위로 제한합니다.