[MIT 6.006 정리] Lec 09. 해싱 (테이블 더블링, 분할 상환, 롤링 해시, Karp-Rabin)

* 본 포스팅은 기본적으로 edwith 플랫폼을 통해 제공되고 있는 MIT 6.006 Introduction to Algorithms (Fall 2011) 강의 내용을 바탕으로 정리한 것입니당 :D

 

------- * ------- * ------- * -------

 

* 해싱 with 체이닝 Recap

• 모든 키에 대한 거대한 집합이 존재할 때 (maybe infinite size...), 실제로 데이터 구조에 저장되는 것은 유한한(finite) n 개의 키일 뿐!
  • 해시 함수 h 를 이용해 n 개의 키를 m 크기의 해시 테이블에 저장 (맵핑!)
  • 서로 다른 키들이 해시 테이블의 동일한 슬롯으로 맵핑될 경우 (충돌), 연결 리스트로 저장함
  • 해당 구조의 총 크기는 n (연결 리스트로 된 총 항목 수) + m (해시 테이블의 크기)
• 체이닝을 이용한 해싱으로 O(1 + alpha) 에 삽입 / 삭제 / 탐색(exact search) 연산을 기대할 수 있음
  
  • 특정 키가 각 슬롯에 들어갈 확률은 1/m  -->  체인(연결 리스트) 길이의 기댓값은 n/m (= alpha) 
  • alpha 가 상수일 때, 상수 연산 시간 O(1) 을 가지게 되는 것

 

* Then, what should 'm' be?  (해시 테이블의 크기 m 을 어떻게 정할 것인가?)

• m 과 n 의 크기가 비슷하면 좋다는 건 알지만( m = O(n) ), m 크기의 해시 테이블을 일단 만든 후 키를 넣게 되는 상황
  • n 의 크기를 모르는 상태에서 데이터 삽입이 이루어지므로, 해시 테이블의 크기를 늘려야 할 수도 있음...!
  • n 이 m 에 비해 엄청 커진다면, alpha 가 커지므로, O(1 + alpha) 가 상수 시간이 아니게 될 수 있음
  • 반대로 n 에 비해 m 을 엄청 크게 설정해둔다면, 메모리 낭비가 커짐 (메모리를 아끼려고 쓰는건데...!)
• m 이 충분히 커서 빠르게 기능하면서도, 충분히 작아서 공간이 낭비되지 않는 적절한 크기로 정해야 함 ^^
• 우선 m 을 임의의 정수로 초기화 한 뒤, 해시 테이블의 크기를 n 에 맞게 늘리거나 / 줄이는 것이 핵심!

 

* 테이블 더블링 (Table doubling)  --  삽입(insert) 연산 기준

• n > m 인 경우, 테이블 크기를 늘려야 함 (m -> m')
  • 크기 m' (m' > m) 의 새로운 테이블 T' 을 만들고, 새로운 해시 함수 h' 를 정의하고, 기존의 테이블 T 에 있던 아이템들을 rehash!
  • 일반적으로 O(n + m + m') 시간 소요되나, 보통 O(n) 라고 말할 수 있음 
    -- m 개의 슬롯을 찾아가는데 O(m) + 각 리스트를 찾아가는데 O(n) + 새로운 해시 테이블을 만드는데 O(m')
• (반례) m' = m+1 로 설정할 경우, m' = n 이 될 때까지 매번 새로운 해시 테이블을 만드는 작업을 수행해야 함
  • (m = 0 으로 시작해서) n 개 아이템을 삽입하는 데에 총 비용은 O(1 + 2 + 3 + 4 + ... + n) = O(n^2) 
• m' = 2m 로 설정할 경우, 새롭게 해시 테이블을 만드는 연산 시간은 많이 들지만, 횟수가 log(n) 수준으로 크게 감소!
  • n 개 아이템을 삽입하는 데에 총 비용은 O(1 + 2 + 4 + 8 + ... + n) = O(n)
  • 이를 '분할 상환(Amortization)' 이라고 함 -- 테이블 더블링의 분할 상환 실행시간은 O(1)

 

+ 분할 상환 (Amortization)

• 전체 k 개의 연산(operations) 을 수행하는 데에 <= k * T(n) 시간이 걸릴 때, 해당 연산이 ' T(n) 분할 상환 실행 시간(amortized running time) ' 이 소요된다고 함(= T(n) 실행시간동안 분할상환 된다!)
  • T(n) = 실행 시간(running time) / 예상 실행 시간 (expected running time)
  • 각 실행마다 걸리는 시간에 대한 것이 아니라, 전체 k 번의 실행에 걸리는 총 시간이 최대 k * T(n) 인 것!
• 모든 연산에 대한 평균값에 해당하므로, 평균 실행시간이 T(n) 이라고 생각할 수도 있음 (= "T(n) on average")

 

+ 삭제 (delete) 연산 for 테이블 더블링

• 삭제 연산에 대해서도 총 O(n) 시간이 소요됨을 증명 가능  --  삭제의 경우, 테이블에서 삭제 후 테이블 크기를 (당분간) 유지함
  • 삭제 후 테이블 크기를 줄였다가 다시 늘리게 되면 그전보다 더 많은 삽입이 필요함 ㅜ
• 방법 1) m = n/2 가 되면 테이블 크기를 m/2 로 줄인다 (shrink)
  • 2^k  <->  2^k+1  로 삽입 / 삭제 연산 상황이 반복될 경우 각 연산 당 선형 시간이 걸리므로 매우 느-림
• 방법 2) m = n/4 가 되면 테이블 크기를 m/2 로 줄인다
  • 테이블이 3/4 가 비었을 때에야 크기를 줄임으로써 다시 늘려야 할 때까지 (n 이 m 보다 다시 커지게 될 때까지) 어느 정도 버퍼가 존재하는 셈!
  • 분할 상환 실행시간이 O(1) 걸리게 됨을 증명 가능
  • k 삽입과 삭제를 무작위로 했을 때, n <= m <= 4n 이 되기 때문에, 해시 테이블은 항상 선형 크기를 갖게 됨
  • 꼭 4 (삭제 상수) 가 아니라도 2 (삽입 상수) 보다 큰 수이면 가능...!
