[펌] 압축 알고리즘 소스 및 정리

http://blog.naver.com/kdr0923/40012945515

압축 알고리즘 소스 및 정리

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

< 그 림 목 차 >

<그림 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

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

2Introduction
우리가 보통 살펴보는 알고리즘들은 대부분이 시간을 절약하기 위한 목적을 가지고 개발된 것 들이다. 하지만, 우리가 지금부터 살펴볼 알고리즘들은 공간을 절약하기 위한 목적을 가진 알고리즘이다.
압축알고리즘이 처음으로 대두되기 시작한 것은 컴퓨터 통신 때문이었다. 컴퓨터 통신에서는 시간이 곧바로 돈으로 연결된다(적어도 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 압축법 중 하나를 사용하거나 또는 둘 다 사용하거나, 혹은 그 응용을 사용한다.

3Run-Length
3.1Run-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.2Run-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.3Run-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실행 결과

filetypeRun-Length
random-bin100.59
random-txt100.24
wave98.20
pdf99.03
text(big)85.04
text(small)98.71
sql96.78

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

4Lempel-Ziv
4.1Lempel-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.2Lempel-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.3Sliding 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);
}

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실행 결과

filetypeLempel-Zip
random-bin100.59
random-txt100.24
wave92.34
pdf83.54
text(big)66.64
text(small)89.69
sql55.18

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

5Variable 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)로 구성한다면 어떨까? 기수 트라이는 각 정보 노드들이 모두 외부 노드인 나무 구조를 의미한다. 이렇게 구성된다면 정보 노드를 찾아가는 과정에서 다른 정보 노드를 만나는 경우가 없어져서 구분자 없이도 비트들을 구성할 수 있다.
예를 들어 다음의 그림과 같이 기수 트라이를 만들고 코드를 재구성해 보도록 하자.

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

<그림 5‑4>의 코드 표는 <그림 5‑2>에 비해서 코드의 길이가 길어졌지만 구분자가 필요 없다는 장점이 있다. 이 <그림 5‑4>를 이용하여 문제의 문자열을 압축하면 다음처럼 된다.

원래 문자열 : ABCDEFABBCDEBDD
압축 비트열 : 01001011101110111101001001011101110100110110

이렇게 어떤 파일에서 사용되는 문자 집합이 전체 집합의 극히 일부분이라면 상당한 압축률로 압축할 수 있음을 보았을 것이다. 이와 같이 문자 코드를 재구성하여 고정된 비트 길이의 코드가 아닌 가변 길이의 코드를 사용하여 압축하는 방법을 가변 길이 압축법(Variable Length Encoding)이라고 한다.
가변 길이 압축법에서 유의할 점은 압축 파일 내에 각 문자에 대해서 어떤 코드로 압축되었는지 그 정보를 미리 기억시켜 두어야 한다는 점이다. 이는 Run-Length 압축법이나 Lempel-Ziv 압축법과 같이 헤더가 식별자와 파일 이름만으로 구성되는 것이 아니라 문자에 대한 코드 또한 기록해 두어야 한다는 것을 의미한다. 기록되는 코드는 코드 자체뿐 아니라, 가변 길이라는 특성 때문에 코드의 길이 또한 기록되어야 한다. 이렇게 되어서 가변길이 압축법은 헤더가 매우 길어지게 된다.
뒤에 나올 Huffman Tree가 가변 길이 압축법의 한 종류이기 때문에 가변 길이 압축법 자체는 자세히 다루지 않겠다.

6Huffman Tree
만일 압축하고자 하는 파일이 전체 문자 집합의 모든 원소를 사용한다면 가변길이 압축법은 여전히 유용할까? 답은 그렇다 이다. 그리고 그것을 가능케 하는 것은 이 절에서 소개하는 Huffman 나무(Huffman Tree)이다.
앞 절에서 살펴본 것과 같이 기수 트라이로 코드를 구성하는 경우 각 정보를 포함하고 있는 외부 노드의 레벨(Level)이 얼마냐에 따라 코드의 길이가 결정되었다. 예를 들어 <그림 5‑4>의 ‘A’문자의 경우는 겨우 비트의 길이가 1이며, ‘F’의 경우는 4가 된다.
그렇다면 압축하고자 파일이 비록 모든 문자를 사용한다 할지라도 그 출현 빈도수가 고르지 않다면 출현빈도가 큰 문자에 대해서는 짧은 길이의 코드를, 출현 빈도가 작은 문자에 대해서는 긴 길이의 코드를 할당하면 전체적으로 압축되는 효과를 가져올 것이다.
그렇다면 압축축하고자 하는 파일을 먼저 읽어서 각 문자에 대한 빈도를 계산해야 한다는 결론이 나오게 되는데, 이러한 빈도가 freq[]라는 배열에 저장되어 있다면 이 빈도를 이용하여 어떻게 빈도와 레벨이 반비례하는 기수 트라이를 만들 것인가 하는 것이 이 절의 문제이며, 그 해결 방법은 Huffman 나무이다.
우선 Huffman 나무의 노드를 다음의 huf 구조체와 같이 정의해 보자.

typedef struct _huf
{
long count; // 빈도
int data; // 문자
struct _huf *left, *right
} huf;

huf 구조체는 Huffman 나무의 노드로서 그 멤버로 빈도를 저장하는 count, 어떤 문자의 노드인지 알려주는 data를 가진다. 이 huf 구조체의 멤버를 의미있는 정보로 채우기 위해서는 우선 문자열에서 각 문자에 대한 빈도를 계산해야 한다. <그림 6‑1> (가)와 같은 문자열이 있다고 할 때 그 빈도수를 나타내면 (나)와 같다.

<그림 6‑1> 빈도수 계산

이제 <그림 6‑1> (나)의 정보를 이용하여 각 노드를 생성하여 죽 배열한다. 그 다음 작은 빈도의 두 노드를 뽑아내어 그것을 자식으로 가지는 분기 노드(Branch Node, 정보를 저장하지 않는 트라이의 내부 노드)를 새로 생성하여 그것을 다시 노드의 배열에 집어넣는다. 이 때 분기 노드의 count에는 두 자식 노드의 count의 합이 저장된다. 이런 과정을 노드가 하나 남을 때까지 반복하면 Huffman 나무가 얻어진다. 이 과정을 <그림 6‑2>에 나타내었다.

<그림 6‑2> Huffman Tree 구성과정

<그림 6‑2>를 차례로 따라가다 보면 그 방법을 자연히 느끼게 될 것이다. 최종적인 결과로 얻어지는 Huffman Tree는 (하) 그림과 같다. (하) 그림을 보면 빈도수가 적은 노드들은 상대적으로 레벨이 크고, 빈도수가 많은 노드들은 레벨이 작음을 알 수 있다.
이제 이런 과정을 수행하는 함수를 작성해 보기로 하자. 우선 빈도와 문자를 저장하고 있는 노드들을 죽 배열하는 장소를 정의해야 할 것이다. 그것은 다음의 head[] 배열이며, nhead는 노드의 개수를 저장하고 있다.

huf *head[256];
int nhead;

앞에서 설명한 바와 같이 문자 i의 빈도가 freq[i]에 저장되어 있다고 한다면 다음의 construct_trie() 함수가 Huffman 나무를 구성해 준다.

void construct_trie(void)
{
int i;
int m;
hum *h, *h1, *h2;

/* 초기 단계 */
for ( i = nhead = 0; i < 256; i++)
{
if(freq[i] != 0) /* 빈도가 0이 아닌 문자에 대해서만 노드를 생성 */
{
if((h = (huf*)malloc(sizeof(huf))) == NULL)
{
printf("\nError : Out of memory.");
exit(1);
}

h->count = freq[i];
h->data = i;
h->left = h->right = NULL;
head[nhead++] = h;
}
}

/* Huffman Tree 생성 단계 */
while (nhead > 1) /* 노드의 개수가 1이면 종료 */
{
m = find_minimum(); /* 최소의 빈도를 가지는 노드를 찾음 */
h1 = head[m];
head[m] = head[--nhead]; /* 그 노드를 빼냄 */
m = find_minimum(); /* 또 다른 최소의 빈도를 가지는 노드를 찾음 */
h2 = head[m];
if((h = (huf*)malloc(sizeof(huf))) == NULL) /* 분기 노드 생성 */
{
printf("\nError : Out of memory");
exit(1);
}

/* 두 자식 노드의 count 합을 저장 */
h->count = h1->count + h2->count;
h->data = 0;
h->left = h1; /* h1, h2를 자식으로 둠 */
h->right = h2;
head[m] = h; /* 생성된 분기 노드를 노드 배열 head[]에 삽입 */
}

huf_head = head[0]; /* Huffman Tree의 루트 노드를 저장 */
}

construct_trie() 함수는 앞에서 보인 Huffman 나무 생성 과정을 그대로 직관적으로 표현했다. 그리고 huf_head라는 전역 변수는 Huffman 나무의 뿌리 노드(Root)를 가리키도록 함수의 마지막에서 설정해 둔다.
이렇게 <그림 6‑2> (하) 그림과 같은 Huffman 나무에서 각 문자에 대한 코드의 길이를 뽑아내어 보면 <그림 6‑3>과 같다.

<그림 6‑3> Huffman Tree에서 얻어진 코드

6.1Huffman Encoding
Huffman 압축 알고리즘은 한마디로 말해서 원래의 고정 길이 코드를 <그림 6‑3>의 가변 길이 코드로 변환하는 것이다. 그러므로 Huffman 나무에서 코드를 얻어내는 방법이 반드시 필요하다.
다음의 _make_code() 함수와 make_code() 함수가 Huffman 나무에서 코드를 생성하는 함수이다. _make_code() 함수가 재귀 호출 형태이어서 그것의 입구 함수로 make_code() 함수를 준비해 둔 것이다. 얻어진 코드는 전역 배열인 code[]에 저장되며, 코드의 길이는 len[]배열에 저장된다.

void _make_code(huf *h, unsigned c, int l)
{
if(h->left != NULL || h->right != NULL) /* 내부 노드(분기 노드)이면 */
{
c <<= 1; /* 코드를 시프트, 결과적으로 0을 LSB에 집어넣는다. */
l++; /* 길이 증가 */
_make_code(h->left, c, l); /* 오른쪽 자식으로 재귀 호출 */
c >>= 1; /* 부모로 돌아가기 위해 다시 원상 복구 */
l--;
}
else /* 외부 노드(정보 노드)이면 */
{
code[h->data] = c; /* 코드와 코드의 길이를 기록 */
len[h->data] = l;
}
}

void make_code(void)
{
/* _make_code()의 입구 함수 */
int i;
for (i = 0; i < 256; i++) /* code[]와 len[]의 초기화 */
code[i] = len[i] = 0;

_make_code(huf_head, 0u, 0);
}

위의 make_code()함수를 이용하면 이제 가변 길이 레코드를 얻어낼 수 있다. 그렇다면 이제 실제로 압축 함수 제작에 들어가야 하는데, 약간의 문제가 있다. 그것은 가변 길이의 코드를 사용하기 때문에 한 바이트씩 디스크로 입출력하게 되어 있는 기존의 시스템과는 좀 다른 점을 어떻게 표현하는가 하는 것이다.

이럴 때 필요한 것이 문제를 추상화 하는 것이다. 즉 디스크 파일을 한 바이트씩 쓰는 것이 아니라 한 비트씩 쓰는 것으로 착각하게 만드는 것이다. 이것을 담당하는 함수가 바로 put_bitseq()함수이다. put_bitseq() 함수를 사용하면 입력 파일에서 읽은 문자에 해당하는 코드를 비트별로 차례로 put_bitseq()의 인자로 주면 put_bitseq() 함수 내에서 알아서 한 바이트를 채워 출력 파일로 출력한다.

#define NORMAL 0
#define FLUSH 1

void put_bitseq(unsigned i, FILE *dst, int flag)
{
/* 한 비트씩 출력하도록 하는 함수 */
static unsigned wbyte = 0;

/* 한 바이트가 꽉 차거나 FLUSH 모드이면 */
/* bitloc는 입력될 비트 위치를 지정하는 전역 변수 */
if (bitloc < 0 || glag == FLUSH)
{
putc(wbyte, dst);
bitloc = 7; /* bitloc 재설정 */
wbyte = 0;
}

wbyte |= i << (bitloc--); /* 비트를 채워넣음 */
}

put_bitseq() 함수는 두 가지 모드로 작동한다. NNORMAL은 일반적인 경우로서 한 바이트가 꽉 차면 파일로 출력하는 모드이고, FLUSH 모드는 한 바이트가 꽉 차 있지 않더라도 현재의 wbyte를 파일로 출력한다. 이 두 가지 모드를 둔 이유는 파일의 끝에서 가변 길이 코드라는 특성 때문에 한 바이트가 채워지지 않는 경우가 생기기 때문이다.

<Huffman 압축 알고리즘(FILE *src, char *srcname)>
{
FILE *dst = 출력 파일;

length = src 파일의 길이;
헤더를 출력; /* 식별자, 파일 이름, 파일 길이 */

get_freq(src); /* 빈도를 구해 freq[] 배열에 저장 */
construct_trie(); /* freq[]를 이용하여 Huffman Tree 구성 */
make_code(); /* Huffman Tree를 이용하여 code[], len[] 배열 설정 */

code[]와 len[] 배열을 출력;

destruct_trie(huf_head); /* Huffman Tree를 제거 */

rewind(src);
bitloc = 7;
while(1)
{
cur = getc(src);
if(feof(src)) break;
for (b = len[cur] - 1; b >= 0; b--)
put_bitseq(bits(code[cur], b, 1), dst, NORMAL);
/* 비트별로 읽어서 put_bitseq() 수행 */
}

put_bitseq(0, dst, FLUSH); /* 남은 비트열을 FLUSH 모드로 씀 */
fclose(dst);
}

Huffman 압축 알고리즘의 본체는 매우 간단 명료하다.
그런데 한 가지 살펴볼 것이 있다. 일반적으로 실제 파일을 이용하여 Huffman 나무를 구성하여 코드를 구현해 보면 그 길이가 대략 14를 넘지 않는다. 그렇다면 code[] 배열을 위해서는 여분을 생각해서 16비트를 할당하면 될 것이다. 그런데 코드의 길이인 len[] 배열을 위해서는 최대 0~14 까지만 표현 가능하면 되므로 한 바이트를 모두 사용하는 것보다 4비트만 사용하면 상당히 헤더의 길이를 줄일 수 있을 것이다. 이것을 <그림 6‑4>에 나타내었다.

<그림 6‑4> code[]와 len[]의 저장

<그림 6‑4>와 같이 저장하면 총 128 * 5 바이트 즉 640 바이트의 헤더가 덧붙게 된다. 이렇게 저장하는 방법은 소스의 huffman_comp() 함수에 구현되어 있으므로 참고하기 바란다.

또한 Huffman 압축법과 같은 가변 길이 압축법은 앞에서 설명한 바와 같이 원래 파일의 길이도 저장하고 있어야 복원이 제대로 이루어진다. 결국 다른 압축법에 비해서 Huffman 압축법은 헤더의 길이가 매우 긴 편이다.

6.2Huffman Decoding
앞 절과 같은 방법으로 압축된 파일을 다시 원상태로 복원하는 방법을 생각해 보자. 압축된 파일의 헤더에는 code[]와 len[]에 대한 정보가 실려있다. 이 둘을 이용하면 원래의 Huffman 나무를 새로 구성할 수 있다. 우선 압축 파일의 헤더를 읽어 code[]와 len[]을 다시 설정했다고 하자.
그렇다면 다음의 trie_insert() 함수와 restruct_trie() 함수를 이용하여 Huffman 나무를 재구성할 수 있다. trie_insert() 함수는 인자로 받은 data의 노드를 code[data]와 len[data]를 이용하여 적절한 위치에 삽입한다. 삽입하는 방법은 매우 간단하다. code[data]의 비트를 차례로 분석하여 트라이를 타고 내려가면서 노드가 생성되어 있지 않으면 노드를 생성한다. 그래서 제 위치인 외부 노드에 도착하면 노드의 data 멤버에 인자 data를 설정하면 된다.

