11. Data Compression

1. Introduction

Date compression을 통해 우리는 정보를 손실없이 유지하면서 저장공간과 데이터 전송시 시간을 줄일 수 있다.

많은 파일들은 redundancy를 가지고 있고, 이를 제거하는 것이 data compression의 핵심이다.

Moore's law에 의해 우리는 이전보다 더욱 많은 저장공간과 빠른 속도를 가지게 되었지만, 그만큼 더 많은 데이터들이 생산되고 있다. 따라서, data compression이 여전히 매우 중요하다.

파일 압축, 이미지 압축, 커뮤니케이션 등 여러가지 영역에서 data compression이 응용되고 있다.

Data compression과정은, bitstream B를 compress하여 C(B)를 만들고, 다시 expand하여 original bitstream B로 복원하는 작업을 말한다. Compression ratio란, 압축후bit / 압축전bit 이다.

수학공식이나 모스부호 같은 것들도 일련의 data compression으로 볼 수 있다.

파일의 압축을 위해서는 먼저 파일의 실제 binary data를 읽어야 한다. 우리는 표준입출력을 사용할 수 있다.

BinaryStdIn의 API는 다음과 같다.

boolean readBoolean() //1bit 읽어서 true/false return

char readChar() //8bit 읽어서 character return

char readChar(int r) //r bit 읽어서 character return, r bit 문자 인코딩일 경우 사용

boolean isEmpty() //읽을 bitstream이 더 이상 없는지 확인

void close() //bitstream 읽기를 끝냄

BinaryStdOut의 API는 다음과 같다.

void write(boolean b) //1bit 쓰기

void write(char c) //문자에 대응하는 8bit 쓰기

void write(char c, int r) //문자에 대응하는 rbit 쓰기

void close() //bitstream 쓰기를 끝냄

예를 들어, int month = 12일 때, BinaryStdOut.write(month) 로 쓸 수 있지만, 1년은 12달까지밖에 없으므로 4bit로 표현가능하다. 따라서 BinaryStdOut.write(12, 4)로 하는 것이 더 낫다

참고로, 모든 bitsting을 압축할 수 있는 Universal data compression 알고리즘은 존재하지 않는다.

그게 가능하다면, 모든 bitstring은 압축을 반복하여 최종적으로 0bit가 될 수 있다.

Random bitstream이 존재할 때, 이것을 압축한다는 것은 Random generator 프로그램을 찾아내 압축하는 것과 같으므로 매우 어려운 문제이다.

2. Run-length coding

Run-length encoding은 실제 상황에서 bitstream은 0이 연속적으로 길게 나오고, 1이 연속적으로 길게 나오는 것들이 반복되는 경우가 많다는 것에 기반한다. 예를 들어, bitstream이 0000001111000 일 경우, 연속으로 나오는 bit가 6, 4, 3 개이므로 fixed length 3bit로 연속bit갯수를 counting하여 인코딩하면 110 100 011로 encoding할 수 있다. 이 경우 compression ratio = 8=9/13 이다.일반적으로, 최대 count = 256으로 설정하여 fixed length 8bit encoding을 한다.

3. Huffman compression

Huffman compression은 1) 데이터에서 각 문자가 나오는 횟수들을 통계를 내고, 그것을 기반으로 character의 code를 결정한다. 2) input stream을 읽으면서 해당 code로 encoding한다. 이 때, code의 길이는 variable-length이고 각 code의 prefix는 다른 code와 겹치지 않으므로 순차적으로 읽었는데, 고유하게 구분된다.

1번과정을 보자.

encoding되는 character의 code는 어떻게 결정될까? 그것은 binary trie를 생성함으로서 해결된다.

예를 들어서, 특정 파일에서 character frequency가 A는 5번, B는 2번, C는 1번, D는 1번, R은 2번 !는 1번 나왔다고 해보자.

가장 적은 횟수로 나오는 2개를 선택하면 C, !이다. parent node P1을 만든 후, C, !를 children node로 설정한다. P1의 frequency는 children node들의 frequency를 더한 값인 2가 된다.

가장 적은 횟수로 나오는 2개를 선택하면 D, P1이다. parent node P2를 만든 후, D, P1를 children node로 설정한다. Frequcney값은 1 + 2 = 3 이다.

가장 적은 횟수로 나오는 2개를 선택하면, R, B이다. parent node P3를 만든 후, R, B 를 children node로 설정한다. Frequency값은 2 + 2 = 4 이다.

