Lempel-Ziv-Welch: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
→Caso speciale: ripristino da vandalismo del 25/5/11 |
|||
Riga 374:
</code>
====Caso speciale====
Come accennato prima, vi è un caso speciale di decompressione: Cosa succede se il decoder riceve un codice Z che non è ancora nel dizionario? Finché il decoder è sempre un codice indietro all'encoder, Z può essere nel dizionario dell'encoder solo se l'encoder lo genera, quando emette il precedente codice X per Y. Così gli Z codici, alcuni ω che sono Y + ? e il decoder possono determinare il carattere sconosciuto come segue:
# # # Il decoder sa che Z è stato aggiunto nel dizionario dell'encoder per Y+qualche carattere sconosciuto "?"
# Conosce che "?" è la prima lettera di ω
# La prima lettera di ω=Y+? deve essere anche la prima lettera di Y
# ω deve essere quindi Y+x, dove x è la prima lettera di Y(x=?)
# Ciò implica che Z=ω=Y+x
# Trovato Z, questo viene inserito nel dizionario
# Si procede in maniera analoga con il resto della decompressione
Questa situazione accade ogni volta che l'encoder incontra input sotto la forma cScSc, dove c è un singolo carattere ed S è una stringa; cS è già all'interno del dizionario, ma cSc no. L'encoder emette il codice per cS, inserendo un nuovo codice per cSc nel dizionario. Dopo individua la presenza di cSc nell'input (partendo dalla seconda c di cScSc) ed emette il nuovo codice appena inserito.
Anche se l'input sotto tale forma è un caso raro, questo schema diventa piuttosto comune quando il flusso di input è caratterizzato da significanti ripetizioni. In particolare, lunghe stringhe di un singolo carattere (che sono comuni in vari tipi di immagini la quale l'LZW spesso comprime) generano ripetutamente schemi di questo genere.
Per rendere chiaro il processo utilizzato in tale caso speciale, si consideri il seguente esempio:
Line 421 ⟶ 431:
| 2 || <span style="background-color: yellow">C</span><math>\alpha_1</math> || C || C+? || C || ||
|-
| 3 || <span style="background-color: yellow">C<math>\alpha_1</math></span> || || || || || <math>\alpha_1</math>=???
|}
</div>
<div style="float:right;clear:right">{| class="wikitable"
!colspan="2"|Dizionario
|-
| |||