http://www.cs.fit.edu/~mmahoney/compression/text.html


http://www.maximumcompression.com/data/summary_mf.php



quicklz - very simple and fast algorithm

출처 : http://hansicgu.hemosu.com

0. 손실, 비손실 압축


 손실 압축과 비손실 압축이라는 단어를 한번쯤을 들어보았을 것이다. 손실 압축은 말 그대로 원본의 데이터를 압축한 후 이 압축을 풀었을 때의 데이터가 원본 데이터와는 100% 동일하지 않은 압축을 말한다. 그림이나 동영상, 음성 데이터 등은 원본과 100% 같지 않아도 데이터를 사용하는 것이 가능하므로 약간의 손실을 갖지만 높은 압축율을 갖는 손실 압축을 주로 사용하게 된다. 그에 반해 TEXT 데이터나 GBA에서 사용되는 폰트 데이터 등 약간의 손실로도 원본 데이터를 알아보는데 지장이 생긴다면 압축을 하지 않으니만 못할 것이다. 따라서 이 경우에는 압축율이 다소 낮지만 원본의 데이터가 100% 복원되는 비손실 압축이 주로 사용된다. 손실 압축과 비손실 압축의 구분은 본 강좌에서 그다지 큰 영향을 갖지는 않으나 앞으로 소개할 알고리즘이 비손실 알고리즘이라는 사실은 기본적으로 알아두시길.



1. RLE(Run Length Encoding)란?


 만약 33 33 33 33 33 33 33 이라는 데이터가 존재한다면 어떻게 압축을 하면 될까?
대부분의 사람들이 33이 7개 연속으로 존재한다고 저장하면 되지 않겠는가 하는 생각을 할 것이다.
이런 기본적인 concept으로부터 시작하는 압축 알고리즘이 RLE방식이다.
RLE방식은 한 문자(한 byte)가 몇 번 반복되는지를 저장하는 방식이다. 따라서 RLE방식은 같은 문자가 여러번 반복되는 데이터에 대해 효율적인 압축방법이 되리란 것을 쉽게 예상할 수 있을 것이다. 텍스트의 경우 여러번 반복되는 데이터가 존재하기 힘드므로 텍스트를 RLE로 압축할 경우 효율이 낮고 오히려 압축데이터의 크기가 더 커지는 경우가 허다하다. 게임을 시작할 때의 로고를 생각해보자. 대부분 검은 바탕이나 단색바탕에 로고 자체도 매우 단순하여 타일전체가 단색인 경우가 많다. 따라서 이런 그림의 경우에 RLE방식으로 압축하는 게 효율적일때가 많다.



2. 어떻게 압축하면 될까?


 0x33이라는 문자가 7번 반복된다는 사실을 어떻게 저장하면 될까.
반복되는 문자 뒤에 반복회수를 적어준다면 33 07 형태가 되는데 이 방법에는 약간의 문제가 있다.
만약 01 02 03 04 형태의 데이터가 존재한다면 01 01 02 01 03 01 04 01 로 저장해야 되는데 이 경우 데이터가 2배로 늘어나게 되므로 "압축"의 의미와는 다소 거리가 멀게 된다.

 그렇다면 반복되는 문자가 존재할 때만 "반복이 시작된다"의 의미를 갖는 문자가 나타나게 한다면 0x01 0x02 0x03 0x04는 그대로 01 02 03 04 로 저장하면 될 것이다. 편의상 이 문자를 < 로 표현하도록 하겠다. 주의할 점은 반복이 시작됨을 알리는 구분자(separator)가 '<'가 아닐수도 있다는 점이다.
구분자는 알고리즘을 구현하는 사람 맘대로 결정하는 것이 가능하다.

 그럼 이 구분자 < 로 RLE방식으로 압축해 보도록 하자. 주어진 데이터는 다음과 같다.

   33 33 33 33 33 33 33 11 11 11 22 33 22

33이 7번 반복되고 11 이 3번, 22 33 22 는 반복되는 문자가 없다는 것을 알 수 있다.
그러면 이를 압축할 경우

   < 33 07 < 11 03 22 33 22

의 형태로 압축이 되는 것이다.  33의 경우 7개의 바이트가 단지 3바이트만으로 표현되므로 50% 이상 압축되었다.  그러나 11의 경우 3바이트를 압축하여 3바이트가 되었으므로 압축하지 않는 것과 그 크기가 같으므로 압축의 의미를 갖지 못하게 된다. 따라서 이 방식으로 압축할 경우 4바이트 이상 반복되는 문자가 출현할 경우 압축을 시도하면 될 것이다.

 그런데 이 방식으로 저장할 경우 구분자와 같은 문자가 출현할 경우 압축 데이터가 판별하기 모호해지게 된다. 구분자로 < 를 사용하는데 데이터 중 < 라는 데이터가 존재할 경우 위의 방식을 그대로 적용하면

   < < 33 33    =>(압축)=>   < < 33 33

과 같이 저장되게 된다. 그렇다면 이를 역으로 압축을 해제할 경우 제대로 압축이 해제 될리가 없다.
구분자 < 가 출현했으니 그 다음 바이트 < 가 33번 반복된다는 의미를 갖는다고도 볼 수 있으므로 원래의 데이터와는 달라져버린다. 따라서 구분자로 사용되는 문자가 출현할 경우에는 별도의 압축 방법을 생각해야 한다.

 이 경우 구분자가 문자로 출현할 경우 구분자를 한번 더 써주는 방식을 택하면 된다.
위의 데이터를 압축한다면

   < < < < 33 33

 이 되는데 < 뒤에 <가 존재할 경우 <를 그대로 저장하는 것이므로 이 방식으로 압축을 해제할 경우

   < < 33 33

 으로 원하는 결과를 얻을 수 있게 된다. 이 방법은 위에서와 마찬가지로 구분자가 두배의 용량이 된다는 단점이 있으므로 전체 데이터에서 출현 빈도수가 낮은 문자를 구분자로 사용하면 가능한한 효율을 높일 수 있게 된다.
 여기서 설명한 방식은 RLE방식의 한가지 방법일 뿐이다. 압축알고리즘이 워낙 간단한데가 구현이 간단해 수많은 압축형식이 있을 수 있다. 따라서 앞의 설명은 RLE가 뭐다 라는 정도의 설명이라고만 생각해도 충분하다.



3. GBA에서의 구현방식


 GBA에서는 압축데이터 앞에 4 바이트의 헤더가 존재한다. 이 4 byte를 뒤에서부터 읽어들인다.
왜 뒤에서부터 읽는가에 대한 내용은 빅 엔디언, 리틀 엔디언의 차이이므로 관심이 있는 사람은 이에 대해 찾아보면 금방 이해할 수 있을 것이다.  어쨌든 이 4 byte의 정보가 압축 데이터에 대한 내용을 담고 있다.

  30 00 0e 00 .. .. .. .. ..

 이라면 4byte를 뒤에서부터 읽을 경우 00 0e 00 30 이 된다. 이 때 맨 뒤의 바이트는 압축방법에 대한 정보를 담고 있고 앞의 세 바이트는 압축을 풀었을 때의 크기를 담고 있다.
 맨 뒤의 바이트가 30 인 것은 이 데이터가 RLE방식으로 압축되었다는 것을 의미하고 앞의 세 바이트 00 0e 00은 압축을 해제했을 때의 데이터의 크기가 0e 00 즉 0xe00 byte가 된다는 것을 의미한다.

 그 뒤의 데이터는 역시 위에서 설명한 RLE방식으로 압축되어 있으나 GBA에서 사용하는 방식은 약간 다르다. GBA에서는 Flag_byte(앞에서의 구분자 역할) 1 byte 뒤에 Data_byte N byte가 뒤따르는 방식을 사용한다. 이 설명만으로는 정확한 압축 방법을 알기 힘들테니 우선 Flag_byte에 어떤 정보가 담겨 있는지 알아보자.

 Flag_byte는 1 byte이므로 8 bit 인데 MSB는 압축이 되었는가에 대한 정보를 갖고 있고 MSB를 제외한 bit들은 반복횟수를 의미한다.

 Flag_byte : _ _ _ _  _ _ _ _
             ^
             1이면 압축데이터, 0이면 압축되지 않은 데이터

 가 된다. 따라서 압축이 되었는지의 여부는 ( flag_byte & 0x80 ) 으로 알 수 있고 반복 횟수는 ( flag_byte & 0x7f ) 로 알 수 있다.

 우선은 Flag_byte를 읽어 압축이 되었는가, 반복 횟수는 몇번인가 를 알 수 있을 것이다.
