LZW Compression

이번 포스팅에서는 LZW 압축 알고리즘에 대해 알아보려고 한다. LZW 알고리즘은 Lempel-Ziv-Welch(사람 이름)*의 약자로 무손실 압축 알고리즘이다.

* Lempel-Ziv가 만든 LZ78 알고리즘을 개선한 것이다.

이 LZW 압축 알고리즘은 단순해서 GIF, TIFF와 같은 파일에 주로 사용되지만 Unix에서 단순 파일을 압축하는 용도로도 많이 사용된다.

그럼 본격적으로 LZW에 대해 살펴보기 전에 간단한 핵심 아이디어를 살펴보면 데이터 공간을 절약하기 위해 패턴을 만들어서 재사용한다. 사실 압축 알고리즘이 패턴을 사용하는 것은 일반적이긴 한데 어떻게 패턴을 만들어서 사용하는지 아래에서 더 자세히 살펴보도록 하자.

일반적으로 ASCII 코드는 각 문자를 8비트로 나타낸다. 때문에 최대 표현할 수 있는 문자*는 256개이다. (0~255까지) 그런데 LZW 알고리즘은 ASCII 코드가 표현할 수 있는 비트를 9비트에서 12비트까지 확장한다. 때문에 총 4096개중 기본 문자 256개를 제외하고 3840개를 추가적으로 사용한다.

이 추가적인 부분에 들어가는 것은 한 번 이상 나온 문자의 결합 (Combinations of symbols) 값이 들어간다.

다시 말해서 LZW는 문자를 순서대로 읽으면서 문자열로 그룹화하고, 그룹화한 문자열을 코드로 변환한다. 즉 그룹화된 문자가 코드가 되는 것이다.

위에서 언급한 것처럼 LZW 알고리즘은 간단하다. 의사 코드를 보면 쉽게 이해 할 수 있다.

* PSEUDOCODE 1 Initialize table with single character strings 2 P = first input character 3 WHILE not end of input stream 4 C = next input character 5 IF P + C is in the string table 6 P = P + C 7 ELSE 8 output the code for P 9 add P + C to the string table 10 P = C 11 END WHILE 12 output code for P

소개하고 있는 의사 코드는 LZW 알고리즘에 의해 확장된 공간 안에 중복되는 문자의 합을 넣기 위해 테이블을 만드는 과정이다. (사실 테이블만 만들면 압축 및 해제는 쉽기 때문에.) 그래서 P를 첫 번째 문자 , C를 다음 문자로 선언하고 테이블에서 P + C 값이 있는지 확인한다. 있으면 테이블의 값을 사용해서 P + C의 테이블 값이 없을 때까지 계속 진행한다. 이렇듯 문자열의 끝까지 진행하여 테이블을 만들고 압축을 하는 것이다.

(http://people.cs.pitt.edu/~kirk/cs1501/assignments/lzw/lzw.cxx C++로 만들어진 코드는 해당 URL을 참조하면 된다.)

그럼 지금까지 알아본 의사 코드를 바탕으로 예시를 들어보자.

LZW 알고리즘을 사용해서 BABAABAAA 문자열을 압축한다고 해보자.

그림 1. LZW Compression Algorithm

그림 1을 차근차근 따라가보면 쉽게 알 수 있다. 문자열에서 가장 처음 문자부터 하나씩 검사하고 없으면 확장된 공간인 256부터 채워나간다. 그래서 마지막 스텝을 보면 260 까지 즉, 5개가 새로 채워지고 이 중 3개가 중복으로 사용되었다는 것을 알 수 있다. (왼쪽에 3개가 재사용되었기 때문에)

그 결과로 BABAABAAA를 압축하면 [66, 65, 256, 257, 65, 260]과 같이 길이 9의 문자열이 길이 6으로 변환되었다는 것을 확인 할 수 있다. (압축률 33.3%)

그렇다면 이번에는 반대로 압축 해제하는 방법에 대해 알아보자.

*    PSEUDOCODE
1    Initialize table with single character strings
2    OLD = first input code
3    output translation of OLD
4    WHILE not end of input stream
5        NEW = next input code
6        IF NEW is not in the string table
7               S = translation of OLD
8               S = S + C
9        ELSE
10              S = translation of NEW
11       output S
12       C = first character of S
13       OLD + C to the string table
14       OLD = NEW
15   END WHILE

압축하는 방법처럼 압축 해제 하는 의사 코드를 확인해보면, 순서대로 문자 코드를 검사하면서 테이블을 만들어 나간다. (압축할 때는 없을 때만 했는데 비해 압축 해체 할 때는 매번 테이블을 만들어 나간다.) 이 의사 코드를 바탕으로 위에서 했던 압축을 해제하는 예시를 보면 아래와 같다.