압축 풀때 사용되는 Deflate 알고리즘.

안녕하세요 Geeks_Company 입니다. 

현재 unzip 관련된 모듈 제작 중입니다. (프로젝트 중이므로 짬짬히 합니다 ^^)

일단 , 관련된 알고리즘은 RFC 1951에서 설명한 것을 참조 합니다.

http://tools.ietf.org/html/rfc1951



압축을 풀때 사용되는 방식은 크게 4가지가 있습니다.

            00 - no compression ( 비 압축 )
            01 - compressed with fixed Huffman codes ( 고정된 허프만 코드 방식의 압축 )
            10 - compressed with dynamic Huffman codes ( 동적 허프만 코드 방식의 압축 )
            11 - reserved (error) (예약 - 에러)


이글에서 설명할 부분은 01 번 고정된 허프만 코드 방식입니다. 

일반적인(General) 방식의 압축 풀시에 사용되는 알고리즘 입니다. 


  do
               read block header from input stream.
               // 입력 스트림에서 블럭의 헤드 부분을 읽습니다. 

               if stored with no compression
               // 비 압축 방식일 경우

                  skip any remaining bits in current partially                  
                     processed byte
                  // 현재 진행인 바이트 중 남은 비트를 Skip 합니다.

                  read LEN and NLEN (see next section)
                  // Len 을 읽고 NLen을 읽습니다. 

                  copy LEN bytes of data to output
                  // Len byts 만큼의 Data를 복사 합니다. 



               otherwise
               // 비 압축이 아닐 경우 ( 고정, 동적 방식의 허프만 코드 )

                  if compressed with dynamic Huffman codes
                 // 동적 허프만 방식 으로 압축된 방식일 경우

                     read representation of code trees (see
                        subsection below)
                     // 코드 트리를 읽어 들입니다.

                  loop (until end of block code recognized)
                  //  마지막 블락을 만날때까지 반복 합니다 ( value == 256 )

                     decode literal/length value from input stream
                     // 입력값으로 부터 문자열/길이 를 풀어 냅니다. 

                     if value < 256
                     // 값이 256 보다 적다면

                        copy value (literal byte) to output stream
                        // 출력에 현재 값을 저장 합니다. (256보다 적은것은 0 - 255 값이므로 해당 값을 적으면 됩니다.)

                     otherwise
                     // 값이 256 보다 크다 면?

                        if value = end of block (256)
                           break from loop
                        // 값이 256이면 Loop 구문을 빠져 나갑니다.

                        otherwise (value = 257..285)
                        // 값이 257 ~ 285 이면    (실제로 사용 되는 값의 범위는  287 까지 이지만, 286 ~ 287 은 비 사용)

                           decode distance from input stream
                           // distance를 풀어 냅니다.

                           move backwards distance bytes in the output
                           stream, and copy length bytes from this
                           position to the output stream.
                           // 출력에서 뒤로 distance만큼 이동한후, 위에서 풀어 낸 길이 만큼
                           // 현재 포지션에서 복사를 합니다. 

                  end loop
            while not last block



쉽게 적으면,

1. 압축된 데이터를 읽습니다.
2. 압축된 데이터를 디코딩 해서 값을 얻습니다.
3. 값이 256보다 적으면, ASCII 코드 값의 범위는 255까지 이니, 고스란히 복사를 합니다.
4. 값이 256과 같으면 종료 합니다.
5. 값이 256보다 크면, Len 과 distance를 토대로 값을 반복해서 적습니다.


압축 방식에 사용되는 방식은 LZ77 (distance 와 length 기반) 과 Huffman Code 법입니다.

오늘은 여기까지 적고 다음에는 예시를 따라서 Decoding 하는 법을 보여 드리겠습니다.