압축이 되었을 경우, 즉 Flag_byte가 1일 경우 Flag_byte에 뒤따르는 1 byte의 문자가 반복되게 되는데 이 반복회수는 ( flag_byte & 0x7f ) + 3 이 된다. 즉 80 33 이라면 Flag_byte가 80으로 1000 0000이므로 압축이 되었고 그 뒤의 33이 0+3번, 즉 3번 반복된다는 의미를 갖게 되는 것이다. 따라서 80 33은 압축을 풀면 33 33 33 이 된다.

 압축이 되지 않는 부분에 대해서는 이 반복 횟수의 의미가 다르다.  MSB가 0일 경우 그 뒤의 데이터들이 압축이 되지 않았다는 뜻인데 그 압축되지 않은 데이터의 개수가 ( flag_byte & 0x7f ) + 1 개라는 뜻이다. 따라서 04 01 02 03 04 05 를 압축을 해제하려면 우선 04를 읽어 압축되지 않은 데이터가 5개라는 내용이므로 01 02 03 04 05 가 된다.

 실제로 나리키리2 의 남코 오프닝 부분에 대한 데이터를 이용하여 압축을 해제하는 전체적인 과정을 보도록 하자.

       30 00 0E 00 85 00 81 88 81 11 00 14 80 11 00 14
                   ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^
       80 11 00 14 80 11 00 14 80 11 85 00 81 88 91 11
       ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^
       85 00 81 88 91 11 85 00 07 88 88 A8 00 11 11 21
       ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^
       C7 80 11 00 51 89 11 8D 00 00 0A 80 00 00 B5 80
       ^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^^^^ ^^
       ....

 압축된 데이터의 앞부분 0x40 byte만을 뽑아내어 구분자와 데이터를 group화 한 것이다.
밑줄쳐진 부분은 한 덩어리로 맨 앞이 flag_byte, 그 뒤가 모두 data_byte라고 생각하면 된다.
앞에서의 설명과 같이 00 0E 00 30이므로 RLE로 0xE00만큼의 데이터가 압축되었음을 알 수 있다.
85 00 은 0x00이 8번 반복되었음을 의미하고 81 88은 0x88이 4번 반복됨을 의미한다.
역시 마찬가지로 81 11은 0x11이 4번 반복되는 것이고 00 14의 경우 압축되지 않은 데이터가 1개 존재하는 것이므로 14가 1개가 존재함을 알 수 있다. 위의 압축을 풀면 다음과 같다.

       00 00 00 00 00 00 00 00 88 88 88 88 11 11 11 11
       ^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^ ^^^^^^^^^^^
       14 11 11 11 14 11 11 11 14 11 11 11 14 11 11 11
       ^^ ^^^^^^^^ ^^ ^^^^^^^^ ^^ ^^^^^^^^ ^^ ^^^^^^^^
       00 00 00 00 00 00 00 00 88 88 88 88 11 11 11 11
       ^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^ ^^^^^^^^^^^
       11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11
       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
       ....

 역시 압축할 때 한덩어리가 되는 부분을 group지어 놓았다. 다소 보기 난해한 면은 있으나 쓸 줄 아는 것이라곤 그림판 뿐인데다가 미적 센스는 빵점이니 텍스트가 오히려 나을것이다 -_-;;;
혹시나 저 텍스트를 이쁘게 그려주실 분 계시면 연락바란다 =_=-b



4. 코드를 보여달라고?


 코드는 직접 짜보는 것이 좋다는 것이 지론이긴 하지만 직접 적용하는 과정을 보여주는 것이 더 낫지 않을까 하여 압축을 푸는 부분에 대한 코드만 간략히 소개하도록 한다. 다시 압축하는 코드는 압축 방법을 곰곰히 잘 생각해보면 금방 짤 수 있을 것이다.
 C 코드와 압축 데이터가 저장된 file과 압축을 해제했을 때의 데이터가 저장된 file을 링크하니 압축하는 코드를 만들게 된다면 두 파일들의 내용으로 제대로 동작하는지 확인하면 될 것이다.

다운로드


int RLUnComp(FILE *src, FILE *dst)
{
       long header=0;                // 헤더를 저장한다.
       long len;                // 압축을 해제했을 때의 데이터 크기
       long count=0;                // 압축을 얼마나 해제했는가

       int i;
       int flag_byte;                // flag_byte
       int data_byte;                // data_byte

       for(i=0;i<4;i++) {
               header|=((fgetc(src))<<(8*i));        // 뒤에서부터 4바이트를 읽는다
       }

       if((header&0xff)!=0x30) {
               printf("This is not an RLE data\n");
               return -1;
       }

       printf("This is compressed with RLE\n");

       len=header>>8;                // 뒤의 한 바이트는 잘라낸다

       while(count<len) {
               flag_byte=fgetc(src);                // flag_byte를 읽고
               if(flag_byte&0x80) {                // 압축 데이터라면
                       data_byte=fgetc(src);        // data_byte를 읽어
                       for(i=0;i<(flag_byte&0x7f)+3;i++) {
                               fputc(data_byte,dst);
                               count++;        // (flag_byte&0x7f)+3 만큼 반복한다.
                       }
               }
               else {                                        // 압축되지 않은 데이터라면
                       for(i=0;i<(flag_byte&0x7f)+1;i++) {
                               data_byte=fgetc(src);
                               fputc(data_byte,dst);        // (flag_byte&0x7f)+1 만큼의
                               count++;                // data_byte를 그대로 출력한다.
                       }
               }

       }
       return 0;
}


@. 다음 강좌는 LZ77이 되겠습니다.. 만 아직 데이터를 완벽히 분석한게 아니라 며칠 시간이 걸릴지도 모르겠습니다. RLE는 워낙에 간단해서 분석이 쉬웠는데 LZ77은 아직 알 수 없는 데이터들이 존재하는군요 -.-;;;;

@2. 당근 채찍 아무거나 좋습니다. 리플로 반응을 좀 보여주세요 ioi

출처 : http://hansicgu.hemosu.com

현존하는 최고의 효율을 자랑하는 압축 알고리즘,
Huffman.(참고로 사람 이름-_-;)

요즘 게시판에서도 압축에 관해 말이 많이 일고 있기에,
비록 원론적인 설명이지만 궁금해하시는 분들의 속을 시원스레 뚫어주기 위해서,
이렇게 글을 쓰게 되었습니다.



=====================================================

abcacbcdcbcacdcacddd
라는 문자열을 압축해야 합니다.
총 글자수 20개, 총 20byte입니다.

허프만 압축 알고리즘은 이진트리(binary tree)를 기반으로 합니다.

우선 각 문자당 중복되는 글자수를 세어봅시다.

a : 4
b : 3
c : 8
d : 5

이제 이 값을 가지고 가장 효율적인 트리를 구성해야 합니다.

가장 작은 두 값을 골라냅시다.

a : 4
b : 3

↓

    [7]
     │
┌───┐
[a:4]   [b:3]


다시 가장 작은 두 값을 골라냅시다.

a+b : 7
d : 5

↓

          [12]
           │
     ┌───┐
    [7]        [d:5]
     │
┌───┐
[a:4]   [b:3]


또 골라냅시다.


a+b+d=12
c=8

↓

                 [20]
                  │
            ┌───┐
          [12]        [c:8]
           │
     ┌───┐
    [7]        [d:5]
     │
┌───┐
[a:4]   [b:3]




이제 트리가 완성되었습니다.

각 트리의 가지(edge)에, 왼쪽 가지에는 0, 오른쪽 가지에는 1을 부여합니다.

                 [20]
                  │
           0┌───┐1
          [12]        [c:8]
           │
    0┌───┐1
    [7]        [d:5]
     │
0┌───┐1
[a:4]   [b:3]


상위 노드부터 순차적으로 훑어(-_-)내립니다.


a = 000
b = 001
c = 1
d = 01

이제 되었습니다.
아까의 문자열을 압축합시다.

abcacbcdcbcacdcacddd
=> 000001100010011011001100010110001010101

총 47bit = 5byte 7bit.

20byte였던 문자열이 1/4로 줄어들었습니다!


====================================================


그렇다면 압축을 풀때엔 어떻게 하느냐.

아까의 트리를 다시 불러옵니다.


                 [20]
                  │
           0┌───┐1
          [12]        [c:8]
           │
    0┌───┐1
    [7]        [d:5]
     │
0┌───┐1
[a:4]   [b:3]


000001100010011011001100010110001010101

이것이 압축된 문자열.

0이면 왼쪽으로, 1이면 오른쪽으로 검색해나갑니다.

                 [20]
            ↓    │
           0┌───┐1
          [12]        [c:8]
    ↓     │
    0┌───┐1
    [7]        [d:5]
↓   │
0┌───┐1
[a:4]   [b:3]


압축된 문자열의 첫 글자는 'a' 라는 걸 알 수 있습니다.
그 다음 문자는 'b' 가 되겠죠.

출처 : http://blog.naver.com/ksw7998/100011805897
참고 링크 : http://portal.kisti.re.kr/~report/data/1997/full_text/xml/CE001-X0047/CE001-X0047.xml

< 목   차 >
1 Prologue 3
2 Introduction 4
3 Run-Length 6
3.1 Run-Length 압축 알고리즘 6
3.2 Run-Length 압축 복원 알고리즘 10
3.3 Run-Length 압축 알고리즘 전체 구현 11
4 Lempel-Ziv 19
4.1 Lempel-Ziv 압축 알고리즘 19
4.2 Lempel-Ziv 압축 복원 알고리즘 26
4.3 Sliding Window를 이용한 Lempel-Ziv 알고리즘의 구현 27
5 Variable Length 39
6 Huffman Tree 43
6.1 Huffman 압축 알고리즘 51
6.2 Huffman 압축 복원 알고리즘 56
6.3 Huffman 압축 알고리즘 구현 60
7 JPEG (Joint Photographic Experts Group) 72
7.1 JPEG이란 72
7.2 다른 기술과의 비교 72
7.3 압축 방법 73
7.4 Baseline 압축 알고리즘 75
7.5 JPEG의 실제 압축 / 복원 과정 76
7.6 확장 JPEG 79
8 MPEG (Moving Picture Expert Group) 80
8.1 MPEG의 개념 80
8.2 MPEG의 표준 81
8.2.1 MPEG 1 81
8.2.2 MPEG 2 82
8.2.3 MPEG 4 83
8.3 MPEG의 기본적인 압축 원리 84
8.3.1 시간,공간의 중복성 제거 84
8.3.2 I,P,B영상 86
9 Conclusion 87

