22.03.16 png 압축 알고리즘

LZ77 & 허프만 부호화를 포함한 압축 알고리즘인 DEFLATE를 사용한다. 

빈도수를 파악해 자주 나타날수록 더 적은 비용으로 압축한다. 

 

LZ77 알고리즘 

Dictionary 방식의 압축 알고리즘 

현재 압축하려는 데이터가 이전에 존재했는지 파악하여 반복 여부를 표시한다. 

부호화 도중에 새로 나타나는 심볼열을 dictionary에 기록하고 다음 부호화에 사용하는 형태이다. 

 

반복되는 데이터를 기록한 LZ77 방식과 그렇지 않은 COD 방식의 메모리 할당 차이는 아래 그림과 같다.

진한 파란색 영역은 메모리를 거의 차지하지 않고 빨간색은 많은 메모리를 차지한다. 

허프만 부호화 

엔트로피 부호화로 데이터 문자가 얼마나 자주 출현하는지 빈도를 파악해 빈도수가 높은 기호에 짧은 접두어 코드를 부여한다. 

 

예를 들어, 

aaabbaabcd 라는 문자열이 있을 때

가장 많이 쓰인 것은 a => 5번, b => 3번 , c => 1번, d => 1번

이 순서대로 짧은 코드를 부여한다. 

a = 0, b = 01, c = 011, d = 111

그리고 다음과 같이 나타낼 수 있다. 

00001010001011111

 

압축 전 문자열은 80비트지만 부호화 후 17비트로 21% 압축된다. 

 

참고문서링크 

https://compress-or-die.com/Understanding-PNG

Finally understanding PNG