Lzma

Article on other languages:

• LZMA
• LZMA
• Lempel-Ziv-Markow-Algorithmus
• Lempel-Ziv-Markov_chain_algorithm
• LZMA
• LZMA
• LZMA
• LZMA
• LZMA
• LZMA
• LZMA

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

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]

Overview

The LZMA uses an improved LZ77 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 reference implementation of LZMA is included as part of the 7z and 7-Zip suite of tools. Source code is distributed under the terms of the GNU LGPL license with a special exception for linked binaries. The special exception allows redistribution of binaries linked to unmodified LZMA to be free of any LGPL requirements (e.g., they do not need to allow reverse engineering or binary modifications.)

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.

As of version 4.58 (beta) of LZMA SDK, there is also ANSI C reference implementation of LZMA compression and decompression routines available as well.

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, 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.

—^[5]

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, from version 4.6 onwards^[6]
• 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).
• PECompact
• WinZip

Notes

External links

• 7-Zip Official homepage.
• p7zip 7-Zip homepage for Linux.
• Data compression, Compressors & Archivers
• LZMA Utils, command line compression program similar to gzip and bzip2
• PylibLZMA, a python interface using the liblzma API.