[Algorithm] Rabin-Karp Algorithm (라빈-카프 알고르짐)

Rabin-Karp Algorithm은 hasing을 사용해 텍스트의 패턴 문자열 집합 중 중 하나를 찾는 문자열 검색 알고리즘이다. 1987년 마이클 라빈(Michael Rabin)과 Richard Karp(리차드 카프)가 개발했다. 이 알고리즘의 핵심 아이디어는 검색하려는 패턴의 해시값을 계산한 다음 이 해시를 패턴과 길이가 같은 텍스트의 하위 문자열의 해시값과 비교하는 것이다. 이 방법을 사용하면 패턴과 일치할 가능성이 없는 텍스트의 많은 부분을 빠르게 건너뛸 수 있기 때문에 특히 패턴이 텍스트보다 훨씬 작은 경우 검색의 속도를 크게 높일 수 있다. 알고리즘의 개요는 아래와 같다.

 

1. 해시 함수
   : 각 문자열을 숫자 값으로 변환하는 해시 함수를 선택한다.
2. 초기 해시 값
   : 길이가 m인 패턴 P의 해시값과 텍스트 T의 처음부터 m까지 문자의 초기 해시값을 계산한다.
3. 검색
   : 텍스트 T의 처음부터 시작해 길이 m의 하위 문자열의 해시값가 패턴 P의 해시값을 비교한다. 해시값이 일치하면 해시 충돌로 이한 오탐을 방지하기 위해 실제 하위 문자열과 패턴이 정확히 일치하는지 확인한다.
4. 롤링 해시
   : 텍스트 T의 각 후속 문자에 대해 이전 해시값을 업데이트해 길이 m의 새 부분 문자열의 해시값을 계산한다(해시값을 처음부터 다시 계산하지 않기 위해). 이 작업은 상수 시간 내에 수행되므로 알고리즘을 효율적으로 만든다.
5. 일치 항목 발견
   : 해시값이 일치하고 실제 비교를 통해 일치하는 것이 확인되면 일치하는 위치를 보고한다.
6. 텍스트 T의 마지막에 도달할 때까지 실행한다.

예를 통해 살펴보자.

 

Text T = "abdabc"에서 Pattern P = "abc"를 검색해보자.

1. hash("abc") = 1 + 2 + 3 = 6 (a = 1, b = 2, c = 3)이라고 간단한 함수를 가정한다.
2. P의 해시를 계산하면: hash("abc") = 6
3. T의 첫 번째 m = 3 (길이가 3) 문자의 초기 해시를 계산하면: hash("abd") = 1 + 2 + 4 = 7
4. "abd"의 해시가 "abc"의 해시와 일치하지 않으므로 T의 다음 부분 문자열인 "bda"로 이동한다.
5. "bda"의 해시를 업데이트하교 비교한다 - 첫 문자인 a의 값을 기존 해시값에서 빼주고, 새로 추가된 문자인 a의 값을 더해주면 : hash("bda") = 7
6. 이 과정을 계속 진행한다.
7. 텍스트 T에서 하위 문자열 "abc"에 도달하면 해시값이 6으로, 패턴 P의 해시값과 일치한다.
8. 실제 일치 여부를 확인해 해시 충돌(hash collision)이 아닌지 확인한다. 정확히 일치하므로 일치여부를 보고한다.

실제 Rabin-Karp Algorithm은 보다 정교한 해시 함수를 사용하고 대용량 텍스트와 패턴을 처리함으로써 속도와 정확성을 모두 보장한다.

 

참고

- https://blog.naver.com/ndb796/221240679247