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:

Labels

1018 325i 3D 3D Printer 3M 500GB 7200RPM 747 850i A-GPS A-ha A8 ACCIDENT Actor Administrator Privilege ADOBE AdSense aGPS Airplane Algorithm Animation Ansur Antennagate API Apple AppleCare April Fool ARLuxrender Asian Assisted GPS ATT Audi Auto Bash Battleship BBC Bejeweled Bejeweled 3 Belkin Bike BITCOIN Black n Decker Blender Blog Blogspot Bluetooth BMW Bose Browser BTC Bump mapping Butter Butterface Butterfly C C++ C220 Calculator Calvin Klein CAR Cartoon Casshern CBR CBR600RR Cell CF CG Chair Chinese Chrome City Hunter CK Clie Clothe Coffee Coffee maker Color Comics Command Prompt Comment Commercial Compiler Computer Computer architecture Computer graphics Computer science Connex Content-Aware Fill Cowboy Bebop CRYPTOCURRENCY Cryptography CURL Cygwin Dabdate DB Decal Design Design thinking Development Digital Camera Digital communication Disaster Diskette Display Dog Dragon Ball Drama Drawing Driving Drying rack DSP Duck E-TRADE EA Earthquake Easter Egg eBay Economy Encryption ENGINEERING Error ESL etc ETH Ethernet expect F1 Face Fashion find Firefox Fish Flight Dynamics Floppy FON Food FREE Fun FWD G4 Game Gangsta Gangster GDAX GFX Ghost GIT Gizmo5 Golf Google Google Analytics Google Voice Gossip GPS Graphics Green Day GTI Gundam Gurren Lagann Hacking Hackintosh HANGOUTS HARRP HASP SRM HCI HDD Headset Helicopter Helio High-tech History Hobby Honda Horror HP HTS Humor Hyundai iBook iBook G4 IKEA Illustration Image processing information theory Initial D Intel Internet Intro Iomega iPad iPhone iPhone 4 iPhone theme iPod iPod Video Iron IU Jailbreak Japan Java Jawbone Jeremy Jordan Jet Jetpack K12KB KAO Ken Block Ketchup Keynote KORBIT Korea Korean Kpop KRAKEN Kumho Kuwait Language Laptop LaserJet LCD Leaf Lego Lenovo Leopard Lexus LG Library Light saber Lightning Linear algebra Linux login LTC LTE Luxrender Lyric M30 MAC MacBook Macintosh MACOS Macross Macross 2 Macross Plus Magic MapReduce MARKET Matlab Mazinger Z MDRCBB Mechanical engineering Memory MESSAGE Microsoft Microwave Miniature Mio MLT Mobile Mobile Phone Moped Motorcycle Motorola Mouse Movie MP4 Music Music video Network Nike NODE. JS Nonlinear Optimization NORWAY Novel Octave Odaiba Olleh OpenGL Opening Orthodontics Oslo OSX Outlook Parody PBRT pctools Peanut Performance Perl Phone Photoshop PHP Picture Pidgin Plane Playstation Poem Polar bear Pop Portuguese post Pragma Prank Call Printer Program PROGRAMMING Protocol PS PUMA Push Push Push II PushPush PwnageTool PYTHON QuickTime R8 RAM RAYTRACING RAZR RC Recording Report Robot Rock Rocket punch RSYNC Russel Crowe RWD Samsung Sandstorm Satellite Satellite Radio Scanner Science Score Script SD SDK Security sed Semantic Web Semiconductor SF Shell SHOW SIP Skype SK네트웍스 Slang Sleeve Soccer SOFTWARE Sonata Song Sounddock Soundgarden Space Spyshot SQL SSD ssh sshd Stanford bunny StarTrek Starwars Stethoscope Steve Jobs Sticker Stock Storage system Subaru Sun Super Deformed T-Shirt Taekwon V TALK TBD Tease Technology Teeth Telecommunication Tennis tethering Textfree TH55 The Perfect Storm Theme TI-89 TIBURON Tires Titanium Tom Mabe Tooth Tooth Explorer Torrent Toshiba Toshiba Power Saver Toy TPS Transformer Tsunami TV TV shows Ubuntu UC Ultrabase UMN Universal Century Unix Unlock USB Used Video Virtuosity Vista Visual Studio VISUALC++ VoIP VW WALLET Wallpaper Wanna Girl Wardriving Web 3.0 Wedding WiFi Wild Willy Windows Windows 7 Windows Vista Wireless WireShark WMV WOW WPS WRE54G X61 xargs XBOX XCode Yamato YF Youtube Z Gundam Zeliard Zuma 김간지 김현국 미국여자 방배추 뽀로로 위성 라디오 유희열 일본여자 조까를로스 주역 천자문 周易 天字文 德經 老子

Blog Archive