void trie_insert(int data)
{
int b = len[data] -1; /* 비트의 최좌측 위치(MSB) */
huf *p, *t;

if (huf_head == NULL) /* 뿌리 노드가 없으면 생성 */
{
if ((huf_head = (huf*)malloc(sizeof(huf)) == NULL)
{
printf("\nError : Out of memory.");
exit(1);
}

huf_head->left = huf_head->right = NULL;
}

p = t = huf_head;

while (b >= 0)
{
if (bits(code[data], b, 1) == 0) /* 현재 검사 비트가 0이면 왼쪽으로 */
{
t = t->left;
if (t == NULL) /* 왼쪽 자식이 없으면 생성 */
{
if ((t = (huf*)malloc(sizeof(huf))) == NULL)
{
printf("\nError : Out of memory.");
exit(1);
}

t->left = t->right = NULL;
p->left = t;
}
}
else /* 현재 검사 비트가 1이면 오른쪽으로 */
{
t = t->right;
if (t == NULL) /* 오른쪽 자식이 없으면 생성 */
{
if ((t = (huf*)malloc(sizeof(huf))) == NULL)
{
printf("\nError : Out of memory.");
exit(1);
}

t->left = t->right = NULL;

p->right = t;
}
}

p = t;
b--;
}
t->data = data; /* 외부 노드에 data 설정 */
}

다음의 restruct_trie()함수는 위의 trie_insert() 함수에 코드의 길이가 0이 아닌 문자에 대해서만 Huffman 나무를 재구성하도록 인자를 보급한다.

void restruct_trie(void)
{
int i;
huf_head = NULL;
for (i = 0; i < 256; i++)
if (len[i] > 0) trie_insert(i);
}

압축을 푸는 과정도 압축을 하는 과정과 유사하게 매우 간단하다. 압축을 푸는 과정을 한마디로 말하면 압축 파일에서 한 비트씩 읽어와서 그 비트대로 Huffman 나무를 순회한다. 그러다가 외부 노드에 도착하면 외부 노드의 data 멤버에 실린 값을 복원 파일에 써넣으면 되는 것이다.
여기서 문제가 되는 점은 압축 파일에서 한 비트씩 읽어내는 방법인데, 이것 또한 앞절에서 살펴본 바와 같이 파일에서 한 비트씩 읽어들이는 것처럼 착각할 수 있도록 다음의 get_bitseq() 함수를 작성하는 것으로 해결된다.

int get_bitseq(FILE *fp)
{
static int cur = 0;
if (bitloc < 0) /* 비트가 소모되었으면 다음 문자를 읽음 */
{
cur = getc(fp);
bitloc = 7;
}

return bits(cur, bitloc--, 1); /* 다음 비트를 돌려 줌 */
}

위의 부함수들을 이용하여 다음과 같이 Huffman 압축의 복원 알고리즘을 정리할 수 있다

<Huffman 압축 복원 알고리즘(FILE *src)>
{
FILE *dst = 복원 파일;
huf *h;

헤더를 읽어들임; /* 식별자와 파일 이름, 파일 길이 */
code[]와 len[]을 읽어들임;

restruct_trie(); /* Huffman Tree를 재구성 */

n = 0;
bitloc = -1;
while (n < length) /* length 는 파일의 길이 */
{
h = huf_head;
while (h->left && h->right)
{
if (get_bitseq(src) == 1) /* 읽어들인 비트가 1이면 오른쪽으로 */
h = h->right;
else /* 0이면 왼쪽으로 */
h = h->left;
}

putc(h->data, dst);
n++;
}

destruct_trie(huf_head); /* Huffman Tree 제거 */
fclose(dst);
}

6.3Huffman 압축 알고리즘 구현
이제까지의 논의를 바탕으로 Huffman 압축 알고리즘을 실제로 구현한 C 소스이다.

/* */
/* HUFFMAN.C : Compression by Huffman's algorithm */
/* */

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

/* Huffman 압축에 의한 것임을 나타내는 식별 코드 */
#define IDENT1 0x55
#define IDENT2 0x66

long freq[256];

typedef struct _huf
{
long count;
int data;
struct _huf *left, *right;
} huf;

huf *head[256];
int nhead;
huf *huf_head;
unsigned code[256];
int len[256];
int bitloc = -1;

/* 비트의 부분을 뽑아내는 함수 */
unsigned bits(unsigned x, int k, int j)
{
return (x >> k) & ~(~0 << j);
}

/* 파일에 존재하는 문자들의 빈도를 구해서 freq[]에 저장 */
void get_freq(FILE *fp)
{
int i;

for (i = 0; i < 256; i++)
freq[i] = 0L;

rewind(fp);

while (!feof(fp))
freq[getc(fp)]++;
}

/* 최소 빈도수를 찾는 함수 */
int find_minimum(void)
{
int mindex;
int i;

mindex = 0;

for (i = 1; i < nhead; i++)
if (head[i]->count < head[mindex]->count)
mindex = i;

return mindex;
}

/* freq[]로 Huffman Tree를 구성하는 함수 */
void construct_trie(void)
{
int i;
int m;
huf *h, *h1, *h2;

/* 초기 단계 */
for (i = nhead = 0; i < 256; i++)
{
if (freq[i] != 0)
{
if ((h = (huf*)malloc(sizeof(huf))) == NULL)
{
printf("\nError : Out of memory.");
exit(1);
}
h->count = freq[i];
h->data = i;
h->left = h->right = NULL;
head[nhead++] = h;
}
}

/* 생성 단계 */
while (nhead > 1)
{
m = find_minimum();
h1 = head[m];
head[m] = head[--nhead];
m = find_minimum();
h2 = head[m];

if ((h = (huf*)malloc(sizeof(huf))) == NULL)
{
printf("\nError : Out of memory.");
exit(1);
}
h->count = h1->count + h2->count;
h->data = 0;
h->left = h1;
h->right = h2;
head[m] = h;
}

huf_head = head[0];
}

/* Huffman Tree를 제거 */
void destruct_trie(huf *h)
{
if (h != NULL)
{
destruct_trie(h->left);
destruct_trie(h->right);
free(h);
}
}

/* Huffman Tree에서 코드를 얻어냄. code[]와 len[]의 설정 */
void _make_code(huf *h, unsigned c, int l)
{
if (h->left != NULL || h->right != NULL)
{
c <<= 1;
l++;
_make_code(h->left, c, l);
c |= 1u;
_make_code(h->right, c, l);
c >>= 1;
l--;
}
else
{
code[h->data] = c;
len[h->data] = l;
}
}

/* _make_code()함수의 입구 함수 */
void make_code(void)
{
int i;

for (i = 0; i < 256; i++)
code[i] = len[i] = 0;

_make_code(huf_head, 0u, 0);
}

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

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

/* 파일의 이름을 받아 그 파일의 길이를 되돌림 */
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;
}

#define NORMAL 0
#define FLUSH 1

/* 파일에 한 비트씩 출력하도록 캡슐화 한 함수 */
void put_bitseq(unsigned i, FILE *dst, int flag)
{
static unsigned wbyte = 0;
if (bitloc < 0 || flag == FLUSH)
{
putc(wbyte, dst);
bitloc = 7;
wbyte = 0;
}
wbyte |= i << (bitloc--);
}

/* Huffman 압축 함수 */
void huffman_comp(FILE *src, char *srcname)
{
int cur;
int i;
int max;
union { long lenl; int leni[2]; } length;
char dstname[13];
FILE *dst;
char temp[20];
int b;

fseek(src, 0L, SEEK_END);
length.lenl = ftell(src);
rewind(src);

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 문자열 삽입 */
putw(length.leni[0], dst); /* 파일의 길이 출력 */
putw(length.leni[1], dst);

get_freq(src);
construct_trie();
make_code();

/* code[]와 len[]을 출력 */
for (i = 0; i < 128; i++)
{
putw(code[i*2], dst);
cur = len[i*2] << 4;
cur |= len[i*2+1];
putc(cur, dst);
putw(code[i*2+1], dst);
}

destruct_trie(huf_head);

rewind(src);
bitloc = 7;
while (1)
{
cur = getc(src);

if (feof(src))
break;

for (b = len[cur] - 1; b >= 0; b--)
put_bitseq(bits(code[cur], b, 1), dst, NORMAL);
}
put_bitseq(0, dst, FLUSH);
fclose(dst);
}

/* len[]와 code[]를 이용하여 Huffman Tree를 구성 */
void trie_insert(int data)
{
int b = len[data] - 1;
huf *p, *t;

if (huf_head == NULL)
{
if ((huf_head = (huf*)malloc(sizeof(huf))) == NULL)
{
printf("\nError : Out of memory.");
exit(1);
}
huf_head->left = huf_head->right = NULL;
}

p = t = huf_head;
while (b >= 0)
{
if (bits(code[data], b, 1) == 0)
{
t = t->left;
if (t == NULL)
{
if ((t = (huf*)malloc(sizeof(huf))) == NULL)
{
printf("\nError : Out of memory.");
exit(1);
}
t->left = t->right = NULL;
p->left = t;
}
}
else
{
t = t->right;
if (t == NULL)
{
if ((t = (huf*)malloc(sizeof(huf))) == NULL)
{
printf("\nError : Out of memory.");
exit(1);
}
t->left = t->right = NULL;
p->right = t;
}
}
p = t;
b--;
}
t->data = data;
}

/* trie_insert()의 입구 함수 */
void restruct_trie(void)
{
int i;

huf_head = NULL;
for (i = 0; i < 256; i++)
if (len[i] > 0) trie_insert(i);
}

/* 파일에서 한 비트씩 읽는 것처럼 캡슐화 한 함수 */
int get_bitseq(FILE *fp)
{
static int cur = 0;

if (bitloc < 0)
{
cur = getc(fp);
bitloc = 7;
}

return bits(cur, bitloc--, 1);
}

/* Huffman 압축 복원 알고리즘 */
void huffman_decomp(FILE *src)
{
int cur;
char srcname[13];
FILE *dst;
union { long lenl; int leni[2]; } length;
long n;
huf *h;
int i = 0;

rewind(src);
cur = getc(src);
if (cur != IDENT1 || getc(src) != IDENT2)
{
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);
}
length.leni[0] = getw(src);
length.leni[1] = getw(src);

for (i = 0; i < 128; i++) /* code[]와 len[]을 읽어들임 */
{
code[i*2] = getw(src);
cur = getc(src);
code[i*2+1] = getw(src);
len[i*2] = bits(cur, 4, 4);
len[i*2+1] = bits(cur, 0, 4);
}
restruct_trie(); /* 헤더를 읽어서 Huffman Tree 재구성 */

n = 0;
bitloc = -1;
while (n < length.lenl)
{
h = huf_head;
while (h->left && h->right)
{
if (get_bitseq(src) == 1)
h = h->right;
else
h = h->left;
}
putc(h->data, dst);
n++;
}
destruct_trie(huf_head);
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 : HUFFMAN <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) /* 압축 */
{
huffman_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) /* 압축의 해제 */
{
huffman_decomp(src);
printf("\nFile decompressed & created.");
}

fclose(src);

tend = clock(); /* 종료 시각 저장 */
printf("\nTime elapsed %d ticks", tend - tstart); /* 수행 시간 출력 : 단위 tick */
}

6.4실행 결과

filetypeHuffman
random-bin113.80
random-txt97.32
wave94.76
pdf92.34
text(big)63.18
text(small)572.88
sql60.08

앞의 두 알고리즘과는 다르고 random-txt에서 압축이 되었다. 이는 전체 파일에 나타나는 문자가 몇 개 안되기 때문에 허프만 코드에 의해서 압축이 되었다고 생각할 수 있다. random-bin에서 압축이 안된 것은 상대적으로 많은 문자가 사용되었기 때문에 Trie의 Depth가 깊어져서 코드 값이 길어졌기 때문이다. 또한 text(small)의 경우 값이 커진 것은, 허프만 압축의 특성상 헤더가 추가 되는데, 원래 파일이 워낙 작았기 때문에 헤더의 크기에 영향을 받은 것이다.

7Compare

filetypeRun-LengthLempel-ZipHuffman
random-bin100.59100.59113.80
random-txt100.24100.2497.32
wave98.2092.3494.76
pdf99.0383.5492.34
text(big)85.0466.6463.18
text(small)98.7189.69572.88
sql96.7855.1860.08

주로 텍스트 파일을 이용한 테스트 였기 때문에, Lempel-Zip압축 방법이 대체로 우수한 압축률을 보여주고 있다. Huffman 압축 방식도 파일이 극히 작은 경우만 아니라면 어느정도의 압축률을 보여주고 있다. Run-Length는 text파일의 경우가 아니고선 거의 압축을 하지 못했다.

8JPEG (Joint Photographic Experts Group)
8.1JPEG이란
1982년, 국제 표준화 기구 ISO(International Standard Organization)는 정지 영상의 압축 표준을 만들기 위해 PEG(Photographic Exports Group:영상 전문가 그룹)을 만들었다. PEG의 목표는 ISDN을 이용하여 정지 영상을 전송하기 위한 고성능 압축 표준을 만들자는 것이 주 목적이 되어 이를 수행하게 된 것이다.
1986년 국제 전신 전화 위원회 CCITT(International Telegraph and Telephone Consultative Committee)에서는 팩스를 이용해 전송하기 위한 영상 압축 방법을 연구하기 시작하였다. CCITT의 연구 내용은 PEG의 그것과 거의 비슷하였기 때문에 1987년 이 두 국제 기구의 영상 전문가가 연합하여 공동 연구를 수행하게 되었고, 이 영상 전문가 연합을 Joint Photographic Expert Group이라고 하였으며, 이것의 약자를 따서 만든 말이 바로 JPEG이다. 1990년 JPEG에서는 픽셀당 6비트에서 24비트를 갖는 정지 영상을 압축할 수 있는 고성능 정지 영상 압축 방법에 대한 국제 표준을 만들어 내게 되었다. 후에 JPEG에서는 만든 압축 알고리즘을 이용한 파일 포맷이 만들어 지게 되고 이것이 오늘날까지 오게 된 것이다.

8.2다른 기술과의 비교
다른 기술과 차별화 되는 JPEG의 압축기술 GIF파일 포맷에 대해서 먼저 알아보기로 한다. 이 영상이미지 데이터는 최대 256컬러 영상까지만 저장할 수 있었기 때문에 실 세계의 이미지와 같은 것들을 저장하는데 한계가 있다. 지금은 트루컬러까지 모니터에서 지원이 되는데 이를 다른 곳에 응용하기에는 무리가 있었던 것이다.
GIF파일에서 사용하는 알고리즘을 LZW라고 하는데 이는 이를 개발한 Abraham Lempel과 Jakob Ziv이고 이를 개선시킨 Terry Welch등 세 사람의 이름을 따서 만든 압축 알고리즘으로 press, zoo, lha, pkzip, arj등과 같은 우리가 잘 알고 있는 프로그램에서 널리 사용되는 것이다. 이 압축 방법의 특징은 잡음의 영향을 크게 받기 때문에 애니메이션이나 컴퓨터 그래픽 영상을 압축하는 데는 비교적 효과적이라고 할 수 있었지만, 스캐너로 입력한 사진이나 실 세계의 이미지 같은 경우에 이를 압축하는 데는 효과적이지 못하다고 평가되고 있다.
이에 비해 TIFF나 BMP등의 파일 포맷은 24비트 트루컬러까지 지원하여 시진 등의 이미지를 잘 표현해 낼 수 있지만 압축 알고리즘 자체가 LZW, RLE등의 방식을 사용하였으므로 압축률이 그렇게 좋지 않다는 단점이 있다.
이에 반해 현재의 JPEG기술은 사진과 같은 자연 영상을 약 20:1이상 압축할 수 있는 성능을 가지고 있어서 현재 사용되고 있는 정지 영상 파일 포맷 중에서는 최고의 압축률을 자랑하고 있다.
하지만 장점이 있으면 단점도 존재하기 마련이다. 단점이라면 기존의 영상 파일을 압축하는 시점에서 영상의 일부 정보를 손실 시키기 때문에 의료 영상이나 기타 중요한 영상 혹은 자연 영상 등에는 사용하는데 무리가 있다. 즉, GIF, TIFF등의 영상 파일은 영상을 압축한 후 복원하면 압축하기 전과 완전히 동일한 비손실 압축 방법이지만 JPEG이미지 포맷의 경우 손실 압축방법이라는 것이다. 하지만 손실이 된다고 해도 원래의 이미지와 그렇게 다르지 않은(거의 동일한) 이미지를 얻을 수 있기 때문에 영상 정보가 중요한 부분이 아니라면 효율적인 방법이라고 할 수 있다.

