Lempel-Ziv-Welch: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
mNessun oggetto della modifica |
m Bot: apostrofo dopo l'articolo indeterminativo e modifiche minori |
||
Riga 24:
Presentato<ref name="WelchIEEE">Terry Welch, [http://ieeexplore.ieee.org/xpls/abs_all.jsp?tp=&arnumber=1659158&isnumber=34743 "A Technique for High-Performance Data Compression"], ''IEEE Computer'', June 1984, p. 8–19.</ref> da [[Terry Welch|Welch]] nel 1984, l'algoritmo si basa su precedenti ricerche effettuate da [[Jacob Ziv]] ed [[Abraham Lempel]].<br />
Questi ultimi, infatti, pubblicarono nel 1977 un documento sulla compressione "sliding-window" (a finestre scorrevoli), seguito poi nel 1978 da un'altra ricerca relativa alla compressione basata su "dizionari".<br />
I due algoritmi furono chiamati, rispettivamente, [[LZ77]] ed [[LZ78]].
Nel 1984, [[Terry Welch]] migliorò [[LZ78]] dando origine all'algoritmo conosciuto oggi come LZW (acronimo di Lempel-Ziv-Welch).
<br />
Riga 34:
L'input dell'algoritmo di compressione ('''encoder''') e di decompressione ('''decoder''') è costituito da una sequenza finita di simboli ([[Stringa (formale)|stringa]]), appartenenti ad un insieme detto alfabeto.<br />
Come esempio, immaginiamo di voler archiviare una sequenza di [[DNA]].<br />
In generale, una parte di DNA è composta da una ''sequenza'' (finita) di 4 tipi di acidi:
'''A'''denina, '''T'''imina, '''C'''itosina e '''G'''uanina.<br />
L'alfabeto, sulla quale è costruita una sequenza di DNA, è l'insieme:<br />
Riga 73:
|}
Le nuove voci vengono aggiunte a quelle già presenti nel dizionario, estendendolo man mano che si avanza con l'elaborazione dell'input.<br />
Rimpiazzando le sequenze ripetute con i nuovi simboli, otteniamo il seguente risultato:
<div style="text-align:center;font-size:15px"><math>\alpha_1</math><math>\alpha_2</math><math>\alpha_1</math><math>\alpha_2</math><math>\alpha_1</math>G</div>
Riga 105:
(d'ora in avanti chiamata '''buffer''') che verrà modificata/cancellata più volte durante l'esecuzione. Inizialmente il buffer è vuoto (cioè non contiene alcun simbolo).
La stringa inizia ad essere esaminata dal primo simbolo; nel buffer vengono collezionati i vari caratteri incontrati, fino a che non si formi una sequenza '''non''' contenuta nel dizionario.
Nel nostro esempio,
Riga 115:
! Iterazione !! Input !! Buffer corrente !! Simbolo in output !! Voce aggiunta nel dizionario
|-
| 1 || ACGTACGTACG || (vuoto) || (nessuno) || (nessuna)
|-
| 2 || <span style="background-color: yellow">A</span>CGTACGTACG || A || ||
|-
| 3 || <span style="background-color: yellow">AC</span>GTACGTACG || AC || ||
|}
Riga 137:
| 4 || A<span style="background-color: yellow">C</span>GTACGTACG || C || A || AC ((<math>\alpha_1</math>))
|-
| 5 || A<span style="background-color: yellow">CG</span>TACGTACG || CG || ||
|-
| 6 || AC<span style="background-color: yellow">G</span>TACGTACG || G || C || CG ((<math>\alpha_2</math>))
Riga 188:
|| ACG ((<math>\alpha_5</math>))
|-
| 14 || ACGTAC<span style="background-color: yellow">GT</span>ACG || GT || ||
|-
| 15 || ACGTAC<span style="background-color: yellow">GTA</span>CG || GTA || ||
|-
| 16 || ACGTACGT<span style="background-color: yellow">A</span>CG || A || <math>\alpha_3</math> || GTA ((<math>\alpha_6</math>))
Riga 198:
| 18 || ACGTACGT<span style="background-color: yellow">ACG</span> || ACG || ||
|-
| 19 || ACGTACGTACG || || <math>\alpha_5</math> ||
|}
</div>
Riga 229:
</div>
<br style="clear:both" />
La stringa codificata risulta ACGT<math>\alpha_1\alpha_3\alpha_5</math>.
L'input ACGT ACGT ACG è di 11 simboli, mentre l'output ACGT<math>\alpha_1\alpha_3\alpha_5</math> è di 7 simboli, quindi il rapporto di compressione è:
<math>\left(1 - \frac{7}{11} \right) * 100 \approx 36%</math>
Riga 394:
! Iterazione !! Input !! Buffer corrente !! Simbolo in output !! Voce aggiunta nel dizionario
|-
| 1 || CCC || (vuoto) || (nessuno) || (nessuna)
|-
| 2 || <span style="background-color: yellow">C</span>CC || C || ||
|-
| 3 || <span style="background-color: yellow">CC</span>C || CC || ||
|-
| 4 || C<span style="background-color: yellow">C</span>C || C || C || CC ((<math>\alpha_1</math>))
|-
| 5 || C<span style="background-color: yellow">CC</span> || CC || ||
|-
| 6 || CCC || || <math>\alpha_1</math> ||
Riga 709:
* {{en}} – [http://marknelson.us/1989/10/01/lzw-data-compression/ Un articolo sulla compressione LZW.]
* [http://www.oldwildweb.com/implementazione-lzw-c-ugo-cirmignani.html Un
* {{US patent|4558302}}, Terry A. Welch, ''High speed data compression and decompression apparatus and method''
| |||