[zlib] deflate algorithm에 대해서

1.

deflate는 압축이다.

2. 

압축 연산은 3가지의 함수로 이루어 진다.

    deflateInit - 메모리 할당 및 내부 상태 변수 할당

    deflate - 실제 압축

    deflateEnd - 할당 메모리 소거

3.

z_stream stream;

stream.zalloc = Z_NULL; // 메모리를 할당하는 함수를 지정해 달라는 것, 함수 포인터를 넣어야한다. 기본적으로 사용하는 메모리 할당을 사용하겠단 것이다.

stream.zfree = Z_NULL; // 메모리를 해제할 때 사용하는 함수 포인터를 설정

stream_opaque = Z_NULL; //함수 포인터의 아규먼트를 전달 하도록 되어 있다.

이 3 인자는 하나로 돌아가는 연관이 되어 있다.

deflateInit( &stream, 

                 z스트림    압축 level

,,,, 쓰다 보니깐 이건 그냥 함수 사용법이다. 이건 널리고 널린것.

다시

1.

Deflate는 데이터 압축 알고리즘이다.LZ77 알고리즘과 Huffman coding을 합친것이다.

2.

우선 LZ77에 대해서 살펴본다.

3.

DEFLATE알고리즘은 RFC 1951로 공개되어 있으며 내부적으론 LZ77 압축 알고리즘과 Huffman coding을 차례로 적용한 것이다.

압축을 해제하는 과정은 단지 압축을 수행하는 과정의 역순이다.

LZ77의 기본 개념은 현재 압축하려는 데이터가 이전에 존재했었는지를 알아보고, 그렇다면 전체 정보를 기록할 필요없이 해당 데이터가 반복된다고만 표시하는 것이다.

...

( http://studyfoss.egloos.com/5355158 )

4.

참고 문헌

http://zlib.net/feldspar.html

http://blueh.blog.me/150016691928

5.

여기서 정말 친절히 설명해주었다.

http://blog.daum.net/aswip/4443541

6.

그래도 뭔가 어중되다. 외국 사이트에 들어가서 한번 본다.

( http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lz77.html )

인코딩 알고리즘은 아래와 같다.

1. 입력 stream의 맨 처음 coding position으로 위치한다.

2. Window에서 lookaheadbuffer를 위한 가장 긴 매치를 찾는다.

3. (P, C)로 output을 낸다.

    P는 윈도우의 포인터이다.

    C는 lookahead buffer의 일치하지 않는 첫번째 캐릭터이다.

4. 만약 lookahead buffer가 비어있지 않다면, 코딩 포지션을 L+1 캐릭터만큼 이동하고 step2로 돌아간다.

예를 하나 들어보자,

    ● Step은 encoding step을 나타낸다.이것은 각각의 순간에 encoding algorithm이 만들어낸 output을 의미한다.

    ● Pos는 coding position을 의미한다. 맨 처음 문자는 coding position을 1로 갖는다.
    ● Match는 가장 길게 매치된 window를 나타낸다.
    ● Char 는 매치되는 문자열 이후의 lookabead buffer의 첫번째 문자를 나타낸다.
    ● Output은 format (B,L) C로 나타낸다

        - (B,L)은 Match로의 pointer (P)이다. 이러한 구조는 다음과 같이 디코딩된다.

           " 윈도우의 B캐릭터로 가라 그리고 L캐릭터를 output으로 복사해라. "

        - C는 명시적인 캐릭터이다.

Input stream for encoding :

Pos	1	2	3	4	5	6	7	8	9
Char	A	A	B	C	B	B	A	B	C

Table 1 : 인코딩 프로세스

Step	Pos	Match	Char	Output
1.	1	--	A	(0,0) A
2.	2	A	B	(1,1) B
3.	4	--	C	(0,0) C
4.	5	B	B	(2,1) B
5.	7	A B	C	(5,2) C

디코딩

Window는 encoding과 동일하게 유지된다. 각각의 스텝에서 알고리즘은 input으로 부터 (P, C)의 쌍을 읽는다. 이것은 윈도우로부터 P와 C로 명시되는 연결을 출력한다.

7.

번역은 했는데 좀더 연습해서 완전히 이해해야겠다.