Egloos | Log-in
F/OSS study
F/OSS study
[zlib] DEFLATE algorithm (1) - LZ77
zlib: 1.2.5


zlib은 범용 무손실 압축 알고리즘(DEFLATE)을 이용한 압축/해제 라이브러리로
특허에 영향을 받지 않았기 때문에 널리 사용되어 왔다.
(구체적으로, *nix 계열의 기본(?) 압축 도구인 gzip이 이를 이용한 것이다.)

DEFLATE 알고리즘은 RFC 1951로 공개되어 있으며
내부적으로는 LZ77 압축 알고리즘과 Huffman coding을 차례로 적용한 것이므로
이들 압축 방식에 대해서 각각 살펴보기로 한다.

LZ77 압축 알고리즘은 Abaraham Lempel과 Jacob Ziv가 1977에 발표한 것으로
(LZ77이라는 이름은 발표자들의 성의 첫 글자와 발표년도를 합친 것이다.)
사전 기반의 압축 방식이며 여러 LZ* 알고리즘의 기본이 된다.

압축을 해제하는 과정은 단지 압축을 수행하는 과정의 역순이기 때문에
이 후로는 별도의 설명이 필요치 않는 한 압축을 수행하는 과정에 대해서만 살펴볼 것이다.

LZ77의 기본 개념은 현재 압축하려는 데이터가 이전에 존재했었는지를 알아보고
그렇다면 전체 정보를 기록할 필요없이 해당 데이터가 반복된다고만 표시하는 것이다.
(따라서 첫 부분에 나오는 데이터는 - 별도의 사전이 주어지지 않는 한 - 압축할 수가 없다.)

하지만 실질적으로 이전의 데이터를 모두 보관하고 있는 것은 불가능(?)하므로
정해진 크기만큼의 데이터만을 보관하며, 이는 새로운 데이터를 압축할 때마다
조금씩 이동되므로 sliding window라고 부른다.
(정해진 공간 내에 새로운 데이터가 들어오면 그 만큼의 예전 데이터는 나가야 한다.
이는 데이터 스트림을 고정시켜 두고 보면 해당 공간(window) 자체가
옆으로 미끄러지며 이동(sliding)하는 것처럼 생각할 수 있을 것이다.)

또한 sliding window 내의 데이터들은 현재 데이터를 압축할 때 참고하기 때문에
압축된 코드의 원문을 기록한 일종의 사전이라고도 볼 수 있다.
데이터의 기본 단위는 1바이트(8비트)이며 현재 데이터로부터 시작하여
일치하는 최대한 긴 길이의 데이터 sequence를 sliding window 내에서 찾은 후
(일치한 길이, 시작 위치)의 쌍을 기록한다.

위에서 본 대로 sliding window의 위치는 계속 변경되므로,
시작 위치는 현재 데이터의 위치로부터 sliding window 내의 데이터 시작 위치에 이르는
(역방향) 상대 거리를 저장하도록 한다. 압축된 데이터의 크기는 일치한 길이 및 시작 위치를
저장할 수 있는 범위에 따라 달라지지만 기본적으로 3바이트 정도는 차지하기 때문에
일치하는 데이터의 길이가 3바이트 미만이라면 압축을 수행하지 않는 것이 더 효율적이다.

sliding window 내의 데이터들은 압축되지 않은 원본 그대로의 상태로 참조하므로
압축된 데이터는 별도의 버퍼에 저장해야 한다. LZ77이 압축을 수행하기 위해
데이터를 입력받으면 이는 압축 여부에 상관없이 처리된 크기 만큼 sliding window로 포함된다.

이제 실제 zlib에서 처리하는 과정을 살펴보기로 한다.
먼저 처리할 데이터를 표현하기 위해 z_stream이라는 자료 구조를 사용한다.
z_stream은 사용자와 zlib이 함께 관리하는 것으로 중요한 필드만 뽑아내면 다음과 같다.

zlib.h:
typedef struct z_stream_s {
    Bytef    *next_in;  /* next input byte */
    uInt     avail_in;  /* number of bytes available at next_in */
    ...
    Bytef    *next_out; /* next output byte should be put there */
    uInt     avail_out; /* remaining free space at next_out */
    ...
    struct internal_state FAR *state; /* not visible by applications */
    ...
} z_stream;