8.3압축 방법
JPEG이 압축을 대상으로 삼는 사진과 같은 자연의 영상이 인접한 픽셀간에 픽셀 값이 급격하게 변하지 않는다는 속성을 이용하여 사람의 눈에 잘 띄지 않는 정보만 선택적으로 손실 시키는 기술을 사용하고 있기 때문이다.
이러한 압축 방법으로 인한 또 다른 단점이 있다. 인접한 픽셀간에 픽셀 값이 급격히 변하는 컴퓨터 영상이나 픽셀당 컬러 수가 아주 낮은 이진 영상이나, 16컬러 영상 등은 JPEG으로 압축하게 되면 오히려 압축 효율이 좋지 않을 뿐더러 손실된 부분이 상당히 거슬려 보인다는 것이다.
즉, 다른 이미지 압축 기술과 차별화 되는 신기술임에는 분명하지만 사용목적에 따라서 적절한 압축 알고리즘을 사용하는 것은 기본이라 하겠다.
JPEG의 압축방법 JPEG압축 알고리즘을 사용했다고 해서 이게 단 한가지의 압축 알고리즘만이 존재한다는 의미가 아님을 알고 있어야 한다. 다음과 같이 JPEG압축 알고리즘은 크게 네부분으로 나누어 볼 수 있다.
1. DCT(Discrete Cosine Transform) 압축 방법 :
일반적으로 JPEG영상이라고 하면 통용되는 압축 알고리즘이다.
2. 점진적 전송이 가능한 압축 방법 :
영상 파일을 읽어 오는 중에도 화면 출력을 할 수 있는 것을 의미하며 전송 속도가 낮은 네트워크를 통해 영상을 전송 받아 화면에 출력할 때 유용한 모드라고 할 수 있다. 즉, 영상의 일부를 전송 받아 저해상도의 영상을 출력할 수 있으며, 영상 데이터가 전송됨에 따라서 영상의 화질을 개선시키면서 화면에 출력이 가능하다는 것이다.
3. 계층 구조적 압축 알고리즘 :
피라미드 코딩 방법이라고도 하며, 하나의 영상 파일에 여러 가지 해상도를 갖는 영상을 한번에 저장하는 방법이다.
4. 비손실 압축 :
JPEG압축이라고 하여 손실 압축만 존재하는 것은 아니다. 이 경우에는 DCT압축 알고리즘을 사용하지 않고 2D-DPCM이라고 하는 압축방법을 이용하게 된다.

이처럼 JPEG표준에는 이와 같은 여러 가지 압축 방법이 규정되어 있지만, 일반적으로 JPEG로 영상을 압축하여 저장한다고 하면, DCT를 기반으로 한 압축 저장방법을 의미 한다.
이러한 방법을 또 다른 용어로 Baseline JPEG이라고 하며, JPEG영상 이미지를 지원하는 모든 어플리케이션은 이 이미지 데이터를 처리할 수 있는 알고리즘을 반드시 포함하고 있어야 한다. 즉, 나머지 3가지의 압축 방법을 꼭 지원하지 않아도 되는 선택사항이라는 의미이다.

8.4Baseline 압축 알고리즘
이 방법은 손실 압축 방법이기 때문에 영상에 손실을 많이 주면 화질이 안 좋아지는 대신 압축이 많이 되고, 손실을 적게 주면 좋은 화질을 유지하기는 하지만 압축이 조금밖에 되지 않는다는 것이다. 이처럼 손실의 정도를 나타내는 값을 Q펙터라고 말하는데 이 값의 범위는 1부터 100까지의 값으로 나타나게 된다. Q펙터가 1이면 최대의 손실을 내면서 가장 많이 압축되는 방식이고 100이면 이미지 손실을 적개 주기는 하지만 압축은 적게 되는 방식이다. Q펙터가 100이라고 하여 비손실 압축이 이루어 지는 것은 아니라는데 주의할 필요가 있다.
베이스라인 JPEG은 JPEG압축 최소 사양으로, 모든 JPEG관련 애플리케이션은 적어도 이 방법을 반드시 지원해야 한다고 했다. 이러한 방식이 어떤 단계를 거치면서 수행되게 되는지 알아보도록 하자.
1. 영상의 컬러 모델(RGB)을 YIQ모델로 변환한다.
2. 2*2 영상 블록에 대해 평균값을 취해 색차(Chrominance)신호 성분을 다운 샘플링 한다.
3. 각 컬러 성분의 영상을 8*8크기의 블록으로 나누고, 각 블록에 대해 DCT알고리즘을 수행시킨다.
4. 각 블록의 DCT계수를 시각에 미치는 영향에 따라 가중치를 두어 양자화 한다.
5. 양자화된 DCT계수를 Huffman Coding방법에 의해 코딩하여 파일로 저장한다.

이렇게 압축된 파일을 다시 원 이미지로 복원할 때는 반대의 과정을 거치게 된다. 이러한 압축과 복원에 관해 어떤 식으로 처리가 되는지 그림으로 살펴보면 아래와 같다

<그림 7‑1> JPEG Encoding / Decoding 단계

8.5JPEG의 실제 압축 / 복원 과정
1. 컬러모델 변환 :
컬러를 표현하는 방법에는 여러 가지가 있다. 가장 흔하게 사용하는 방법으로 RGB가 있다. 하지만 이러한 표현방법이 이것뿐이라면 좋겠지만 실제로는 그렇질 않다는 것이다.
RGB컬러는 모니터에서 사용하는 색상이고 빛의 3원색을 조합했을 때 나오는 색도 세 가지인데 이들은 하늘색(Cyan), 주황색(Magenta), 노랑색 (Yellow)이고, 이들의 조합으로도 모든 컬러를 표현 할 수 있게 된다. 이러한 방법을 CMY모델이라고 하며, 컬러 프린터가 이 모델을 이용해서 프린팅을 하게 된다.
우리가 논의 하려고 하는 YIQ라고 하는 모델은 밝기(Y : Luminance)와 색차(Chrominance : Inphase & Quadrature) 정보의 조합으로 컬러를 표현하는 방법이다.
다른 방법도 있다. 색상(Hue), 채도(Saturation), 명도(Intensity)의 색의 3요소로 색을 표현하는 HSI모델 등 여러 가지 컬러 모드가 있는 것이다.
RGB모델은 YIQ모델로 변환하는 방법이 있는데.. 이른 각각의 모델들도 서로 변환이 될 수 있다. RGB를 YIQ모델로 변환하는 식은 다음과 같다.

Y0.2990.5870.114R
I=0.596-0.275-0.321G
Q0.212-0.523-0.311B
<그림 7‑2> RGB의 YIQ 변환 식

