Search This Blog

Saturday, August 1, 2009

7-zip 이야기

7-zip logo

과거 7-zip의 압축 효율은 뛰어나지만 압축 및 압축해제 속도에서 속도가 다른 압축 solution에 대해서 뒤쳐져 있었습니다. 하지만 최근 압축 및 압축 해제 속도 또한 인상적인 진보가 보고 되고 있으며 많은 사용자를 확보해 가고 있습니다. 그렇다면 7-zip이 data compression format에서 best 일까요?

지금까지 압축 알고리듬은 run-length encoding (RLE), dictionary coders, Burrows-Wheeler transform(BWT), prediction by partial matching (PPM) 등의 method가 개발되어져 왔습니다. 이러한 알고리듬은 entropy encoding과 결합이 되는데 지금까지 Huffman coding과 arithmetic coding 등이 개발되 왔습니다.

RLE는 symbol과 symbol의 count만을 저장하는 고전적인 method입니다.
Dictionary coder는 dictionary에 있는 string들을 찾아서 더 짧은 string으로 치환합니다. LZ 계열이 대표적인 예이며, zip 등이 대표적인 application입니다.
BWT는 source data를 permutation했을때 압축에 용이한 pattern이 더 많이 발생할 수도 있다는 사실에 근거하여 압축전 permutation을 합니다. 대표적인 application으로는 bzip2가 있습니다.
PPM은 context modeling과 prediction에 기반한 통계적 접근을 합니다. PPM model은 다음 symbol을 추정하기 위하여 이전 symbol의 정보를 이용합니다. 이 방식은 높은 computation power와 많은 memory를 요구하는 대신 발생 확률이 높은 string을 찾아 내어 dictionary coder보다 더 높은 압축률을 보여줍니다. PAQ 알고리듬은 PPM을 base로 개발된 것 입니다.
Entropy encoding은 더 자주 발생하는 string일 수록 더 짧은 code를 할당함으로써 data를 압축하는 것입니다. 대표적인 예로 Huffman coding과 arithmetic coding이 있습니다. 사실 Huffman coding은 arithmetic coding의 부분 집합으로 arithmetic coding이 Huffman coding보다 최적화 된 값에 가깝습니다. 따라서 arithmetic coding이 Huffman coding보다 더 좋은 성능을 가지게 됩니다.

7-zip은 Russian freelancer programmer인 Igor Pavlov에 의해 2000년부터 개발되어온 open source file archiver입니다. 7-zip은 원래 MS Windows 환경에서 개발이 되었습니다. 그러나 현재 Posix/Linux를 위한 command line version이 p7zip이라는 이름으로 배포 되고 있습니다. Windows에서 7-zip은 command line interface와 graphic user interface, 그리고 shell integration된 상태로 사용할 수 있습니다.


7-zip은 GNU Lesser GPL에 의해 배포되고 있습니다. 다시 말하면 7-zip code를 이용한 어떤 상용 program도 7-zip library를 dynamic link library로 제공하는 한 source code를 공개할 의무가 없습니다. 또한 SourceForge.net 2007 community choice award for "Technical Design"과 "Best Project"를 수상한 경력이 있는 project입니다.

7-zip 압축의 핵심 Lempel-Ziv-Markov chain algorithm (LZMA)입니다. LZMA는 상대적으로 새로운 압축 알고리듬으로 7-zip을 통해 널리 사용되기 시작했습니다. LZMA는 range coder와 함께최대 4GB의 LZ-based sliding dictionary를 사용합니다. LZMA compression ratio는 다른 high-gain compression format들 보다 비슷하거나 우월합니다.

LZMA는 1998년부터 개발되어온 data compression 알고리듬입니다. 이 알고리듬은 LZ77과 비슷한 dictionary compression scheme을 사용하고 bzip2보다 높은 high compression ratio와 variable compression-dictionary size를 가지고 있습니다. LZMA는 arithmetic coding 방식을 사용하는 range encoder와 함께 LZ77의 향상된 version을 사용합니다. zlib, gzip, 그리고 zip에 사용되는 deflate algorithm이 LZ77과 Huffman coding을 사용하는 것을 생각하면, LZMA의 압축 성능이 더 좋을 것을 미루어 짐작할 수 있습니다. 실제로 LZMA는 기존 deflate와 비교하여 더 큰 dictionary size와 Huffman coding보다 성능이 좋은 range encoder를 사용합니다.

하지만 7-zip이 best는 아닙니다. 실제 최고의 압축률을 보이고 있는 압축 solution은 context mixing algorithm을 사용하는 PAQ을 채용한 WinRK, PAQ8PX 등으로 보고 되고 있습니다. PAQ는 2000년 이후 Florida Tech에서 개발된 context mixing method를 사용하는 압축 알고리듬입니다. Context mixing은 확률을 이용한 predictor와 arithmetic coder를 채용한 algorithm으로 기존의 dictionary coder와 Huffman coder들보다 진보한 압축 algorithm을 채용하고 있습니다. 현재 PAQ는 느린 속도와 많은 메모리를 요구하지만 최고의 압축률을 가지고 있는 것으로 알려져 있으며, 현재도 지속적으로 연구가 진행중입니다.

Alzip logo

Alzip은 초기에 open source bzip2 file format을 copy하였으나 독자적인 file format이라고 주장한다는 의심을 받았으며, alzip의 error recovery는 지금도 의심받고 있습니다. 하지만 현재 closed file format으로 알려져 있으며 제작사는 decompression library를 제공하고 있지 않습니다. Alzip은 압축률에 있어서 Windows XP built-in zip보다 성능이 뒤쳐지는 것으로 알려지고 있으며, 압축/압축 해제 속도면에 있어서 상위에 랭크되고 있습니다.

압축 알고리듬은 압축률과 더불어 H/W 요구 한계, 압축/압축 해제 속도가 같이 고려되어져야 할 것입니다. 아무리 압축률이 좋은 알고리듬이더라도 너무 비싼 H/W를 요구하거나 너무 긴 시간을 요구한다면 적용할 수 있는 application도 없을 뿐더러 일반 end user들에게도 외면 받게 될 것입니다. 현재 7-zip은 H/W 발전과 algorithm 개선을 통하여 적절한 balance를 가지고 있다고 보입니다. 하지만 언젠가 PAQ이 그 자리를 대신하거나 더 좋은 알고리듬이 제시될 수도 있을 것입니다.

For more information:

No comments:

Post a Comment

Blog Archive