Case Study : Huffman Coding
Huffman Coding
: 대표적인 데이터 압축 알고리즘의 하나
- 무손실 Lossless : 데이터 손실이 있으면 안 되는 경우에 사용한다.
- 손실 Lossy : 압축률 측에서 효율적이다.
가령 6개의 문자 a,b,c,d,e,f로 이루어진 파일이 있을 때, 문자의 총 개수는 100,000개이고 각 문자의 등장 횟수가 아래와 같을 때
a : 45
b : 13
c : 12
d : 16
e : 9
f : 5
-> 각 문자를 3 비트로 만듬
a : 000
b : 110
c : 010
d : 011
e : 100
f : 101
(45 + 13 + 12 + 16 + 9 + 5) * 3비트 = 300000비트
고정길이 코드를 사용하면 각가의 문자를 표현하기 위해서 3비트가 필요하며, 따라서 파일의 길이는 300,000 비트가 된다.
-> 가변길이 코드를 사용하면
a : 0 1비트 * 45 = 45000비트
b : 101 3비트 * 13 = 39000비트
c : 100 3비트 * 12 = 36000비트
d : 111 3비트 * 16 = 48000비트
e : 1101 4비트 * 9 = 36000비트
f : 1100 4비트 * 5 = 20000비트
위 테이블의 가변길이 코드를 사용하면 224,000비트가 된다.
: 압축 효과가 좋아졌다.
근데 이거를 1비트 2비트만 사용하면 파일 크기는 줄어든다고 생각 할 수 있겠으나
인코딩을 하는 것이 나중에 다시 디코딩이 가능해야 하는데 문제가 있을 수 있다.
이런 규칙 : Prefix Code
Prefix Code
: 어떤 codeword(101, 010 같은 것) 도 다른 codeword의 prefix(접두사)가 되지 않는 코드
(codeword란 하나의 문자에 부여된 이진코드를 말함)
-> 어떤 코드도 다른 코드의 접두사가 될 수 없는 것이다.
0일 경우 어떤 코드도 0 으로 시작 불가
101 일 경우 어떤 코드도 101로 시작 불가
그래서 1101일 경우에는 110이 없고 11010도 없음
: 모호함이 없이 decode가 가능하다.
: prefix code는 하나의 이진트리로 표현이 가능하다.
-> 접두사가 겹치지 않으므로 이진 트리로 만들기 용이하다.
prefix code 인 경우에는 child가 하나씩 있는 것
Huffman Coding
주어진 인코딩할 데이터파일에 대해서 그 데이터파일을 구성하는 각각의 문자들과 문자가 데이터 파일에 등장하는 횟수가 주어졌을 때, 그 데이터파일을 인코딩하기 위해서 우리가 만들 수 있는 prefix 중에서 최종적으로 압축되는 데이터파일의 길이가 최소가 될 수 있도록 인코딩하는 옵티말한 코딩
-> prefix 코드를 사용해서 인코딩을 한다면 huffman coding 보다 더 짧게 압축 할 수는 없다고 증명된 코딩
파일이 서로 다른 5개의 문자로 구성되었다면 prefix code는 문자 자체랑은 상관 없이 동작한다.
Run-Length Encoding
무손실 압축 기법
런(run)은 동일한 문자가 하나 혹은 그 이상 연속해서 나오는 것을 의미한다.
예를 들어 스트링 s = "aaabba"는 다음과 같은 3개의 run으로 구성된다.
aaa bb a
run-length encoding에서는 각각의 run을 그 run을 구성하는 문자 와
run의 길이 의 순서쌍 (n, ch)로 인코딩한다.
여기서 ch가 문자이고 n은 길이이다.
가령 위의 문자열 s는 다음과 같이 코딩돤다. 3a2b1a.
run-length encoding 은 길이가 긴 run 들이 많은 경우에 효과적이다. (그림 등 - jpeg)
jpeg도 한가지 단일 알고리즘으로 단독 사용 하지는 않고 그 중 한 단계로 알고리즘을 삽입한다.
댓글
댓글 쓰기