이와 같은 식을 이용해서 JPEG압축을 하기 위해서는 컬러 모델을 YIQ모델로 변환을 한다. 많은 모델 중에서 이 모델로 변환을 하는 이유는 이중에서 Y성분은 시각적으로 눈에 잘 띄는 성분이지만 I, Q성분은 시각적으로 잘 띄지 않는 정보를 담고 있는 성질이 있어서, Y값만을 살려두고 I, Q값을 손실시키면 사람이 봤을 때에는 화질의 차이를 별로 느끼지 않으면서 정보를 양을 줄일 수 있는 장점이 있기 때문이다.

2. 색차 신호 성분 다운샘플링 : 앞에서도 이야기 했던 바와 같이 I와 Q의 성분은 시각적으로 눈에 잘 띄지 않는 정보들이기 때문에 이정보는 손실을 시켜도 사람이 보는데 특별한 지장을 주지 않는다.
손실을 시킨다는 의미이지 지워버린다는 의미는 아니다. 즉, Y값은 기억시키고, I, Q값은 가로 세로 2x2혹은 2x1크기를 블록당 한 개 만을 기억시키는 방식으로 정보만을 줄인다는 개념이다.
즉, 두번째 단계인 지금은 컬러모델을 변환한 것을 ‘다운 샘플링’ 한다는 것이다.

3. DCT적용 : JPEG알고리즘을 적용할 이미지 영상 블록에 어떤 주파수 성분이 얼마만큼 포함되어 있는지를 나타내는 8x8크기의 계수를 얻을 수 있게 된다. 픽셀간의 값의 변화율이 작은 밋밋한 영상은 저주파 성분을 나타내는 계수가 크게 나오게 되고, 픽셀간의 변화율이 큰 복잡한 영상은 고주파 성분을 나타내는 계수가 크게 나온다. 컬러를 표시하기 위한 각각의 YIQ성분은 8x8크기의 블록으로 나뉘어지고, 각 블록에 대해 DCT가 수행이 된다.
DCT는 Discrete Cosine Transform의 약자로 영상 블록을 서로 다른 주파수 성분의 코사인 함수로 분해하는 과정을 일컷는다.
이처럼 DCT를 수행하는 이유는 영상데이터의 경우 저주파 성분은 시각적으로 큰 정보를 가지고 있는 반면 고주파 성분의 경우는 시각적으로 별 의미가 없는 정보를 가지고 있기 때문에 시각적으로 적은 부분을 손실을 줌으로써 시각적인 손실을 최소화하면서 데이터 양을 줄이기 위한 것이다.

4. DCT 계수의 양자화 : 이론적으론 DCT자체만으로는 영상에 손실이 일어나지 않으며, DCT계수들을 기억하고 있으면 DCT역 변환을 통해 원 영상을 그대로 복원해 낼 수 있다. 실제로 영상에 손실을 주며, 데이터 량을 줄이는 부분은 DCT계수를 양자화 하는 바로 이 단계에서 이다.
계수 양자화란 여러 개의 값을 하나의 대표 값으로 대치시키는 과정을 말한다. 예를 들어 0에서 10까지의 값은 5로 대치시키고 10에서 20까지의 값은 15로 대치시키면 0부터 20까지의 값으로 분포되는 수많은 수들을 5와 15라는 두 개의 값으로 양자화 시킨 것이 된다. 이처럼 양자화 과정을 거치면 기억해야 할 수많은 경우의 수가 단지 몇 개의 경우의 수로 축소되기 때문에 데이터에 손실이 일어나지만 데이터 량을 크게 줄이는 장점이 있다.
양자화를 조밀하게 하면 데이터의 손실이 적어지는 대신 데이터 량은 그만큼 조금 줄게 되고, 양자화가 성기면 데이터의 손실은 많아지는 대신 데이터 량은 그만큼 많이 줄게 됩니다.
저주파 영역을 조밀하게 양자화하고 고주파 영역은 성기게 양자화하면 전체적으로 영상의 손실이 최소화 되면서 데이터 량의 감소를 극대화 시킬 수 있게 된다.
이처럼 주파수 성분 별로 어느 정도 간격으로 양자화를 하느냐에 따라 데이터 이미지의 질이 결정이 되는데 ISO에서는 실험적으로 결정한 양자화 테이블을 이용하여 양자화를 수행하는 것이 통상적이다.
영상의 화질과 압축률을 결정하는 변수인 Q펙터가 작용하는 부분도 바로 이 단계로. Q펙터를 크게 하면 전체적으로 양자화를 조밀하게 해서 손실을 줄임으로써 영상의 화질을 좋게 하고, Q펙터를 크게 하면 전체적으로 양자화 간격을 넓혀 화질에 손상을 많이 주어서 압축이 많이 되도록 하게 된다.

5. Huffman Coding : 양자화된 DCT계수는 자체로서 압축 효과를 갖지만 이를 더 효율적으로 압축하기 위해서 Huffman Coding으로 다시 한번 압축하여 파일에 저장을 한다.
JPEG의 실제 압축과 복원과정 알아보기 지금까지 영상데이터가 인코딩되는 과정을 단계적으로 알아보았다.

8.6확장 JPEG
베이스라인 JPEG은 JPEG에 필요한 최소의 기능만을 규정한 것이라고 설명을 했다. 이 외에도 JPEG내에는 많은 압축 방법이 존재한다. 확장 JPEG의 기능은 반드시 지원할 필요는 없지만, JPEG파일 내에서 사용될 수 있으므로 확장 JPEG의 기능을 일단 인식은 할 수 있어야 하고, 지원되지 않는 기능이 파일에 들어 있을 경우 에는 에러메시지를 출력하도록 하여야 한다.

9MPEG (Moving Picture Expert Group)

9.1MPEG의 개념
MPEG은 동영상 압축 표준이다. MPEG 표준에는 MPEG1과 MPEG2, MPEG4, MPEG7 이 있다. 각각에 대해 비디오(동화상 압축), 오디오(음향 압축), 시스템(동화상과 음향 등이 잘 섞여있는 스트림)에 대한 명세가 존재한다.
MPEG1은 1배속 CD 롬 드라이버의 데이터 전송속도인 1.5 Mbps에 맞도록 설계되었다. 즉 VCR 화질의 동영상 데이터를 압축했을 때 최대비트율이 1.15 Mbps가 되도록 MPEG1-비디오 압축 알고리즘이 정해졌으며, 스테레오 CD 음질의 음향 데이터를 압축했을 때 최대비트율이 128 Kbps(채널당 64Kbps)가 되도록 MPEG1-오디오 압축 알고리즘이 정해졌다. MPEG1-시스템은 단순히 음향과 동화상의 동기화를 목적으로 잘 섞어놓은(interleave) 것이다.
MPEG2는 보다 압축 효율이 향상되고 용도가 넓어진 것으로서, 보다 고화질/고음질의 영화도 대상으로 할 수 있고 방송망이나 고속망 환경에 적합하다. 즉 방송 TV (스튜디오 TV, HDTV) 화질의 동영상 데이터를 압축했을 때 최대비트율이 4 ( 6, 40)Mbps가 되도록 MPEG2-비디오 압축 알고리즘이 정해졌으며, 여러 채널의 CD 음질 음향 데이터를 압축했을 때 최대 비트율이 채널당 64 Kbps 이하로 되도록 MPEG2 오디오 압축 알고리즘이 정해졌다.
MPEG2 -시스템은 여러 영화를 한데 묶어 전송하여주고 이때 전송시 있을 수 있는 에러도 복구시켜줄 수 있는 일종의 트랜스포트 프로토콜이다.
MPEG4는 매우 높은 압축 효율을 얻음으로써 매우 낮은 비트율로 전송하기 위한 것이다. 이를 사용함으로써 이동 멀티미디어 응용을 구현할 수 있다. MPEG4는 아직 표준이 완전히 만들어지지 않았으며, 매우 높은 압축 효율을 위해 내용기반(model-based) 압축 기법이 연구되고 있다.

9.2MPEG의 표준

9.2.1 MPEG 1
MPEG 1의 표준은 4 부분으로 나누어져 있다.