next_in은 입력받을 데이터가 저장된 버퍼를 가리키며 avail_in은 입력 버퍼 내의 바이트 수이다.
마찬가지로 next_out과 avail_out은 (압축된) 데이터가 저장될 버퍼와 바이트 수를 나타낸다.
이 값들은 zlib이 데이터를 처리할 때마다 갱신되며 avail_in이 0이 되면
zlib을 이용하는 외부 프로그램이 zlib에게 다음 (입력) 데이터 스트림을 제공해주어야하며,
avail_out이 0이 되면 외부 프로그램이 압축된 데이터를 별도의 공간으로 옮기거나
적절한 처리를 하여 출력 버퍼를 비워주어야 한다.

내부적인 처리를 위한 정보들은 state 필드가 가리키는 internal_state 구조체에 저장된다.
sliding window의 크기는 2의 거듭제곱 형태이며, 기본값은 최대 크기인 32K(2^15)가 사용된다.
이 값은 압축 초기화 루틴에서 변경할 수 있으며, 이 때 (2의) 지수 만을 넘기면 된다.

sliding window의 탐색은 가장 단순하게 구현한다면
매번 전체 윈도우 내의 데이터를 모두 검색하도록 할 수 있겠지만 이는 매우 비효율적이므로
실제로는 입력 데이터에 대한 해시값을 계산하여 데이터가 나타난 위치를 해시 테이블에 유지한다.
해시 테이블의 크기도 2의 거듭제곱 형태이며, 기본값은 최대 크기인 32K가 사용된다.
마찬가지로 이 값도 초기화 루틴에서 변경 가능하며, 이 때 (지수 - 7) 값을 넘겨야 한다.

또한 해시 충돌 문제를 해결하기 위해 해시에는 가장 최근에 일치한 데이터의 위치만을 보관하고
이전에 일치한 위치들은 별도의 배열에 저장하여 탐색할 수 있도록 하였다.

다음은 위에서 설명한 자료 구조를 포함하는 internal_state 구조체의 일부이다.

deflate.h:
typedef struct internal_state {
    ...
    Bytef *window;
    /* Sliding window. Input bytes are read into the second half of the window,
     * and move to the first half later to keep a dictionary of at least wSize
     * bytes. With this organization, matches are limited to a distance of
     * wSize-MAX_MATCH bytes, but this ensures that IO is always
     * performed with a length multiple of the block size. Also, it limits
     * the window size to 64K, which is quite useful on MSDOS.
     * To do: use the user input buffer as sliding window.
     */

    ulg window_size;
    /* Actual size of window: 2*wSize, except when the user input buffer
     * is directly used as sliding window.
     */

    Posf *prev;
    /* Link to older string with same hash index. To limit the size of this
     * array to 64K, this link is maintained only for the last 32K strings.
     * An index in this array is thus a window index modulo 32K.
     */

    Posf *head; /* Heads of the hash chains or NIL. */

    uInt  ins_h;          /* hash index of string to be inserted */
    ...
} FAR deflate_state;

sliding window는 window 필드가 가리키며 이는 z_stream.next_in 버퍼를 직접 이용하지 않고
별도의 버퍼를 할당해서 사용한다. 실제로 할당된 크기는 지정한 윈도우 크기보다 2배 큰데,
앞쪽 절반에는 실제 sliding window가 채워지며 뒤쪽 절반에는 처리할 데이터가 차례로 입력되므로
이 크기 내에서는 (시작 offset만 증가시켜) 실제로 window를 slide 시킬 수 있다.
따라서 window_size에는 1 << (windowBits+1) 값이 저장된다.

prev 필드는 sliding window 내의 현재 해시값과 일치하는 예전 위치들을 저장하는 배열이며
head 필드는 해시 테이블을 가리키고, ins_h는 현재 입력된 데이터에 대한 해시값을 저장한다.

앞서 말한대로 압축을 위해서는 최소 연속된 3개의 데이터가 일치해야 하므로
해시값을 계산할 때도 3 바이트의 데이터를 이용한다.
즉, 다음 바이트와 다다음 바이트의 값을 미리 이용하여 해시값을 계산한다.

#define MIN_MATCH  3

#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)

#define INSERT_STRING(s, str, match_head) \
   (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
    match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
    s->head[s->ins_h] = (Pos)(str))

INSERT_STRING 매크로는 새로운 데이터를 처리할 때 호출되는 것으로
s는 internal_state 구조체, str은 s->window 내의 해당 데이터의 인덱스를 나타내며,
match_head 인자는 해당 데이터를 이용해 계산한 해시값에 해당하는 위치,
즉 이전에 동일한 3바이트 (이상)의 데이터가 존재했던 위치를 알아내기 위한 출력 인자이다.