< 그 림 목 차 >

<그림 3‑1> Run-Length 압축 알고리즘 10
<그림 3‑2> 압축 파일 헤더 구조 12
<그림 4‑1> 슬라이딩 윈도우와 해시테이블 22
<그림 5‑1> 8비트에서 7비트로 줄이는 압축 알고리즘 39
<그림 5‑2> 문자 코드의 재구성 40
<그림 5‑3> <그림 5‑2>코드의 기수 나무 41
<그림 5‑4> 문자 코드의 재구성 41
<그림 6‑1> 빈도수 계산 44
<그림 6‑2> 허프만 나무 구성과정 48
<그림 6‑3> 허프만 나무에서 얻어진 코드 51
<그림 6‑4> code[]와 len[]의 저장 55
<그림 7‑1> JPEG Encoding / Decoding 단계 76
<그림 7‑2> RGB의 YIQ 변환식 77

1 Prologue
지금 생각하면 우스운 일이지만 몇 년 전만 하더라도 28800bps의 모뎀을 굉장히 빠른 통신 장비로 알고 있었다. 그러다가 56600bps의 모뎀이 발표되었을 때는 전화선의 한계를 뛰어 넘은 대단한 물건이라고 다들 놀라와 했다. 내 경우에도 56600bps 모뎀을 구입해서 처음 사용하던 날 감격의 눈물을 흘렸을 정도였으니..
전화로 통신을 하던 그 당시 사람들의 생각은 다들 비슷했을 것이다. 어떻게 하면 같은 내용의 자료를 더 짧은 시간에 전송할 수 있을까. 통신속도가 점차 빨라지면서(처음에 사용하던 2400bps에 비하면 거의 20배 이상의 속도 향상이었다.) 이런 고민은 줄어들 것이라 생각했지만, 그런 고민은 오히려 더 커져 만 갔다. 속도가 빨라지는 것보다 사람들이 주고받는 자료의 전송 량이 더 크게 증가한 것이다. 이럴 수록 더 강조되던 것이 바로 [압축] 이었다.
파일 압축이라고 하면 winzip, alzip 등을 생각할 것이다. 이런 종류의 프로그램들은 임의의 파일을 원래의 크기보다 작은 크기로 압축시켰다가 필요할 때 다시 원래대로 한치의 오차도 없이 복구 시켜 준다.
하지만 압축이란 것이 모두 앞에서 언급한 프로그램들처럼 원본을 그대로 복원해줄 수 있는 것이 아니다. 때에 따라서는 원본으로의 복원이 불가능한 압축 방법들이 유용하게 사용될 상황도 존재한다.
전자의 경우를 ‘비손실 압축’, 후자의 경우를 ‘손실 압축’ 이라고 하는데, 이 자료에서는 모든 압축의 근간이 되는 간단한 압축 알고리즘들을 살펴볼 것이고 뒤에 손실 압축의 대표적인 MPEG에 대해서 다룰 것이다.
이제 우리는 압축의 세계로 들어간다.

2 Introduction
우리가 보통 살펴보는 알고리즘들은 대부분이 시간을 절약하기 위한 목적을 가지고 개발된 것 들이다. 하지만, 우리가 지금부터 살펴볼 알고리즘들은 공간을 절약하기 위한 목적을 가진 알고리즘이다.
압축알고리즘이 처음으로 대두되기 시작한 것은 컴퓨터 통신 때문이었다. 컴퓨터 통신에서는 시간이 곧바로 돈으로 연결된다(적어도 model을 사용하던 시절에는 그랬다). 예를 들어 1MByte의 파일을 다운로드 받으려면 28,800bps 모뎀을 사용하면 약 6분, 56,600bps 모뎀을 사용하더라도 약 3분 이상의 시간이 소요됐었다. 하지만 이 파일을 전송 전에 미리 1/2로만 압축할 수 있다면 전송시간 역시 1/2로 줄어들 것이다. 즉, 통신 비용 역시 1/2로 줄어든다는 것이다.
압축 알고리즘은 크게 두 부류로 나뉜다. 비손실 압축(Non-lossy Compression)과 손실 압축(Lossy Compression)이 그것인데 말 그대로 비손실 압축은 압축했다가 다시 복원할 때 원래대로 파일이 복구된다는 뜻이고, 손실 압축은 복원할 때 100% 원래대로 복구되지 않는다는 뜻이다.
일반적으로 PC사용자들이 사용하는 압축프로그램들은 모두 비손실 압축을 지원한 프로그램들이다. 그렇다면 손실 압축은 어떤 경우에 사용하는 것일까?
확장자가 exe나 com으로 끝나는 실행파일이나, 기타 한 바이트만 바뀌더라도 프로그램 실행에 지장을 주는 파일들은 반드시 비손실 압축을 해야 한다. 그러나 그림 파일이나 동화상처럼 눈으로 보는 것에 지나지 않는 파일의 경우 약간의 손실이 있어도 무방하다.
일반적으로 손실 압축이 비손실 압축에 비해서 압축률이 훨씬 좋기 때문에 손실 압축도 또한 큰 중요성을 가지고 있다. 요즘 화제가 되고 있는 JPEG(정지 화상 압축 기술, Joint Photographic Expert Group), MPEG(동화상 압축 기술, Moving Picture Expert Group) 등도 대표적인 손실 압축법으로 주목 받고 있는 것들이다.

압축 알고리즘은 그 중요성으로 인해 오랫동안 연구되어 왔고, 많은 알고리즘이 있다. 가장 대표적인 압축 알고리즘은 Run-Length 압축법으로 동일한 바이트가 연속해 있을 경우 이를 그 바이트와 몇 번 반복되는지 수치를 기록하는 방법이다. 그러나 Run-Length 압축법은 간단함에 대한 대가로 압축률이 그다지 좋지 않아서 다른 방법들이 연구되어 왔다.
그래서 실제로 구현되는 압축 방법은 이 절에서 소개하는 Huffman 압축법과 Lempel-Ziv 압축법이다. 가변길이 압축법은 한 바이트가 8비트라는 고정 관념을 깨고, 각각을 다른 비트로 압축하는 방법이고, 그 중에서도 Huffman 압축법은 빈도가 높은 바이트는 적은 비트수로, 빈도가 낮은 바이트는 많은 비트수로 그 표현을 재정의하여 파일을 압축한다.
반면에 Lempel-Ziv법은 그 변종이 여러 개 있지만 가장 효율적인 동적 사전(Dynamic Dictionary)을 이용한 방법을 주로 사용한다. 동적 사전법은 파일에서 출현하는 단어(Word)들을 2진 나무(Binary Tree)나 해시를 이용한 검색 구조에 삽입하여 동적 사전을 구성한 다음, 이어서 읽어진 단어가 동적 사전에 수록되어 있으면 그에 대한 포인터를 그 내용으로 대체하는 방법으로 압축을 행한다. 주로 사용하는 ZIP 등도 Huffman 압축법이나 Lempel-Ziv 압축법 중 하나를 사용하거나 또는 둘 다 사용하거나, 혹은 그 응용을 사용한다.

3 Run-Length
3.1 Run-Length Encoding
Run-Length 압축법은 동일한 문자가 이어서 반복되는 경우 그것을 문자와 개수의 쌍으로 치환하는 방법이다. 예를 들어 다음의 문자열은 Run-Length 압축법으로 쉽게 압축될 수 있다.

원래 문자열 : ABAAAAABCBDDDDDDDABC
압축 문자열 : ABA5BCBD7ABC 

개 념적으로는 위와 같이 간단하지만 개수로 사용된 5나 7이라는 문자가 개수의 의미인지 아니면 그냥 문자인지를 판별하는 방법이 없다. 만일 압축할 파일이 알파벳 문자만을 사용한다면 위와 같은 압축이 그대로 사용 가능할 것이다. 그러나 일반적으로 0부터 255까지의 모든 문자가 사용된 파일을 압축한다면 단순한 위의 방법으로는 압축이 불가능하다.
그래서 탈출 문자(Escape Code)라는 것을 사용한다. 문자가 반복되는 모양을 압축할 때 <탈출 문자, 반복 문자, 개수>와 같이 표현한다. 예를 들어 탈출 문자를 ‘*’라고 한다면 위의 문자열은 다음처럼 압축 될 수 있다.

원래 문자열 : ABAAAAABCBDDDDDDDABC
압축 문자열 : AB*A5BCB*D7ABC 

