신문에 실린 기사를 분석하여 각 글자들의 빈도수를 분석하여 이 기사의 내용을 압축하기위해 고안된 알고리즘이다.
이진 트리를 사용하여 빈도수가 높은 글자에 적은 용량을 부여하고 빈도수가 적은 글자에는 큰 용량을 부여하는 과정이다.
글자마다 용량을 부여한다는 의미는 우리가 흔히 사용하는 아스키 코드를 사용하지 않고 글자 빈도수를 이용한 효율적인 새로운 엔코딩 비트열을 만드는 것을 의미한다.
압축하고 싶은 문자열 : AABACDDFAABBBBACCEEEE
- 빈도수
A : 6
B : 5
C : 3
D : 2
E : 4
F : 1
- 각 알파벳의 고정 길이 코드
A : 000
B : 001
C : 010
D : 011
E : 100
F : 101
각 알파벳의 가변 길이 코드를 허프만코드를 통해 직접 구해보도록 하자. 이진트리를 이용하여 구할 수 있다.
허프만 코드 과정
허프만 코드에는 규칙이 있다
- 모든 집합을 빈도순으로 정렬한다
- 빈도가 가장 낮은 2개의 그룹을 합친다.
- 빈도수가 큰 그룹에 0을 주고 빈도수가 작은 그룹에 1을 준다.
- 임의의 심벌이 다른 심벌의 첫 부분이 아니어야 한다. (아래에서 자세히 설명)
예시
1. 각 알파벳의 빈도수를 구한다.
2. 빈도수가 낮은 것부터 오름차순 정렬한다. 최소값 2개를 합친다.
3. 오름차순으로 정렬한다. 정렬되어있기 때문에 가장 낮은 두개를 합친다.
4. 정렬한다.
5. 가장 낮은 두 개를 합친다.
6. 정렬한다. 위에서 9, A:6, 6 3개를 정렬시킨다. 정렬 후 가장 낮은 두개를 합친다.
7. 정렬한다.
8. 남은 2개를 합친다. 트리의 간선에 0과 1을 부여해줘야한다. 왼쪽에 1을 주고 오른쪽에 0을 준다. 빈도수가 높은쪽에 0을 줘야하기 때문이다.
9. 0과 1을 부여해준다. 이진트리를 따라 부여된 수를 차례로 적어 허프만코드를 통해 얻어낸 인코딩을 정리해준다.
각 알파벳의 가변 길이 코드
A : 00
B : 10
C : 010
D : 0110
E : 11
F : 0111
각 알파벳의 고정길이 코드와 다르게 알파벳의 데이터 길이가 일정하지 않은 이유는 압축된 데이터로부터 원래 데이터를 추출 할 때 서로 다른 심벌을 가져야 하기 때문이다.
만약 심벌이 1, 0, 00 로 3가지로 나눠진다고 가정하면 압축된 데이터가 “1000”일 경우 첫번째 수 1을 떼어내고 나머지로 경우의 수를 따져보면 “0” “0” “0”, “0” “00”, “00” “0” 로 3가지 방법으로 분류되기 때문에 원래 데이터가 뭐였는지 알 수 없다.
알파벳의 고정길이코드와 가변길이코드를 통해 인코딩된 데이터를 보자
고정길이코드 : 000000001000010011011101000000001001001001000010010100100100100
가변길이코드 : 000010000100110011001110000101010100001001011111111
고정길이코드보다 허프만코드를 이용해 얻은 가변길이코드가 더 짧은 것을 알 수 있다.
실제 데이터 : AABACDDFAABBBBACCEEEE
가변길이코드 : 000010000100110011001110000101010100001001011111111
실제 데이터는 21글자로 21*8(bit) = 168(bit)이다
압축된 데이터는 51글자이지만 이진데이터이므로 글자당 1(bit)크기로 계산하면 51(bit)이다
압축률은 51/168 * 100 = 약 30.35% 이다.
압축을 해제하는 것은 비트 데이터(가변길이코드)를 허프만트리에 넣고 루트 노드로부터 탐색해서 리프노드가 나오면 치환해주고 다시 루트부터 탐색하는 과정을 거쳐주면 된다. 이것을 위해 임의의 심벌이 다른 심벌의 첫 부분이 아니어야 하는 조건을 만족시켰던 것이다.
참고 : http://keepcalmswag.blogspot.com/2018/08/1_28.html, https://taeminator1.tistory.com/51, https://clansim.tistory.com/73
댓글