블로그는 귀차니즘

First Sensation
  • 공지
  • 지역로그
  • 태그
  • 방명록

LZSS - Lempel Ziv Storer Szymanski 압축

Programming 2008/02/25 19:10 귀차니스트

  앞서 적었던 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를 비롯하여 신경 써주어야 할 것들이 있습니다. 나름 까다로운 코드가 될 수 있겠네요.
크리에이티브 커먼즈 라이센스
Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

"Programming" 분류의 다른 글

Script Interpreter - boost::spirit (0)2010/03/09
Gradient에 대한 정리 (2)2009/01/07
한게임 자동테트리스 Ver 0.6 (40)2008/11/15
한게임 자동테트리스 Ver 0.2 (27)2008/11/03
Read Sector From Floppy (0)2008/07/17
2008/02/25 19:10 2008/02/25 19:10
TAG Decode, LZSS, 디코드, 디코딩, 압축
받은 트랙백이 없고, 댓글이 없습니다.

트랙백 주소 :: http://www.filewiki.net/tc/trackback/17

댓글을 달아 주세요

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

블로그 이미지
First Sensation 귀차니스트
rss
  • 관리자
  • 글쓰기

카테고리

  • 전체 (118)
    • Computer (3)
    • Language (14)
    • Reverse Engineering (1)
    • Algorithm (9)
    • TopCoder (3)
    • Library (2)
    • Programming (21)
    • Programming Tip (9)
    • PSP-Programming (10)
    • Program (5)
    • Small Talk (33)
    • Document (4)
    • OS Develope (4)

최근에 올라온 글

  • Script Interpreter - b....
  • VirtualHttpServer - 가.... (2)
  • 음.. 여러가지 일이 있.... (2)
  • 어후.. 드디어 인터럽트....
  • Kernel Image에 어이없....

최근에 달린 댓글

  • 헠 ㅋ 다음에도 들러주세용 ㅋㅋ. 귀차니스트 03/09
  • ㅎㅎ RSS로 첨 온 글이네.ㅋ. 당구리 02/22
  • 음.. 한글화 파일 0.5 버젼은.... 귀차니스트 02/22
  • 관리자만 볼 수 있는 댓글입.... 비밀방문자 01/30
  • 어떤 의미이신지 잘 모르겠네.... 귀차니스트 01/23

달력

«   2010/03   »
일 월 화 수 목 금 토
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      

링크

  • kkamagui 프로그래밍 세상.
  • runner님의 이글루.
  • 당구리의 마굿간.
  • 동우fly.
  • 류광의 번역 이야기.
  • 서광열의 프로그래밍 언....
  • 준호씨의 블로그.
  • 최익필의 이름없는 블로그.
  • 위키는 귀차니즘.

최근에 받은 트랙백

  • 한게임 테트리스 인공지.... 고니's Life 2009
  • ACM 706 (Uva ID) : LCD.... 알고리즘 트레이닝 : Oh... 2009
  • 문제 4 : LCD 디스플레.... 최익필의 이름없는 블로그 2009
  • 궁극의 예외처리. 이름없는 블로그 2008
  • Maximum sum. 티스토리 지점 2008

글 보관함

  • 2010/03 (1)
  • 2010/02 (1)
  • 2010/01 (1)
  • 2009/12 (3)
  • 2009/08 (1)

태그목록

  • 관악기
  • boost
  • TTF
  • istream_iterator
  • 어쌔신 크리드
  • 탑코더
  • Pangya
  • interface design guide
  • Borland
  • ostream_iterator
  • Singleton
  • As Casting
  • PSP
  • 프로그래밍
  • Develope
  • 컬러체험단
  • OTF
  • Compiler
  • Textcube
  • 동방환상마작
  • TShell
  • 전위연산
  • COM
  • boost::random
  • Library
  • HTML Parser
  • Parent
  • Interface
  • Generics
  • 분양

지역로그 : 태그 : 방명록 : 관리자 : 글쓰기
귀차니스트’s Blog is powered by Textcube 1.7.5 : Risoluto / Designed by DesignNia.net