허프만 코드 (Huffman code)

허프만 코드

허프만 코딩은 문자의 빈도 또는 확률정보를 이용해 통계적 압축을 하는 방법

- 텍스트에서 문자가 출현하는 빈도수에 따라 다른 길이의 부호를 부여
- 빈도가 높은 문자는 짧은 코드를 가지고, 빈도가 낮은 문자는 긴 문자가 됨

접두부(prefix code)

각 문자에 부여된 이진 코드가 다른 문자에 부여된 이진코드의 접두부가 되지 않은 코드
겹치지 않도록 이진코드를 만드든 것

허프만 코딩은 프리픽스 코드가 되어야만 디코딩 했을때 문제가 발생하지 않기 때문에 적용 되어야 함
*최적코드: 인코딩된 메시지의 길이가 가장 짧은 코드

인코딩 방법

1. 주어진 텍스트에서 각 문자의 출현 빈도수를 계산
2. 각 문자의 빈도수를 이용하여 허프만 트리를 생성하여 각 문자에 이진코드를 부여
3. 주어진 텍스트의 각문자를 코드로 변환하여 압축된 텍스트를 생성
(부모 노드를 만들 때 왼쪽에는 0, 오른쪽에는 1을 부여)

 

트리를 만들때 부모노드와 삽입되는 노드의 빈도를 삽입 될때마다 비교하여
큰값은 1번코드를 부여하는쪽(오른쪽 자식)으로
작은값은 0번코드로 부여하는 쪽(부모의 왼쪽자식)으로
규칙을 정해 만들어도 같은 비트수를 가지는 허프만 트리가 완성

성능 및 특징

허프만 트리를 만드는데 드는 시간 + 길이 m인 텍스트의 실제 인코딩 시간
O(nlogn) + O(m) = O(nlogn+m)