Chapter 3 Lossless Data Compression

 

 

* 데이터 압축의 두 갈래 Lossy와 Lossless

 - Lossy : 손실을 허용하기에 압축률 높다. / mp3

 - Lossless : 무손실 그러나 압축률 낮다. 정보 손실이 없기에 text 압축 유용 / FLAC

 

* 엔트로피와 코딩 기초

 - 정보의 측정

=> 확률이 낮을수록 정보량(비트수) 많다. P(X)와 I(X) 반비례

 

 - 엔트로피

= Average amount of information to the possible outcomes in certain event

 = Minimum average codeword length to encode each symbol

 = 각각의 문자를 인코딩하는데 드는 평균 비트수! 작을수록 효율적임

 = Lossless 를 할 때 entropy 계산해서 효과성을 따져본다.

 = symbol message를 encode(데이터압축) 할 때 가장 작은 정보량을 계산할 때 유용하다.

 = 각각의 심볼을 바이너리로 표현한 것을 코드워드라 한다.

  = 심볼이 편향된 경우, equal일 때와 비교해 entropy 값이 낮아진다. 엔트로피가 낮아지면 압축률을 높일 수 있으므로 Data Compression ratio가 증가한다는 것을 말한다. 즉, 엔트로피는 효율성을 말하고 최대 압축률을 제공할 수 있다.

 

 

* Entropy coding

1) RLE (Run Length Encoding)

 

2) Shannon-Fano Coding

 : 수평으로 sorting

 

 example)

 

3) Huffman Coding

 : 더 자주 일어나는 심볼에 적은 비트수를 할당한다.

 : 수직으로 sorting

 

 example)

 

 

* Dictionary based coding

1) LZ77 coding

 : widely used ZIP, text compression / 텍스트 압축 시 자주 사용됨

 - o : 꺽쇠 포함 몇문자 전으로 가야하는지

 - l : 숫자로 표시할 문자의 길이

 

 

2) LZW coding