MIT - Introduction to Algorithms - Lecture 9. Table doubling, Karp-Rabin 해싱 테이블 더블링, Karp-Rabin 문자열 찾기 Review

MIT - Introduction to Algorithms 

- Lecture 9. Table doubling, Karp-Rabin 

해싱 테이블 더블링, Karp-Rabin 문자열 찾기 Review

Copyright to MIT & Srini Devadas & Erik Demaine

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/

code, data, note pdf  : https://courses.csail.mit.edu/6.006/fall11/notes.shtml
한글 번역과 슬라이드를 보고싶은 분은 Edwith - 파이썬을 이용한 알고리즘의 이해 항목 강의를 참조하세요.

URL : https://www.edwith.org/introalgorithm/

지난 시간 해싱을 왜 써야하는지 체이닝을 이용한 해싱에서 상수시간을 기대할 수 있는 효과를 알게되었습니다.
우리는 Chaining 기술을 통해 n개의 유한한 키 값들을 m 크기의 slot table에 넣어 표기할 수 있었습니다 - linked list
Chaining에서 순서는 중요하지 않았음
구조의 총 크기는 n+m
m : size of hash table, n: sum of all of the linked list
균일하다고 가정할 때 예상하는 체인 길이 expected chain length $= {n \over m} = \alpha$=적재율
expected op time $= \theta(1+\alpha)$
$\alpha$가 constant라면 우리는 상수 시간 복잡도를 가진다.

해싱에 대해 다 배운 것 같지만 우리는 한 가지 중요한 부분이 빠졌다.
그것은 m의 적정값을 어떻게 구할 것인가이다.
m과 n이 비슷하면 좋지만 실제로 우리는 n의 크기를 모른다.
늘려야할 수도 있기 때문
만약 n이 많이 크다면 n/m = alpha 역시 커지게 된다.
이것은 시간복잡도가 O(1+alpha)로 상수시간이 이니게 된다.
만약 m을 크게 잡는다면 낭비가 크다.
메모리 공간을 아끼고 싶어했던 원래 취지에서 벗어남

우리가 원하는 정도 $m=\theta(n), \alpha = \theta(1)$
ex) start small m=8, grow/shrink as neccessary
m이 항상 최소한 n이 되도록 만들어보자
m=8, empty -> n=9
If n>m: grow table
m`=m+1: cost of n inserts
$\theta(1+2+3+4+ \cdots +n) = \theta(n^2)$
새로운 데이터를 삽입할 때마다 항상 새롭게 테이블을 만들어줘야함

m`=2m: cost of n inserts
데이터가 초과될 때 m을 2배씩 늘려야하지만 log(n)번 동안만 늘리면 된다.
O(n log(n)) (이진 탐색 트리의 복잡도)을 생각할 수도 있지만 더 좋은 걸 희망함
$=\theta(1+2+4+8+ \cdots +n)$
$=\theta(n)$
= Table Doubling

grow table의 의미: m->m`
메모리를 할당하고 새롭게 해싱
build new hash h`
rehash: for item in T: T`.insert(item);
이것의 시간은? O(n)
general theta(n+m+m`)

=>Amortization
- operation takes T(n) amortized  if k operations take <= k*T(n) time
- think of meaning T(n) on average where average over all operations
cf) amortize (빚을) 분할 상환하다
비유 : 하루 50달러의 월세는 싸다고 느끼지만 초당 나눠서 낸다면 더 싸게 느낌
분할상환 실행 시간은 theta(1)
k번 삽입 : theta(k) time -> Constant time
삭제에 대해서도 O(k), 삭제 후에도 해시 테이블 크기는 그대로 놔둔다
가장 비용이 많이드는 것은 데이터를 초과 삽입을 통해 새로운 해시 테이블을 만들 때

Deletion:
1. if m= n/2 then shrink : slow theta(n) per op
n=8,9,8,9일 때 9로 변할 때는 2배로 늘려줘야하고 8이 될 때는 2배로 줄어주는 선형 시간적인 시간이 걸리는 문제점이 있다. -> 느려짐
2. if m= n/4 then shrink m/2
amortized time -> theta(1)

list append, pop은 상수 시간이 걸림, 배열을 활용 : 테이블 더블링을 활용
연산이 최악이되는 상수시간이 걸릴 때는?
테이블이 거의 채워갈 때쯤 두 배 크기의 테이블을 만들고 그 후 원래 테이블에서 데이터를 삽입할 때마다 새로운 테이블로 넘길 때...?
구현이 까다로움 굳이 구현하려고 하지도 않음

string matching: 워드 파일에서 큰 문자열을 찾는 것
given two strings s&t does s occur as a substring of t? 두 개의 문자열 s& t

s='6.006', t=INBOX
s=구글 검색어, t=구글 웹
cf) substring 어떤 문자열에서 앞부분이나 뒷부분을 제거함으로써 얻어지는, 문자열의 일부분.

simple algorithm으로는 O(|s|*|t|)만큼 걸리기에 시간이 오래걸림

예전 검색 엔진이 사용하던 방법 : 단어 수가 문자 수보다 적은 걸 이용해 문자열을 단어로 나눠서 검색하는 방법 => 지금은 그럴 필요가 없다고 밝혀짐

우리가 원하는 복잡도 정도는 O(|s|+|t|)
문자열을 비교하는 대신 문자열의 해시 값을 비교
비교할 때 시간이 많이 들지라도 해싱을 이용해 적당한 크기로 줄일 수 있다면 두 개의 단어가 같은지 비교, 충돌이 있는지 확인으로 빨라질 수 있음
연산당 상수 시간

Rolling hash ADT
-r maintains a string x / r(): hash value of x = h(x)
-r.append(c): add character c to end of x
-r.skip(c):delete first char of x(assuming it is c)

Karp-Rabin algorithm:

O(|s|+|t|+ #of match * |s|)
r.append(c) : u -> u*a + ord(c)
r->r*a+ord(c) mod m
r.skip(c): u -> u-c*a
skip은 삭제