탈 출 문자에서 탈출의 의미는 보통의 경우에서 벗어남을 말한다. 즉 탈출 문자 ‘*’가 나오기 전에는 단순한 문자열이지만 이 탈출 문자가 나오면 그 다음의 반복 문자와 그 다음의 개수를 읽어 들여서 반복 문자를 개수만큼 늘여 해석하면 된다.
또 한가지 남은 문제가 있다. 그것은 탈출 문자가 탈출의 의미로 해석되는 것이 아니라 문자로서 해석되어야 할 경우도 있다는 점이다. 이것은 마치 printf() 함수의 서식 문자열에서 ‘%’와 유사하다. %d나 %f는 그 문자를 의미하는 것이 아니라 정수나 실수형으로 대치될 부분이라는 표시이다. 즉 %가 탈출의 의미를 가지고 있다는 뜻이다. 그러나 정작 ‘%’라는 문자를 출력하기 위해서는 어떻게 해야 하는가?
C에서는 ‘%’를 출력하기 위해서 ‘%%’를 사용한다. 마찬가지로 Run-Length 압축법에서도 탈출 문자 ‘*’를 문자로 해석하기 위해서 ‘**’를 사용하면 될 것이다.
그렇다면 ‘*’ 문자가 계속해서 반복되는 경우는 어떻게 해야 하는가? 이 문제는 상당히 복잡하다. 만일 ‘*****’와 같은 문자열의 일부분이 있다면 ‘**5’와 같이 압축할 수 있는가? 아니면 ‘***5’와 같이 압축하는가? 둘 다 문제가 있다. 전자의 경우 ‘*5’와 같이 해석할 수 있으며, 후자의 경우는 ‘*’문자와 5 다음의 문자가 있다면 이를 개수로 해석해서 5를 반복하는 것으로 해석할 수 있다.
이렇게 탈출 문자가 반복되는 경우 그것을 <탈출 문자 반복 문자 개수>의 표현으로 나타내면 모호하게 되므로 탈출 문자자의 경우는 아무리 반복 횟수가 많더라도 단순하게 <탈출 문자, 탈출 문자>와 같이 압축한다(실제로는 더 길어지지만).

원래 문자열 : ABCAAAAABCDEBBBBBFG*****ABC
압축 문자열 : ABC*A5BCDE*B5FB**********ABC 

이 러한 이유로 탈출 문자 ‘*’는 가장 출현 빈도수가 적은 문자를 택해야 한다. 왜냐하면 탈출 문자가 문자로 해석되는 경우에는 그 길이가 두 배로 늘어나기 때문이다. 이 출현 빈도수라는 것이 사실 모호하기 짝이 없지만 일단은 영어의 알파벳이나 기호, 탭 문자(0x09), 라인 피드(0x0A), 캐리지 리턴(0x0D) 그리고 널문자(0x00)와 같은 코드들은 매우 많이 사용되기 때문에 피해야 한다. 따라서, 압축하는 파일에 따라 탈출 문자를 적절히 조정해 주면 압축 효율을 높일 수 있을 것이다.
그렇다면 과연 몇 개의 문자가 반복되었을 때 <탈출 문자, 반복 문자, 개수>로 치환할 것인가 하는 문제를 결정하자. ‘AA’처럼 두 문자가 반복되었다면 ‘*A2’로 하는 것은 두 바이트가 3바이트로 늘어나게 되므로 치환하지 말아야 할 것이다. 그렇다면 ‘AAA’와 같이 세 문자가 반복된다면 ‘*A3’으로 하는 것은 똑같이 세 바이트가 소요되므로 치환을 하든 하지 않든 변화가 없다. 따라서 같은 문자가 최소 3번 이상 반복되는 경우에만 치환을 하도록 한다.
그리고 개수를 나타내는 것 또한 1Byte를 사용하기 때문에 반복되는 문자의 개수는 255 이상이 될 수 없다. 만약 255개를 넘어버린다면 254에서 한번 잘라주고, 그 다음은 문자가 처음 나온 것으로 생각하면 된다.
위와 같은 방법으로 구현된 Run-Length 알고리즘은 다음과 같다.

<Run-Length 압축 알고리즘(FILE *src)
{
  char code[10];      /* 버퍼 */
  cur = getc(src);        /* 입력 파일에서 한 바이트 읽음 */
  code_len = length = 0;
 
  while(!feof(src))
  {
       if (length == 0)    /* code[]에 아무 내용이 없으면 */
       {
           if (cur != ESCAPE)
           {
               code[code_len++] = cur;
               length++;
           }
           else        /* 탈출 문자이면 <탈출문자 탈출문자>로 대체 */
           {
               code[code_len++] = ESCAPE;
               code[code_len++] = ESCAPE;
               flush(code);        /* 출력 파일에 써넣음 */
               length = code_len = 0;
           }
          
           cur = getc(src);
       }
       else if (length == 1)   /* 반복 횟수가 1 이었으면 */
       {
           if (cur != code[0])     /* 읽은 문자가 버퍼의 문자와 다르면 */
           {
               flush(code);    /* 버퍼의 내용을 출력 */
               length = code_len = 0;
           }
           else    /* 읽은 문자가 버퍼의 문자와 같으면 */
           {
               length++;
               code[code_len++] = cur;     /* 'A' -> 'AA' */
               cur = getc(src);
           }
       }
       else if (length == 2)       /* 반복 횟수가 2 이면 */
       {
           if (cur != code[1])     /* 읽은 문자가 버퍼의 문자와 다를 경우 */
           {
               flush(code);    /* 버퍼의 내용을 출력 */
               length = code_len = 0;
           }
           else    /* 읽은 문자가 버퍼의 문자와 같으면 */
           {
               length++;
               code_len = 0;
               code[code_len++] = ESCAPE;      /* 'AA' -> '*A3' */
               code[code_len++] = cur;
               code[code_len++] = length;
               cur = getc(src);        /* 다음 문자를 읽음 */
           }
       }
       else if (length > 2)        /* 반복 횟수가 3 이상이면 */
       {
           if (cur != code[1] || length > 254)   
           {       /* 읽은 문자 != 버퍼의 문자 or 반복 횟수 > 255 */
               flush(code);        /* 버퍼의 내용 출력 */
               length = code_len = 0;
           }
           else    /* 읽은 문자가 버퍼의 문자와 같으면 */
           {
               code[code_len-1]++;     /* 반복 횟수만 증가 */
               length++;
               cur = getc(src);        /* 다음 문자를 읽음 */
           }
       }
  }
 
  flush(code);        /* 버퍼의 내용을 출력 */
} 

<그림 3‑1> Run-Length 압축 알고리즘

3.2 Run-Length Decoding
압축을 하고 나면 다시 복원을 하는 알고리즘도 있어야 할 것이다. Run-Length 압축법의 복원은 상당히 단순하다. 파일을 읽으면서 탈출 문자가 없으면 그대로 두면 되고, 탈출 문자를 만난다면, 다음 글자를 하나 더 읽어봐서 다시 탈출 문자가 나오면 탈출 문자를 그대로 기록하고, 숫자가 나오면 탈출 문자 전의 문자를 그 숫자만큼 반복해서 적으면 된다.
위와 같은 방법으로 구현된 Run-Length 압축 복원 알고리즘은 다음과 같다.

<Run-Length 압축 풀기 알고리즘(FILE *src)>
{
  int cur;
  FILE *dst;
  int j;
  int length;
 
  dst = fopen(출력파일);
  cur = getc(src);
  while (!feof(src))
  {
       if (cur != ESCAPE)      /* 탈출 문자가 아니면 */
           putc(cur, dst);
      
       else    /* 탈출 문자이면 */
       {
           cur = getc(src);
           if (cur == ESCAPE)      /* 그 다음 문자도 탈출 문자이면 */
               putc(ESCAPE, dst);
          
           else        /* 길이만큼 반복 */
           {
               length = getc(src);
               for (j = 0; j < length; j++)
                   putc(cur, dst);
              
           }
       }
      
       cur = getc(src);
  }
 
  fclose(dst);
} 

3.3 Run-Length 압축 알고리즘 전체 구현
실제로 압축된 파일의 복원을 위해서는 몇 가지 추가적인 정보가 필요하다. 그것은 복원하려는 파일이 과연 Run-Length 압축 알고리즘에 의한 것인지를 판별하는 식별 코드와 복원할 파일의 원래 이름이다. 이 두 정보는 압축할 때 압축 파일의 선두(헤더)에 기록되어 있어야 한다.
Run-Length 압축 알고리즘의 식별 코드는 편의상 0x11과 0x22로 했고, 이어서 원래 파일의 이름이 나오고, 끝을 나타내는 NULL문자가 이어진다. 다음은 이 헤더의 구조를 나타낸 그림이다.

<그림 3‑2> 압축 파일 헤더 구조

이 상으로 Run-Length 압축 알고리즘에 대한 설명을 마친다. Run-Length 알고리즘은 알고리즘이 단순할 뿐만 아니라 이미지 파일이나 exe 파일처럼 똑같은 문자가 반복되는 경우 매우 좋은 압축률을 보여준다. 그러나 똑같은 문자가 이어져 있지 않은 경우에는 압축률이 매우 떨어지는 단점이 있다.
위와 같은 방법으로 구현된 전체 Run-Length 알고리즘은 다음과 같다.

/*                                                                  */
/*   RUNLEN.C  :  Compression by Run-Length Encoding                */
/*                                                                  */

#include <stdio.h>
#include <string.h>
#include <dir.h>
#include <time.h>
#include <stdlib.h>

/* 탈출 문자 */
#define ESCAPE  0xB4

/* Run-Length 압축법에 의한 것임을 나타내는 식별 코드 */
#define IDENT1  0x11
#define IDENT2  0x22

/* srcname[]에서 파일 이름만 뽑아내어서 그것의 확장자를 rle로 바꿈 */
void make_dstname(char dstname[], char srcname[])
{
  char temp[256];
 
  fnsplit(srcname, temp, temp, dstname, temp);
  strcat(dstname, ".rle");
}

