허프만 코드 (Huffman Code)

I. 문자의 빈도 기반 접두부호 생성, 허프만 코드의 개요

무손실 압축 위한 엔트로피 부호화로, 데이터 등장 빈도에 따라 다른 길이 부호 사용 알고리즘

개념도	설명
	– 접두어 코드 사용 압축 – 접두어 코드 표현 왼쪽 서브 노드: 0 오른쪽 서브 노드: 1 – 루트→리프 경로가 접두어

– 허프만 코드는 무손실 압축, 심볼의 출현 빈도에 따른 가변 길드 코드와 접두사 코드 생성

– 압축: 만들어진 이진 트리 기반 해당 문자 접두어 코드로 변환
– 해제: 노드 탐색 시 리프 노드까지 트리의 좌, 우 노드 순회

구분	수행 절차	설명
압축	초기화	– 모든 문자 출현 빈도에 따라 나열
	해 선택	– 빈도수 가장 낮은 두 개 결합 – 두 노드 위 부모 노드 생성, 연결
	실행가능성 검사	– 기호를 가진 노드가 리프 노드 조건 만족하는지 여부 검사
	최종 해 검사	– 허프만 트리 완성 여부 – 미완성 시 2, 3단계 반복 수행
해제	버퍼 준비	– 허프만 트리와 압축 해제된 데이터를 담을 버퍼를 준비
	비트 해석	– 압축 데이터에 미탐색 부분 Read
	트리 순회	– Read 비트가 0 → 왼쪽 노드로 이동 – Read 비트가 1 → 오른쪽 노드로 이동

절차	허프만 트리 생성	설명
초기화		– aaabaacdd의 빈도 a:5, b:1, c:1, d:2
해 선택	– b, c 이용 트리 생성 – b, c트리에 d트리생성 – 남은a로 최종트리생성	– 현재 시점에서 빈도가 가장 작은 노드 두 개 선택 (리프 노드 조건)
실행 가능성 검사		– 기호 가진 노드가 리프 노드 조건을 만족하는지 검사
최종해 검사		– 모든 노드가 트리에 속하도록 완성까지 반복 수행, 검증 (완성도 개념도 참조)

– 압축 결과: 0 0 0 100 0 0 101 11 11

a	a	a	b	a	a	c	d	d
0	0	0	100	0	0	101	11	11

– 원본 데이터(ASCII 코드 시)의 크기는 72bit → 15bit로 압축

절차	허프만 트리	버퍼 상황
버퍼 준비	– 허프만 트리, 압축 데이터와 버퍼(루트 숫자) 준비
비트 해석 및 트리 해석	– 압축 해제된 버퍼 Read – 왼쪽으로 이동, 해당하는 리프 노드의 a를 압축 해제 버퍼에 추가하고 루트노드로 복귀 – 세 번째 비트까지 0 계속 Read, 3번째까지 a 추가
비트 해석 및 트리 해석	– 1 해당, 오른쪽 이동, 리프 노드X → 다음비트 Read – 0 해당, 왼쪽 이동, 리프 노드X → 다음비트 Read – 0 해당, 왼쪽 이동, 리프 노드 b를 압축 해제 버퍼 에 추가, 루트 노드로 복귀
	– 압축 데이터에 해당하는 전체 대상을 수행시 까지 반복 수행 후 종료

code = 0
while more symbols:
print symbol, code
code = (code + 1) << ((bit length of the next symbol) – (current bit length))

도리: