개발 공부 - [Huffman Coding] 압축 (Compression) - 1

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도 한가지 단일 알고리즘으로 단독 사용 하지는 않고 그 중 한 단계로 알고리즘을 삽입한다.