[알고리즘] 허프만 코드

개요

허프만 코드란 최적 이진 코드를 만드는 알고리즘 중 하나이다.

 

Fixed-length binary code

코드의 길이가 고정적이다.

ex) a : 00, b : 01, c : 11 등

문제점 : 자주 나타나는 코드의 길이도 고정이므로 낭비가 생긴다.

 

Variable-length binary code

코드의 길이가 가변적이다.

ex) a : 10, b: 0, c : 11 등

자주 나타나는 코드의 길이를 줄일 수 있다.

문제점 : 위의 예시에서 d를 00으로 표기하는 방법을 추가하면 00이 d인지, bb인지 구별할 수 없어진다.

 

optimal binary code (최적 이진 코드)

주어진 파일에 있는 문자들을 이진코드로 표현하는데 필요한 비트의 개수가 최소가 되는 코드이다.

Prefix code

한 문자의 코드워드가 다른 문자의 코드워드의 앞부분이 될 수 없는 코드이다.

ex) a : 10, b : 0, c : 11 등

앞으로 읽을 비트를 확인하지 않아도 코드를 해석할 수 있다.

prefix code 예시

Prefix code 예시

파일 A에 들어있는 문자가 bbbaac라고 하고,  코드를 다음과 같이 나타낼 수 있다고 하자.

c1, c2, c3에 대한 각각의 이진 코드는 다음과 같다.

따라서 c3가 파일 A에 대한 최적 이진 코드가 된다.

총 비트 수를 구하는 방법은 다음과 같다.

허프만 코드 구축 방법

1. 빈도수를 데이터로 갖는 n개의 노드를 생성한다.

2. 빈도수의 합이 최소가 되는 노드를 merge 시켜 이진 트리를 구축한다.

3. 모든 노드가 하나의 이진 트리가 될 때 까지 단계(2)를 반복한다.

 

허프만 코드 구축 예시

a, b, c, d, e, f 6개의 문자에 대해 각각의 빈도수가 다음과 같다고 하자.

a	b	c	d	e	f
16	5	12	17	10	25

(1) 가장 빈도수가 적은 b와 e를 합친다.

(2) 그 다음 빈도수가 작은 c와 (b,e)를 합친다.

(3) 다음으로 빈도수가 작은 a와 d를 합친다.

(4) (b, c, e)와 f를 합친다.

(5) (a, d)와 (b, c, e, f)를 합친다.

완성!!