Lempel-Ziv-Markov chain algorithm

Lempel-Ziv-Markov chain algorithm

The Lempel-Ziv-Markov chain-Algorithm (LZMA) is an algorithm used to perform data compression. It has been under development since 1998 [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.] 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 [cite web |url=http://tukaani.org/lzma/benchmarks |title=A Quick Benchmark: Gzip vs. Bzip2 vs. LZMA |accessdate=2008-09-02 |last=Collin |first=Lasse |date=2005-05-31 |work= [http://tukaani.org/ The Tukaani Project] ] [cite web |url=http://blog.i-no.de//archives/2008/05/08/index.html#e2008-05-08T16_35_13.txt |title=Gzip, Bzip2 and Lzma compared |accessdate=2008-09-02 |last=Klausmann |first=Tobias |date=2008-05-08 |work= [http://blog.i-no.de/ Blog of an Alpha animal] ] ) and a variable compression-dictionary size (up to 4 GB).Overview of the LZMA format [http://www.7-zip.org/7z.html 7z Format] ]

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.Fact|date=July 2008

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:

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 [cite web
url=http://fedoraproject.org/wiki/Features/RPM4.6
title=Features/RPM4.6
publisher=Red Hat, Inc.
accessdate=2008-08-30
]
* 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

* [http://www.7-zip.org/ 7-Zip] Official homepage.
* [http://p7zip.sourceforge.net/ p7zip] 7-Zip homepage for Linux.
* [http://www.unet.univie.ac.at/~a0503736/php/drdoswiki/index.php?n=Main.Compress Data compression, Compressors & Archivers]
* [http://tukaani.org/lzma/ LZMA Utils] , command line compression program similar to gzip and bzip2
* [http://pypi.python.org/pypi/pyliblzma PylibLZMA] , a python interface using the liblzma API.


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Lempel-Ziv-Markov chain-Algorithm — Lempel Ziv Markow Algorithmus (LZMA) ist ein freier Datenkompressionsalgorithmus, der von Igor Pavlov seit 1998 entwickelt wird und vergleichsweise gute Kompressionsraten und eine hohe Geschwindigkeit beim Entpacken erreicht. Er ist benannt nach… …   Deutsch Wikipedia

  • Algoritmo de cadena Lempel-Ziv-Markov — Saltar a navegación, búsqueda El algoritmo de cadena Lempel Ziv Markov (Lempel Ziv Markov chain Algorithm LZMA) es un algoritmo para la compresión de datos. Obtenido de Algoritmo de cadena Lempel Ziv Markov Categorías: Wikipedia:Infraesbozos |… …   Wikipedia Español

  • Abraham Lempel — Infobox Scientist name = Abraham Lempel imagesize = 400 caption = Abraham Lempel in 2007 birth date = birth place = Lvov, Poland residence = flag|Israel work institution = Technion Israel Institute of Technology field = Information theory known… …   Wikipedia

  • Lossless data compression — is a class of data compression algorithms that allows the exact original data to be reconstructed from the compressed data. The term lossless is in contrast to lossy data compression, which only allows an approximation of the original data to be… …   Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • Dynamic Markov compression — (DMC) is a lossless data compression algorithm developed by Gordon Cormack and Nigel Horspool [1]. It uses predictive arithmetic coding similar to prediction by partial matching (PPM), except that the input is predicted one bit at a time (rather… …   Wikipedia

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия

  • LZMA — LZMA, pour Lempel Ziv Markov chain Algorithm, est un algorithme de compression de données en développement jusqu à 2001 et utilisé dans le format 7z du programme 7 Zip et par StuffitX. Il utilise une compression avec dictionnaire assez similaire… …   Wikipédia en Français

  • LZMA2 — LZMA LZMA, pour Lempel Ziv Markov chain Algorithm, est un algorithme de compression de données en développement jusqu à 2001 et utilisé dans le format 7z du programme 7 Zip et par StuffitX. Il utilise une compression avec dictionnaire assez… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”