1. 다중화 시스템부 : 동영상 및 음향 신호들의 비트열(Bit-stream) 구성 및 동기화 방식을 기술
2. 비디오부 : DCT와 움직임 추정(Motion Estimation)을 근간으로 하는 동영상 압축 알고리즘을 기술
3. 오디오부 : 서브밴드 코딩을 근간으로 하는 음향 압축 알고리즘을 기술
4. 적합성 검사부 : 비트열과 복호기의 적합성을 검사하는 방법

MPEG 1 영상 압축 알고리즘의 기본 골격은 움직임 추정과 움직임 보상을 이용하여 시간적인 중복 정보 제거한다.

1. 시간적인 중복성 - 수십 장의 정지 영상이 시간적으로 연속하여 움직일 때 앞의 영상과 현재의 영상은 서로 비슷한 특징을 보유
2. 제거방법 - DPCM(Differential PCM) 사용
3. DCT 방법을 이용하여 공간적인 중복 정보 제거
4. 공간 중복성 - 서로 인접한 화소끼리는 서로 비슷한 값을 소유
5. 제거방법 - DCT와 양자화를 이용

9.2.2 MPEG 2
MPEG 2의 표준화는 1990년 말부터 본격화 되었고 디지털 TV와 고선명 TV(HDTV) 방송에 대한 요구 사항이 추가되었고, 그 후 1995년 초 국제 표준으로 채택되었다.
MPEG 1과 마찬가지고 4 부분으로 나누어져 있지만 비디오부에서 디지털 TV와 고선명 TV 방송에 대한 사항이 첨가 되어있다.

1. 다중화 시스템부 : 음향, 영상, 다른 데이터 전송, 저장하기 위한 다중화 방법 정의
2. 비디오부 : 고화질 디지털 영상의 부호화를 목표로 MPEG-1에서 요구하는 순방 향 호환성을 만족, 격행 주사(Interlaced scan) 영상 형식과 HDTV 수준 의 해상도 지원 명시. 5개의 프로파일(Profile)과 4개의 레벨(Level)이 정 의
3. 오디오부 : 다중 채널 음향(샘플링 비율=16, 22.05, 24KHz)의 저전송율 부호화를 목표. 5개의 완전한 대역 채널(Left, Right, Center, 2 surround), 부가적 인 저주파수 강화 채널, 7개 해설 채널, 여러나라의 언어 지원 채널들 이 지원. 채널당 64Kbits/sec 정도의 고음질로 스테레오와 모노음을 부 호화
4. 적합성 검사부

MPEG 2 영상 압축 과정
1. 움직임 추정과 움직임 보상을 이용하여 시간적인 중복성을 제거
2. DCT와 양자화를 이용하여 공간적인 중복성을 제거

앞의 두 가지의 기본적인 압축 방법에 의하여 얻어진 데이타들의 발생 확률에 따라 엔트로피(Entrophy) 부호화 방법을 적용함으로써 최종적으로 압축 효율을 극대화

MPEG 2 표준은 멀티미디어 응용 서비스에 필수적인 디지털 저장 매체와 ISDN(Integrated Service Digital Network), B-ISDN(Broadband ISDN), LAN과 같은 디지털 통신 채널, 위성, 케이블, 지상파에 의한 디지털 방송매체 등을 응용 대상으로 삼고 있다.

9.2.3 MPEG 4
MPEG 4의 목적은 빠른 속도로 확산되고 있는 고성능 멀티미디어 통신 서비스 고려하여 기존의 방식과 새로운 기능들을 모두 지원할 수 있는 부호화 도구 제공를 제공하는 것이다. 그리고 양방향성, 높은 압축율 및 다양한 접속을 가능케 하는 AV(Audio/Video) 표준 부호화 방식을 지원한다. 또한 내용 기반 부호화(Content-based coding) 기술을 개발하고 초저속 전송에서부터 초고속 전송에 이르기까지 모든 영상 응용 분야에 융통성있게 대응할 수 있도록 한다.

주요 기능으로는 내용 기반 대화형 기능과 압축 기능, 광범위한 접근 기능을 갖고 있으며 내용 기반 대화형 기능은 멀티미디어 데이터 접근 도구, 처리 및 비트열 편집, 복합 영상 부호화, 향상된 시간 방향으로의 임의 접근을 할 수 있고 압축기능은 향상된 압축 효율, 복수개의 영상물을 동시에 부호화 할 수 있다. 그리고 광범위한 접근 기능은 내용 기반의 다단계 등급 부호화, 오류에 민감한 환경에서의 견고성을 갖도록 한다.

9.3MPEG의 기본적인 압축 원리
처음에 MPEG-1은 352 * 240에 30을 기준으로 하는 낮은 해상도로 출발하였다. 그러나 음향 부분에서만은 CD수준인 16BIT 44.1Khz STEREO 수준으로 표준안이 제정되었다. MPEG에서 사용하는 동영상 압축원리는 두가지 기본 기술을 바탕으로 하고 있다.

9.3.1 시간,공간의 중복성 제거
동영상은 정지 영상과 달리 정지영상을 여러장 연속하여 저장하여 이루어지는 파일이다. 예를들어 AVI 파일을 동영상 편집 프로그램으로 풀어서 본다면 거의 비슷한 화면이 프레임수에 따라 여러장 있는 것을 알 수가 있다. MPEG은 이러한 시간에 따른 화면의 중복성을 제거하고 착시현상을 이용하여 실제와 비슷한 영상을 만들어내는 원리를 가지고 있다. 이러한 중복성은 시간적 중복성(TEMPORAL REDUDANCY)과 공간적 중복성(SPATIAL REDUDANCY)이 있는데 앞의 AVI화일의 예가 시간적 중복성이 되고 공간적 중복성은 예를 들어 카메라가 정지영상이나 한 인물을 집중적으로 촬영할 때 그 영상들의 공간 구성값의 위치는 비슷한 값들이 비슷한 위치에서 이동이 적어지는 확률이 높아지기 때문에 나타나는 중복성이라고 할 수 있다.

위에서 설명한 두가지 항목을 해결하기 위한 방법으로 시간의 중복성을 해결하기 위한 방법으로는 각 화면의 움직임 예상(Motion Estimation)의 개념을 응용하고 공간의 중복성을 해결하기 위한 방법으로는 DCT (Discreate Cosine Transforms)라는 개념과 양자화(quantigation)의 개념을 응용한다. vMotion Estimation은 16 * 16 크기의 블록으로 수행을 하며 DCT는 8 * 8 크기로 수행된다.

v DCT(Discreate Cosine Transforms)
영상에 있어서 고주파 부분을 버리고 저주파 부분에 집중시켜 공간적 중복성을 꾀하는 개념이다. 예를들어 에지(EDGE)가 많은 부분, 즉 얼굴의 윤곽이나, 머리카락이 흩날리는 부분 등은 화소 변화가 많으므로 이 부분을 제거하여 압축률을 높인다.

v 양자화(quantigation)
DCT로 구해진 화상정보의 계수값을 더 많은 '0'이 나오도록 일정한 값(quantizer value)으로 나오게 나누어 주다. 따라서 영상 데이터의 손실이 있더라도 사람의 눈에서 이를 시각적으로 감지하기 힘들게 된다면 어느 정도의 데이터에 손실을 가하여 압축률을 높이게 되는 것이다. 가장 단순한 양자화기는 스칼라(Scalar)양자화기로써 VLC(가변길이 부호기)와 병행하여 사용된다. 우선 입력 데이터가 가질 수 있는 값의 범위를 제한된 숫자의 구역으로 분할하여 각 구역의 대표 값을 지정한다. 스칼라 양자화기는 입력되는 화소값이 속하는 구역의 번호를 출력하고 구역의 번호로부터 이미 지정된 대표 값을 출력한다. 여기서 구역의 번호를 양자화 인덱스(quantigation index)라 하고 각 구역의 대표 값을 양자화 레벨(quantigation level)이라고 한다.
이 과정에서 최종적으로 나오는 이진 부호를 연속적으로 연결한 것을 비트 열이라 부르고 이보다 진보된 방법이 벡터 양자화기로서 전자의 스칼라 양자화기보다 압축률이 높다.
이 방법의 경우 입력이 인접한 화소의 블럭으로 이루어지며 양자화 코드에서 가장 유사한 코드 블록(양자화 레벨값에 해당)을 찾아 인덱스 부호값으로 결정한다. 간단하게 말하자면 스칼라(Scalar)양자화기는 2차원 적으로 압축하는 방식이며 벡터 양자화기는 3차원적으로 압축하는 방법이다.
MPEG-1에서는 버퍼의 상태에 따라서 이 값이 가변적으로 바뀌게 되어있고 MPEG-2에서는 이 방법에 화면의 복잡도를 미리 예측하여 양자화 값이 변하도록 미리 분석(forward analysys)하는 방법도 사용되어 화질을 향상시킬 수 있다..

