허프만 코드(Huffman code)

허프만 코드는 데이터를 효율적으로 압축하는데 사용하는 방법으로 탐욕 알고리즘 중 하나입니다.

압축하고자 하는 문자열에서 자주 등장하는 문자는 짧은 비트로 표현하고 거의 등장하지 않는 문자는 긴 비트로 표현합니다. (가변 길이 코드)

즉, 문자의 빈도수를 이용합니다.

 

예시를 들어 설명하겠습니다.

EX) 압축하고자 하는 문자열 : ABBCCCDDDDEEEEEFFFFFF

-> 고정 길이 코드 : A ~F. 6개의 문자를 구분하기 위해 3bit 필요. (2^2(4) < 6 < 2^3(8) 이므로 3bit가 필요하다.)

-> 가변 길이 코드 : 허프만 코드를 이용해서 나온 값.

 

[표 1]

 

<압축 결과>

고정 길이 코드 : 000001001010010010011011011011100100100100100101101101101101101

 

가변 길이 코드 : 100010011001101101101000000000101010101111111111111

 

허프만 코드를 사용한 결과(가변 길이 코드)가 더 짧다는 것을 볼 수 있습니다. -> 효율적으로 압축.

이제 어떻게 허프만 코드(가변 길이 코드)를 만드는지 알아보겠습니다.

 

압축하고자 하는 문자열의 예시는 마찬가지로 "ABBCCCDDDDEEEEEFFFFFF"를 사용하겠습니다.

문자열이 위의 [표 1]을 만들 때와 같으므로 허프만 코드를 완성시키면 [표 1]의 가변 길이 코드가 왜 저렇게 나왔는지 알 수 있습니다.

 

 

 

[그림 1]

 

우선 허프만 코드를 만들기 위해 트리를 만들어야 합니다.

우선 알파벳 별 빈도수를 저장한 노드들을 생성합니다. (그림 1)

 

[그림 2]

 

빈도수를 비교하여 가장 작은 빈도수를 가진 노드와 두 번째로 작은 빈도수를 가진 것을 찾아서 두 개의 빈도수를 합친 수로 노드를 하나 만들어 줍니다.

그리고 만들어준 노드의 왼쪽 자식에는 가장 작은 빈도 수의 노드를 연결하고 오른쪽 자식에는 두 번째로 작은 빈도수를 가진 노드를 연결합니다. (그림 2)

 

[그림 3]

 

이를 반복하여 비교할 노드가 한 개가 남을 때까지 반복합니다. (그림 3)

 

[그림 4]

 

완성한 트리 노드의 왼쪽 간선에는 0, 오른쪽 간선에는 1 가중치를 둡니다.

트리들의 단 노드가 압축하고자 하는 문자가 되며 그 문자들을 루트로부터 탐색했을 때 지난 간선들의 가중치들의 합이 허프만 코드(가변 길이 코드)가 됩니다. EX) A : 1-0-0-0 / E : 0-1

인코딩은 문자열들의 문자를 구한 허프만 코드로 치환해주면 됩니다.

디코딩도 위에 완성된 트리(그림 4)를 사용해서 하는데 인코딩된 문자열들을 앞에서부터 읽어들여 root 노드로부터 0이 나오면 왼쪽 자식으로 이동하고 1이 나오면 오른쪽 자식으로 이동하여 단 노드가 나올때까지 이를 반복합니다. 단 노드가 나온 경우 그 노드에 알맞은 알파벳을 출력한 후 다시 루트 노드로 돌아가서 반복합니다.

 

 

저는 문자 A~F로만 이루어진 문자열을 입력받아 각 문자별 허프만 코드를 출력하고 인코딩 디코딩한 결과를 출력하는 소스를 작성해 보았습니다.

이번에는 노드의 최소값 노드와 2번째 최소값 노드를 구할 때 그냥 변수를 이용하였는데 최소 힙을 이용하여 구하는 방법도 있습니다.

 

소스 코드 : https://gist.github.com/fpdjsns/a46dede3cbd4a05599c94fcda562a0e0 (A~F)

 

[실행 결과]

 

+

A~F만 입력받던 것을 알파벳 대문자 입력받는 것으로 바꾸어보았습니다.

소스코드 : https://gist.github.com/fpdjsns/b82d2ba881ab011f0fe001bb395fa282 (대문자)

 

[실행 결과]