[자료구조] 허프만 코드

허프만 코드에 대해 알아보자. 

이번 글은 허프만 코드를 주제로 했지만, 우선순위 큐(Priority Queue) 를 먼저 선행하고 와야 한다. 

 

먼저 허프만 코딩이 무엇인지 알아보자.

허프만 코딩은 문자의 빈도 또는 확률정보를 압축하는 알고리즘이다. 

예를 들어 aaaabbbc 라는 문자가 있다고 가정했을 때,

a = 4 , b = 3 , c = 1 로 표현하고 

이를 통해 빈도가 높은 문자(a) 빈도가 낮은 문자(c) 로 표현할 수 있다.

 

여기서 a 에 111(2) 이란 값을 부여하고

b 와 c 는 111(2) 를 부여하면 중복되는 문제가 발생한다. 

이는 복호화할 때 문제가 발생할 수도 있기 때문에, 값이 겹치면 안된다.

 

 

허프만 코드를 만들기 위해선 다음과 같은 과정을 거쳐야 한다.

1. 주어진 텍스트에서 각 문자의 출현 빈도수를 계산

2. 각 문자의 빈도수를 이용해 허프만 트리를 생성해 각 문자에 이진코드를 부여

3. 주어진 텍스트의 각 문자를 코드로 변환해 압축된 텍스트를 생성

 

 

글로 보는 것 보다는 직접 보는게 나을거 같아 바로 진행해 보겠다.

만약 aabzzzc 를 예로 들어보겠다.

 

1. 각 글자의 빈도수를 따져 순서를 정한다.  난 (z , a , b, c) 순으로 정함

2. 다음으로 빈도수가 적은 글자부터 부모노드를 만들어 나간다.

3. 노드를 잇는 선을 기준으로 왼쪽을 0, 오른쪽을 1로 정함 (반대로 설정 가능)

 

그렇다면

z 는 0(2)

a 는 10(2)

b는 110(2)

c는 111(2)

로 표현 할 수 있다.