먼저 UPDATE_HASH 매크로를 호출하여 해시값을 계산하는데 이 때 s->window[str]이 아닌
s->windows[str + 2]에 해당하는 (다다음) 데이터를 인자로 전달한다.
때문에 최초 해시 테이블 구성 시 맨처음 2 바이트는 수동으로 입력해 주어야 하며
이를 위해 다음과 같은 코드가 사용된다.

s->ins_h = s->window[0];
UPDATE_HASH(s, s->ins_h, s->window[1]);

이 후의 3번째 바이트부터는 정상적으로 INSERT_STRING 매크로를 이용할 수 있다.
그리고 해시 테이블에 저장된 위치를 각각 prev와 match_head 인자에 저장한 뒤
해시 테이블을 현재 위치로 업데이트한다.

zlib의 압축 루틴은 초기화 시 지정한 level과 strategy 인자에 따라 달라지는데
우선 여기서는 Z_DEFAULT_STRATEGY에 대해서만 고려할 것이다.
주어진 level 값은 LZ77 수행 시 검사할 데이터 검사에 연관된 여러 매개 변수들을 조정한다.

deflate.c:
typedef struct config_s {
   ush good_length; /* reduce lazy search above this match length */
   ush max_lazy;    /* do not perform lazy search above this match length */
   ush nice_length; /* quit search above this match length */
   ush max_chain;
   compress_func func;
} config;

