[Algorithm Part 2] 10. Data Compression

데이터 압축은 파일의 크기를 줄임으로써, 저장 공간이 작아질 뿐만, 전송 시간이 빨라지는 효과를 줄 수 있다.

이번 글에서는, lossless compression(=무손실 압축)만 다룰 것이다.

즉, 데이터 손실 없이 데이터를 압축하는 방법에 대해서만 살펴볼 것이다.

(데이터 압축 평가 시, 입축 비율(compression rate)일 사용할 것이다.)

---

Universal data compression

모든 bitstring를 압축해주는 알고리즘은 존재하지 않는다.

Proof (by 귀류)

모든 1000-bitstring을 압축해주는 알고리즘이 있다고 가정하자.

그럼 $2^{1000}$개 bitstring을 최소 999 bits로 압축해야 한다.

하지만 999 bits는 $2^{999}$개만 존재한다.

$2^{1000} > 2^{999}$개이기에, 위 가정은 모순이다.

Undecidability

모든 파일의 통용되는 최적화 압축 방법은 존재하지 않는다.

즉, 각 파일마다 서로 다른 최적화 알고리즘이 존재한다.

---

1. Run-length coding

단순 중복이 있는 bitstream을 압축하는 방법이다.

bitstream은 0과 1이 교차로(번갈아) 나타나는 stream이다.

 

run-length coding은 bitstream이 교차할 때마다,

교차 이전 연속적으로 나타난 bit 개수를 통해, 데이터를 압축 한다.

• 0 bit에서 1 bit으로 교차했을 경우, 교차 이전 연속적으로 나타난 0 bit의 개수를 계산한다.
• 1 bit에서 0 bit으로 교차했을 경우, 교차 이전 연속적으로 나타난 1 bit의 개수를 계산한다.

이때, 일반적으로 8-bits를 사용해 개수를 표현한다. 즉, 최대 255개까지 표현할 수 있다.

만약 개수가 255개를 넘어섰을 경우, 이후 8-bits를 0으로 처리한 후, 넘어선 개수를 표현한다.

---

2. Huffman compression

huffman compreesion은 빈도수가 높은 문자는 적은 bits로 압축하고, 빈도수가 낮은 문자는 많은 bits로 압축한다.

대표적인 예가 morse code다. 하지만, morse code에는 문제점이 있다.

여러 가지 방법으로 decode될 수 있다는 점이다. 즉, decode 방식이 unique하지 않다는 것이다.

다시 말해, non-prefix code이라는 뜻이다.

이 문제를 해결하기 위해선, prefix code로 수정해야 한다.

• non-prefix code: 임의의 codeword가 다른 codeword의 접두사로 포함되는 경우
• prefix code: 모든 codeword가 다른 codeword의 접두사로 포함되지 않는 경우

huffman code는 수많은 prefix code들 중 corpus를 가장 작게 압축할 수 있는 prefix code를 의미한다.

---

Make prefix code

prefix code는 이진 trie로 표현할 수 있다.

이때, 모든 leaf node에만 char를 할당한다.

codeword는 root node부터 char node(=leaf node)까지의 경로(left=0, right=1)를 의미한다.

Compression

1. 이진 trie의 경로(root → leaf)로 압축한다. 
2. codeword를 저장한 ST로 압축한다.

Expansion

이진 trie의 경로(leaf to root)로 푼다.

How to transmit Trie

• Trie to Bits: preorder로 trie를 순회하면서,
  • leaf node를 방문할 경우, write 1-bit + codeword 
  • non-leaf node를 방문할 경우, write 0-bit
• Bits to Trie: bits를 통해, trie를 재구성한다. (생략)

---

Huffman code

• corpus를 기반으로, 각 character의 빈도수를 계산한다.
• 각 character를 root로 두는 trie를 만든다.
• trie가 하나가 될 때까지 다음 과정을 반복한다.
  • weight가 가장 낮은 2개 tries(A, B)를 선택한다. (by Priority Queue)
  • A, B를 하나의 trie(=C)로 합친다. 이때, C's weight는 A's weight + B's weight이다.

 

위 알고리즘을 적용하면 optimal prefix code가 만들어진다.

증명은 생략하겠다.

---

3.LZW

LZW 장점은 code model을 transmit하지 않아도 된다는 점이다.

Compression

1. string을 key, codeword를 value로 하는 symbol table 생성한다.
   이때, codeword는 W-bits로 고정한다.
2. 모든 단일 문자(single-char) key를 ST에 추가해 초기화한다.
3. ST에서 다음 조건을 만족하는 가장 긴 key(string) s를 찾는다. (s는 text 미탐색 부분의 접두사다.)
4. s의 value(codeword)를 사용해 s를 압축한다.
5. s + c를 ST에 추가한다. (이때, c는 text 미탐색 부분의 첫 문자다.)
6. 미탐색 부분을 압축한다. (by 재귀 3 ~ 5)

Trie로, code table(=ST)를 표현한다.

각 node는 char과 codeword가 저장되어 있으며,

해당 codeword의 key는 경로(root → current)노드들의 char로 알 수 있다.

Expansion

1. codeword을 key, string를 value로 하는 ST를 생성한다.
2. 모든 단일 문자(single-char) value를 ST에 추가해 초기화한다.
3. W-bits(=codeword)로 value(=string) $s_i$를 찾아 decode한다. (W-bits는 압축파일의 W-bits 접두사다.)
4. $s_{i-1}$ + ($s_i$의 첫문자)를 ST에 추가한다.
5. 미탐색 부분을 decode한다. (by 재귀 3 ~ 4)

크기가 $2^W$인 배열을 통해, code table(=ST)를 표현한다.

 

decode 알고리즘을 보면 알겠지만,

decode할 때 만들어 내는 code table은 encode할 때 만드는 code table보다 한 단계 느리다.

때문에, decode시 까다로운 경우(codeword가 code table에 없는 경우)가 생긴다. 

위 예시를 포함한 details(e.g., ST이 꽉찬 경우)는 생략하겠다. ㅜㅜ

---

statistical methods

1. static model: 모든 text에 같은 모델 적용 (e.g., ASCII, Morse code)
2. dynamic model: text 기반으로 모델 생성 (e.g., Huffman code)
3. adaptive model: text를 읽으면서, 모델을 학습 및 update한다. (e.g., LZW)

---

Summary

lossless compression

• represent fixed-length symbols with variable-length codes: Huffman code
• represent variable-length symbols with fixed-length codes: LZW

위에서 본 알고리즘처럼, text의 정보를 활용해 text를 압축하는 방법이 가장 실용적이고 효과적인 방법이다.