허프만 부호화
허프만 부호화은 기호의 빈도에 따라 길이가 다른 접두 부호를 구성해 평균 코드 길이를 줄인다 무손실 엔트로피 부호화 분야의 대표적인 기술로, 데이터의 표현과 입력 조건에 맞는 계산 절차를 정의한다. 적용 목적이 유사한 다른 방법과 비교할 때 정확성 보장과 결과의 해석이 중요하다.
| 분류 | 알고리즘 · 무손실 엔트로피 부호화 |
|---|---|
| 주요 목적 | 기호의 빈도에 따라 길이가 다른 접두 부호를 구성해 평균 코드 길이를 줄인다 |
| 핵심 방법 | 빈도가 가장 낮은 두 노드를 우선순위 큐에서 꺼내 부모를 만들고 합산 빈도를 다시 넣는다 |
| 복잡도 | 기호 종류 k에 대해 구축 O(k log k), 인코딩은 출력 비트 수에 의존 |
| 적용 조건 | 입력 기호의 빈도·확률 분포가 필요하고 복호화용 코드 정보가 있어야 한다 |
| 참고 자료 | 기술 자료 |
| 관련 분야 | 자료구조, 계산 복잡도 |
허프만 부호화은 기호의 빈도에 따라 길이가 다른 접두 부호를 구성해 평균 코드 길이를 줄인다 무손실 엔트로피 부호화 분야의 대표적인 기술로, 데이터의 표현과 입력 조건에 맞는 계산 절차를 정의한다. 적용 목적이 유사한 다른 방법과 비교할 때 정확성 보장과 결과의 해석이 중요하다.[1]
핵심 작동은 다음과 같다. 빈도가 가장 낮은 두 노드를 우선순위 큐에서 꺼내 부모를 만들고 합산 빈도를 다시 넣는다. 구성된 이진 트리의 경로로 각 기호의 비트 부호를 정의한다. 이 절차에서 각 단계에 유지되는 값의 의미를 정의하고 자료구조 또는 수치 표현에 따라 처리 순서를 구현한다.
계산 특성은 기호 종류 k에 대해 구축 O(k log k), 인코딩은 출력 비트 수에 의존 실제 구현에는 입력 기호의 빈도·확률 분포가 필요하고 복호화용 코드 정보가 있어야 한다 단계마다 유지되어야 하는 불변식, 종료 조건과 입력 경계를 검사하면 수학적 모델을 프로그램의 동작과 연결할 수 있다.
활용과 다른 기법과의 관계에서는 고정된 기호별 독립 접두 부호의 평균 길이를 최소화한다. DEFLATE 등에서 다른 압축 단계와 결합된다. 실제 시스템에서는 시간·메모리 사용, 입출력 비용, 정밀도와 저장 형식이 성능에 영향을 줄 수 있다. 필요한 경우 가장 작은 입력과 중복·퇴화 상태도 시험해야 한다.[2]