수만 글자로 이루어진 거대한 웹 문서 속에서 사용자가 입력한 특정 단어를 찾아내는 '문자열 검색(String Matching)' 알고리즘. 우리는 이전 글에서 접두사와 접미사의 반복을 이용해 불일치 시 빠르게 건너뛰는 천재적인 KMP 알고리즘을 살펴보았습니다. 하지만 KMP는 코드가 매우 복잡하고 LPS 테이블이라는 전처리 과정을 거쳐야 하는 까다로움이 있습니다. 만약 "문자열의 텍스트 자체를 한 글자씩 비교하지 않고, 각 문자열을 암호화된 '숫자(Hash)'로 바꿔서 한 번에 퉁치고 비교한다면 어떨까?"라는 신선한 발상에서 탄생한 알고리즘이 있습니다. 바로 암호학과 해시(Hash) 함수의 마법을 문자열 탐색에 우아하게 접목시킨 '라빈-카프(Rabin-Karp)' 알고리즘입니다. 여러 개의 패턴을 동시에 찾을 때 진면목을 발휘하는 이 해싱 기반 알고리즘의 롤링 해시(Rolling Hash) 원리를 낱낱이 파헤쳐 보겠습니다.
1. 라빈-카프 알고리즘의 핵심 원리: 문자열의 수치화
기본적인 브루트 포스(Brute Force) 탐색은 본문과 패턴의 글자를 하나하나 대조합니다. 이와 달리 라빈-카프 알고리즘은 찾고자 하는 '패턴 문자열' 전체를 특정한 해시 함수를 통해 고유한 정수(Hash Value)로 변환합니다. 그리고 본문 텍스트에서도 패턴과 똑같은 길이만큼 창문(Window)을 설정하고, 그 창문 안에 있는 텍스트의 해시값을 계산합니다.
만약 본문의 부분 문자열에서 계산된 해시 숫자와 패턴의 해시 숫자가 다르다면, 두 문자열은 100% 다른 문자열이므로 글자를 비교할 필요도 없이 과감하게 옆으로 넘어갑니다. 해시 숫자 단 한 번의 비교만으로 긴 문자열의 일치 여부를 O(1) 수준으로 판별해 내는 것이 핵심입니다.
2. 알고리즘의 심장: 롤링 해시 (Rolling Hash) 테크닉
라빈-카프 알고리즘이 진정으로 위대한 이유는 창문을 한 칸 옆으로 밀었을 때(Sliding), 새로운 부분 문자열의 해시값을 처음부터 다 다시 계산하지 않는다는 점에 있습니다. 이를 가능케 하는 기술이 바로 롤링 해시(Rolling Hash)입니다.
2-1. 수학적 재활용의 마법
예를 들어 본문 "ABCD"에서 길이 3짜리 창문을 밀어본다고 합시다. 첫 번째 창문 "ABC"의 해시값을 계산해 두었습니다. 창문을 오른쪽으로 한 칸 밀어 두 번째 창문 "BCD"의 해시값을 구할 때, 'B'와 'C'의 정보는 이미 이전 연산에 포함되어 있습니다. 롤링 해시 기법은 기존 해시값에서 창문을 빠져나가는 맨 앞글자 'A'의 가중치를 빼버리고, 창문에 새롭게 들어오는 맨 뒷글자 'D'의 가중치를 새롭게 더해주는 단순한 사칙연산만 수행합니다.
// 롤링 해시 점화식의 개념적 표현
새로운 해시 = (기존 해시 - 빠져나가는 글자의 값) * 진수 + 새로 들어오는 글자의 값
이러한 수학적 트릭 덕분에 창문을 아무리 여러 번 밀더라도, 다음 부분 문자열의 해시값을 구하는 시간은 길이에 상관없이 무조건 상수 시간 O(1)로 압축됩니다. 결과적으로 본문 전체(길이 N)를 한 번 훑는 시간 복잡도를 O(N)으로 만들어 줍니다.
3. 해시 충돌(Hash Collision)의 방어
문자열을 고정된 숫자로 변환하는 모든 해시 함수에는 숙명적인 결함이 존재합니다. 바로 완전히 다른 문자열임에도 불구하고 우연히 계산 결과가 똑같은 숫자로 나와버리는 '해시 충돌(Hash Collision)' 현상입니다. (예: "APPLE"과 "MELON"의 해시값이 우연히 똑같이 1234로 계산될 확률)
3-1. 충돌 확인을 위한 이중 검사
라빈-카프 알고리즘은 이를 방어하기 위해 다음과 같은 검증 로직을 거칩니다.
- 패턴의 해시값과 본문의 창문 해시값이 다르다면: 무조건 다른 문자열이므로 가차 없이 넘어갑니다.
- 두 해시값이 같다면: "어? 진짜 찾은 걸 수도 있지만, 우연히 충돌이 난 걸 수도 있잖아?" 라고 의심합니다. 이때만 예외적으로 두 문자열의 글자를 앞에서부터 1:1로 직접 대조(String.equals)하여 진짜 일치하는지 최종 확인을 거칩니다.
해시 함수를 대충 짜서 충돌이 너무 잦아지면 매번 1:1 대조를 해야 하므로 최악의 경우 속도가 O(N $\times$ M)으로 떨어집니다. 따라서 매우 큰 소수(Prime Number)를 활용하여 모듈로 연산(%)을 수행해 해시 충돌 확률을 로또 당첨 수준으로 극단적으로 낮추는 것이 구현의 핵심입니다.
1. 라빈-카프(Rabin-Karp) 알고리즘은 긴 문자열 속에서 패턴을 찾을 때, 글자를 직접 비교하는 대신 패턴과 본문의 해시(Hash) 숫자값을 비교하여 탐색 속도를 극대화합니다.
2. 창문을 한 칸씩 슬라이딩할 때 기존 해시값에서 앞글자를 빼고 새 글자를 더하는 롤링 해시(Rolling Hash) 기법을 통해, 해시 갱신 연산을 O(1)로 처리하는 것이 성능의 핵심입니다.
3. 완전히 다른 문자열의 해시값이 겹치는 해시 충돌이 발생할 수 있으므로, 해시값이 일치할 때만 예외적으로 실제 문자열을 1:1로 직접 검증하는 방어 로직이 필수적입니다.