소개 (Introduction)

허프만 코드는 데이터를 압축하는 알고리즘이다.
greedy 알고리즘을 사용하고 특정한 prefix-free binary code 를 이용한다.​

binary code

문자(symbol) -> binary string (이진 코드)로 mapping한 것.
binary string으로 시퀀스가 0 or 1이다.
쉽게 말해서 알파벳이 32가지 있다면, 그 string을 encode해서 binary string으로 mapping한다.
32가지 이기때문에 5-bit가 필요하고, 각각 fixed-length code가 만들어진다.
a = 00000, b = 00001 … 이렇게 mapping된다.

개선 방법

5-bit로 fixed-length code를 사용하는 것 보다 더 좋은 방법이 없을까?

variable-length code를 사용하는 것이다.
자주 나오는 문자는 작은 code로 mapping하는 것이다.

애매한 문제

fixed-length encoding인 {a, b, c, d} = {00, 01, 10, 11} 있는데,
variable-length code로 {0, 01, 10, 1}로 한다고 가정하면,
“001” 이라는 code가 들어왔을 경우, 어떻게 decode를 해야 될까?

AB(0 01)도 되고, AAD(0 0 1)로도 가능하게 된다.
문자의 끝과 다음 시작문자가 명확하지 않다.
그래서 prefix-free code가 필요하다.

prefix-free code

문자 i, j에 대해서 서로 다른 prefix를 가지도록 f(i), f(j)로 encode하는 것이다.

예를들어, {0, 10, 110, 111}

​왜 유용한가?
0은 1bit로 줄어드는 건 알겠는 데, 뒤에 110, 111은 3-bit라 압축이 아니라 커질거 같다고 생각할수 있다.
그러나 답은 문자들이 모두 non-uniform으로 구성되어 있어, 모든 문자의 확률이 다르다는 것이다.

  • A : 60%
  • B : 25%
  • C : 10%
  • D : 5%

일때,

문자 등장 확률fixed-lengthvariable-length (prefix-free)
A : 60%000
B : 25%0110
C : 10%10110
D : 5%11111

평균적으로 얼마나 많은 bits가 필요한지 기대값을 계산해보면,
variable-length : 0.6(확률) * 1(bit수) + 0.25 * 2 + 0.1 * 3 + 0.05 * 3 = 1.55 가 된다.
즉, fixed-length를 사용하면 기대값이 2bit인데 반해 variable-length를 사용하면 1.55로 더 줄어들게 되는 것이다.

문제 정의

유용한 사실은 binary code 와 binary tree 가 mapping 된다는 것이다.

Mapping Binary Tree

왼쪽은 0, 오른쪽은 1
encoding은 binary tree의 root로 부터 bit 경로이다.
decodeing은 반복적으로 rootd에서 leaf까지 Tree 경로를 따라가면 만나는 leaf노드가 해당 binary code에 mapping된 symbol 이다.​

여러개 binary tree 가 있지만 그 중에 평균 encoding length 가 최소가 되는 binary tree(T)를 찾아야 한다.

encoding length인 기대값 L(T)는 각 leaf에 대해 확률 * bit수의 합으로 (T는 tree를 의미한다.)

알고리즘

어떻게 최소가 되도록 binary tree 를 구성할 수 있을 까?

top-down approach

one idea 접근 방법으로 top-down approach로 divied and conquer 알고리즘 디자인 패러다임을 생각할 수 있다. 그러면 어떻게 그룹을 나눌까?

subtree T1, T2 로 나누는 데 빈도가 50%씩 나눠야 한다.
그렇게 해야 한쪽에 depth가 긴 것이 나오지 않기 때문이다.

divede and conquer (T1과 T2는 서로 50%에 가까운 빈도)

이렇게 반복적으로 하기엔 복잡하다

bottom-up approach

top-down이 복잡하여 허프만이 생각한게 bottom-up 방식이다.
tree를 root가 아니라 leaf부터 만드는 방식이다.

Bottom-up approach

그렇다면 다음으로 문제가 있다

어떻게 leaf를 안전하게 묶을까?

– Greedy 방법으로 가장 빈도수가 작은 2개의 leaf를 묶는 것이다.

어떻게 반복적으로 수행할 수 있을 까?

– leaf노드 2개를 묶어서 새로운 “meta-symbol” 1개로 만드는 것이다.

새로운 “meta-symbol” 의 확률은 leaf노드 각 확률을 더한 것과 같다.
각 symbol 이 나올 확률이기 때문에 새로운 meta-symbol 나올 확률도 각 symbol과 같기 때문이다.

증명

허프만 코드는 Greedy 방법으로 가장 빈도수가 작은 2개를 묶어서 tree를 구성하는 것이다.
그러면 어떻게 이게 encoding length가 가장 작은 tree로 구성될 수 있을 까?

key lemma

  1. 가장 작은 두 symbol이 깊은 depth에 sibling으로 있는 것이 최적이다.
  2. L(T) – L(T’)에서 확률 p는 depth에 독립적이다.
    L(T)가 가장 작은 값이 optimal한 것이다.
    optimal한 L(T) = L(T*) 일때,
    L(T*) – L(T^) >= 0 이면, L(T^) 역시 optimal이다.

공부한 출처 : https://www.coursera.org/learn/algorithms-greedy/home/week/3