/* 파일의 이름을 받아 그 파일의 길이를 되돌림 */
long file_length(char filename[])
{
  FILE *fp;
  long l;

  if ((fp = fopen(filename, "rb")) == NULL)
       return 0L;

  fseek(fp, 0, SEEK_END);
  l = ftell(fp);
  fclose(fp);
 
  return l;
}

/* code[] 배열의 내용을 출력함 */
void flush(char code[], int len, FILE *fp)
{
  int i;
  for (i = 0; i < len; i++)
  putc(code[i], fp);
}

/* Run-Length 압축 함수 */
void run_length_comp(FILE *src, char *srcname)
{
  int cur;
  int code_len;
  int length;
  unsigned char code[10];
  char dstname[13];
  FILE *dst;

  make_dstname(dstname, srcname);

  if ((dst = fopen(dstname, "wb")) == NULL)   /* 출력 파일 오픈 */
  {
       printf("\n Error : Can't create file.");
       fcloseall();
       exit(1);
  }

  /*  압축 파일의 헤더 작성 */
  putc(IDENT1, dst);      /* 출력 파일에 식별자 삽입 */
  putc(IDENT2, dst);
  fputs(srcname, dst);    /* 출력 파일에 파일 이름 삽입 */
  putc(NULL, dst);        /* NULL 문자 삽입 */

  cur = getc(src);
  code_len = length = 0;

  while (!feof(src))
  {
       if (length == 0)
       {
           if (cur != ESCAPE)
           {
               code[code_len++] = cur;
               length++;
           }
           else
           {
               code[code_len++] = ESCAPE;
               code[code_len++] = ESCAPE;
               flush(code, code_len, dst);
               length = code_len = 0;
           }
          
           cur = getc(src);
       }
       else if (length == 1)
       {
           if (cur != code[0])
           {
               flush(code, code_len, dst);
               length = code_len = 0;
           }
           else
           {
               length++;
               code[code_len++] = cur;
               cur = getc(src);
           }
       }
       else if (length == 2)
       {
           if (cur != code[1])
           {
               flush(code, code_len, dst);
               length = code_len = 0;
           }
           else
           {
               length++;
               code_len = 0;
               code[code_len++] = ESCAPE;
               code[code_len++] = cur;
               code[code_len++] = length;
               cur = getc(src);
           }
       }
       else if (length > 2)
       {
           if (cur != code[1] || length > 254)
           {
               flush(code, code_len, dst);
               length = code_len = 0;
           }
           else
           {
               code[code_len-1]++;
               length++;
               cur = getc(src);
           }
       }
  }

  flush(code, code_len, dst);
  fclose(dst);
}

/* Run-Length 압축을 복원 */
void run_length_decomp(FILE *src)
{
  int cur;
  char srcname[13];
  FILE *dst;
  int i = 0, j;
  int length;

  cur = getc(src);
  if (cur != IDENT1 || getc(src) != IDENT2)   /* Run-Length 압축 파일이 맞는지 확인 */
  {
       printf("\n Error : That file is not Run-Length Encoding file");
       fcloseall();
       exit(1);
  }

  while ((cur = getc(src)) != NULL)       /* 헤더에서 파일 이름을 얻음 */
       srcname[i++] = cur;
 
  srcname[i] = NULL;
  if ((dst = fopen(srcname, "wb")) == NULL)
  {
       printf("\n Error : Disk full? ");
       fcloseall();
       exit(1);
  }

  cur = getc(src);
  while (!feof(src))
  {
       if (cur != ESCAPE)
           putc(cur, dst);
       else
       {
           cur = getc(src);
           if (cur == ESCAPE)
               putc(ESCAPE, dst);
      
           else
           {
               length = getc(src);
               for (j = 0; j < length; j++)
                   putc(cur, dst);
           }
       }
      
       cur = getc(src);
      
  }

  fclose(dst);
}

void main(int argc, char *argv[])
{
  FILE *src;
  long s, d;
  char dstname[13];
  clock_t tstart, tend;

  /* 사용법 출력 */
  if (argc < 3)
  {
       printf("\n Usage : RUNLEN <a or x> <filename>");
       exit(1);
  }

  tstart = clock();       /* 시작 시각 기록 */
 
  s = file_length(argv[2]);   /* 원래 파일의 크기를 구함 */

  if ((src = fopen(argv[2], "rb")) == NULL)
  {
       printf("\n Error : That file does not exist.");
       exit(1);
  }
 
 
  if (strcmp(argv[1], "a") == 0)      /* 압축 */
  {
       run_length_comp(src, argv[2]);
       make_dstname(dstname, argv[2]);
       d = file_length(dstname);       /* 압축 파일의 크기를 구함 */
       printf("\nFile compressed to %d%%", (int)((double)d/s*100.));
  }
  else if (strcmp(argv[1], "x") == 0)     /* 압축의 해제 */
  {
       run_length_decomp(src);
       printf("\nFile decompressed & created.");
  }
 
  fclose(src);
 
 
  tend = clock();     /* 종료 시각 기록 */
  printf("\nTime elapsed %d ticks", tend - tstart);   /* 수행 시간 출력 : 단위 tick */
}
 

3.4 실행 결과


filetype Run-Length   
random-bin 100.59   
random-txt 100.24   
wave 98.20   
pdf 99.03   
text(big) 85.04   
text(small) 98.71   
sql 96.78 

Run-Length 알고리즘의 특성 때문에 Random 파일에 대해서는 오히려 파일 크기가 증가하는 결과가 나타났다. 다른 경우에는 조금씩 압축이 되었으며, 크기가 큰 텍스트 파일에 대해서는 상당히 많은 압축이 되었다. 이것은 텍스트 파일에 들어있는 연속된 Space나 Enter 등을 압축 한 것으로 해석된다. SQL 역시 Space가 많아서 압축이 되었을 것이라 생각한다.

4 Lempel-Ziv
4.1 Lempel-Ziv Encoding
Run-Length 압축 알고리즘도 실제로 많이 사용되지만, 이 절에서 소개하는 Lempel-Ziv 알고리즘 또한 실제에서 가장 많이 사용되는 매우 우수한 압축 알고리즘이다.
Run-Length 알고리즘은 똑같은 문자가 반복되는 경우 그것을 <탈출 문자, 반복 문자, 반복 횟수>로 치환하는 방법이었다. 이와 유사하게 Lempel-Ziv 압축법은 현재의 패턴이 가까운 거리에 존재한다면 그것에 대한 상재적 위치와 그 패턴의 길이를 구해서 <탈출 문자, 상대 위치, 길이>로 패턴을 대치하는 방법이다.

원래 문자열 : ABCDEFGHIJKBCDEFJKLDM
압축 문자열 : ABCDEFGHIJK<10,5>JKLDM 

위 의 그림을 보면, 원래 문자열에서 ‘BCDEF’라는 패턴이 뒤에 다시 반복된다. 이 때 뒤의 패턴을 <10,5>와 같이 10문자 앞에서 5문자를 취하라는 코드를 삽입함으로써 압축할 수 있고, 그 반대로 복원 할 수도 있다.
이렇게 떨어진 두 패턴뿐만 아니라 서로 겹쳐있는 패턴에 대해서도 이런 표현이 가능하다.

원래 문자열 : CDEFABABABABABAJKL
압축 문자열 : CDEFAB<2,9>JKL 
 
원래 문자열 : CDEFAAAAAAAJKL
압축 문자열 : CDEFA<1,7>JKL 

두 번째 예를 보면 Lempel-Ziv 압축법은 Run-Length 압축법과 마찬가지로 동일한 문자의 반복에 대해서도 Run-Length 압축법과 비슷한 압축률을 보임을 알 수 있다. 게다가 첫 번째와 같이 동일한 패턴이 반복되는 경우 Run-Length로는 압축하기 곤란하지만 Lempel-Ziv 압축법에서는 간단하게 압축된다.
이렇게 간단한 원리는 Lempel-Ziv 압축법은 그 실제 구현에서 여러 가지 다양한 방법이 있다. 가장 대표적인 방법은 정적 사전(Static Dictionary)법과 동적 사전(Dynamic Dictionary)법이다.
정적 사전법은 출현될 것으로 예상되는 패턴에 대한 정적 테이블을 미리 만들어 두었다가 그 패턴이 나올 경우 정적 테이블에 대한 참조를 하도록 하여 압축하는 방법이다.
이 방법은 압축하고자 하는 파일의 내용이 예상 가능한 경우에 매우 좋은 방법이다. 예를 들어 C의 소스 파일만을 압축하고자 할 경우 C의 예약어와 출현 빈도가 높은 식별자(Identifier)에 대해 테이블을 미리 만들어 둔다면 매우 높은 효율과 빠른 속도의 압축을 할 수 있을 것이다. 그러나 임의의 파일을 압축하고자 할 때에는 그 효율을 장담하지 못한다.
동적 사전법은 파일을 읽어들이는 과정에서 패턴에 대한 사전을 만든다. 즉 동적 사전법에서 패턴에 대한 참조는 이미 그전에 파일 내에서 출현한 패턴에 한한다. 동적 사전법은 파일을 읽어들이면서 사전을 구성해야 하는 부담이 생기기 때문에 속도가 느리다는 단점이 있으나, 임의의 파일에 대해 압축률이 좋은 경우가 많다.
우리는 정적 사전법은 동적 사전법과 별로 다를 것이 없으므로 동적 사전법만 다루기로 한다.
동적 사전법을 실제로 구현하는데 있어 가장 중요한 자료 구조는 Sliding Window이다. Sliding Window는 전체 파일의 일부분을 FIFO(First In First Out) 구조의 메모리에 유지하고 있는 것을 의미한다. 그리고 이 Sliding Window는 파일에서 문자를 읽을 때마다 파일 내에서의 상대 위치가 끝 쪽으로 전진하게 된다.
그리고 Sliding Window는 윈도우 내의 어떤 부분에 원하는 패턴이 있는지 찾아낼 수 있는 검색 구조까지 갖추고 있어야 한다.

