Egloos | Log-in
F/OSS study
F/OSS study
[zlib] DEFLATE algorithm (2) - Huffman coding
zlib: 1.2.5

이전 글 보기:


앞서 살펴본 대로 LZ77 압축 과정을 수행하고 나면 Huffman coding에 사용할 트리를 구성하기 위해
각각의 데이터의 (원문 그대로이든 압축이 되었든) 발생 빈도수를 기록해 두어야 한다.

Huffman coding을 위해 유지해야 할 정보는 다음과 같은 총 3가지이다.
  • literal : 압축되지 않은 경우의 원래 데이터 바이트 (0-255)
  • length : 압축된 경우 일치하는 데이터의 길이 (3-258)
  • distance : 압축된 경우 일치하는 데이터의 시작 위치 (3-MAX_DIST)

이 중 literal과 length 데이터는 동일한 하나의 트리(ltree)로 관리하고
distance 데이터는 별도의 트리(dtree)로 관리하여 코드를 부여하게 된다.
하지만 코드가 너무 분산되어 코드의 길이가 길어지는 막기위해
가능한 모든 범위의 값 마다 코드를 부여하지 않고 일정한 범위로 묶어서 같은 코드를 공유하며,
공유한 데이터를 구분하기 위한 extra bit를 추가적으로 (압축하지 않은 상태로) 사용한다.

예를 들어 ltree의 경우 literal에 256 가지, length에 256 가지 정보가 필요하므로
트리의 전체 코드 수는 512 개가 되어야 하지만, 압축된 length들은 특정한 단위로 묶어서
다음과 같이 285 개의 코드 만 사용하도록 하였다.

    Extra               Extra               Extra
Code Bits Length(s) Code Bits Lengths   Code Bits Length(s)
---- ---- ------    ---- ---- -------   ---- ---- -------
257   0     3       267   1   15,16     277   4   67-82
258   0     4       268   1   17,18     278   4   83-98
259   0     5       269   2   19-22     279   4   99-114
260   0     6       270   2   23-26     280   4  115-130
261   0     7       271   2   27-30     281   5  131-162
262   0     8       272   2   31-34     282   5  163-194
263   0     9       273   3   35-42     283   5  195-226
264   0    10       274   3   43-50     284   5  227-257
265   1  11,12      275   3   51-58     285   0    258
266   1  13,14      276   3   59-66

참고로 0-255까지는 literal 데이터이고 256은 EOB(End-of-Block)를 나타내는 코드로 쓰이며
257의 경우에는 LZ77을 통해 3개의 데이터가 압축된 것을 뜻하고 이 때 extra bit는 필요치 않다.
265의 경우에는 11개 혹은 12개의 데이터가 압축되었으며 이를 구분하기 위해 1비트의 extra bit가 필요하다.

dtree의 경우에도 비슷한 이유로 다음과 같은 코드를 이용한다.

     Extra           Extra               Extra
Code Bits Dist  Code Bits   Dist     Code Bits Distance
---- ---- ----  ---- ----  ------    ---- ---- --------
  0   0    1     10   4     33-48    20    9   1025-1536
  1   0    2     11   4     49-64    21    9   1537-2048
  2   0    3     12   5     65-96    22   10   2049-3072
  3   0    4     13   5     97-128   23   10   3073-4096
  4   1   5,6    14   6    129-192   24   11   4097-6144
  5   1   7,8    15   6    193-256   25   11   6145-8192
  6   2   9-12   16   7    257-384   26   12  8193-12288
  7   2  13-16   17   7    385-512   27   12 12289-16384
  8   3  17-24   18   8    513-768   28   13 16385-24576
  9   3  25-32   19   8   769-1024   29   13 24577-32768

이러한 length code와 distance code로의 변환을 위해 trees.h 파일에
_length_code와 _dist_code라는 테이블이 존재한다.

각 코드의 발생 빈도를 기록하는 작업은 _tr_tally_lit() 및 _tr_tally_dist() 매크로가 수행하는데
먼저 압축되지 않은 원문 그대로인 (literal) 경우를 살펴보면 아래와 같다.

deflate.h:
# define _tr_tally_lit(s, c, flush) \
  { uch cc = (c); \
    s->d_buf[s->last_lit] = 0; \
    s->l_buf[s->last_lit++] = cc; \
    s->dyn_ltree[cc].Freq++; \
    flush = (s->last_lit == s->lit_bufsize-1); \
  }

