[Algorithm] Greedy로 Huffman code 풀기

Greedy 란?

각 단계에서 가장 최적의 선택을 하는 것으로,

그 순간에는 최선의 선택이지만 전체적으로는 최적해를 보장하지는 않는 알고리즘입니다.

 

 

Huffman code란?

데이터를 인코딩(encoding)/디코딩(decoding)하기 위해 필요한 알고리즘입니다.

 

 

인코딩하는 과정

---

① 입력 문자열에서 문자의 빈도수를 구한다.

② 빈도수를 기준으로 이진 트리를 생성한다.

③ 왼쪽 자식 노드는 0, 오른쪽 자식 노드는 1를 부여해서 huffman 코드를 생성한다.

④ 입력 문자열에서 찾은 huffman 코드를 순차적으로 연결하여 하나의 비트 스트림으로 생성한다.

 

 

디코딩하는 과정

---

① 저장된 비트 스트림을 읽어 각 문자의 huffman code를 생성해서 원래 문자로 변형한다.

 

 

디코딩하는 과정에서 중요하게 살펴볼 조건이 있습니다.

prefix code입니다.

 

a = 01, m = 10, n = 111, o = 0, r = 11, s = 1, t = 0011 이라고 했을 때,

만약 저장된 문자열 100110111을 해석할 때 해석할 수 있는 결과가 많아집니다.

 

즉 어떤 문자의 코드가 다른 문자의 코드의 접두사(prefix)가 되지 않는 코드를 의미합니다.

 

 

문제를 풀면서 자세히 이해해보록 하겠습니다.

 

 

 

Huffman code 문제풀기

---

 

	a	b	c	d	e	f
Frequence	45	13	12	16	9	5

frequency가 작은 두 개의 값을 꺼냅니다.

두 노드의 frequency를 합치고 다시 값을 넣습니다.

	a	b	c	d	ef
Frequence	45	13	12	16	14

이 과정을 반복합니다.

 

	a	d	fe	cf
Frequence	45	16	14	25

 

 

	a	cf	def
Frequence	45	25	30

 

 

	a	bcdef
Frequence	45	55

 

 

 

Frequence

 

 

모든 노드가 다 빠져나왔다면 왼쪽 노드에는 0, 오른쪽 노드에는 1 비트를 부여합니다.

a: 0

b: 101

c: 100

d: 111

e: 1101

f: 1100

 

 

구한 결과로 보면 비트열이 서로 겹치지 않음을 확인할 수 있고 이 조건을 prefix code라고 부릅니다.

 

 

 

◡̈