정의
허프만 코딩은 코드의 길이가 해당 문자의 상대적 빈도 또는 가중치에 따라 달라지도록 문자에 코드를 제공합니다. 허프만 코드는 길이가 가변적이며 접두사가 없습니다(즉, 코드가 다른 코드의 접두사가 아님을 의미함). 접두사 없는 바이너리 코드는 인코딩된 문자가 나뭇잎에 저장된 바이너리 트리로 표시되거나 시각화될 수 있습니다.
허프만 트리 또는 허프만 코딩 트리는 트리의 각 잎이 주어진 알파벳의 문자에 해당하는 전체 이진 트리로 정의됩니다.
허프만 트리는 최소 외부 경로 가중치와 연관된 이진 트리로 처리됩니다. 즉, 주어진 잎 세트에 대해 가중치가 부여된 경로 길이의 최소 합과 연관된 것입니다. 따라서 목표는 최소 외부 경로 가중치로 트리를 구성하는 것입니다.
아래에 예가 나와 있습니다-
문자 빈도표
| 문자 | z | k | m | c | u | d | l | e |
| 빈도 | 2 | 7 | 24 | 32 | 37 | 42 | 42 | 120 |
허프만 코드
| 문자 | 빈도 | 코드 | 비트 |
|---|---|---|---|
| e | 120 | 0 | 1 |
| d | 42 | 101 | 3 |
| l | 42 | 110 | 3 |
| u | 37 | 100 | 3 |
| c | 32 | 1110 | 4 |
| m | 24 | 11111 | 5 |
| k | 7 | 111101 | 6 |
| z | 2 | 111100 | 6 |
Huffman 트리(위 예의 경우)는 다음과 같습니다. -
