(23.03.25)
algorithms S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기
http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf
정리한 내용
5.2 Huffman encoding
---> prefix encoding
예전에 수업들으면서 정리했던 내용: https://hey-stranger.tistory.com/152
Huffman encoding
- 빈도수에 따라서 문자를 bit로 표현하는 방법이다.
- 빈도수가 높을수록 더 적은 bit, 빈도수가 낮을수록 더 많은 bit으로 표현한다.
- 이를 표현할 때 prefix-free encoding을 사용한다.
- 가변적인 길이의 code로 표현하기 때문에 저장공간 활용력이 좋다고 볼 수 있다.
Prefix code
- prefix는 전위부를 뜻하는 말이다.
- prefix는 variable-length code이다.
- 자신의 코드를 제외한 코드의 prefix 집합 안에 자신의 코드가 들어 있을 때, 이는 prefix code가 아니다.
- 자기 자신을 제외한 코드의 prefix 집합에 자신의 코드가 포함되어 있지 않을 때, prefix code이다.
- prefix-free code == prefix code
- prefix code는 full binary tree로 표현할 수 있다. 그 예시는 아래와 같다.
- fully binary tree는 완전 이진 트리. 모든 노드는 자식이 아예 없거나, 자식노드가 2개 있다.
Huffman encoding 과정
(1) 각 character에 대한 leaf node 생성하고, 빈도수에 따라서 min priority queue에 넣는다.
(2) 빈도수가 가장 낮은 2개의 노드를 queue에서 제거한다.
(3) 선택한 2개의 노드의 빈도수를 합하고 부모노드를 생성한다.
(4) 생성한 부모노드를 min priority queue에 넣는다.
(5) 2~4번 단계를 반복하고, 최종적으로 마지막 남은 노드는 root 노드가 된다.
-----> 진행과정을 보면, 매 순간마다 가장 작은 빈도수 2개의 노드를 선택하기 때문에 greedy algorithm이라고 할 수 있다.
huffman code 진행과정 예시
