간단한 파일 압축의 원리

* 압축의 종류

손실 압축

> 데이터 압축 과정에서 원본 데이터 손실

 

비손실 압축

> 압축 이후에도 원본 데이터 유지

 

 

---

 

그 중 비손실 압축의 종류

1 ) Run-Length Encoding (RLE)

> 예를 들어, AAAABBBBCCCDEEEE란 데이터가 있다면

00000111111111100000011.. 처럼 0과 1로 변환될 것이다

이것을 0 5 1 10 0 6 1 2.. (처음 0이 개, 1이 10개...) 처럼 데이터 크기를 더  줄일 수 있다.

이것을 또 0과 1을 없애서 5 10 6 2로 줄일 수 있다. 무손실이기 때문에 원본으로 복구도 가능하다

 

2 ) 허프만 부호화

> 모든 글자 탐색 후 점수 부여

aaabbc라는 글자를 보면 a가 3개, b가 2개, c가 1개이다. 이때 가장 빈도수가 높은 a에 0을 할당,

b에 10을 할당, c에 11을 할당해서 0 0 0 10 10 11 로 48bit 데이터가 9bit로 변환하는 것이다.

 

3 ) LZ - (LZ 77, 78)

>1977년 발표

> 허프만 부호화는 모든 글자를 한번 읽어야 하지만 LZ는 러닝타임에 무언가를 함

> 단어에게도 큰 의미 부여

ABBCBCABABCAABCAAB 라는 데이터가 있다고 하자

A라는 글자를 보고 사전을 만들면서 비교대조를 한다 A를 사전을 보고 비슷한 단어가 있는지를 보는데,

없으면 0을 주고 사전에 1번으로 저장한다. 그 다음 B를 보면 겹치는 글자가 없어서 역시 0을 주고 사전에 2번으로 저장한다. 다음 BC를 보면 저장된 2번의 B와 가장 유사하고 B가 저장되어있으니 C에 2를 준다. 이런식으로 만들면서 비교대조를 하는 방식이다. 그 결과 (0, A), (0, B), ( 2, C), (3,A), (2, A), (4,A), (6,B)가 완성된다.

 

 

그 중, LZ 77 의 압축기법도 여러갈래로 나뉘는데, 그 종류 중 DEFLATE라는 압축 방법이 있다.

이 방식은 LZ 77로 나온 결과를 다시 허프만으로 덧입힌 방법이다. .ZIP이나 .winZIP, .zlip, .gzip + 에 쓰인다.

 

이 3가지 비손실 압축 기법에 대해 알아보았는데, 대부분 이 압축 기법을 이용한다고 한다.

 

 

 

 

 

 

소스 참조

https://www.youtube.com/watch?v=v63h5e5wWwc