허프만 코드 알고리즘

허프만 코드 알고리즘은 압축 알고리즘 중의 하나이다.

알집 역시 허프만 코드 알고리즘으로 한 번 압축하고 난 후에, 

Lempel이라는 알고리즘으로 한 번 더 압축한다고 한다. 

그만큼 실제로도 허프만 코드 알고리즘은 압축 알고리즘에서 중요하다는 말!

허프만 코드 알고리즘에 대해서 소개

자주 쓰이는 문자에 작은 bit를 비교적 덜 쓰이는 문자에 큰 bit를 할당해서 문자열을 전체적으로 압축하는 

개념이다.

예를 들어, AABBAC에서 

A => 3번

B => 2번

C => 1번

출현한다. 

가장 많이 사용하는 A에는 0을,

그 다음 B에는 01, C에는 11을 부여해

A(0)A(0)B(01)B(01)A(0)C(11)로 만든다.

=> 000101011

영문자 하나는 1byte이기 때문에 6byte가 사용되었다. (6 * 8 =  48 bit)

압축된 허프만 코드는 9bit가 된다. 

9/48 = 0.18     => 20%로 압축된다!

허프만 코드의 작동 방법?

예를 들어, CDDCACBCBCCCBBCDA라는 문자열이 있다.(총 17byte)

1) 빈도수 검사

2) 빈도수 대로 정렬(Repeat 1/2)

3) 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만듦(Repeat 2/2)

4) 빈도수 대로 정렬(Repeat 1/2)

5) 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만듦(Repeat 2/2)

6) 빈도수 대로 정렬(Repeat 1/2)

7) 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만듦(Repeat 2/2)

8) 트리 완성!

허프만코드 작성

가장 윗 트리에서 빈도수가 큰 트리에 0을 작은 트리에 1을 부여

위(최상위) 트리 노드를 기준으로 비트를 참조한다.

부모노드에서 출발하여 문자열에 다다를때까지 비트를 더하여 참조한다. 즉, 

D => 000

A => 001

B => 01

C => 1 

디코드 하는 방법?

호프만 트리를 타고 내려가면서 문자를 만나면 치환을 한다.(복호화 과정)

1000000100110110111101011000001

최상위 노드를 기준으로 비트의 수를 따라가며 알파벳을 만날 때까지 따라간다.

1(C)/000(D)/000(D) ..........

=> CDDCACBCBCCCBBCDA 가 된다!

참조 http://wooyaggo.tistory.com/95