[Algorithm] 문자열 검색 - 라빈-카프 알고리즘

* Python을 기준으로 합니다

---

문자열 검색 - 라빈-카프 알고리즘 (Rabin-Karp Algorithm)

- 개념

• 문자열 검색 (String Matching) : 주어진 문자열 내에서 특정한 패턴을 가진 문자열을 탐색하는 것
  • e.g.) `This is Rabin Karp Algorithm`라는 문자열이 주어졌을 때, 패턴 `Karp`는 14번째 index에 있음
  • 이때 naive 한 문자열 검색 방법으로써 전체 문자열을 순회하면서 주어진 패턴과 일치하는지 여부를 판단하는 방식을 고려할 수 있음
    - BUT, 해당 방식은 $N$ 길이의 문자열과 $M$ 길이의 패턴에 대해 $O(NM)$의 time complexity가 소모되므로 길이가 긴 문자열에 적용하기 어려움
• 라빈-카프 알고리즘
  • 해시를 사용하여 일치하는 패턴을 탐색하는 알고리즘으로써, $O(N+M)$의 time complexity를 가짐
  • 특히 라빈-카프 알고리즘은 해시 값이 다르면 패턴과 sub-string이 다르다는 점을 활용함
    - BUT, 해시는 반드시 충돌이 발생하므로(비둘기집 원리, 생일문제) 동일한 해시 값을 가지더라도 패턴과 sub-string이 다를 수 있음
    - 따라서 해시 값이 같을 경우, 추가적으로 문자열이 동일한지 비교하는 과정이 필요
  • 해시 값의 계산
    1. 해시를 처음부터 다시 계산하지 않고, 전체 문자열에 대해 slide 하는 방식으로 sub-string의 해시를 업데이트하는 Rolling Hash Function을 사용
    2. 먼저 해시를 계산하기 위해, base $b$와 적당한 소수 $p$를 modulus로 선택하자
       - 일반적으로 $b$는 ASCII code 값을 사용하고, $p$는 2를 사용
    3. 그러면, 문자열의 $i$에서 $i+1$ index로 slide 할 때 해시 값은:
       (Eq. 1) $H = (H-(T[i-m]*b^{m-1})%p)*b+T[i]$
       - $h$ : hash 값, $T$ : 주어진 문자열, $m$ : 패턴 길이 
  • 라빈-카프 알고리즘의 동작
    1. 길이가 $m$인 패턴의 해시 값과 첫 번째 sub-string의 해시 값을 계산함 
    2. 문자열의 처음부터 끝까지 다음을 반복
       - 현재 sub-string의 해시 값과 패턴의 해시 값이 같으면, 해당 sub-string이 주어진 패턴과 일치하는지 확인
       - 만약 일치하면 시작 index를 배열에 저장
       - Rolling hash를 통해 다음 sub-string의 해시 값을 계산
    3. 최종적으로 일치하는 sub-string의 시작 index가 담긴 배열을 반환

Rolling Hash의 동작

- 구현

1. 문자열 검색을 위한 naive approach

• 단순하게 문자열을 순회하면서 일치하는 패턴을 찾는 방식으로 동작함

def naive_search(pattern, text):
  m = len(pattern)
  n = len(text)
  result = []

  #전체 문자열에 대해 반복
  for i in range(n-m+1):
    j = 0
    #현재 index i에서 시작하는 sub-string이 패턴과 일치하는지 확인
    while j<m and text[i+j] == pattern[j]:
      j+=1
    
    #sub-string이 패턴과 전부 일치하면 
    if j == m:
      result.append(i) #시작 index를 추가

  return result


#-------
text = 'This is Rabin Karp Algorithm'
pattern = 'Karp'
print(naive_search(pattern, text)) #[14]

text = 'This is Rabin Karp Algorithm'
pattern = 'is'
print(naive_search(pattern, text)) #[2, 5]

2. 라빈-카프 알고리즘

• Rolling hash function을 활용하여 문자열 일치 여부를 판단함

def rabin_karp(pattern, text):
    M = len(pattern)
    N = len(text)
    result = []

    # 해시 계산용
    mod = 2 #modulus (소수)
    base = 128 #base (ASCII code size)
    h = 1 #prime power
    
    #문자열, 패턴 해시 값은 0으로 초기화
    pattern_hash = 0 
    text_hash = 0 

    #prime power = (base^(M-1)) % mod 계산
    for i in range(M-1):
        h = (h*base) % mod

    #먼저 M 길이의 패턴 해시 값과 첫번째 sub-string의 해시 값을 계산함
    for i in range(M):
        pattern_hash = (base*pattern_hash + ord(pattern[i])) % mod
        text_hash = (base*text_hash + ord(text[i])) % mod

    #이후 전체 문자열에 대해 반복
    for i in range(N-M+1):
        #해시 값이 같으면, 패턴과 sub-string이 일치할 수 있음
        if pattern_hash == text_hash:
            j = 0
            #현재 index i에서 시작하는 sub-string이 주어진 패턴과 일치하는지 확인
            while j < M and text[i+j] == pattern[j]:
                j += 1
            #일치하면
            if j == M:
                result.append(i) #배열에 시작 index 저장

        #다음 sub-string으로 slide하여 해시 값 계산 (rolling hash)
        if i < N-M:
            text_hash = (base*(text_hash-ord(text[i])*h) + ord(text[i+M])) % mod
            #해시 값이 음수인 경우
            if text_hash < 0:
                text_hash += mod
    
    return result
 
#-----------
text = 'This is Rabin Karp Algorithm'
pattern = 'Karp'
print(rabin_karp(pattern, text)) #[14]

text = 'This is Rabin Karp Algorithm'
pattern = 'is'
print(rabin_karp(pattern, text)) #[2,5]