v Motion Estimation
일반적인 실시간 동영상 압축방식에서는 아날로그 시그널(영상)을 이용해서 디지털 화하는데 일정한 움직임을 연산하여 추정할 수 있는 기능이 필요한데 이 기능을 수행해 주는 역할을 Motion Estimation이라고 한다.

9.3.2 I,P,B영상
이 세가지 영상은 MPEG 화상정보를 구성하고 있는 세가지 요소이다. 각 요소의 역할은 다음과 같다.

① I-FRAME (Intra-Frame) : 정지 영상을 압축하는 것과 동일한 방법을 사용하는 것으로 연속되는 화면의 기준을 이루는 화면이다.
② P-FRAME (Predict-Frame) : 이전에 재생된 영상을 기준으로 삼아 기준 영상 (I-PRAME)과의 차이점만을 보충하여 재생하는 화면이며 그 다음에 재생될 P-영상의 기준이 되기도 한다.
③ B-FRAME (Bidirectional-Frame) : I영상과 P영상 또는 P영상과 다음 P영상 사이에 들 어가는 재생된 영상인데 두 개의 기준영상을 양방향 에서 예측해서 붙여내는 영상이라서 이러한 이름을 갖는다.
④ 각 프레임의 배열 및 진행순서는 다음과 같다. (MPEG-1의 경우)

영상의 진행 방향
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
┃I┃B┃B┃P┃B┃B┃P┃B┃B┃I┃B┃B┃P┃B┃B┃P┃B┃B┃I┃B┃...
└── MPEG의 1프레임 ───┘

10Conclusion
지금까지 세 가지의 압축 알고리즘을 살펴 보았다. Run-Length 압축법과 Lempel-Ziv 압축법은 고정 길이 압축법이고, Huffman 압축법은 가변 길이 압축법이라는 점에서 크게 구분된다. 그리고 그 프로그래밍도 판이하게 달랐다.
일반적으로 압축 알고리즘의 속도 면에서 보면 Run-Length 압축법이 가장 빠르지만 압축률은 가장 낮다. Run-Length 압축법은 파일 내에 동일한 문자의 연속된 나열이 있어야만 압축이 가능하기 때문이다.
이에 비해 Lempel-Ziv 압축법은 동일한 문자의 나열을 압축할 뿐 아니라, 동일한 패턴까지 압축하기 때문에 대부분의 경우에서 압축률이 가장 뛰어나다. 그러나 패턴 검색 방법이 최적화되지 않으면 속도면에서 불만을 안겨준다.
Huffman 압축법은 텍스트 파일처럼 파일을 구성하는 문자의 종류가 적거나, 파일을 구성하는 문자의 빈도의 편차가 클수록 압축률이 좋아진다. Huffman 압축법은 많은 빈도수의 문자를 짧은 길이의 코드로, 적은 빈도수의 문자를 긴 길이의 코드로 대치하는 방법이어서 Huffman 나무가 한쪽으로 쏠려 있을수록 압축률이 좋다.
그러나 빈도수가 고를 경우 Huffman 나무는 대체로 균형을 이루게 되어 압축률이 현저히 떨어진다. 또한 Huffman 압축법은 빈도수의 계산을 위해서 파일을 한번 미리 읽어야 하고, 다음에 실제 압축을 위해서 파일을 또 읽어야 하는 부담이 있어 실행 속도가 그리 빠르지는 않다.
실제 상용 압축 프로그램들은 주로 Huffman 압축법의 개량이나 Lempel-Ziv 압축법의 개량, 혹은 이 둘과 Run-Length 압축법까지 총동원해서 최대의 압축률과 최소의 실행시간을 보이도록 최적화되어 있다.
MPEG에 대해서는 가볍게 알아본 수준이므로 따로 결론을 내리지 않는다.

10.1테스트 실행 결과 표

Lempel-ZivHuffmanRun-Length
　압축전압축후압축률시간
(tick)압축후압축률시간
(tick)압축후압축률시간
(tick)

1048576010526665100.39 5191048119699.96 33310526667100.39 63
10485761052778100.40 521048699100.01 331052778100.40 6
102400102837100.43 4103000100.59 3102837100.43 0
1024010287100.46 010888106.33 010287100.46 0
10241037101.27 01660162.11 01037101.27 0

1048576010485745100.00 672875544083.50 28210485759100.00 61
10485761048586100.00 6887589583.53 291048587100.00 6
102400102413100.01 68604284.03 3102413100.01 0
1024010252100.12 0916289.47 010252100.12 0
10241035101.07 01496146.09 01035101.07 0
19416618605595.82 1718020192.81 518943697.56 1
230302247497.59 21972085.63 02302499.97 0
11140994689.28 1709463.68 01064295.53 0
4290387690.35 0321274.87 0421298.18 0
1837159086.55 0162888.62 0183699.95 0
61658294.48 01004162.99 060498.05 0
10586696846130579.92 1093858877881.13 290995282794.01 61
2855505175218261.36 218243571185.30 80282902099.07 18
1578364131426583.27 102151947296.27 49157489499.78 9
132526094908171.61 84119684790.31 39131460099.20 7
122431787419471.40 9394726077.37 31121108398.92 8
50015645563891.10 3048390896.75 1549886099.74 2
31931030070794.17 2031342398.16 9319376100.02 2
23801123404498.33 12238312100.13 7238467100.19 1
13219512991798.28 7132607100.31 4132438100.18 1
1035529809594.73 510265799.14 310324599.70 0
1228589196874.86 911164590.87 312111498.58 1

9506895661847669.62 1278549073257.76 188853588389.79 53
64797647006972.54 8337477157.84 1259613692.00 3
59879436163960.39 9332880054.91 1148952881.75 3
57580537551565.22 7133111457.50 1152511291.20 3
55658424077643.26 11127277349.01 936782066.09 2
26510414425754.42 4513922152.52 519696074.30 1
1038947997676.98 126188459.56 29780594.14 0
512663961477.27 72917556.91 14757492.80 0
205291548975.45 21266561.69 01941894.59 0
10304760273.78 1680065.99 0906587.98 0
5121316661.82 1338466.08 0406979.46 0
102170468.95 01209118.41 078176.49 0

4114291970.95 1298472.53 0354286.10 0
3081175256.86 0235076.27 0228274.07 0
2051159277.62 0176986.25 0176285.91 0
1541114774.43 01543100.13 0132886.18 0
118130110.17 0728616.95 0132111.86 0
2740148.15 06712485.19 040148.15 0
212160099381746.84 44192205443.46 332121615100.00 14
98003157260758.43 9362384463.66 2192199994.08 5
18603210091254.24 1512149465.31 317352493.28 1
560733433261.23 43807167.90 15594599.77 0

11 참고문헌
C언어로 설명한 알고리즘, 황종선 외 1인
C로 배우는 알고리즘, 이재규
http://java2u.wo.to/lectures/etc/ImageProcessing/image_processing0.html
http://viplab.hanyang.ac.kr/~hhlee/reference/ip/mpeg/intro-mpeg-kor.html

블로그 > 광식이의 무선기술동향 이야기