The Lempel-Ziv-Markov chain-Algorithm (LZMA) is an algorithm used to perform data compression. It has been under development since 1998[1] and is used in the 7z format of the 7-Zip archiver. This algorithm uses a dictionary compression scheme somewhat similar to LZ77 and features a high compression ratio (generally higher than bzip2 [2][3]) and a variable compression-dictionary size (up to 4 GB).[4]
Contents |
Overview
The LZMA uses an improved LZ77 and a Deflate compression algorithm, backed by a range encoder.
Streams for data, repeated-sequence size and repeated-sequence location seem to be compressed separately.[citation needed]
7-Zip reference implementation
The LZMA implementation extracted from 7-zip is available as LZMA SDK and has been put by Igor Pavlov under the public domain.[5] It was originally distributed under the terms of both the LGPL and Common Public License, with a special exception for linked binaries. Version 4.61 beta, was released into the public domain on November 23, 2008.
The reference open source LZMA compression library is written in C++ and has the following properties:
- Compression speed: approximately 1 MB per second on a 2 GHz CPU
- Decompression speed: between 10 and 20 MB per second on a 2 GHz CPU
- Support for multi-threading.
In addition to the original C++ the LZMA SDK contains reference implementations of LZMA compression and decompression ported to ANSI C, C#, and Java.[6] There also exists an implementation in Pascal and Python bindings for the C++ library.[7][8]
This (the 7-Zip) implementation uses several variants of hash chains, binary trees and Patricia tries as the basis for its dictionary search algorithm.
Decompression-only code for LZMA generally compiles to around 5kB and the amount of RAM required during decompression is principally determined by the size of the sliding window used during compression. Small code size and relatively low memory overhead, particularly with smaller dictionary lengths, and free source code make the LZMA decompression algorithm well-suited to embedded applications.
Algorithm
Paul Sladen summarizes the algorithm:
LZMA is effectively deflate (zlib, gzip, zip) with a larger dictionary size, 32MB instead of 32kB. LZMA stands for Lempel-Ziv-Markov chain-Algorithm, after string back-references have been located, values are reduced using a Markov chain range-encoder (aka arithmetic coding) instead of huffman.[9]
Users
Software that uses or supports LZMA:
- cramfs and SquashFS, with applied patches
- Inno Setup
- Nullsoft Scriptable Install System
- Peazip, GUI frontend to command-line 7z and POSIX 7z binaries
- UPX, from version 2.92 (beta) and above, features optional LZMA compression
- The RPM Package Manager has experimental LZMA support since version 4.6.0[10]
- PiSi (Packages Installed Successfully, as Intended) Pardus[citation needed]
- dpkg, from version 1.13.35.
- GNU Tar, from version 1.20 (using the --lzma switch or --auto-compress (-a) with the archive's filename ending in .tar.lzma or .tlz).
- It is also a part of the Cygwin distribution for Windows and used there at least by MiKTeX.[11]
- WinZip
- GNU GRUB (version 2), for compressing core.img (only on x86 BIOS platforms).
Notes
- ^ The SDK history file states that it was in development from 1996, and first used in 7-zip 2001-08-30. Aside from some unreferenced comments about 1998, the algorithm appears to have been unpublished before its use in 7-zip.
- ^ Collin, Lasse (2005-05-31). "A Quick Benchmark: Gzip vs. Bzip2 vs. LZMA". The Tukaani Project. Retrieved on 2008-09-02.
- ^ Klausmann, Tobias (2008-05-08). "Gzip, Bzip2 and Lzma compared". Blog of an Alpha animal. Retrieved on 2008-09-02.
- ^ Overview of the LZMA format 7z Format
- ^ http://www.7-zip.org/sdk.html
- ^ http://www.7-zip.org/sdk.html
- ^ http://www.birtles.org.uk/programming/
- ^ http://www.joachim-bauch.de/projects/python/pylzma/
- ^ Paul Sladen. "Comment on 7-zip, LZMA and blah". Retrieved on 2007-10-06.
- ^ "RPM 4.6.0 (4.6.0-rc3)". rpm.org. Retrieved on 2008-12-31.
- ^ Schenk, Christian. "Creating a custom package repository". miktex.org. Retrieved on 2008-10-15.
External links
- Official home page
- LZMA SDK (Software Development Kit)
- LZMA Utils
- Data compression, Compressors & Archivers
|
||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
No comments have been added.
