Algorithm 8 – Data Compression, Huffman, LZW

Coursera 에서 제공하는 Princeton 대학교의 Algorithm 수업인 Algorithm Part 1 의 8 번째 수업입니다.

Data Compression

주된 이유는 전송 시간과 저장 공간을 절약하기 위해서다. 무어의 법칙이 말해주듯이 제품의 성능은 점점 좋아지는데, 그럼에도 불구하고 사람들이 만들어 내는 데이터의 양은 더 급격히 증가한다. 그래서 압축이 필요하다.

이번시간에 배울 기법은 3 가지다.

  • Run-length
  • Huffman
  • LZW

data compression 응용은

  • generic file compression

GZIP 같은 파일 압축이나, PKZIP 같은 아키이빙. 그리고 파일시스템에서도 압축을 할 수 있다.

  • multimedia, communication, database

GIF, MP3, V.42 bis model(?) 등 다양한 곳에 압축을 활용한다고 한다.

 

(http://www.programering.com)

강의에서 사용하는 용어를 좀 정리하고 가자. 바이너리 B 에 대해 compression, 압축 C(B) 를 하고 expansion, 복원(?) 를 해서 B 를 얻는다. 중요한점은 loseless 여야 한다는 것.

compression ratioC(B) / B 로 정의한다. natural language 의 경우 50~75% 이상의 압축이 가능하다고 한다.

Binary Stream

구현에 사용할 바이너리 스트림 API 를 보자. 코드는 BinaryStdIn.java BinaryStdOut.java 에서 구할 수 있다.

public class BinaryStdIn {
    boolean readBoolean() {} //read 1 bit and return as a boolean
    char readChar() {} //read 8 bits and return as a char
    char readChar(int r) {} //read r bitsand return as a char
    [similar methods for byte (8 bits); short (16 bits); int (32 bits); long and double (64 bits)]
    boolean isEmpty() {} //is the bitstream empty?
    void close() {} //close the bitstream
}

public class BinaryStdOut {
    void write(boolean b) {} //write the specified bit
    void write(char c) {} //write the specified 8-bit char
    void write(char c, int r) {} //write the r least significant bits of the specified char
    [similar methods for byte (8 bits); short (16 bits); int (32 bits); long and double (64 bits)]
    void close() {} //close the bitstream
}

찾아보니까 자바에서 기본적으로 제공되는건 ByteArrayStream 이 있더라.

Data Representation

12/31/1999 를 표시하는 법을 생각해 보자.

(1) char8 bit 10개니까 80 bit

(2) int32 bit 3개니까 96 bit

(3) bit 단위를 지정할 수 있다면 4 + 5 + 12 + 3(align) = 24 bit

month = 12
day = 31
year = 199

BinaryStdOut.write(month, 4)
BinaryStdOut.write(day, 5)
BinaryStdOut.write(year, 12)

이는 데이터 표현만 잘 해도 알고리즘 없이 상당부분 압축할 수 있다는 소리다. 일레로 1990년도에 만들어졌던 유전자 데이터베이스는 아스키로 AGCT 를 표현했다고 한다. 4종류의 문자밖에 없으니까 2 bit 로 표현 가능함에도 불구하고

Universal Data Compression

No algorithm can compress every bitstring

contraction 을 이용해 증명하면

  • 모든 비트스트림을 압축할 수 있는 알고리즘 U 가 있다 하자.
  • 주어진 비트스트링 b0 을 압축해서 더 작은 사이즈의 b1 을 얻고
  • 이 과정을 반복하면 사이즈가 0 이 될때까지 압축이 가능하다. 이건 말이 안된다.
  • 따라서 모든 비트스트림을 압축할 수 있는 알고리즘 U 는 없다.

Run-Length Encoding

0000000000000001111111000000011111111111 의 비트가 있을때 n-bit0 또는 1runs (긴 나열을 말하는 듯함) 을 표시한다.

예를 들어 위의 데이터를 4비트 카운트를 이용해 표시하면

bin  1111 0111 0111 1011
dec    15    7    7   11

만약에 run 의 길이가 지정된 n-bit 로 표시할 수 있는 수보다 크면 0 부터 다시 세면 된다. JPEG, ITU-T T4 Group 3 등에 응용한다고 함.

구현은

// http://algs4.cs.princeton.edu/55compression/RunLength.java.html
public class RunLength {

  private final static int R = 256; // max run-length count
  private final static int lgR = 8; // # of bits per count
  
  public static void compress() {
    int run = 0;
    boolean old = false;
    
    while (!BinaryStdIn.isEmpty()) {
      boolean current = BinaryStdIn.readBoolean();
      
      // alternate bit
      if (current != old) {
        BinaryStdOut.write(run, lgR);
        run = 1;
        old = !old;
      }
      // same bit
      else {
        // max count
        if (run == R - 1) {
          BinaryStdOut.write(run, lgR);
          // print dummy alternate bit whose length is 0
          run = 0;
          BinaryStdOut.write(run, lgR); 
        }
        
        run++;
      }
    }
    
    BinaryStdOut.write(run, lgR);
    BinaryStdOut.close();
  }
  
  public static void expand() {
    boolean bit = false;
    
    while (!BinaryStdIn.isEmpty()) {
      int run = BinaryStdIn.readInt(lgR); // read lgR bit
      
      for (int i = 0; i < run; i ++)
        BinaryStdOut.write(bit);
      
      bit = !bit;
    }
    
    BinaryStdOut.close();
  }
}

테스틀 어찌해야하는가

 

(http://help.adobe.com)

bitmap 을 압축하는데 run-length 를 사용하면 효과적이다. 글자에서 대부분의 비트가 0 (흰색) 이기 때문이다.

흑백 그림을 예로 들어보자. 인치당 300 픽셀이고, 사이즈가 8.5 x 11 인치라 했을때, 한 이미지를 표시하기 위해 필요한 비트는 300 * 8.5 * 300 * 11 = 8.415 백만 비트가 필요하다.

Huffman Encoding

fixed-length code 말고 모스코드같은 variable-length code 를 생각해 보자.

모스코드에서 * * * - - - * * * 는 여러 방법으로 해석될 수 있다. SOS, V7, IAMIE, EEWNI 모두 가능하다. 모호한것이다. 모스부호에서는 이 문제를 해결하기 위해 글자마다 갭을 두어, 올바르게 해석될 수 있도록 한다.

인코딩에서 ambiguity 를 해결하려면 어떤 codeword 도 다른 code wordprefix 가 되지 않도록 해야 한다.

  • Fixed-length code
  • Append special stop char to each codeword (e.g 모스)
  • Prefix-free code

이 중에서 prefix-free 인 코드를 만드는법을 살펴보자. binary trie 를 만들어 leaf 에 문자를 놓고, 그 문자까지 도달하는 경로가 인코딩 값이다.

(http://www.programering.com)

compression 을 위해 심볼테이블을 만들거나, 아니면 leaf 부터 따라 올라가고, 그 path 를 뒤집어 출력할 수 있다.

expansion 은 루트부터 시작해서 path 를 따라 내려가다가 leaf 에서 만나는 문자를 출력하면 된다.

한가지 생각해 볼 것은, 빈도가 많은 문자를 짧은 인코딩 값(path) 를 가지도록 해야 압축률이 높아진다는 것이다. 이를 위해 각 문자의 frequency 를 이용해야 한다.

허프만 코드 API를 보면

public class Huffman {

    // support extended ASCII
    private static final int R = 256;
    
    private static class Node implements Comparable {

        private char ch;
        private int  freq;
        private final Node left, right;
    
        public Node(char ch, int freq, Node left, Node right) {
            this.ch = ch;
            this.freq = freq;
            this.left = left;
            this.right = right;
        }
    
        public boolean isLeaf() {
            return left == null && right == null;
        }

        @Override
        public int compareTo(Node that) {
            return this.freq - that.freq;
        }
    }
    
    public static void compress()
    public static void expand()
    private static Node buildTrie(int[] freq)
    private static void writeTrie(Node x)
    private static void buildCode(String[] st, Node x, String s)
    private static Node readTrie()
}

이제 expansion 을 구현하자. 스트림의 가장 첫 부분에, 몇 개의 문자인지를 int 로 표시하는 규약을 정하면

public void expand() {
  Node root = readTrie(); // read in encoding trie
  int N = BinaryStdIn.readInt(); // read in # of chars
  
  for (int i = 0; i < N; i++) {
    Node x = root;
    while (!x.isLeaf()) {
      if (!BinaryStdIn.readBoolean())
        x = x.left;  // 0
      else
        x = x.right; // 1
    }
    
    BinaryStdOut.write(x.ch, 8); // print char
  }
  
  BinaryStdOut.close();
}

running timeN 에 비례한다.

expansion 하는 쪽에서도 trie 를 가지고 있어야한다. trie 를 전송하기 위해 writeTrie 함수를 만들어 보자. triepreorder 로 순회하면서 leaf 의 경우 1 과 문자 값을, internal node 의 경우 0 을 출력한다.

private static void writeTrie(Node x) {
  if (x.isLeaf()) {
    BinaryStdOut.write(true); // leaf
    BinaryStdOut.write(x.ch, 8);
    return;
  }
  
  BinaryStdOut.write(false);
  writeTrie(x.left);
  writeTrie(x.right);
}

이러면 비트스트림으로 온 trie 를 해석하는 함수 readTrie 를 만들자. 마찬가지로 pre-order 로 읽는다.

private static Node readTrie() {
  // leaf
  if (BinaryStdIn.readBoolean()) {
    char c = BinaryStdIn.readChar(8);
    return new Node(c, 0, null, null);
  }
  
  Node l = readTrie(); 
  Node r = readTrie();
  return new Node('\0', 0, l, r);
}

Shannon-Fano algorithm

어떻게 가장 최적(압축률이 높은) prefix-free code 를 만들까? Shannon-Fano 알고리즘을 이용하면

  • symbol Sfreq 으 합이 최대한 같은 두 집단으로 나눈다 S0, S1
  • S00 부터 시작하고, S11 부터 시작하도록 codeword 를 만든다
  • 위 두 단계를 반복한다.

근데 이 알고리즘은 보면 알겠지만, 최적이 아니다. 이는 freq 값이 {5, 1}, {2, 1, 2, 1} 처럼 구성될 수 있기 때문이다.

Huffman algorithm

허프만 알고리즘은 최적의 prefix-free code 를 만들기 위해

  • 각 문자를 이용해 single node trie 를 만든다.
  • freq 값이 가장 작은 두개를 골라 합치고, internal node 에 값을 누적
  • 반복한다

(http://lcm.csa.iisc.ernet.in/dsa)

이 과정에서 가장 낮은 frequency 를 갖는 문자가 아래로 가는 것을 보장하기 때문에 최적의 prefix-free code 를 찾는다 말할 수 있다. (좀 더 자세한 증명은 책을 보라고 함)

구현은

// construct huffman encoding trie 
private static Node buildTree(int[] freq) {
    PriorityQueue pq = new PriorityQueue();
        
    for (char c = 0; c  0)
            pq.add(new Node(c, freq[c], null, null));
        
    // if only one char
    if (pq.size() == 1) {
        if (freq['\0'] == 0) pq.add(new Node('\0', 0, null, null));
        else                 pq.add(new Node('\1', 0, null, null));
    }
        
    // merge two tries
    while (pq.size() > 1) {
        Node l = pq.remove();
        Node r = pq.remove();
        Node p = new Node('\0', l.freq + r.freq, l, r); // parent
        pq.add(p);
    }
    
    return pq.remove();
}

Compression

구현은

public static void compress() {
    String s = BinaryStdIn.readString(); // input
    char[] input = s.toCharArray();
    
    // tabulate freq counts
    int[] freq = new int[R];
    for (int i = 0; i < R; i++)
        freq[input[i]]++;
    
    // build huffman trie
    Node root = buildTrie(freq);
    
    // build syombol table
    String[] st = new String[R];
    buildCode(st, root, "");
    
    // print trie for decoder
    writeTrie(root);
    
    // print N (# of input)
    BinaryStdOut.write(input.length);
    
    // encode
    for (int i = 0; i < input.length; i++) {
        String code = st[input[i]];
        
        // traverse huffman trie
        for (int j = 0; j < code.length(); i++) {
            if (code.charAt(j) == '0')
                BinaryStdOut.write(false);
            else if (code.charAt(j) == '1')
                BinaryStdOut.write(true);
            else throw new IllegalStateException("Illegal State");
        }
    }
    
    BinaryStdOut.close();
}

private static void buildCode(String[] st, Node x, String s) {
    if (!x.isLeaf()) {
        buildCode(st, x.left, s + '0');
        buildCode(st, x.right, s + '1');
    } else {
        st[x.ch] = s; 
    }
}

전체 코드는 Huffman.java

Huffman Summary

정리하면

  • tabulate char frequencies and build trie
  • encode file by traversing trie or lookup table

러닝타임은 바이너리 힙을 이용할 경우(우선순위 큐) N + RlogR 이다. 여기서 R 은 알파벳 사이즈. N 은 입력 문자의 수다.

N 은 입력 문자를 인코딩 하는데, R logRR 개의 문자에 대해 freq 값을 이용해 trie 를 만드는데 걸리는 시간

LZW Compression

Lempel-Ziv-Welch 의 약자다. 세 분이 만드신듯

알고리즘을 보기 전에 데이터 압축 모델에 대해 좀 생각해보자.

(1) 빠르고, 범용적이지만 최적은 아닌 static model (e.g ASCII)
(2) 모델을 매번 생성하고, 전송해야하지만 최적인 Dynamic model (e.g Huffman)

이 둘을 섞은 adaptive model 도 있다. 즉 매 텍스트마다 모델을 업그레이드 해 나가는 것이다. 머신러닝?!

Progressively learn and upate model as you read text

  • More accurate modeling produces better compression
  • Decoding must start from beginning

LZW compression 이 그 예다. LZW 압축 알고리즘은 모델을 읽으면서 만들기 때문에, 전송할 필요가 없다.

텍스트를 읽다가 codeword table 에 이미 존재하면, 문자를 더 읽어 테이블에 없을 경우에만 추가한다. 그림으로 보면

  • Create ST associating W-bit codewords with string keys
  • Initialize ST with codewords for single-char keys
  • Find longest string s in ST that is a prefix of unscanned part of input
  • Write the W-bit codeword associated with s
  • Add s + c to ST where c is next char in the input

LZW compression 에선 longest string matching 이 필요하므로 trie 를 이용할 수 있다.

(http://www.programering.com)

LZW Implementation

자세한 코드는 LZW.java 여기로. 그리고 메모리 사용량을 줄이기 위해 ternary search trie 를 이용한다. TST.java

// ref: http://algs4.cs.princeton.edu/55compression/LZW.java.html
private static final int R = 256;  // # of input chars
private static final int L = 4096; // # of codewords = 2^W
private static final int W = 12;   // codeword width

public static void compress() {
  String input = BinaryStdIn.readString();
  
  // codewords for single chars
  TST tst = new TST();
  for(int i = 0; i  0) {
    String s = tst.longestPrefixOf(input);
    BinaryStdOut.write(s, W);
    
    int t = s.length();
    if (t < input.length() && code < L)
      st.put(input.substring(0, t + 1), code++)
    
    input = input.substring(t);
  }
  
  BinaryStdOut.write(R, W); // write "stop" codeword
  BinaryStdOut.close();
}

expansion 은 테이블에서 codeword 를 읽어가면서 테이블을 만들면 된다. 심볼이 아니라 값으로 검색하므로 2^W 길이의 array 만 있으면 된다.

tricky case 가 있는데

compression 은 같은데 expansion 이 좀 복잡하다. 41 42 81 83 80 에서 83 을 해석할때, 테이블에 있어야 해석을 하는데 없으므로 막혀버린다.

이 경우를 잘 보면 83 을 해석해야 하고, 현재 테이블에 82 까지의 심볼만 존재한다. 그리고 방금 전 까지 읽은건 81 이다. 83ABA 인데, 이건 81 의 심볼을 val 이라 하면 val + val.charAt(0) 과 동일하다.

구현은

public static void expand() {
    String[] st = new String[L];
    int i; // next available codeword value
    
    for (i = 0; i < R; i++) 
        st[i] = "" + (char) i;
    
    st[i++] = ""; // termination codeword
    
    int codeword = BinaryStdIn.readInt(W);
    if (codeword == R) return; // if empty message
    String val = st[codeword];
    
    while(true) {
        BinaryStdOut.write(val);
        
        codeword = BinaryStdIn.readInt(W);
        if (codeword == R) break;
        
        String s = st[codeword];
        
        // tricky case
        if (codeword == i) s = val + val.charAt(0);
        // add string into table
        if (i < L) st[i++] = val + s.charAt(0);
        
        val = s;
    }
    
    BinaryStdOut.close();
}

해석할때 val 은 지난단계의 해석, s 는 현재 읽은 값의 해석이라 생각하면 쉽다.

Lossless Data Compression

LZW 같은 경우 특허가 있었는데, 2003년에 만료되었다고 한다. 이 알고리즘의 많은 변형이 있는데, LZ77 은 특허가 없어서 오픈소스에 많이 쓰인다고 함. deflate zlibLZ77Huffman 을 섞여 쓰는 대표적인 압축 알고리즘

bit / char 를 기준으로 보면 아스키는 7, 허프만은 4.7 정도의 성능을 보여준다. 1995년에는 Burrows-Wheeler 알고리즘이 발명되었는데 2.29 정도까지 압축한다. 1999년에는 RK 알고리즘이 1.89 까지 압축에 성공함.

Summary

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

lossy compression 의 경우 FFT, 프랙탈 등 수학적 도구를 이용해 만드 알고리즘들이 많다.

그리고 압축의 이론적 한계는 shanon entropy 에 의해

Reference

(1) Algorithms: Part 2 by Robert Sedgewick

(2) http://introcs.cs.princeton.edu

(3) The NSA and Encryption

(4) Data Compression Lecture Note

(5) Huffman Algorithm

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.