• 파이썬 리스트는 테이블 더블링을 활용해서 삽입(append) & 삭제(pop) 연산을 상수 (분할 상환) 시간에 수행 가능함!

 

* 문자열 찾기 (String matching)

• 두 개의 문자열 s, t 가 주어졌을 때, s 가 t 에 존재하는지 확인하는 문제  (일반적으로 len(s) << len(t))
• 가장 단순한 알고리즘은, 문자열 t 를 s 크기 만큼 슬라이딩 윈도우(sliding window) 를 하며 각 문자열을 비교하는 것!
  • O( |s| * (|t|-|s|) ) ~ O(|s| * |t|) 의 비용이 소요됨 ㅜ
• 롤링 해시를 이용한 Karp-Rabin 알고리즘을 통해 O(|s| + |t|) 의 비용으로 연산 가능함!
  • 두 문자열을 직접 비교하는 대신 문자열의 해시 값을 비교하는 것이 핵심
  • 큰 문자열을 해싱을 이용해 적당한 크기로 줄이고, 두 해시값을 비교했을 때 충돌이 있다면 확인해주기

 

+ 롤링 해시 (Rolling hash ADT)

• 슬라이딩 윈도우 방식으로 문자열 t 을 앞에서부터 s 크기 만큼 비교해 나갈 때, i 번째 부분 문자열(substring) 은 (i-1) 번째 문자열과 (s-1) 만큼 일치함!
  • i-1 번째 문자열의 맨 앞자리 문자를 제외(skip) 하고 문자열 t 의 다음 문자를 더한(append) 것!
  • 이미 (s-1) 개 문자에 대한 해시값을 계산한 상황이므로 이를 이용하자!
• 이미 해시 값을 아는 상황에서, 롤링해시 r 는 기본적으로 문자열 x 을 보존(maintain) 함
  • r(x): 현재 문자열 x 의 해시 값을 줌
  • r.append(c): 문자 c 를 문자열 x 의 끝에 삽입 (추가)
  • r.skip(c): 문자열 x 의 첫번째 문자 (c) 를 삭제 
• 롤링 해시 r 는 나누기 방법을 이용한 해시 함수를 사용함! 

 

+ Karp-Rabin 문자열 찾기 알고리즘

• rs : 문자열 s 의 해시 값을 주는 롤링 해시  /  rt : 문자열 t 의 첫 부분 (t[:len(s)]) 의 해시 값을 주는 롤링 해시
  • for c in s: rs.append(c)
  • for c in t[:len(s)]: rt.append(c)
• rs() == rt() 인지 비교 후, 같지 않으면, for 반복문을 통해 다른 부분에 대해서도 같은지 확인을 이어나감
  • 첫 문자를 버리고, 다음 문자를 더해준 뒤 이를 다음 확인 대상으로 삼음
  • for i in range(len(s), len(t)):
        rt.skip(t[i-len(s)])
        rt.append(t[i])
• rs() == rt() 인지 비교 후, 같으면, 해시 값만 같은게 아니라 실제 문자열도 같은지 (충돌이 있는 것은 아닌지) 추가로 확인 필요!
  
  • 해시 값이 같은 두 문자열 (s & t 의 부분 문자열) 의 각 문자를 비교 후, 같다면 found match!
  • check whether s == t[i-len(s)+1 : i+1]
  • 같지 않다면, 두 개가 다를 확률을 1/s 로 만들어야 함  -->  아니면 상수 시간에 처리되지 않음! (?? 확인 필요)
• 총 소요 시간 O(|s| + |t| + (# of match) * |s|) -- 같은 게 확인될 때마다 (충돌을 확인해야 하므로) s 만큼 더 걸림