[알고리즘] Huffman codes : greedy algorithm

(2021.11.08)

알고리즘 수업들으면서 정리하기 18탄

 

w10-2 녹화강의

huffman code 개념, 만드는 방법, greedy 알고리즘

 

---

 

 

Huffman codes

 

• each character를 binary charcter code로 디자인하는 것
• optimal prefix code 라고도 한다.
• huffman code는 빈도수에 따라서 설정해준다.
• huffman code는 variable-length code이며, fixed-length code보다 효율적이다.
• (fixed-length code는 3비트로 표현한다--> 많은 저장용량을 차지한다.)
• prefix-free code (prefix code)

 

출처: 교수님 강의노트

 

 

 

 

huffman code의 가장 큰 특징은 prefix-free code(prefix code)이다.

prefix는 전위부를 뜻하는데 말 그대로 앞부분이라는 뜻이다.

 

 

 

prefix-free code를 사용하면, 코드를 보고 어떤 문자인지 알아내는데에 모호함이 없다.(ambiguity)

Every message encoded by a prefix code is unambiguous

 

 

 

Building Huffman codes

• Huffan codes는 tree를 이용해서 만든다.
• tree는 밑에서부터 만들고, n개의 character라면 n개의 leaves가 된다.
• key는 빈도수
• leaves들은 tree로 병합된다. n-1 번의 merging operations.
• merger의 결과 = 두 개의 nodes의 빈도수의 합
• C = n개의 character들의 집합 ( C= { c | c는 character } )
• f[c] = c character의 빈도수

 

 

출처: 교수님 강의노트

 

 

 

 

Huffman buliding 과정

 

1. 각 character에 대한 leaf node를 생성하고, frequency에 따라 min priority queue에 넣는다.
2. character가 1개 초과일 때(2개 이상)만 반복(while 문: 3~5 반복)                                                    
3. 가장 빈도수가 낮은 2개의 노드를 제거한다. (x와 y)                                                               
4. f[z] = f[x] + f[y] 를 계산해서 부모 node z 를 생성한다.                                                                                    c.
5. 이 node를 queue에 추가한다.
6. 마지막 node가 root node가 된다.

 

 

 

 

 

Performance of greedy Huffman code

 

 

 

 

 

Greediness of Huffman codes

 

결론적으로, Huffman code는 그때 그때 가장 작은 frequency 2개를 골라 tree를 만드는 것이기 때문에 greedy choice라고 할 수 있고, Huffman code의 subtree는 모두 huffman tree의 조건을 만족하기 때문에 optimal substructure 이라고 할 수 있다.

• Greedy choice property : if x and y have the two lowest counts, then the optimal algorithm will have them at the same path length (their codes are two of the longest)
• Optimal substructure : every subtree of a Huffman code defines an optimal code for its leaf characters