Huffman Coding

 문자를 인코딩할 때, 고정된 길이로 압축하는 것보다 가변길이를 선택하는 것이 좋다. 많이 등장하는 문자는 짧게, 적게 등장하는 문자는 길게 인코딩하면 압축률이 좋아질 것이다. 하지만 가변길이를 선택할 경우, 디코딩 할 때, 문제가 없도록 인코딩 규칙을 짜야된다. 즉, 어떤 인코딩된 코드도 다른 인코딩된 코드의 prefix가 되면 안된다. 

1. Huffman Encoding

huffman coding은 가장 작은 frequency의 문자들을 합쳐가면서 이진트리를 만드는 방식이다. huffman coding 방식에 따르면 가장 압축률이 좋은 인코딩 방식을 얻을 수 있다. 수학적 귀납법에 의해 증명이 가능하다.

Proof)

 

2. Run Length Encoding

AAABBAA => 3A2B2A 로 인코딩된다.

긴 run이 올 때 효율적이며, 특히 이미지 데이터 압축에 많이 활용된다고 한다.

 

3. Huffman with run-length encoding

Huffman과 run length encoding이 합쳐진 방식이다. 즉, AAA 그리고 AA가 서로 다르게 인코딩 되어진다.

위 방식을 사용하기 위해, 파일을 두 번 읽어야되는데, 한 번은 run들을 찾기 위함이고, 다른 한 번은 encoding하기 위함이다.

a. CodeWord 부여하기

인코딩을 3bit로 한다고 해도, 메모리에는 제한된 길이로 저장이 된다. 다른 말로 하자면, 2bit나 3bit로 인코딩 되어도 메모리에는 8bit로 저장이 되는 것이다. 따라서 각 인코딩 문자의 codelength를 저장할 필요가 있다. 

b. CodeWord 검색

인코딩된 문자를 검색하기 위해, 이진 트리는 효율적이지 못하다. 따라서, 같은 문자로 구성된 Run들은 연결리스트를 활용해서 구현한다.