s의 internal_state 구조체이고 c가 데이터 바이트의 값을 나타내며,
flush는 저장된 버퍼(d_buf, l_buf)가 다 찼는지 검사하기 위한 출력 인자이다.

이 경우 literal을 저장하는 것이므로 이러한 length code 및 distance code를
고려하지 않고 값 자체를 s->dyn_ltree의 인덱스로 이용하고 있음을 볼 수 있다.
또한 distance는 0으로 고려하므로 s->dyn_dtree는 업데이트하지 않는다.

s->d_buf와 s->l_buf는 LZ77 처리 결과를 스트림 내의 순서대로 저장하는 버퍼로
이 후 구성된 Huffman code를 이용해 데이터를 압축할 때 참조하게 된다.
s->last_lit이 s->lit_bufsize-1과 같아지면 이 버퍼가 가득찬 것이므로
버퍼에 저장된 내용을 Huffman code를 통해 압축해서 출력 스트림으로 내보낸다.

LZ77을 통해 압축된 데이터의 경우에는 _tr_tally_dist() 매크로를 이용한다.

#define d_code(dist) \
   ((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)])

# define _tr_tally_dist(s, distance, length, flush) \
  { uch len = (length); \
    ush dist = (distance); \
    s->d_buf[s->last_lit] = dist; \
    s->l_buf[s->last_lit++] = len; \
    dist--; \
    s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \
    s->dyn_dtree[d_code(dist)].Freq++; \
    flush = (s->last_lit == s->lit_bufsize-1); \
  }

이 때 s->dyn_ltree와 s->dyn_dtree를 참조할 때
_length_code와 _dist_code 배열을 통해 인덱스를 계산하는 것을 볼 수 있다.

이렇게 모든 입력 스트림을 다 처리하거나 내부 버퍼가 가득차게 되면
기록된 정보를 이용해 Huffman code를 구성하고 이를 통해 압축을 수행한다.
Huffman coding 알고리즘은 여러 문서에서 다루고 있으므로 자세히 살펴보지는 않겠지만
DEFLATE 알고리즘에서 추가적으로 고려하는 사항들이 존재하므로 언급하고자 한다.

일반적으로 Huffman coding을 위한 트리 생성 시 빈도가 가장 낮은 두 노드를
어떤 순서로 배치하느냐에 따라서 동일한 입력에 대해 다른 Huffman code가 만들어질 수 있다.
zlib에서는 이러한 모호함을 없애기 위해 다음과 같은 엄격한 규칙을 추가하였다.
  • 노드의 높이(즉, 코드의 길이)가 다르다면 낮은 쪽을 왼쪽에 배치한다.
  • 노드의 높이가 같다면 원본 데이터에서 낮은 값을 갖는 쪽을 왼쪽에 배치한다.

이러한 제약 사항이 생기면 각 데이터에 주어진 코드의 길이 정보 만으로
언제라도 동일한 Huffman code를 생성할 수 있게 된다.
따라서 DEFLATE 알고리즘에서는 각 데이터 별로 주어진 실제 코드를 저장하는 대신
코드의 길이 만을 저장하고, 이 후 압축 해제(INFLATE) 시 이를 동적으로 구성하도록 한다.

게다가 이러한 코드 길이 정보 자체도 비슷한 값들이 자주 사용되므로
길이 정보를 다시 한 번 Huffman coding을 이용하여 압축하는데
앞에서와 마찬가지로 다음과 같은 추가적인 정보를 이용한다.
  • 0 : 해당 데이터가 사용되지 않음
  • 1-15 : 실제 코드의 길이에 해당
  • 16 : 바로 이전의 코드 길이를 3-6번 반복. extra bit 2개 필요
  • 17 : 사용되지 않은 데이터(코드 길이 0)가 3-10번 반복. extra bit 3개 필요
  • 18 : 사용되지 않은 데이터가 11-138번 반복. extra bit 7개 필요

이러한 심볼을 가지고 Huffman code를 생성하고 나면
앞서와 마찬가지로 직접 코드를 저장하지 않고 코드 길이 만을 저장하면 된다.

이렇게 압축된 스트림은 복원을 위해 실제 데이터 저장 전에 이러한 코드를 먼저 저장해야 하는데
위에서 본대로 데이터 압축 시 사용한 ltree와 dtree는 물론,
이러한 트리 자체를 압축하기 위한 bltree (bit length tree)도 저장해야 한다.

