Rolling Hash

Gonsoso 2015. 1. 22. 17:34

rsync라는 유틸리티를 알게되서 알아본 알고리즘.

예시를 이용한 정리.

다음 주어진 문자열 String 2를 String 1에서 검색 또는 비교하는 상황이라 하자.

String 1: "abcdeabcdefaaa", String 2: "bcd"

Naive한 방식은 문자열을 3개의 문자열 단위로 문자 하나씩 비교하는 방식이다.

Rolling Hash 알고리즘을 사용해서 이 상황을 풀어보자.

과정 1-1.

먼저 String 2의 문자열 "bcd"의 Hash 값을 구해놓는다.

Pattern = b*7^0 + c*7^1 d*7^2 = 98*1 + 99*7 + 100*49 = 5691

String 1의 substring의 Hash value를 구하고 Pattern의 Hash value와 비교하는 방식이 되겠다.

Substring 1: "abc"

Hash value = a*7^0 + b*7^1 + c*7^2 = 97*1 + 98*7 + 99*49 = 5634

이러면 Hash value를 계산하고 비교하면 되기 때문에 문자열들을 비교시 문자 하나씩 비교할 필요가 없어진다.

과정 1-2.

다음 substring 2는 "bcd"와 pattern "bcd"를 비교한다.

이때 Substring 2: "bcd"를 위해 Hash value를 구해야 하는데

Substring 2는 abc 에서 a가 빠지고 bc에 d가 합쳐진 문자열이다.

즉, Substring 1: a*7^0 + b*7^1 + c*7^2 의 기존 식에서 제거되는 a와 추가되는 d 값을 처리하면 해결된다.(이걸 수학으로 표현하면 빼고 나누고 더하고 이리 처리 하면 되보이는데 ... )

이것을 풀어보면

Base: a*7^0 + b*7^1 + c*7^2

Drop a: a*7^0 + b*7^1 + c*7^2 - a*7^0

Divide by 7: b*7^0 + c*7^1

Add d: b*7^0 + c*7^1 + d*7^2

Substring 2 = [ { ( a*7^0 + b*7^1 + c*7^2 ) - a*7^0 } / 7 ] + d*7^2 = b*7^0 + c*7^1 + d*7^2 가 된다.

실제 사례에서, 긴 Pattern이 적용될때 지수가 커져서 Overflow가 발생된느 상황을 막기위해서 큰 소수로 modulo 연산을 해준다.