간단한 알고리즘
- n개의 초기 허프만 트리 모음이 준비되며, 각 트리는 단일 리프 노드입니다. 가중치(빈도)별로 구성된 우선 순위 대기열에 n개의 트리를 유지합니다.
- 처음 두 트리(가중치가 가장 작은 트리)를 제거하거나 삭제합니다. 이 두 나무를 결합하여 루트가 두 나무와 자식으로 연결되고 가중치가 두 자식 나무의 가중치 합인 새 나무를 만듭니다.
- 이 새 나무를 우선 순위 대기열에 보관하십시오.
- 모든 부분적인 Huffman 트리가 하나로 결합되지 않을 때까지 2-3단계를 반복합니다.
욕심 많은 알고리즘입니다. 각 반복에서 알고리즘은 가중치가 가장 작은 두 하위 트리를 병합하기 위해 "탐욕적인" 결정을 만듭니다. 알고리즘이 원하는 결과를 줄 수 있습니까?
- 정리형:x와 y를 빈도가 가장 낮은 두 문자로 설정합니다. x와 y가 형제 관계인 최적의 코드 트리가 있으며, 그 깊이는 트리의 다른 리프 노드만큼 최소입니다.
- 정리:Huffman 코드는 접두어가 없는 최적의 바이너리 코드로 처리됩니다(greedy 알고리즘은 주어진 문자 집합에 대해 최소 외부 경로 가중치를 사용하여 Huffman 트리를 구성합니다).