※ 2022년 4월 12일에 작성된 글입니다.
Huffman Coding
- 데이터 문자의 등장 빈도에 따라서 다른 길이의 부호를 사용하는 알고리즘
Huffman Coding Tree
- 각 글자의 빈도가 알려져 있는 메시지의 내용을 압축하는데 사용되는 이진 트리
생성 절차
| 문자 | 빈도 수 |
|---|---|
| A | 41 |
| B | 35 |
| C | 62 |
| D | 4 |
| E | 97 |
- 모든 문자를 빈도수에 따라 나열한다.
- 가장 빈도수가 낮은 노드 2개를 고른다.
- 해당 노드를 자식 노드로 하는 새로운 부모 노드를 만든다.
- 하나의 루트 노드가 나올 때까지 2~3번 과정을 반복한다.
