압축알고리즘

압축알고리즘에는 대표적으로 두가지 방법론이 존재한다.

1. 비손실 압축 : 원래의 정보를 그대로 보존해야 하기 때문에 손실압축보다 압축률의 성능에 있어서 불리하다. 원본데이터를 그대로 유지시킬수 있어야 하기때문에 텍스트데이터에 많이 사용된다.
2. 손실 압축 : 일부 사람이 감지할수 없는 고음역대 주파수,  픽셀값에 의도적으로 제거하여 압축률을 크게 높이는 방식이기때문에 사진파일,동영상파일,오디오파일에 많이 사용된다.

이 문서에서는 비손실압축 알고리즘에 초점을 맞추며 Huffman tree with run-length encoding알고리즘기법을 사용하여 압축프로그램을 만든다.

• 앞으로 Huffman tree with run-length encoding알고리즘을 HTRE라고 하겠음.

HTRE의 기반이되는 기술에는 엔트로피 정보이론, 자료구조, 비트연산 등이 있다.

HTRE알고리즘의 핵심은 동일한 비트가 반복되는것에 대해서 특정한 비트(적은비트수)를 부여하고 정보를 기록하고 부호화를 진행 한뒤, 기록된 정보를 바탕으로 어떤 데이터가 최적화되어 특정 비트로 바꼇는지 알아내어 다시 복원하는것이다.

따라서 반복되는 데이터가 많이 등장할수록 성능이 증가하며, 반복되는 데이터가 거의없을경우는 원본파일보다 압축하고나서의 크기가 더 커질수 도있다. 압축하고자 하는 파일의 데이터를 읽었을 때 먼저, 데이터를 분류시키고 분류된 데이터에대하여 비트를부여해야하는데(여기서의 비트를 codeword라고함) 분류량이 너무 많아지면 codeword를 만드는데있어서 codeword의 길이가 굉장히 길어질 수가 있기 때문에 이 부분에서 성능저하가 발생한다. 이러한 codeword를 생성하는 방법때문인데, HTRE알고리즘에서 codeword를 생성하는 방식은 prefix를 앞에두지않기떄문이다

성능을 높이기 위해서는 빈도수가 많은 데이터에 대해서 codeword를 최적화해주는 작업이 필요할 수 있다. 

부호화과정에서는 반드시 유일복호화가 가능해야한다. 예를들어, A라는 문자를 인코딩했는데 어떠한경우에는 123이나오고 어떠한경우에는 456이 나온다면 이에대한 추가적인 알고리즘이 더 필요하며 성능저하를 일으킬 수 있다. HTRE알고리즘은 Huffman tree를 기반으로 codeword를 부여하기때문에 유일복호화할 수 있다. 왜냐하면 prefix를 앞에두지않는 codeword를 생성하기 때문이다. 

샤년의 제 1정리

P는 특정심볼이 나올 확률, 𝒍은 부호(비트)길이이다. 

H(X)는 어떠한 정보에대해서 평균정보량을 뜻한다. 평균정보량이 낮을수록 다음심볼의 불확실성이 줄어들어 다음심볼의 확률예측률을 높여준다.

따라서 부호화과정에서 부호설계의 핵심은 평균정보량이 낮을수록 좋다.

평균부호어길이는 심볼이나올확률 곱하기 심볼데이터의 비트길이이다. 따라서 평균부호어길이가 적어야 압축률을 높일 수 있다. 이것에 대해서는 부호화과정에서 부호설계를 어떻게하느냐에 따라 달려있다.

HTRE알고리즘에서 run들을 분류하는 방법에 대해서 먼저 다룬다.

예를들어 ‘abaacda’라는 문자열이 있을 때, 파일에서 처음부터읽어나가는데 다른바이트가 나오기바로전까지가 하나의 run이 된다.

a, b, aa, c, d, a 로 분류할수 있는데 마지막 a는 앞에서 발견됬기 때문에 다시 run을 생성하는게아니라 a라는 run의 빈도수를 1증가시킨다.