Sliding Window의 FIFO 구조 때문에 가장 적절하게 사용될 수 있는 구조는 원형 큐(Circular Queue)이다. 그리고 Sliding Window의 검색 구조는 주로 해쉬(Hash)나 2진 나무(Binary Tree)를 사용한다.
일반적으로 FIFO 구조(Sliding Window)의 크기는 압축률에 상당한 영향을 미치며, 검색 구조는 압축 속도에 큰 영향을 미친다. 즉 Sliding Window가 크면 동적 사전이 그만큼 더 방대하게 구성되어서 패턴을 찾아낼 확률이 크게 되고, 검색 구조가 효율적일수록 패턴을 빨리 찾아내기 때문이다.
이 자료에서 작성할 Lempel-Ziv 압축법은 원형 큐와 한 문자에 대한 해시(연결법)로 패턴을 찾아낸다.
설명을 위해 다음 그림을 보자

<그림 4‑1> Sliding Window와 해시테이블

<그림 4‑1> (가) 그림은 큐 queue[]의 모양을 보여준다. 큐에는 압축할 파일에서 문자를 하나씩 읽어서 저장해 놓는다. front는 큐의 get() 명령 시 빠져나올 원소의 위치이고, rear는 큐의 put() 명령 시 새 원소가 들어갈 위치를 의미한다. 그리고 cp는 찾고자 하는 패턴이고, sp는 cp위치에 있는 패턴과 일치하는 앞쪽의 패턴 위치를 저장하고 있다. 그리고 length는 일치한 패턴의 길이를 의미하고 (가) 그림에서는 5가 된다.
(나) 그림은 해시 테이블 jump_table[]의 모습이다. jump_table[]은 큐에 있는 문자가 어느 위치에 있는지 바로 찾을 수 있도록 큐에서의 위치들을 연결 리스트로 구성하고 있다. 예를 들어 ‘G’라는 문자를 큐 내에서 찾으려면 선형 검색처럼 처음부터 끝까지 검색해야 하는 것이 아니라, jump_table[‘G’]로서 연결 리스트의 시작 위치를 찾은 다음 연결 리스트를 타고 가면 14의 위치와 9의 위치에 ‘G’라는 문자가 있음을 알 수 있다.
참고로 Lempel-Ziv 압축법에서는 패턴을 <탈출문자 상대위치 패턴길이>로 나타내는데 이 자료에서는 상대 위치와 패턴 길이 모두 1바이트를 사용한다. 즉 상대 위치는 앞으로 255만큼, 패턴의 길이도 255만큼이 가능하다는 이야기다. 패턴을 찾는 장소가 바로 큐이기 때문에 큐의 길이도 255보다 큰 것은 아무 의미가 없다. 이렇게 상대 위치와 패턴의 길이를 몇 비트로 나타낼 것인가에 따라 큐의 크기를 정해 준다.
Sliding Window에서 가장 핵심적인 부분은 원하는 패턴을 찾아내는 함수이다. 이 부분은 다음의 qmatch() 함수에 구현되어 있다. 이 qmatch() 함수는 Lempel-Ziv 압축법에서 압축 시에 가장 많이 호출되고 가장 많이 시간이 소요되는 부분이므로 충분히 최적화되어 있어야 한다.

int qmatch(int length)
  {
  int i;
  jump *t, *p;
  int cp, sp;
  cp = qx(rear - length);     // cp의 설정
  p = jump_table + queue[cp];
  t = p->next;

  while (t != NULL)
       {
       sp = t->index;          // sp의 설정, 해시 테이블에서 바로 읽어온다
       for (i = 1; i < length && queue[qx(sp+i)] == queue[qx(cp+i)]; i++);
       if (i == length) return sp;
                               // 패턴을 찾았으면 sp를 되돌림
       t = t->next;            // 패턴 검색에 실패했으면 다음 위치로 이동
       }
  return FAIL;                // 패턴이 큐 내에 없음
  }
 

qmatch() 함수는 결국 cp와 length로 주어지는 패턴을 큐 내에서 찾아서 그 위치 sp를 되돌려주는 기능을 한다.

<Sliding Window를 이용한 LZ 압축 알고리즘(FILE *src, char *srcname)>
  {
  FILE *dst = 출력파일;
  jump_table[] 초기화;
  init_queue();
  put(getc(src));
  length = 0;
 
  while (!feof(src))
{
       if (queue_full())
    {
       if (sp == front)   /* 현재 추정된 패턴이 큐에서 벗어나려 하면 */
           {                  /* 현재까지의 정보로 출력 파일에 쓴다 */
               if (length > 3)    /* 패턴의 길이가 4 이상이면 압축 */
                   encode(sp, cp, length, dst);
               else               /* 아니면 그냥 씀 */
                   for (i = 0; i < length; i++)
                   {
                       put_jump(queue[qx(cp+i)], qx(cp+i));
                                  /* 다음을 위해 jump_table[]에 문자들의 */
                                  /* 위치를 기록 */
                       putc1(queue[qx(cp+i)], dst);
                   }
               length = 0;
           }
           del_jump(queue[front], front);
                          /* 큐에서 빠져 나온 문자는 jump_table[]에서 제거 */
           get();         /* 큐에서 문자 하나를 뺀다 */
    }
       if (length == 0)
       {
           cp = qx(rear-1);  /* cp의 설정, 가장 최근에 들어온 문자 */
           sp = qmatch(length+1); /* 패턴을 찾아 sp에 줌, 길이는 1 */
           if (sp == FAIL)   /* 패턴 검색에 실패했으면 */
           {
               putc1(queue[cp], dst);  /* 출력 파일에 기록 */
               put_jump(queue[cp], cp);
           }
           else
               length++;
           put(getc(src)); /* 다음 문자를 입력 파일에서 읽어 큐에 집어넣음 */
       }
       else if (length > 0)     /* 패턴의 길이가 1 이상이면 */
    {
           if (queue[qx(cp+length)] != queue[qx(sp+length)])
               j = qmatch(length+1);  /* 새로 들어온 문자까지 포함해서 */
                                      /* 패턴의 위치를 다시 검색 */
           else j = sp;
           if (j == FAIL || length > SIZE - 3)
           {                    /* 실패했으면 현재까지의 정보로 압축을 함 */
               if (length > 3)
               {
                   encode(sp, cp, length, dst);
                   length = 0;
               }
               else
               {
                   for (i = 0; i < length; i++)
                       {
                       put_jump(queue[qx(cp+i)], qx(cp+i));
                       putc1(queue[qx(cp+i)], dst);
                       }
                   length = 0;
               }
           }
           else                  /* 패턴 검색에 성공했으면 */
           {
               sp = j;
               length++;         /* 길이를 1증가 */
               put(getc(src));   /* 큐에 새 문자를 집어넣음 */
           }
    }
  }
                                 /* 큐에 남아있는 문자들을 모두 출력
  if (length > 3) encode(sp, cp, length, dst);
  else
       for (i = 0; i < length; i++)
           putc1(queue[qx(cp+i)], dst);
          
  delete_all_jump();                  /* jump_table[] 소거 */
  fclose(dst);
} 

이 알고리즘을 자세히 살펴보면 알겠지만 그 기본적인 틀은 Run-Length 압축법과 유사함을 알 수 있을 것이다. length 변수가 상태를 표시하고 있음이 특히 그렇다.
그리고 주의할 점은 jump_table[]에 위치를 기록하는 시점이다. 쉽게 생각하면 큐에 입력할 때 집어넣은 것으로 착각할 수 있기 때문이다. jump_tablel[]에 문자의 위치를 집어넣는 정확한 시점은 파일에 그 문자를 출력할 때이다.
그리고 큐 내에 일치하는 패턴이 두 개 이상 있을 때 어느 것이 우선적으로 선택되어야 하는가 하는 문제 또한 중요하다. 이 때 적절한 기준은 cp 쪽에 가까운 패턴을 취하는 것이다. 이렇게 하는 이유는 패턴이 cp에서 멀 경우 패턴의 다음 문자들까지도 일치할 수 있으나 sp의 앞부분이 큐에서 벗어나는 경우가 있기 때문에 압축을 중단해야 하는 경우가 생기기 때문이다.
이러한 점은 put_jump() 함수에서 자연스럽게 구현된다. put_jump() 함수는 항상 최근에 들어온 그 문자의 위치를 가장 앞에 두기 때문에 jump_table[]에서 검색할 때 퇴근에 들어온 문자의 위치가 선택된다.
마지막으로 Run-Length 압축법과 마찬가지로 Lempel-Ziv 압축법에서도 압축 정보의 표시를 위해 탈출 문자(Escape Character)를 사용한다. 그런데 이 탈출 문자가 문자 자체의 의미로 사용될 때 Run-Length에서는 <ESCAPE ESCAPE>쌍을 사용했지만, Lempel_Ziv 법은 <ESCAPE 0x00>쌍을 사용한다.
왜냐하면 탈출 문자가 사용되는 두 가지 용도는 문자 자체를 의미하는 것과 <탈출문자 상대위치 패턴길이> 정보의 시작을 표시하기 위함이다. 그런데 <상대위치>는 항상 0보다 큰 값이어야 하기 때문에(0이면 자기 자신을 의미한다) 압축 정보에서 <ESCAPE 0x00>쌍이 나타날 경우는 없다. 그러므로 충분히 압축 정보와 문자 자체의 의미를 구분할 수 있다.

