Algoritmo Lempel-Ziv-Markov: differenze tra le versioni

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]]).

 

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

 

L'implementazione dell'algoritmo LZMA per il programma [[7-Zip]] è disponibile nel LZMA [[Software development kit|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 rilasciata sotto dominio pubblico il 2 novembre 2008.

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.

 

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:

| Una sequenza LZ77. La distanza è la quartultima distanza LZ77 utilizzata.

|}

{| class="wikitable" border="1"

|-

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.

 

Programmi che utilizzano o supportano LZMA sono:

* [[SQL]] Backup della Red-Gate. Fornisce un semplice sistema di compressione e invio dei dati per backup di server SQL.

* Compressione delle pagine di [[Man (Unix)|man]]

 

<references/>

 

* [http://www.7-zip.org/ Official home page]

* [http://www.7-zip.org/sdk.html LZMA SDK (Software Development Kit)]

[[cs:LZMA]]

[[de:Lempel-Ziv-Markow-Algorithmus]]

[[es:LZMA]]

[[fr:LZMA]]