허프만 알고리즘으로 문자열 압축하기, Huffman Algorithm Encoding

우리는 컴퓨터로 알파벳을 유용하게 표현하기 위해 extended ASCII code 를 이용해 8bit (1byte)에 저장해 사용한다.

예를 들어 문자 'A'는 ASCII code로 '65'이고, binary code로 나타내면 '01000001'이다. 이를 표로 나타낸 이미지를 아래에 가져와보았다. 

만약에 우리가 "BCCABBDDAECCBBAEDDCC"라는 20개의 문자를 별도의 압축 과정없이 전 컴퓨터에게 전송한다 생각해보자. 한 문자는 8bit이므로, 이 문자들은 총 160bits를 사용한다. 이 문자중에는 반복해서 등장하는 알파벳이 존재하기 때문에, 반복하는 각각의 문자를 'Encoding'하여 binary code를 압축시키면 8bit전체를 사용할 필요가 없다. 앞 문장에선 5가지의 알파벳이 등장한다. 2 bits의 binary 수는 00, 01, 10, 11로 4가지 수밖에 표현할 수 없다. 그러므로 3 bits의 binary수를 채택해 A, B, C, D, E 각각의 알파벳을 000, 001, 010, 011, 100으로 5가지의 수로 표현해보자. 이를 "Fixed - Length binary code"라 부른다.

 

인코딩한 binary code를 수신자가 해석하기 위해서는, 원래의 메세지와 각각의 문자표를 어떻게 인코딩했는지 알기 위한 정보들이 적힌 Table data가 함께 전송되야한다. 테이블을 만들기 위해선 앞에서 전송한 "BCCABBDDAECCBBAEDDCC"가 총 5가지의 알파벳이 등장하므로 5*8bits의 데이터가 필요하고, 인코딩한 각 알파벳의 binary code가 필요하므로 5*3bit의 데이터가 더해져야 한다. 그러므로 테이블이 차지하는 데이터는 총 55bits 이다. 

 

이 방법에서 각각의 알파벳이 000, 001, 010, 011, 100... 한 문자 당 3bit로 표현되었으므로 20자짜리 문장은 3*20 = 60bit가 필요하다. 그러므로 인코딩한 텍스트 메세지+테이블은 총 115bits를 차지한다. 이는 앞서 한 문자를 8bit로 표현했을 때(160bits)보다 45bits를 절약한 셈이다.

 

여기까지 인코딩이 무엇인지 살펴보았다. 이제 '허프만 코딩'을 이용한 인코딩을 살펴보자. 

Binary tree로 나타낸 메세지 인코딩 과정

Char	Frequency
A	3
B	5
C	6
D	4
E	2
	20

메세지를 분석해보자. 메세지에 알파벳 'A'는 3번, 'B'는 5번, 'C'는 6번, 'D'는 4번, 'E'는 2번 등장한다. 이를 Binary Tree로 표현하면 위와 같다. 가장 빈도수가 낮은 'E'와 'A'는 왼쪽 최하단 노드로 두고, 그 둘 중 더 낮은 빈도수를 가진 'E'는 왼쪽에, 그래도 더 높은 빈도수를 가진 'A'는 오른쪽 노드에 배치한다. 이렇게 작은 수는 왼쪽으로, 높은 수는 오른쪽으로 배치하는 것을 반복하다 보면 위와 같은 트리 형태 그래프를 얻을 수 있다. 

Char	Frequency	Binary code	bits * Frequency
A	3	001	3*3 = 9 bits
B	5	10	2*5 = 10 bits
C	6	11	2*6 = 12 bits
D	4	01	2*4 = 8 bits
E	2	000	3*2 = 6bits
	20		45bits

이제 그래프의 왼쪽 노드를 0, 오른쪽 노드를 1이라 하고 각 문자별로 Binary code를 써보자. 가장 빈도수가 적은 E와 A는 Depth가 가장 깊기 때문에 3bit로 표현하고 E가 가장 적기 때문에 왼쪽 노드에 그려서 000으로 표현하고, A는 그 다음으로 빈도수가 적기 때문에 오른쪽 노드에 그리고 001이라 적는다. 그렇게 각각의 알파벳을 노드를 타고가서 표현하면 위 테이블과 같은 코드를 얻을 수 있고, 위 메세지의 총 데이터 크기를 알기 위해 각 알파벳의 (Binary code의 bit 수)*(알파벳 빈도수)를 해서 더한다. 그러면 위 인코딩 방법을 통해 "BCCABBDDAECCBBAEDDCC" 메세지를 45bits까지 압축할 수 있다.

 

이제 메세지와 함께 보내질 테이블의 데이터 크기를 알아보자. 테이블에는 문자가 5종류 들어가므로 우선 5*8=40 bits가 필요하다. 그 다음으로, Binary code를 작성하기 위해 사용한 이진수의 갯수는 001, 10, 11, 01, 000.. 총 12개를 사용했다. 그러므로 테이블의 크기는 40bits + 12bits = 52bits이다.

 

따라서 허프만 코딩을 통해 압축한 메세지의 데이터 크기는 97 bits이다. 

메세지에 아무런 처리 없이 그냥 데이터를 전송했을 땐 160 bits가 필요했다. 그 다음으로 알아본 Fixed-length binary code로 메세지를 처리했을 땐 115 bits가 필요했다. 마지막으로 허프만 코딩으로 메세지를 처리하면 97 bits가 필요하다. 이 예를 통해 허프만 알고리즘을 사용하면 단순한 문자열부터 시작해 하나의 큰 텍스트 파일을 전송할 때 큰 효율을 보일 것이란 것을 알 수 있었다.

 

---------

허프만 알고리즘 코딩 중...

struct nodetype
{					// assume that
	char symbol;	// The value of a character
   	int frequency;	// The number of times of character
    				// is in the file
    nodetype* left;
    nodetype* right;
};

 

/*
n = number of characters in the file.
p = poitner in PQ

now initiate PQ nodes
*/

p->symbol = a distinct character in the file;
p->frequency = the frequency of that character in the file;
p->left = NULL;
p->right = NULL;