Algoritmo Lempel-Ziv-Markov

L'algoritmo Lempel-Ziv-Markov chain (LZMA) è un algoritmo utilizzato per la compressione dei dati. In fase di sviluppo dal 1998 è utilizzato nel formato di compressione 7z del programma per archiviazione dati 7-Zip. L'algoritmo utilizza un dizionario di compressione del tutto simile al LZ77 e fra le sue caratteristiche peculiari ha un elevato rapporto di compressione (solitamente maggiore del formato bzip2) e un dizionario di compressione di dimensione variabile (fino a 4 Gbyte).

Introduzione

LZMA utilizza una versione migliorata e ottimizzata dell'algoritmo di compressione LZ77, sostenuta da un range encoder (codificatore). Nei flussi di dati le sequenze di dimensione e locazione ripetuti vengono compresse in maniera differente.

Implementazione in 7-Zip

L'implementazione dell'algoritmo LZMA per il programma 7-Zip è disponibile nel LZMA SDK ed è stata resa disponibile dal suo creatore Igor Pavlov sotto dominio pubblico ed originariamente distribuita sotto ambedue i termini delle licenze LGPL e Common Public License con l'eccezione dei binari linkati del pacchetto. La versione 4.61 beta è stata diffusa sotto dominio pubblico il 2 novembre 2008. La libreria di riferimento open source LZMA è scritta in C++ e presenta le seguenti principali caratteristiche:

• Velocità di compressione: approssimativamente 1 MiB al secondo con una CPU a 2 GHz
• Velocità di decompressione: 10-20 MiB al secondo su una CPU a 2 GHz
• Supporto del multithreading.

L'attuale LZMA SDK in aggiunta all'originale implementazione C++ ne contiene anche una in ANSI C, C# e Java. Esistono anche implementazioni in linguaggio Pascal e Python. L'implementazione utilizzata per 7-Zip usa molte varianti dei metodi delle catene di hash, alberi binari e alberi di Patricia come base per l'algoritmo di compressione a dizionario.

Il codice di sola decompressione di LZMA in genere richiede circa 5 kiB di memoria RAM ed è principalmente determinata dalla dimensione della finestra scorrevole utilizzata durante la decompressione del flusso di dati. L'algoritmo di decompressione LZMA è particolarmente utilizzato nei sistemi embedded grazie alla sua piccola dimensione in termini di codice, il modesto utilizzo della memoria, la ridotta lunghezza del dizionario, nonché per la licenza di software libero.

Algoritmo

Nella compressione LZMA il flusso compresso è rappresentato da un flusso di bit elaborato con un codificatore adattivo binario di range (adaptive binary range coder). Il flusso è suddiviso in due pacchetti, di cui ognuno può descrivere sia un singolo byte o una sequenza LZ77 di lunghezza e distanza implicita o codificata esplicitamente. Esistono 7 tipi di pacchetti:

Codice pacchetto (sequenza di bit)	Descrizione pacchetto
0 + byteCode	Un singolo byte è codificato con il adaptive binary range coder. Quest'ultimo opera in un contesto basato su alcuni numeri della parte più significativa del precedente byte. In modo dipendente dallo stato della macchina può inoltre codificarlo come un singolo byte codificato come differenza fra il byte in oggetto e l'ultimo byte utilizzato nell'ultima distanza LZ77.
1+0 + len + dist	Tipica sequenza LZ77 in cui viene indicata lunghezza e distanza.
1+1+0+0	Sequenza LZ77 di un byte. La distanza è l'ultima distanza LZ77 utilizzata.
1+1+0+1 + len	Una sequenza LZ77. La distanza è l'ultima distanza LZ77 utilizzata.
1+1+1+0 + len	Una sequenza LZ77. La distanza è la penultima distanza LZ77 utilizzata.
1+1+1+1+0 + len	Una sequenza LZ77. La distanza è la terzultima distanza LZ77 utilizzata.
1+1+1+1+1 + len	Una sequenza LZ77. La distanza è la quartultima distanza LZ77 utilizzata.

La lunghezza è codificata nel seguente modo:

Lunghezza codice (sequenza di bit)	Descrizione
0+ 3 bits	La lunghezza è codificata con 3 bit, ottenendo una lunghezza che varia nel range da 2 a 9.
1+0+ 3 bits	La lunghezza è codificata con 3 bit, ottenendo una lunghezza che varia nel range da 10 a 17.
1+1+ 8 bits	La lunghezza è codificata con 8 bit, ottenendo una lunghezza che varia nel range da 18 a 273

La distanza è codificata come segue: per prima cosa una classe di distanza è codificata utilizzando 6 bit. Gli altri 5 bit del codice della distanza codificano l'informazione relativa a quanti bit di distanza diretta devono essere estratti dal flusso dati.

Esempi di utilizzo dell'algoritmo

Elenco (in ordine alfabetico) di alcuni programmi che utilizzano o supportano LZMA.

• CRAMFS con le relative patch applicate.
• Cygwin - Incluso nella distribuzione per Windows di Cygwin ed è utilizzata da MiKTeX.
• Das U-Boot come metodo di compressione opzionale per i file di immagine del kernel dalla versione v2008.10.
• Dpkg dalla versione 1.13.35.
• GNU GRUB (version 2), per la compressione del core.img (solo per BIOS di piattaforme x86).
• GNU tar, dalla versione 1.20 con estensione dei file di archivio .tar.lzma o .tlz).
• Inno Setup
• Linux (per la compressione dell'immagine del kernel dalla versione 2.6.30)
• Lzip, programma stabile di compressione a linea di comando analogo agli strumenti di archiviazione gzip e bzip2
• Man - Compressione delle pagine di man
• Nullsoft Scriptable Install System (NSIS) un sistema di installazione (installer) guidato da script
• p7zip, versione da riga di comando di 7-zip
• Peazip, interfaccia grafica per 7z a riga di comando e binari per POSIX
• PiSi (Packages Installed Successfully, as Intended)
• PowerArchiver
• RPM Package Manager in via sperimentale ha un supporto LZMA dalla versione 4.6.0 e un supporto stabile per LZMA/XZ dalla versione RPM 4.7
• Slackware - La distribuzione Slackware è passata dal formato di pacchetti tgz (basato su gzip) al txz (basato su xz) dalla versione 13.0
• SQL Backup della Red-Gate. Fornisce un semplice sistema di compressione e invio dei dati per backup di server SQL.
• SquashFS con le relative patch applicate.
• Unity motore per videogiochi, utilizza LZMA per comprimere i file web del giocatore.
• UPX, dalla versione (beta) 2.92 in poi comprende come opzionali la compressione LZMA
• WinZip
• XZ Utils, programma di compressione a linea di comando analogo agli strumenti di archiviazione gzip e bzip2

Collegamenti esterni

• Official home page, su 7-zip.org.
• LZMA SDK (Software Development Kit), su 7-zip.org.
• LZMA Utils = XZ Utils, su tukaani.org.
• Data compression, Compressors & Archivers, su unet.univie.ac.at (archiviato dall'url originale il 1º maggio 2009).