고정 길이 코드(fixed length code)
모든 코드의 길이가 똑같은 값을 갖는 코드 체계
예) ascii가 대표적이고 이는 8비트 길이를 갖는다
다루기 쉽다는 장점이 있으나 저장 공간 활용에 단점이 있다
따라서 위의 반대 개념인 가변 길이 코드(variable length code)는 저장 공간의 절약을 위한 것이다
하지만 VLC가 저장공간의 효율을 선택함에 따라 데이터의 처리가 상당히 번거로워진다
접두어 코드(prefix code)
VLC의 한 종류로 무접두어 코드(prefix free code)라고도 불린다
접두어 속성(prefix property) : 코드 집합의 어느 코드도 다른 코드의 접두어가 되지 않는 속성을 가지는 코드이다
예를 들어, 코드 집합 {"0","1","01","010"}은 접두어 코드가 아니다
"0"이 "01"과 "010"의 접두어가 될 수 있기 때문이다
반면, {"00", "010", "100", "101"}은 어느 코드도 다른 코드의 접두어가 되지 않아 접두어 코드이다
a = 00
b = 010
c = 100
d = 101
위 코드 대로라면 'abcd'는 00010100101로 표현한다
아스키 코드로 한다면 8비트가 4개 있으므로 32비트가 필요하지만 접두어 코드로 표현하면 11비트만 필요하다
1. 허프만 트리 만들기
기호의 빈도는 길이가 짧은 접두어 코드를 빈도가 높은 기호에 부여하기 위해 사용한다
빈도가 높은 기호에 작은 접두어 코드를 부여하면 그만큼 저장 공간을 아낄 수 있다
예를 들어 어떤 문자열이 'a'기호 20개와 'b' 기호 5개로 구성되었을 때
'a'코드에 100을 'b'에 코드 11을 부여한다면 변환덴 데이터의 크기는 3*20+2*5=70비트이다
원본 문자열이 8*25=200비트였으니 원본 크기 대비 35% 압축된다
이때 'a'에 11, 'b'에 100을 부여한다면 2*20+3*5=55비트가 된다
이진 트리는 접두어 코드를 표현하는데 사용한다
트리에서 왼쪽 자식 노드는 0, 오른쪽 자식 노드는 1이다
트리에서 모든 기호는 리프 노드에만 기록되어 있고, 루트 노드에서 리프 노드까지 가는 경로가 기호의 접두어 코드가 된다
빈도가 높은 기호일수록 경로를 짧게 빈도가 낮은 기호일수록 경로를 길게 해야 압축률이 높아진다
압축 예제
abcacbcdcbcacdcacddd 문자열을 압축해 보자(총 글자수 20개, 20byte)
각 문자당 중복되는 갯수를 샌다
a - 4, b - 3, c - 8, d - 5
가장 작은 두 값을 골라낸다
a - 4, b - 3
↓
[7]
│
┌───┐
[a:4] [b:3]
다시 가장 작은 두 값을 골라낸다
a+b - 7, d : 5
↓
[12]
│
┌───┐
[7] [d:5]
│
┌───┐
[a:4] [b:3]
또 고른다
a+b+d - 12, c - 8
↓
[20]
│
┌───┐
[12] [c:8]
│
┌───┐
[7] [d:5]
│
┌───┐
[a:4] [b:3]
이제 트리가 완성되었다
각 트리의 가지(edge)에, 왼쪽 가지에는 0, 오른쪽 가지에는 1을 부여합니다.
[20]
│
0┌───┐1
[12] [c:8]
│
0┌───┐1
[7] [d:5]
│
0┌───┐1
[a:4] [b:3]
상위 노드부터 순차적으로 훑어내린다
a = 000
b = 001
c = 1
d = 01
이제 아까 문자열을 압축해보자
abcacbcdcbcacdcacddd
=> 000001100010011011001100010110001010101
총 47bit = 5byte 7bit이다
20byte였던 문자열이 1/4로 줄어들었다
압축 해제 예제
[20]
│
0┌───┐1
[12] [c:8]
│
0┌───┐1
[7] [d:5]
│
0┌───┐1
[a:4] [b:3]
000001100010011011001100010110001010101
압축된 문자열에서 0이면 왼쪽으로, 1이면 오른쪽으로 검색한다
[20]
↓ │
0┌───┐1
[12] [c:8]
↓ │
0┌───┐1
[7] [d:5]
↓ │
0┌───┐1
[a:4] [b:3]
압축된 문자열의 첫 글자는 'a' 라는 걸 알 수 있다
그 다음 문자는 'b' 이다
출처 blog.naver.com/PostView.nhn?blogId=whwo161&logNo=221065253075
댓글