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

[modifica | modifica wikitesto]

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

[modifica | modifica wikitesto]

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:

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

[modifica | modifica wikitesto]

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

[modifica | modifica wikitesto]

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

Note

[modifica | modifica wikitesto]
  1. ^ Christian Schenk, Creating a custom package repository, su docs.miktex.org, miktex.org. URL consultato il 15 ottobre 2008.
  2. ^ RPM 4.6.0 (4.6.0-rc3), su rpm.org. URL consultato il 31 dicembre 2008.
  3. ^ RPM 4.7, su rpm.org. URL consultato il 15 luglio 2009.

Collegamenti esterni

[modifica | modifica wikitesto]
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica
Categorie