블로그는 귀차니즘

  앞서 적었던 RLE8 인코딩과 더불어 많이 알려진 LZSS 압축입니다. 이 것은 1982년 James Storer와 Thomas Szymanski가 원래의 LZ77형 압축 방법에 대해서 개량을 하여 만든 방법이랍니다. 흔히 LZ 압축 방식들이 사전압축 방식을 가지고 있는데, 이 LZSS 압축 또한 마찬가지로 사전 압축을 사용합니다.
  LZSS 압축의 디코드 코드는 아래와 같습니다.

LZSSDecode.cpp (Language : cpp)

1. #include <vector>
2.  
3. const unsigned int MinLength    = 3;
4. const unsigned int MinIndex  = 1;
5.  
6. template< typename DataIterator >
7. void LZSSDecompress( DataIterator CompressData, unsigned int CompressDataLength, std::vector< unsigned char > &DecompressData )
8. {
9.     unsigned int Index;
10.     unsigned int Length;
11.  
12.     unsigned char CompressFlag;
13.  
14.     for( unsigned int i = 0; i < CompressDataLength; ++i )  {
15.        
16.         CompressFlag = *CompressData;
17.         ++CompressData;
18.  
19.         for( int Shift = 0; Shift < 8; ++Shift )    {
20.            
21.             if( ( CompressFlag << Shift ) & 0x80 )  { // 데이터 압축 여부
22.                
23.                 Length  = ( *CompressData >> 0x04 ) + MinLength;
24.                 Index   = ( ( *CompressData & 0x0F ) << 0x08 ) + MinIndex;
25.                 ++CompressData;
26.                 Index   += *CompressData ;
27.                 ++CompressData;
28.  
29.                 std::vector< unsigned char >::iterator Iter = DecompressData.end();
30.                 DecompressData.insert( Iter, Iter - Index, Iter - Index + Length );
31.  
32.                 i += 2;
33.             }
34.             else    {
35.                
36.                 DecompressData.push_back( *CompressData );
37.                 ++CompressData;
38.  
39.                 ++i;
40.             }
41.         }
42.     }
43. }

  이 압축 방식은 웹사이트에서 검색하시면 쉽게 아시겠지만 [압축플래그][데이터]x8 개의 구조로 나뉩니다. 보통의 압축플래그는 8비트이며, 하나의 비트가 0,1의 차이에 의하여 압축된 데이터냐 보통 데이터냐로 구분되죠. 만약 플래그비트가 0이라면 그냥 1바이트를 대상데이터에 복사하면 되며, 1이라면 사전을 이용한 디코딩을 처리해주어야 합니다. 그 사전 코드는 보통 Length, Index 필드를 참조하여 처리하는데, Length 필드는 4비트, Index 필드는 12비트를 사용합니다.
  단순하게 생각하면 2*2*2*2로 길이가 16, 2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2로 길이가 4096 일 것이라 생각하지만 하나의 비트라도 아끼기 위하여 보통 Length와 Index 에 값을 넣을때에는 정해진 숫자를 빼게됩니다. 이 코드에서는 압축된 데이터가 2바이트 이므로 적어도 길이는 3이어야 하겠고, Index 는 한 칸 앞을 전제로 하게 되니 1을 빼게 되는 것입니다. 그래서 MinLength와 MinIndex 가 3과 1이 되는 것이고 실제 디코딩에서는 더해주어야 하죠.
  그리고 압축을 해제할 때 가장 중요한 디코딩 부분은 Length 와 Index 를 얻게 되었으므로 압축이 해제된 데이터필드에서 Index 만큼 앞으로 이동하여 Length 만큼을 가지고와서 데이터를 더해줍니다. 즉, 데이터가 ABCDEFGHIJKLMNOPQRSTUVWXYZ가 있는데 Index가 3, Length가 2라면 맨 끝에 XY가 추가되는 것이죠.
  이 코드를 보면 LZSS 압축이 무척 쉽게 보일겁니다. 이렇게 디코딩 코드는 간편히 작성할 수 있죠. 하지만 인코딩 코드는 Sliding Window를 비롯하여 신경 써주어야 할 것들이 있습니다. 나름 까다로운 코드가 될 수 있겠네요.

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.