허프만 코드 (Huffman Code)

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

가. 허프만 코드의 개념

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

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

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

 

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

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

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

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

aaabaacdd
000100001011111

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

나. 허프만 코드를 이용한 복호화 과정

절차허프만 트리버퍼 상황
버퍼
준비

– 허프만 트리, 압축 데이터와 버퍼(루트 숫자) 준비
비트
해석

트리
해석

– 압축 해제된 버퍼 Read
– 왼쪽으로 이동, 해당하는 리프 노드의 a를 압축 해제 버퍼에 추가하고 루트노드로 복귀
– 세 번째 비트까지 0 계속 Read, 3번째까지 a 추가

– 1 해당, 오른쪽 이동, 리프 노드X → 다음비트 Read
– 0 해당, 왼쪽 이동, 리프 노드X → 다음비트 Read
– 0 해당, 왼쪽 이동, 리프 노드 b를 압축 해제 버퍼 에 추가, 루트 노드로 복귀
 

– 압축 데이터에 해당하는 전체 대상을 수행시 까지  반복 수행 후 종료

 

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

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

 

2 Comments

콘텐츠 사용 시 출처 표기 부탁 드리고, 댓글은 큰 힘이 됩니다^^