분류를 하기위해서는 허프만트리를 구축해야하는데 허프만트리는 힙구조를 이용해 쉽게 구축할 수 있다. 허프만트리 구축을 하기위해서 먼저 모든 run들을 전부 힙에 삽입한다 이때 힙은 min-heap이어야 하며 힙에서의 데이터삽입,데이터삭제시에 우선순위는 run의 빈도수를 토대로 한다. 따라서 run의 빈도수가 낮을수록 힙의 상위측에 속하게 된다. 이렇게 삽입된 모든run들을 힙에서 두개씩꺼내어 새로운 노드로 합친다. 이때 새로운 노드는 두개의 run을 left, right 자식노드로 갖게하며 빈도수를 2개의 run의 빈도수의 합산한 결과로 넣는다. 이런식으로 구축하게되면 빈도수가 많은 run에대해서 빈도수가 적은 run보다 상대적으로 적은 codeword의 길이를 부여받게되는데, prefix규칙에 의해 codeword가 생성되기 때문에 모든 run들이 그런것만은 아니다. 그래서 추가적으로 빈도수가 많은 run이 상대적으로 긴 codeword를 부여 받았을 때 최적화해주는 알고리즘이 필요할 것 이다.

허프만트리를 구축하는 이유는 codeword를 부여하기 위함이다. 허프만트리를 토대로 codeword를 부여하고 인코딩하고 허프만트리를 토대로 codeword를 부여하고 디코딩한다.

실제로 압축하는 과정에는 파일을 2번 읽어야 한다. 첫번째로 읽을때는 run들을 수집하고 허프만트리를 만들고 codeword를 부여하는과정, 두번째로 읽을때는 첫번째로 읽을때 만든 허프만트리를 바탕으로 인코딩을 하기 위함이다.

[최적화하기]

처음에 압축할 때 run들을 수집하고 허프만트리를 구축하는데 그때 빈도수가 높은 run에 대해서 비트수가 많은 codeword가 부여될 수 도 있다. 그래서 이것을 해결해서 성능을 높이고자, 빈도수가 적고 비트수가 적은 codeword랑 위치를 바꿔서 성능을 높이는 방법으로 해결하였다.

인코딩 과정 : 

1. 처음에 압축할 때 run들을 수집하고 빈도수가 많고 codeword길이가 긴 run들과 빈도수가적고 codeword길이가 적은 run들을 추가수집하여 바로 출력파일(압축이 될)에 정보(run)를 쓴다.
2. 허프만트리를 구축하고 codeword를 부여한다.
3. 비트연산을 통한 인코딩을한다.

디코딩 과정 : 

1. 인코딩할때 쓰여졌던 헤더정보들을 바탕으로 run들을 수집한다.
2. 허프만트리를 구축하고 codeword를 부여한다. 단 이때, codeword들이 바뀌기 전 원래 허프만트리로 구축한뒤에 codeword들이 바뀐 run들에대해서 정보를 overwrite한다.
3. 비트연산을 통한 디코딩을 한다.

압축과정에서 허프만트리를 구축할때부터 run들을 exchange시키면 좋겠지만 이렇게되면 허프만트리가 엉망이되어버린다. 따라서 최적화방법을 생각하기전에 방식대로 허프만트리를 구축하고나서 codeword를 부여한뒤에 빈도수가 많은 run들과 빈도수가적은 run들의 codeword길이를 비교해서 서로를 바궈버리고 인코딩하는게 핵심이다. 단  헤더에는 이러한정보들이 미리 쓰여져야한다.

파일사이즈가 크지않은 파일에대해서 이러한 최적화방법을 적용하면 오히려 사이즈가 커질 수 있다. 왜냐하면 사이즈가 작은 파일들은 사이즈가 큰 파일들보다 상대적으로 적은 run들이 수집될것이고, codeword의 길이도 크게 늘어나지않는다. 그래서 바꿔봣자 크게성능차이가없고 오히려 헤더에 부가적인 정보가 더 쓰여지므로 여기서 성능저하를 일으킬 수 있다.

왼쪽<최적화 알고리즘적용(2개의 run에대해서만) > 오른쪽<최적화 알고리즘 적용 전>

왼쪽<최적화 알고리즘적용(복수개의 run에대해서) > 오른쪽<2개의 run에대해서만>

 

<최적화 알고리즘적용(복수개의 run에대해서) > 

전체적인 구현 화면들

<전체적인 결과화면>

<프로그램 첫 실행화면>  

<압축하고자하는 파일을 드래그 했을 때>

 

<압축과정 1> 

<압축과정 2>

<압축된 파일 해제과정1>  

   <압축된 파일해제 과정2>