트리 (코드) 정보는  (bltree는 제외하고) 트리 내의 심볼의 순서대로 코드 길이를 압축된 형태로
저장하는데, 트리 내의 모든 심볼이 사용되지 않았을 수도 있으므로
먼저 사용된 심볼의 수를 다음과 같은 형태로 저장한다.

 5 Bits: HLIT,  # of Literal/Length codes - 257 (257 - 286)
 5 Bits: HDIST, # of Distance codes - 1         (1 - 32)
 4 Bits: HCLEN, # of Code Length codes - 4      (4 - 19)

다만 코드 길이의 경우는 0-18까지의 심볼을 순서대로 저장하지 않고
자주 사용되는 순서에 따라 다음과 같은 순으로 저장한다.

16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15

19개의 심볼 각각에 대해 8비트 이상의 코드가 주어지지는 않을 것이므로
심볼의 코드 길이를 저장하기 위해서는 3비트의 공간이면 충분하다.

그렇다면 bltree를 저장하기 위해 (HCLEN+4)*3비트가 필요하고
dtree와 ltree는 bltree에 부여된 코드를 통해 (HLIT+257) + (HDIST+1)개의 심볼을
저장하므로 정확한 비트 수는 알 수 없지만 어느 정도의 공간이 필요해진다.

따라서, 압축률이 그리 좋지 못한 경우 트리 자체를 저장하기 위한 공간으로 인해
압축된 크기가 별 차이가 없는 경우가 발생할 수 있을 것이다.
DEFLATE 알고리즘은 이러한 경우를 대비하여 압축 방식을 3가지 중 하나로 선택할 수 있게 하였다.
압축된 데이터를 저장하는 블록의 첫 3비트 중 2비트는 이를 구분하기 위한 것으로
다음과 같은 값 중의 하나를 가진다.
  • 00 : 압축하지 않은 블록
  • 01 : fixed Huffman code를 이용하여 압축한 블록
  • 10 : dynamic Huffman code를 이용하여 압축한 블록
  • 11 : 사용하지 않음 (에러로 처리)

00은 전혀 압축을 수행하지 않고 입력 데이터를 그대로 출력으로 내보내는 경우이다.
초기화 루틴에서 level을 0으로 지정한 경우 항상 이러한 타입의 블록을 출력한다.
01은 DEFLATE 알고리즘 자체에서 정해둔 Huffman code를 이용하는 경우이다.
따라서 트리 정보 자체를 저장할 필요가 없으므로 약간의 공간을 줄일 수 있지만
입력 데이터에 따른 최적의 코드가 생성된 것이 아니기 때문에
데이터 자체의 압축률은 그리 좋지 않을 수도 있다.
10은 위에서 본 살펴본 방식으로 생성한 트리를 이용하는 것이다.
(위에서 데이터 발생 빈도를 검사할 때 사용한 트리 이름이 dyn_[ld]tree였다는 것을 기억하자)
11은 나중을 위해 예약해 둔 값으로, 지금은 사용하지 않으며 만약 사용되었다면 에러로 처리한다.

01 타입의 블록에서 사용하는 fixed Huffman code는 다음과 같다.

 Lit Value    Bits        Codes
 ---------    ----        -----
   0 - 143     8          00110000 through
                          10111111
 144 - 255     9          110010000 through
                          111111111
 256 - 279     7          0000000 through
                          0010111
 280 - 287     8          11000000 through
                          11000111

zlib은 위의 3가지 방식 중 어느 것을 이용할 지 결정하기 위해
트리 코드 생성 시 결정된 코드 길이와 해당 데이터의 발생 빈도를 곱하고
또한 고정된 코드 길이 및 발생 빈도를 곱하여 해당 방식을 이용할 때 생성될 코드의 길이를 계산하고
원본 데이터의 길이와 비교하여 (참고로 00 타입은 블록의 길이를 저장하기 위한 4바이트가 추가된다)
이 중 가장 작은 값을 가지는 방식을 선택한다.

=== 참고 문헌 ===


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

제목 : [zlib] API 사용법
zlib: 1.2.5 이전 글 보기: [zlib] DEFLATE algorithm (1) - LZ77[zlib] DEFLATE algorithm (2) - Huffman coding 앞서 zlib에서 사용하는 알고리즘에 대해서 살펴보았으니 이번에는 실제로 zlib의 API를 사용하는 방법에 대해서 살펴보고자 한다. 여기서도 압축 및 해제 시 사용법이 거의 비슷하기 때문에 압축을 수행하는 과정 만을 살펴볼 것이다. 가장 기본적인......more

Commented at 2016/03/17 22:46
비공개 덧글입니다.

:         :

:

비공개 덧글

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

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

최근 등록된 덧글
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