Utente:XDnl/Sandbox: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
eliminate cat di servizio errate |
m fix errore di Lint - Tag di chiusura mancante |
||
| (2 versioni intermedie di 2 utenti non mostrate) | |||
Riga 234:
La stringa codificata risulta ACGT<math>\alpha_1\alpha_3\alpha_5</math>.
L'input ACGT ACGT ACG è di 12 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}{12} \right) * 100 \approx 42\%</math>
Da questo esempio si evince che per ottenere una buona compressione, è necessario che i dati in input contengano numerose ripetizioni.
Riga 240:
Di seguito è riportato lo pseudocodice relativo alla compressione (si assume che il dizionario sia già inizializzato con i simboli dell'alfabeto):
buffer = VUOTO
CICLO
Riga 254:
FINE SE
FINECICLO
===Decompressione===
Riga 364 ⟶ 363:
La stringa ottenuta è quindi ACGTACGTACG (12 simboli), che rispetto a quella compressa ACGT<math>\alpha_1\alpha_3\alpha_5</math>(7 simboli), presenta 5 simboli in più (12-7 simboli), riportando così la stessa dimensione della stringa iniziale prima del processo di compressione e decompressione; da notare il fatto che al termine della decompressione, si ha lo stesso dizionario finale della compressione, giungendo così alle conclusioni che non è necessario l'invio del dizionario, visto e considerato che viene ricostruito dal decoder in maniera del tutto indipendente. Questo conferma la validità del metodo di compressione LZW senza riportare alcuna perdita di simboli (o genericamente di dati).
Lo pseudocodice abbinato alla decompressione è così strutturato:
LEGGI k
INVIA k
Riga 376 ⟶ 375:
FINE CICLO
====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:
Riga 425 ⟶ 423:
La Stringa compressa risulta quindi:
<div style="text-align:center;font-size:15px">"C<math>\alpha_1</math>"</div>
<p>Per il processo di decompressione, sorgono i primi problemi, perchè come si potrà vedere, mancherà <math>\alpha_1</math> nel dizionario del decoder:</p>▼
▲Per il processo di decompressione, sorgono i primi problemi, perchè come si potrà vedere, mancherà <math>\alpha_1</math> nel dizionario del decoder:
<div style="float:left">
{| class="wikitable"
Riga 475 ⟶ 472:
<br style="clear:both" />
Si otterrà così la stessa stringa decompressa di partenza, senza alcuna perdita di dati e risolvendo anche il problema del codice mancante nel dizionario. Lo pseudocodice "alternativo" per questo caso speciale è il seguente:
LEGGI k
INVIA k
Riga 492 ⟶ 489:
buffer = sottostringa
FINE CICLO
=Implementazione=
| |||