LZMA

Az LZMA (a Lempel-Ziv-Markov chain-Algorithm rövidítése) egy veszteségmentes tömörítési algoritmus, amit 1998^[1]^[2] óta fejlesztenek, és eredetileg a 7-Zip archiváló program 7z fájlformátuma használta; mára számos program alkalmazza jó tömörítési aránya miatt. Az LZ77-hez hasonló szótár alapú kódolást használ, és igen jó tömörítési aránnyal rendelkezik (általában jobban tömörít, mint a bzip2), ezért cserébe egy nagyságrenddel nagyobb a memória és processzor-erőforrás felhasználási igénye. Változó méretű tömörítési szótárat tud használni, egészen 4 gigabájtig felfele. (Lásd még LZW.)

Áttekintés

A szabad forrású LZMA tömörítési programkönyvtár (ami C++-ban íródott) az LZ77 tömörítési algoritmus egy továbbfejlesztett változatát használja föl, ami kiegészül egy range coderrel és bináris fájlokhoz való előfeldolgozóval.

Az LZMA az adatfolyamokat, az ismétlési szekvenciák méretét és azok helyét külön-külön tömöríti. Hash-láncok különböző változatait használja, köztük bináris fákat és Patricia-fákat a szótárban való keresés algoritmusában.

BCJ / BCJ2 bináris fájltömörítés

Az LZMA SDK része a BCJ és BCJ2 binárisfájl-tömörítő (branch compression). A kettő között a különbség az, hogy az előbbi csak a közeli (near) jump / call címeket normalizálja, a BCJ2 pedig tömöríti (x86-os CPU-n) a near jump, near call és a conditional near jump címeket is.

LZMA algoritmust használó implementációk

7-Zip implementációk

A GNU LGPL licencű referenciamegvalósítás (lásd 7-Zip) a következő képességekkel bír:

Tömörítési sebesség: kb. 1 MB/s egy 2 GHz-es CPU-n
Kicsomagolás sebessége: 10-20 MB/s egy 2 GHz-es CPU-n
Támogatja a multi-threadinget és a Pentium 4 mikroprocesszor hyper-threading képességét.

A LZMA kicsomagolásához szükséges kód mérete kb. 5 KB, és a kicsomagoláshoz dinamikusan lefoglalt memória mérete sem túl nagy (a szótármérettől függ). Az algoritmus kicsomagolás-része ezért beágyazott rendszerekben is alkalmazható.

A 7-Zip kódja erősen Windows-specifikus módon íródott, ezért nagyon nehéz Unix-kompatibilis változatot készíteni belőle. Ezzel együtt is létezik két működő portja Unix-szerű platformokra: a p7zip egy többé-kevésbé teljes portja a 7z és 7za parancssori 7-Zip verzióknak, POSIX rendszerekre, mint például Linux, Solaris, OpenBSD, FreeBSD, Cygwin, Mac OS X és BeOS.

Létezik egy Mac OS X port is Compress néven (nincs köze az azonos nevű régi Unix parancshoz), de ez nem nevezhető stabilnak. A Mac OS X-et használóknak rendelkezésére áll még a p7zip Fink csomag is, valamint a 7zX.

Önálló implementációk

A mára már elavultnak tekinthető LZMA Unix Port kizárólag az LZMA kódrészletet tartalmazza, így egy gzip-szerű egyszerű adatfolyamtömörítő. Ez az eszköz csak tömörítő, nem pedig egy teljes archiváló program, az általa létrehozott fájl nagyjából (de egy inkompatibilitás miatt nem teljesen) megegyezik a 7-Zip nyers LZMA streamjével. Az LZMA utils megpróbálja közelíteni a parancssori 7-Zip eszközöket a standard Unix viselkedéshez, az algoritmus elterjedését elősegítendő. Nagyjából ugyanazokat a parancssori kapcsolókat ismeri, mint a gzip és a bzip2. A fentebb említett LZMA Unix Port-tól eltérően, az LZMA utils a 7-Zip nyers LZMA-adatfolyamával megegyező fájlokat hoz létre.

Az LZMA utils-ból nőtt ki az xz utils, ami az egyre szélesebb körben használt, platform-független xz tömörítési formátumot kezeli, mely funkcionalitásában megegyezik a gzip és bzip2 programokkal.

A PyLZMA Python Wrapper be- és kicsomagolást is végez Windows és Linux platformokon.

Egyes beágyazott router-dsl-wireless eszközök (mint az US Robotics 9105 és 9106) olyan módosított Linux-verziót futtatnak (a Broadcom által írt forráskód elérhető az USR weboldalán, ami egy olyan fájlrendszert használ, ami lényegében Cramfs (egy ISO 9660-szerű csak olvasható fájlrendszer), csak ZLIB helyett LZMA tömörítést használ. Egy elég vastag összekötő kódréteggel (glue) vették körbe a referencia kicsomagoló-kódot. Módosított cramfs eszközök^{[halott link]} érhetők el az ilyen LZMA Cramfs lemezképek kezelésére.

A FreeArc egy archiváló program, ami az LZMA-t támogatja. A weboldalon megtalálható a szoftver forráskódja mellett az LZMA programkönyvtárhoz készített Haskell nyelvi interfész is.

A PECompact egy kereskedelmi (freeware szerzők számára ingyenes) EXE-tömörítő, ami az LZMA-t is támogatja. Az upack egy másik LZMA-t használó freeware EXE-tömörítő.

Jegyzetek

↑ 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.
↑ Igor Pavlov has asserted multiple times on SourceForge that the algorithm is his own creation.: One of many forum posts with this claim.. [2009. augusztus 25-i dátummal az eredetiből archiválva]. (Hozzáférés: 2009. augusztus 25.)

Források

Informatikai portál • összefoglaló, színes tartalomajánló lap

[1] 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.

[2] Igor Pavlov has asserted multiple times on SourceForge that the algorithm is his own creation.: One of many forum posts with this claim.. [2009. augusztus 25-i dátummal az eredetiből archiválva]. (Hozzáférés: 2009. augusztus 25.)

[1]

[2]