4.2 Lempel-Ziv Decoding
그렇다면 앞 절의 알고리즘으로 압축된 파일을 원래대로 복원하는 알고리즘을 생각해보자. 복원 알고리즘은 매우 간단하다.
복원 알고리즘의 개요는 입력 파일에서 문자를 차례대로 읽어 큐에 저장하는 것이다. 어느 정도 큐에 넣다 보면 큐가 차게 되는데 이 때 큐에서 빠져 나오는 문자들을 출력 파일에 쓰면 된다. 큐에 집어넣을 때 압축 정보가 들어올 때는 그 의미를 해석하여 다시 원 상태로 만든 다음에 큐에 한꺼번에 집어넣으면 아무 문제가 없다. 이런 알고리즘을 구현하기 위한 가장 핵심적인 함수는 put_byte() 함수이다. put_byte()함수는 매우 짧은 함수인데 인자로 주어진 문자를 큐에 집어넣되 큐가 꽉 차 있으면 출력 파일로 출력하는 기능을 한다. 이렇게 put_byte() 함수가 만들어지면 복원 알고리즘 또한 매우 간단하다.

<Sliding Window를 이용한 LZ압축 복원 알고리즘 (FILE *src)>
{
  FILE *dst = 출력 파일;
  init_queue();
  c = getc(src);
  while (!feof(src))
{
       if (c == ESCAPE)         /* 읽은 문자가 탈출 문자이면 */
       {
           if ((c = getc(src)) == 0) /* 그 다음이 0x00이면 탈출문자 자체 */
               put_byte(ESCAPE, dst);
           else                 /* 아니면 <탈출 문자 상대위치 패턴길이> 임 */
           {
               length = getc(src);
               sp = qx(rear - c);
               for (i = 0; i < length; i++) put_byte(queue[qx(sp+i)], dst);
                                /* 정보에 의해서 압축된 정보를 복원함 */
           }
       }
       else                     /* 일반 문자의 경우 */
           put_byte(c, dst);
       c = getc(src);
  }
  while (!queue_empty()) putc(get(), dst);
                                /* 큐에 남아 있는 문자들을 모두 출력 */
  fclose(dst);
} 

4.3 Sliding Window를 이용한 Lempel-Ziv 알고리즘의 구현
이제 까지 설명한 것을 실제로 구현한 소스이다.

/*                                                                  */
/*   LZWIN.C  :  Lempel-Ziv compression using Sliding Window        */
/*                                                                  */

#include <stdio.h>
#include <dir.h>
#include <string.h>
#include <alloc.h>
#include <time.h>
#include <stdlib.h>

#define SIZE 255

int queue[SIZE];
int front, rear;

/* 해시 테이블의 구조 */
typedef struct _jump
{
  int index;
  struct _jump *next;
} jump;

jump jump_table[256];

/* 탈출 문자 */
#define ESCAPE  0xB4

/* Lempel-Ziv 압축법에 의한 것임을 나타내는 식별 코드 */
#define IDENT1  0x33
#define IDENT2  0x44

#define FAIL    0xff

/* 큐를 초기화 */
void init_queue(void)
{
  front = rear = 0;
}

/* 큐가 꽉 찼으면 1을 되돌림 */
int queue_full(void)
{
  return (rear + 1) % SIZE == front;
}

/* 큐가 비었으면 1을 되돌림 */
int queue_empty(void)
{
  return front == rear;
}

/* 큐에 문자를 집어 넣음 */
int put(int k)
{
  queue[rear] = k;
  rear = ++rear % SIZE;

  return k;
}

/* 큐에서 문자를 꺼냄 */
int get(void)
{
  int i;

  i = queue[front];
  queue[front] = 0;
  front = ++front % SIZE;

  return i;
}

/* k를 큐의 첨자로 변환, 범위에서 벗어나는 것을 범위 내로 조정 */
int qx(int k)
{
  return (k + SIZE) % SIZE;
}

/* srcname[]에서 파일 이름만 뽑아내어서 그것의 확장자를 lzw로 바꿈 */
void make_dstname(char dstname[], char srcname[])
{
  char temp[256];

  fnsplit(srcname, temp, temp, dstname, temp);
  strcat(dstname, ".lzw");
}

/* 파일의 이름을 받아 그 파일의 길이를 되돌림 */
long file_length(char filename[])
{
  FILE *fp;
  long l;

  if ((fp = fopen(filename, "rb")) == NULL)
   return 0L;
 
  fseek(fp, 0, SEEK_END);
  l = ftell(fp);
  fclose(fp);
 
  return l;
}

/* jump_table[]의 모든 노드를 제거 */
void delete_all_jump(void)
{
  int i;
  jump *j, *d;

  for (i = 0; i < 256; i++)
  {
       j = jump_table[i].next;
       while (j != NULL)
       {
           d = j;
           j = j->next;
           free(d);
       }
       jump_table[i].next = NULL;
  }
}

/* jump_table[]에 새로운 문자의 위치를 삽입 */
void put_jump(int c, int ptr)
{
  jump *j;

  if ((j = (jump*)malloc(sizeof(jump))) == NULL)
  {
       printf("\nError : Out of memory.");
       exit(1);
  }

  j->next = jump_table[c].next;       /* 선두에 삽입 */
  jump_table[c].next = j;
  j->index = ptr;
}

/* ptr 위치를 가지는 노드를 삭제 */
void del_jump(int c, int ptr)
{
  jump *j, *p;

  p = jump_table + c;
  j = p->next;

  while (j && j->index != ptr)    /* 노드 검색 */
  {
       p = j;
       j = j->next;
  }

  p->next = j->next;
  free(j);
}

/* cp와 length로 주어진 패턴을 해시법으로 찾아서 되돌림 */
int qmatch(int length)
{
  int i;
  jump *t, *p;
  int cp, sp;
 
  cp = qx(rear - length);     /* cp의 위치를 얻음 */
  p = jump_table + queue[cp];
  t = p->next;
  while (t != NULL)
  {
       sp = t->index;
 
       /*  첫 문자는 비교할 필요 없음. -> i =1; */
       for (i = 1; i < length && queue[qx(sp+i)] == queue[qx(cp+i)]; i++);
           if (i == length) return sp;     /* 패턴을 찾았음 */
 
       t = t->next;
  }

  return FAIL;
}

/* 문자 c를 출력 파일에 씀 */
int putc1(int c, FILE *dst)
{
  if (c == ESCAPE)        /* 탈출 문자이면 <탈출문자 0x00>쌍으로 치환 */
{
   putc(ESCAPE, dst);
   putc(0x00, dst);
}
  else
    putc(c, dst);

  return c;
}

/* 패턴을 압축해서 출력 파일에 씀 */
void encode(int sp, int cp, int length, FILE *dst)
{
  int i;
 
  for (i = 0; i < length; i++)        /* jump_table[]에 패턴의 문자들을 기록 */
       put_jump(queue[qx(cp+i)], qx(cp+i));
 
  putc(ESCAPE, dst);      /* 탈출 문자 */
  putc(qx(cp-sp), dst);   /* 상대 위치 */
  putc(length, dst);      /* 패턴 길이 */
}

/* Sliding Window를 이용한 LZ 압축 함수 */
void lzwin_comp(FILE *src, char *srcname)
{
  int length;
  char dstname[13];
  FILE *dst;
  int sp, cp;
  int i, j;
  int written;

  make_dstname(dstname, srcname);     /* 출력 파일 이름을 만듬 */
  if ((dst = fopen(dstname, "wb")) == NULL)
{
   printf("\n Error : Can't create file.");
   fcloseall();
   exit(1);
}

  /* 압축 파일의 헤더 작성 */
  putc(IDENT1, dst);    /* 출력 파일에 식별자 삽입 */
  putc(IDENT2, dst);
  fputs(srcname, dst);    /* 출력 파일에 파일 이름 삽입 */
  putc(NULL, dst);        /* NULL 문자 삽입 */

  for (i = 0; i < 256; i++)       /* jump_table[] 초기화 */
       jump_table[i].next = NULL;
 
  rewind(src);
  init_queue();

  put(getc(src));

  length = 0;
  while (!feof(src))
{
       if (queue_full())       /* 큐가 꽉 찼으면 */
    {
        if (sp == front)    /* sp의 패턴이 넘어가려고 하면 현재의 정보로 출력 파일에 씀*/
           {
               if (length > 3)
             encode(sp, cp, length, dst);
               else
                   for (i = 0; i < length; i++)
                   {
                       put_jump(queue[qx(cp+i)], qx(cp+i));
                       putc1(queue[qx(cp+i)], dst);
                   }
              
               length = 0;
           }
          
           /* 큐에서 빠져나가는 문자의 위치를 jump_table[]에서 삭제 */
           del_jump(queue[front], front);
          
           get();  /* 큐에서 한 문자 삭제 */
    }
   
       if (length == 0)
       {
           cp = qx(rear-1);
           sp = qmatch(length+1);
          
           if (sp == FAIL)
           {
               putc1(queue[cp], dst);
               put_jump(queue[cp], cp);
           }
           else
               length++;
          
           put(getc(src));
       }
       else if (length > 0)
    {
           if (queue[qx(cp+length)] != queue[qx(sp+length)])
               j = qmatch(length+1);
           else j = sp;
           if (j == FAIL || length > SIZE - 3)
           {
               if (length > 3)
               {
                   encode(sp, cp, length, dst);
                   length = 0;
               }
               else
               {
                   for (i = 0; i < length; i++)
                   {
                       put_jump(queue[qx(cp+i)], qx(cp+i));
                       putc1(queue[qx(cp+i)], dst);
                   }
                   length = 0;
               }
           }
        else
           {
               sp = j;
               length++;
               put(getc(src));
           }
    }
  }
 
  /* 큐에 남은 문자 출력 */
  if (length > 3)
       encode(sp, cp, length, dst);
  else
       for (i = 0; i < length; i++)
           putc1(queue[qx(cp+i)], dst);
 
  delete_all_jump();
  fclose(dst);
}

