2022. 4. 16. 14:40ㆍComputer Science/Algorithm
우리는 컴퓨터로 알파벳을 유용하게 표현하기 위해 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를 절약한 셈이다.
여기까지 인코딩이 무엇인지 살펴보았다. 이제 '허프만 코딩'을 이용한 인코딩을 살펴보자.
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;
'Computer Science > Algorithm' 카테고리의 다른 글
[힙] 프로그래머스 이중우선순위큐 파이썬 풀이 (0) | 2023.05.09 |
---|---|
[스택/큐] 프로그래머스 프로세스 파이썬 풀이 (1) | 2023.05.09 |
[스택/큐] 프로그래머스 올바른 괄호 - 파이썬 (0) | 2023.04.14 |
[스택/큐] 프로그래머스 기능개발 - 파이썬 (0) | 2023.04.14 |
[알고리즘을 위한 수학이론] 유클리드 호제법을 PS에 적용하기 -1 (Ft. C++) (0) | 2022.02.28 |