가장 적은 횟수로 나오는 2개를 선택하면, P2, P3이다. parent node P4를 만든 후, P2, P3 를 children node로 설정한다.

Frequency값은 3 + 4 = 7 이다.

가장 적은 횟수로 나오는 2개를 선택하면, A, P4이다. parent node P5를 만든 후, A, P4를 children node로 설정한다.

Frequency값은 5 + 7 = 12 이다.

더 이상 진행할 것이 없으므로, binary trie의 construction을 종료한다. 결과는 아래와 같다.

출처 : coursera, Princeton University Algorithm part2 lecture

character은 모두 leaf node에만 존재하고, code는 root로부터 path이다. frequency를 추적하는 이유는 더 많은 빈도로 나타나는 문자를 더 적은 수의 bit로 encoding함으로서 최대한으로 압축을 하기 위함이다.

코드는 각각 0, 100, 1010, 1011, 110, 111 이므로 각 코드의 prefix는 다른 코드와 겹치지 않는다.

가장 적은 횟수로 나오는 문자의 선택은 Minimum Prioity Queue를 유지시킴으로 구현가능하다.

2번과정을 보자.

먼저, compression을 해보자.우리는 생성된 trie를 기반으로 symbol table을 생성할 수 있다.

예를 들어, input stream이 AB! 라고 하면, symbol table에 의해 A는 0 B는 111 C는 1011이다.

Encoding하면 01111011이다. 원본이 8bit ASCII라고 가정할 경우 compression ratio = 8/24 이다.

expansion의 경우 trie를 이용해 bitstream 순서대로 검색하면 쉽게 구할 수 있다.

만약 compression, expand 하는 장소가 서로 다르다고 해보자. 우리는 expand를 위해 trie를 전달해야하는 문제가 있다 .

우리는 bitstream으로 trie를 전달할 수 있다. trie를 preorder traversal하여 bitstream으로 변환할 수 있다(writeTrie(Node x))

위의 trie의 경우, 01010000010010100010001000010101.... (파란색글씨는 각각 A, D, !를 나타낸다)와 같은 방식으로 쓸 수 있다. expand하는 쪽에서는 해당 bitstream을 전달받아 다시 trie를 생성한다(readTrie())

그렇다면, 이것이 정말 최고의 prefix-free code인가?

Shannon-Fano code라는 것이 있다.

이것은 각 character이 나타나는 빈도수를 조사하고, character들을 동일한(또는 가장 유사한) 빈도수 합를 갖도록 두 집합 S0, S1으로 나눈다. 그리고 S0에는 첫번째 bit에 0을, S1에는 첫번째 bit에 1을 할당한다. 그리고 이러한 부분집합으로 나누어 code bit를 할당하는 과정을 recursive하게 계속 반복하여 모든 character에 대해 code를 할당한다.

하지만, 이것은 optimal한 방법이 아니다. 적어도 Huffman coding은 각각의 character를 encoding하는데 있어서는 optimal하다.

Huffman coding의 실행시간은 frequency 조사와, trie의 construction에 걸리는 시간 RlogR (R은 조사된 문자 종류 갯수)과 인코딩할 input을 하나하나 보면서 encoding하는데 걸리는 시간 N (N은 input stream size)을 더한 N + RlogR 이다.

3. LZW compression

Encoding model에는 여러가지가 있는데, 하나는 모든 텍스트를 고정 길이로 인코딩하는 ASCII, Morse code와 같은 Static model이 있다. 다른 하나는, Huffman code와 같은 특정 텍스트를 기반으로 model을 생성하여 인코딩하는 Dynamic model 이다. 마지막으로 특정 텍스트를 읽으면서 지속적으로 model을 학습시키며 업데이트 시켜서 그것을 기반으로 인코딩하는 Adaptive model이 있다. LZW compression의 encoding model은 Adaptive model에 해당한다.

인코딩 방법은 다음과 같다.

ABRACADABRABRABRA를 인코딩해보자.

ASCII에서 A는 Hex value로 41이다. B는 42, C는 43, D는 44, R은 52이다.

이러한 문자는 이미 symbol table에 지정되어있고, value 80까지는 할당되어있다고 생각해보자.

Symbol table에서 input의 longest prefix를 찾는다.

AB는 없고 A가 longest prefix이므로 41로 인코딩하고 AB = 81로 Symbol table에 추가한다.