허프만 코드 (Huffman Code)

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

가. 허프만 코드의 개념

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

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

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

II. 허프만 코드의 수행 알고리즘

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

III. 허프만 코드를 이용한 압축과 복호화 과정

가. 허프만 코드를 이용한 압축 과정 (사례: aaabaacdd)

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

– 압축 결과: 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를 압축 해제 버퍼 에 추가, 루트 노드로 복귀
	– 압축 데이터에 해당하는 전체 대상을 수행시 까지  반복 수행 후 종료

IV. 허프만 코드 알고리즘 코드