/* 큐에 문자를 넣고, 만일 꽉 찼다면 큐에서 빠져나온 문자를 출력 */
void put_byte(int c, FILE *dst)
{
  if (queue_full()) putc(get(), dst);
  put(c);
}

/* Sliding Window를 이용한 LZ 압축법의 복원 함수 */
void lzwin_decomp(FILE *src)
{
  int c;
  char srcname[13];
  FILE *dst;
  int length;
  int i = 0, j;
  int sp;

  rewind(src);
  c = getc(src);
  if (c != IDENT1 || getc(src) != IDENT2) /* 헤더 확인 */
{
   printf("\n Error : That file is not Lempel-Ziv Encoding file");
   fcloseall();
   exit(1);
}

  while ((c = getc(src)) != NULL)     /* 파일 이름을 얻음 */
   srcname[i++] = c;
 
  srcname[i] = NULL;
  if ((dst = fopen(srcname, "wb")) == NULL)
{
   printf("\n Error : Disk full? ");
   fcloseall();
   exit(1);
}

  init_queue();
  c = getc(src);

  while (!feof(src))
{
       if (c == ESCAPE)        /* 탈출 문자이면 */
       {
           if ((c = getc(src)) == 0)   /* <탈출 문자 0x00> 이면 */
               put_byte(ESCAPE, dst);
           else        /* <탈출문자 상대위치 패턴길이> 이면 */
           {
               length = getc(src);
               sp = qx(rear - c);
               for (i = 0; i < length; i++)
                   put_byte(queue[qx(sp+i)], dst);
           }
       }
       else    /* 일반적인 문자의 경우 */
           put_byte(c, dst);
      
       c = getc(src);
}

 
  while (!queue_empty())  /* 큐에 남아 있는 모든 문자를 출력 */
       putc(get(), dst);
 
  fclose(dst);
}

void main(int argc, char *argv[])
  {
  FILE *src;
  long s, d;
  char dstname[13];
  clock_t tstart, tend;
 

  /* 사용법 출력 */
  if (argc < 3)
  {
   printf("\n Usage : LZWIN <a or x> <filename>");
   exit(1);
}

  tstart = clock();       /* 시작 시간 기록 */
  s = file_length(argv[2]);   /* 원래 파일의 크기를 구함 */

  if ((src = fopen(argv[2], "rb")) == NULL)
  {
       printf("\n Error : That file does not exist.");
       exit(1);
 
  }
  if (strcmp(argv[1], "a") == 0)  /* 압축 */
{
    lzwin_comp(src, argv[2]);
       make_dstname(dstname, argv[2]);
   d = file_length(dstname);       /* 압축 파일의 크기를 구함 */
   printf("\nFile compressed to %d%%.", (int)((double)d/s*100.));
}
  else if (strcmp(argv[1], "x") == 0)     /* 압축의 해제 */
  {
   lzwin_decomp(src);
       printf("\nFile decompressed & created.");
  }
 
  fclose(src);
 
  tend = clock(); /* 종료 시간 기록 */
  printf("\nTime elapsed %d ticks", tend - tstart);   /* 수행 시간 출력 : 단위 tick */
} 

이 프로그램을 실행시켜 보면 우선 속도가 매우 느리다는 점에 실망할 수도 있다. 그러나 압축률은 상용 프로그램에는 못 미치지만 상당히 좋음을 알 수 있을 것이다. 일반적으로 <상대위치>의 비트 수를 늘리면 압축률은 좋아진다. 대신 패턴 검색 시간이 길어지는 단점이 있다.
<상대위치>와 <패턴길이>를 모두 8비트로 표현했지만, 이 둘을 적절히 조절하면 실행 시간을 빨리 하거나 압축률을 좋게 하는 변화를 줄 수 있다. 하지만 이럴 경우 비트 조작이 필요하므로 코딩 시 주의해야 한다.

4.4 실행 결과


filetype Lempel-Zip   
random-bin 100.59   
random-txt 100.24   
wave 92.34   
pdf 83.54   
text(big) 66.64   
text(small) 89.69   
sql 55.18 

Run -Length의 경우와 마찬가지로 Random File에 대해서는 압축을 하지 못했다. 하지만 그 외의 경우는 Run-Length에 비해 상당히 높은 압축률을 보여주고 있다. 이는 조금 떨어진 곳이라도 같은 패턴이 있으면 압축을 할 수 있기 때문에 가능한 결과라 생각한다.

5 Variable Length
영문 텍스트 파일의 경우 사용되는 문자는 영어 대.소문자와 기호, 공백 문자 등 100여 개 안팎이다. 그래서 원래 ASCII 코드는 7비트(128가지의 상태를 표현)로 설계되었으며 나머지 한 비트는 패리티 비트(Parity Bit)로 통신상에서 오류를 검출하는 데 사용하도록 되어 있었다.
통신 에뮬레이터의 환경설정에서 ‘데이터 비트 8’, ‘패리티 None’ 이라고 설정하는 것은 이러한 ASCII코드의 에러 검출 기능을 무시하고 8비트를 모두 사용하겠다는 뜻이다. 이러한 설정 기능은 원래 영어권에서 텍스트에 기반을 둔 통신 환경에서 8비트를 모두 사용할 필요가 없었기 때문에 만들어진 선택 사항이다.
그렇다면 패리티를 무시하고 7비트만으로 영문자를 표기하되, 남은 한 비트를 다음 문자를 위해 사용한다면 고정적으로 1/8의 압축률을 가지는 압축 방법이 될 것이다. 이를 ‘8비트에서 7비트로 줄이는 압축 알고리즘(Eight to Seven Encoding)’ 이라고 한다.

<그림 5‑1> 8비트에서 7비트로 줄이는 압축 알고리즘

위 의 논의는 자연적으로 다음과 같은 생각을 유도한다. 즉 압축하고자 하는 파일이 단지 일부분의 문자 집합만을 사용한다면 이를 표현하기 위해 8비트 전부를 사용할 필요가 없다는 것이다. 예를 들어 ‘ABCDEFABBCDEBDD’라는 문자열을 압축한다고 하자. 이 문자열은 단 6 문자를 사용한다. 그렇다면 사용되는 각 문자에 대해서 다음과 같이 다시 비트를 재구성해보자.

<그림 5‑2> 문자 코드의 재구성

그렇다면 앞의 문자열은 다음과 같이 다시 쓸 수 있으며 결과적으로 압축된다.

원래 문자열 : ABCDEFABBCDEBDD
압축 비트열 : 0 1 00 01 10 11 0 1 1 00 01 10 1 01 01 

하 지만, 이렇게 표현을 하면 압축 비트열은 각 문자 코드마다 구분자(Delimiter)가 필요하게 된다. 만약 구분자가 없이 각 코드를 붙여 쓴다면 그 해석이 모호해져서 압축 알고리즘으로는 쓸모 없게 된다. 예를 들어 압축 비트열의 앞부분인 네 코드를 붙여 쓴다면 ‘010001’이 되는데 이는 ‘ABCD’로도 해석할 수 있지만 ‘DCD’로도 해석할 수 있고 ‘ABAAAB’로도 해석할 수 있다는 뜻이다.
그렇다면 이 모호함을 해결하는 방법은 없을까? 문제 해결의 열쇠는 문자 코드들을 기수 나무(Radix Tree)로 구성해 보는 데서 얻어진다.

<그림 5‑3> <그림 5‑2>코드의 기수 나무
기수 나무는 뿌리 노드에서 원하는 노드를 찾아가는 과정에서 비트가 0이면 왼쪽 자식으로, 1이면 오른쪽 자식으로 가는 탐색 구조를 가지고 있다. 이 그림에서 보면 각 문자들은 외부 노드와 내부 노드 모두에 존재한다. 이러한 구조에서는 구분자가 반드시 필요하게 된다.
그렇다면 이들을 기수 나무로 구성하지 않고 기수 트라이(Radix Trie)로 구성한다면 어떨까? 기수 트라이는 각 정보 노드들이 모두 외부 노드인 나무 구조를 의미한다. 이렇게 구성된다면 정보 