Ecco una ripartizione dei comuni metodi di compressione binaria senza perdita di perdita:
1. Identificazione della ridondanza e dei modelli:
* ripetizione: La forma più semplice. Se lo stesso byte o sequenza di byte si ripete più volte, l'algoritmo li sostituisce con un marker che indica la sequenza ripetuta e il numero di ripetizioni. Questo è spesso chiamato codifica di lunghezza (RLE) . Per esempio:
* Originale:`aaaaabbbcccdd`
* Rle compresso:`5a3b3c2d` (5 a's, 3 b's, 3 c's, 2 d's)
* RLE è più efficace quando ci sono lunghe serie degli stessi dati.
* Compressione basata sul dizionario: Questo metodo crea un dizionario (o tabella) di sequenze frequentemente presenti. Invece di conservare la sequenza completa ogni volta, l'algoritmo memorizza l'indice (o codice) che rappresenta tale sequenza nel dizionario.
* LZ77 e LZ78 (e le loro varianti lzw, deflate): Questi sono algoritmi basati sul dizionario di pietra miliare. Funzionano mantenendo una finestra scorrevole di dati visti di recente.
* LZ77: Cerca sequenze corrispondenti * all'interno * della finestra scorrevole. Quando trova una corrispondenza, memorizza una coppia `(distanza, lunghezza), dove:
* `Distanza`:quanto indietro nella finestra inizia la partita.
* `lunghezza`:quanto dura la sequenza di corrispondenza.
* LZ78: Costruisce un dizionario di * nuove * frasi mentre le incontra. Codifica ogni nuova frase come `(indice, carattere)`, dove:
* `INDICE`:L'indice del prefisso * più lungo * della frase già nel dizionario.
* `Personal`:il personaggio che estende il prefisso per creare la nuova frase.
* LZW (Lempel-Ziv-Welch): Un miglioramento di LZ78. Inizia con un dizionario pre-inizializzato contenente tutti i singoli caratteri. Costruisce il dizionario in modo dinamico mentre elabora i dati. LZW è famoso per essere utilizzato nel formato dell'immagine GIF (sebbene i brevetti su LZW abbiano causato problemi per un po ').
* deflate: Combina LZ77 con la codifica Huffman (spiegata di seguito) per una compressione ancora migliore. È usato in gzip, zlib e png. È molto comune.
2. Codifica statistica (codifica entropica):
* Questi metodi analizzano la frequenza di diversi simboli (byte) nei dati e assegnano codici più brevi a simboli più frequenti e codici più lunghi a quelli meno frequenti. Questo si basa sulla teoria dell'informazione, in cui eventi più probabili richiedono meno informazioni per trasmettere.
* Coding Huffman: Uno schema di codifica a lunghezza variabile. Costruisce un albero binario in base alle frequenze dei simboli. I simboli più frequenti sono posizionati più vicini alla radice dell'albero, con conseguenti lunghezze del codice più brevi.
* L'algoritmo genera un codice prefisso, il che significa che nessun codice è un prefisso di un altro codice, che impedisce l'ambiguità durante la decodifica.
* Codice aritmetica: Rappresenta l'intero flusso di dati come un singolo numero frazionario tra 0 e 1. La lunghezza della frazione è determinata dalle probabilità dei simboli. La codifica aritmetica raggiunge spesso una migliore compressione della codifica di Huffman, specialmente quando si tratta di simboli che hanno probabilità molto diverse. Tuttavia, è più intenso dal punto di vista computazionale.
Esempio illustrativo (semplificato):
Immagina di avere i seguenti dati:`AABBBCCCAADDDEEEFFFFF`
1. rle: Potrebbe comprimere a `2a3b3c2a3d3e4f` (lo riduce, ma non drasticamente).
2. Codice Huffman:
* Analisi della frequenza:
* A:5
* B:3
* C:3
* D:3
* E:3
* F:4
* Huffman Tree Construction (Esempio):
* Combina meno frequente:b (3) e c (3) -> nodo BC (6)
* Combina d (3) ed e (3) -> nodo de (6)
* Combina bc (6) e de (6) -> nodo bcde (12)
* Combina f (4) e a (5) -> nodo AF (9)
* Combina af (9) e bcde (12) -> root (21)
* Assegna i codici (0 per sinistra, 1 per la destra attraversando l'albero) - * Questo può variare in base all'implementazione! *
* A:00
* B:100
* C:101
* D:110
* E:111
* F:01
* Dati compressi:`0000100100100101101101101111111111111010101010101` (molto più corto dell'originale, specialmente per set di dati di grandi dimensioni!)
Considerazioni chiave:
* Complessità: Algoritmi diversi hanno complessità computazionali diverse. Alcuni sono più veloci per la codifica/decodifica ma ottengono rapporti di compressione più bassi. Altri sono più lenti ma ottengono una maggiore compressione.
* Rapporto di compressione: Il rapporto tra dimensione del file originale e dimensione del file compresso. Un rapporto più elevato indica una migliore compressione.
* Utilizzo della memoria: Gli algoritmi richiedono memoria per buffer, dizionari e strutture degli alberi. L'utilizzo della memoria può essere un fattore limitante, soprattutto quando si comprime file di grandi dimensioni.
* Tipo di dati: Alcuni algoritmi sono più adatti per tipi specifici di dati (ad es. Testo, immagini, audio). Ad esempio, gli algoritmi che sfruttano la località spaziale sono buoni per le immagini.
In sintesi, gli algoritmi di compressione binaria funzionano da:
1. Analisi dei dati: Identificazione di modelli, ripetizioni e frequenze statistiche.
2. Rappresentando i dati in modo più efficiente: Utilizzando codici più brevi per elementi comuni e codici più lunghi per elementi rari.
3. Metadati di memorizzazione: Conservare le informazioni necessarie per decomprimere i dati (ad es. Dizionari, alberi di Huffman).
La scelta dell'algoritmo dipende dai requisiti specifici dell'applicazione, incluso il rapporto di compressione desiderato, le risorse computazionali disponibili e il tipo di dati compressi. Spesso, gli approcci ibridi (come Deflate) vengono utilizzati per combinare i punti di forza di diverse tecniche.
software © www.354353.com