local const config configuration_table[10] = {
/*      good lazy nice chain */
/* 0 */ {0,    0,  0,    0, deflate_stored},  /* store only */
/* 1 */ {4,    4,  8,    4, deflate_fast}, /* max speed, no lazy matches */
/* 2 */ {4,    5, 16,    8, deflate_fast},
/* 3 */ {4,    6, 32,   32, deflate_fast},

/* 4 */ {4,    4, 16,   16,  deflate_slow},  /* lazy matches */
/* 5 */ {8,   16, 32,   32,  deflate_slow},
/* 6 */ {8,   16, 128, 128,  deflate_slow},
/* 7 */ {8,   32, 128, 256,  deflate_slow},
/* 8 */ {32, 128, 258, 1024, deflate_slow},
/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */

config 자료 구조의 필드들은 lazy search (혹은 lazy evaluation)와 관련이 있다.
lazy search는 sliding window 내에 일치하는 데이터가 존재할 때
이를 바로 압축에 적용하는 것이 아니라 다음 데이터로부터 시작하는 데이터 또한
일치하는지 검사하여 더 긴 것을 선택하는 방법이다.

즉, 다음과 같은 상황일 때 ABC가 아닌 BCDEFGH를 선택하기 위한 것이다.

<-- sliding window -->   !
......ABCBCDEFGH......   ABCDEFGH
      |                  |
      +------- d --------+

압축된 데이터를 저장하는데 3바이트가 필요하다고 가정하면
lazy search를 통해 다음과 같이 2바이트를 더 줄일 수 있다.

ABC + DEFGH  ==>  (3,d) + (5,d-2) : 6
A + BCDEFGH  ==>  A + (7,d-2)     : 4

실제로 zlib에서는 일치한 길이와 시작 위치(거리)를 위해 각각 1, 2바이트 정도의 공간을 사용한다.
(사실은 Huffman coding으로 인해 다시 압축되므로 정확한 크기는 데이터에 따라 달라진다.)
따라서 길이의 범위는 0-255이지만 최소 길이가 3이므로 이를 더하면 3-258이 되고,
시작 위치의 최대값은 sliding window의 크기보다 약간 작은 값으로 설정된다.

#define MAX_MATCH  258

#define MAX_DIST(s)  ((s)->w_size-MIN_LOOKAHEAD)
/* In order to simplify the code, particularly on 16 bit machines, match
 * distances are limited to MAX_DIST instead of WSIZE.
 */

이제 다시 config 자료 구조의 필드를 살펴보도록 하자.
먼저 nice_length는 zlib이 만족하는 데이터의 길이로, sliding window 탐색 시
해당 길이보다 긴 데이터가 일치하면 이를 최적으로 생각하고 탐색을 종료한다.
max_chain은 sliding window 탐색 시 참조할 해시 테이블의 체인의 최대 길이이다.
즉, nice_length보다 긴 일치하는 데이터를 찾지 못하면 최대 max_chain번 만큼
s->prev 배열을 참조하여 탐색을 시도한다.

max_lazy는 lazy search를 시도할 최대 길이로, 현재 찾은 데이터가 이보다 길다면
lazy search를 적용하지 않고 곧바로 압축한다.
good_length는 lazy search 시의 탐색 overhead를 낮추기 위한 값으로,
현재 찾은 데이터가 이보다 길다면 lazy search 시 max_chain을 1/4로 줄인다.

위에서 볼 수 있듯이 level 9의 경우에는 항상 lazy search를 수행하며
저장할 수 있는 최대 길이만큼 일치하는 경우를 제외하고는
항상 모든 체인을 검사하도록 탐색을 수행하므로 최대의 압축 효율을 얻을 수 있게 된다.

level 값이 4보다 작은 경우에는 이와는 조금 다르게 동작하는데
먼저 level 0일 때 사용되는 deflate_stored() 함수는 전혀 압축을 수행하지 않는다.
1-3일 때 적용되는 deflate_fast() 함수는 lazy search를 적용하지 않으며
대신 이 때 max_lazy 필드를 max_insert_length로 해석하여
일치한 데이터가 이 보다 길다면 해시 테이블 (및 그 체인)에 저장하지 않는다.

level의 기본 값으로는 6을 이용한다.

strategy의 경우 압축을 수행할 전략을 나타내는 것인데 다음과 같은 값들을 이용할 수 있다.
  • Z_DEFAULT_STRATEGY : 위에 살펴본 LZ77 압축 및 Huffman coding을 수행한다.
  • Z_FILTERED : 입력 데이터가 특정한 확률 분포를 가지는 작은 값들의 집합이라고 생각하고, 일치하는 짧은 데이터에 대해서는 LZ77 압축을 수행하지 않고 직접 Huffman coding을 적용하도록 한다.
  • Z_HUFFMAN_ONLY : LZ77 압축을 전혀 수행하지 않고 Huffman coding만을 수행한다.
  • Z_RLE : RLE(Run-Length Encoding)를 수행하고 Huffman coding을 수행한다. RLE는 LZ77에서 일치하는 데이터의 시작 위치가 1인 경우 만을 허용하는 것과 같다.
  • Z_FIXED : Huffman coding 수행 시 미리 정해진 code(tree)를 이용한다.

이렇게 LZ77로 처리한 데이터들은 Huffman coding을 위해 각각의 발생 빈도를 기록한다.
이 후에 이어지는 Huffman coding에 대한 부분은 다음 글에서 살펴볼 것이다.


=== 참고 문헌 ===

by namhyung | 2010/07/10 20:09 | General | 트랙백(2) | 덧글(0)
트랙백 주소 : http://studyfoss.egloos.com/tb/5355158
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Tracked from F/OSS study at 2010/07/12 00:48

제목 : [zlib] DEFLATE algorithm (2)..
zlib: 1.2.5 이전 글 보기: [zlib] DEFLATE algorithm (1) - LZ77 앞서 살펴본 대로 LZ77 압축 과정을 수행하고 나면 Huffman coding에 사용할 트리를 구성하기 위해 각각의 데이터의 (원문 그대로이든 압축이 되었든) 발생 빈도수를 기록해 두어야 한다. Huffman coding을 위해 유지해야 할 정보는 다음과 같은 총 3가지이다. literal : 압축되지 않은 경우의 원래 데이......more

Tracked from at 2014/03/11 00:35

제목 : garcinia cambogia reviews
line6...more

:         :

:

비공개 덧글

◀ 이전 페이지 다음 페이지 ▶

카테고리
General
Application
System
Kernel
Book
Tips
태그
block-layer SMP script git CAaQA3 emacs awk blktrace C perf glibc binutils memory synchronization gcc kernel sed patch CARM elf x86 vcs linux documentation computer-architecture bash algorithm compiler scm build
전체보기
이글루 파인더

최근 등록된 덧글
informsi yang bagus dan be..
by pordanaia at 08/05
Informsi yang bagus dan b..
by jamalsu at 08/01
as inforasi yang menarik http..
by jamalsu at 07/22
최근 등록된 트랙백
Tod's Ferrari Homme
by Tods Pas Cher,Kodak did ..
Mocassin Femme
by Mocassins Homme, I got so..
natural garcinia cambogia
by
rss

skin by jiinny


X