Huffman tree
1. Huffman Coding Trees
1-1. 문제 상황
ASCII codes : 문자 하나당 8bit가 사용되는 크기가 고정된 코딩방법
자주 사용하는 문자를 더 적은 수의 비트로 코딩하면 공간을 줄일 수 있다.
variable-length coding : 문자별로 길이를 다르게 하는 코딩
목표 : external path weight이 최소가 되는 binary tree를 구하는 것
weighted path length of a leaf : weight $\times$ (depth of the leaf)
external path weight = weighted path length의 합
1-2. Huffman tree 생성 과정
1) frequency 중에서 가장 작은 것 두개를 찾는다.
2) 그 둘을 합쳐서 트리를 만든다.(작은 것이 왼쪽에 가도록)
3) 그 둘을 합친 트리를 element 중 하나로 놓는다.
4) 1)-3)을 하나의 트리가 만들어질 때까지 반복
step1)
step2)
step3)
step4)
step5)
step6)
step7)
1-3. Coding and Decoding
Huffman으로 coding된 string은 decode 가능하다.
=> 왜냐면 huffman code의 경우 하나의 code가 다른 code의 prefix가 되지 않기 때문이다. -> Prefix property
Huffman code의.expected cost는
$$\frac{c_1 f_1 + c_2 f_2 + ... + c_n fn}{f_T}$$
로 구할 수 있다.
대부분 fixed-length coding보다 효율적으로 나온다.
1-4. Uniqueness of Huffman Tree
No, huffman tree는 unique하지 않다.
왼쪽과 오른쪽 노드는 마음대로 정할 수 있기 때문이다.
=> 그래도 external path weight는 여전히 최소로 유지할 수 있음.
1-5. Optimality of Huffman Tree
Theorem
Huffman coding tree gives the minimum external path weight
(Proof)
Lemma 1) 최소의 frequency를 가진 두 문자를 자매 노드(리프 노드만큼의 깊이를 가진)로 가지는 optimal tree가 존재한다.
Lemma 1 proof) = proof by contradiction
최소의 frequency를 가지는 sibling L = {x, y}가 가장 깊지 않다고 하고 $z \notin L$ 인 z가 가장 깊다고 해보자.
z와 y를 바꾸면 더 최소의 external path weight을 가지게 된다. 이것이 contradiction이라는 결론을 내릴 수 있다.
그렇기 때문에 가장 작은 frequency를 가진 L = {x, y}는 가장 깊은 곳에 있어야 한다.
만약 x, y가 sibling이 아니라면, $x \in L$ 과 $z \notin L$이 서로 sibling이라고 고려해보자. 만약 y와 z를 바꾸면 또다른 optimal tree가 만들어진다. 그렇기 때문에 x와 y는 sibling이 되어야 한다.
이제 Theorem은 mathematical Induction으로 증명할 수 있다.
n이 number of character라고 할 때 = number of leaves
n = 2일 때, Huffman tree는 optimal하다. => 또다른 트리를 만들 수가 없음
Induction hypothesis
: n-1 letter의 Huffman tree가 optimal하다고 가정
n letter의 Huffman tree가 optimal하다는 것을 proof by contradiction으로 증명한다.
1. T를 n개의 letter가 있는 huffman tree라고 생각.
2. x와 y letter를 T tree에서 가장 frequency가 낮은 letter라고 가정한다. x, y는 huffman tree에서 가장 깊은 노드이다.(by definition)
3. v를 x와 y의 부모 노드라고 가정하자. T'는 v를 weight가 w(x) + w(y)인 v'인 leaf node로 교체한다고 생각해보자. T' 또한 Huffman Tree이고 IH에 의해 optimal tree라는 것을 알 수 있다.
4. T를 not optimal이라고 가정하면, Z를 EPW(External Path Weight)가 T보다 작은(optimal) tree라고 가정해보자. Lemma 1에 의해 Z가 x, y를 가장 깊은 sibling으로 삼고 있음을 알 수 있다. Z'를 parent of x and y를 w(x) + w(y)를 weight로 가지는 v''라는 노드로 교체한다고 생각해보자. 그러면 EPW(Z) = EPW(Z') + w(x) + w(y) >= EPW(T') + w(x) + w(y) = EPW(T)(optimal tree)이다.
따라서 contradiction이 발생함을 알 수 있다.
T는 optimal해야 함을 알 수 있다.
1-6. Trie
Huffman tree는 Trie(prefix tree)의 한 종류이다
BST와 Trie 모두 key를 store하고 retrieve하지만
- In BST, a node는 key에 대응한다.
- In Trie, path가 key에 대응한다.
=> all the descendants of node는 같은 Prefix를 공유한다.