bzip2 (Italiano)

Bzip2 utilizza diversi livelli di tecniche di compressione impilati uno sopra laltro, che si verificano nel seguente ordine durante la compressione e nellordine inverso durante la decompressione:

1. Codifica run-length (RLE) dei dati iniziali.
2. Burrows – Wheeler transform (BWT) o block sorting.
3. Trasformazione Move-to-front (MTF).
4. Run-length encoding (RLE) del risultato MTF.
5. Codifica Huffman.
6. Selezione tra più tabelle Huffman.
7. Codifica base 1 unaria della selezione della tabella di Huffman.
8. Codifica delta (Δ) delle lunghezze di bit del codice Huffman.
9. Matrice di bit sparsi che mostra quali simboli vengono utilizzati.

Codifica della lunghezza di esecuzione inizialeModifica

Qualsiasi sequenza da 4 a 255 simboli duplicati consecutivi viene sostituita dai primi 4 simboli e una lunghezza di ripetizione compresa tra 0 e 251. Pertanto la sequenza AAAAAAABBBBCCCD viene sostituito con AAAA\3BBBB\0CCCD, dove \3 e \0 rappresentano i valori di byte 3 e 0 rispettivamente. Le sequenze di simboli vengono sempre trasformate dopo 4 simboli consecutivi, anche se la lunghezza della sequenza è impostata su zero, per mantenere la trasformazione reversibile.

Nel peggiore dei casi, può causare unespansione di 1,25, e in nel migliore dei casi, una riduzione a < 0,02. Sebbene la specifica teoricamente consenta di codificare sequenze di lunghezza 256-259, il codificatore di riferimento non produrrà tale output.

Lautore di bzip2 ha affermato che il passaggio RLE era un errore storico ed era solo inteso per proteggere limplementazione BWT originale da casi patologici.

Trasformata Burrows – Wheeler Modifica

Questo è lordinamento a blocchi reversibile che è al centro di bzip2. Il blocco è completamente autonomo, con buffer di ingresso e uscita che rimangono della stessa dimensione: in bzip2, il limite operativo per questa fase è 900 kB. Per il block-sort viene creata una matrice (nozionale), in cui la riga i contiene tutto il buffer, ruotato a partire dal simbolo i-esimo. Dopo la rotazione, le righe della matrice vengono ordinate in ordine alfabetico (numerico). Un puntatore a 24 bit viene memorizzato contrassegnando la posizione iniziale per quando il blocco non è trasformato. In pratica, non è necessario costruire la matrice completa; piuttosto, lordinamento viene eseguito utilizzando i puntatori per ogni posizione nel buffer. Il buffer di output è lultima colonna della matrice; questo contiene lintero buffer, ma è stato riordinato in modo che probabilmente contenga grandi sequenze di simboli identici.

Trasformazione Move-to-frontEdit

Ancora una volta, questa trasformazione non altera la dimensione del blocco elaborato. Ciascuno dei simboli in uso nel documento viene inserito in una matrice. Quando un simbolo viene elaborato, viene sostituito dalla sua posizione (indice) nellarray e tale simbolo viene spostato allinizio dellarray. Leffetto è che i simboli ricorrenti immediatamente vengono sostituiti da simboli zero (le lunghe serie di qualsiasi simbolo arbitrario diventano così sequenze di simboli zero), mentre gli altri simboli vengono rimappati in base alla loro frequenza locale.

Dati molto “naturali” contiene simboli identici che ricorrono entro un intervallo limitato (il testo è un buon esempio). Poiché la trasformazione MTF assegna valori bassi ai simboli che riappaiono frequentemente, ciò si traduce in un flusso di dati contenente molti simboli nellintervallo intero basso, molti dei quali sono identici (simboli di input ricorrenti diversi possono effettivamente mappare allo stesso simbolo di output). Tali dati possono essere codificati in modo molto efficiente con qualsiasi metodo di compressione legacy.

Codifica della lunghezza di esecuzione dellMTF resultEdit

Lunghe stringhe di zeri nelloutput della trasformazione da spostamento in avanti ( che derivano da simboli ripetuti nelloutput del BWT) sono sostituiti da una sequenza di due codici speciali, RUNA e RUNB, che rappresentano il run-length come numero binario. Gli zeri effettivi non vengono mai codificati nelloutput; uno zero solitario diventa RUNA. (Questo passaggio in effetti viene eseguito contemporaneamente a MTF; ogni volta che MTF produce zero, aumenta invece un contatore per poi codificare con RUNA e RUNB.)

La sequenza 0, 0, 0, 0, 0, 1 sarebbe rappresentato come RUNA, RUNB, 1; RUNA, RUNB rappresenta il valore 5 come descritto di seguito. Il codice di run-length viene terminato raggiungendo un altro simbolo normale. Questo processo RLE è più flessibile del passaggio RLE iniziale, in quanto è in grado di codificare interi arbitrariamente lunghi (in pratica, questo è solitamente limitato dalla dimensione del blocco, in modo che questo passaggio non codifichi una corsa di più di 900000 byte). La lunghezza della corsa è codificata in questo modo: assegnando i valori di posizione 1 al primo bit, 2 al secondo, 4 al terzo, ecc. Nella sequenza, moltiplica ogni valore di posizione in un punto RUNB per 2 e somma tutto i valori di posizione risultanti (per i valori RUNA e RUNB allo stesso modo) insieme. Questo è simile alla numerazione biiettiva in base 2.Pertanto, la sequenza RUNA, RUNB restituisce il valore (1 + 2 × 2) = 5. Come esempio più complicato:

RUNA RUNB RUNA RUNA RUNB (ABAAB) 1 2 4 8 16 1 4 4 8 32 = 49

Huffman codingEdit

Questo processo sostituisce i simboli a lunghezza fissa nellintervallo 0–258 con codici a lunghezza variabile basati sulla frequenza di utilizzo. I codici utilizzati più frequentemente finiscono per essere più brevi (2–3 bit), mentre i codici rari possono essere assegnati fino a 20 bit. I codici vengono selezionati con cura in modo che nessuna sequenza di bit possa essere confusa per un codice diverso.

Il codice di fine flusso è particolarmente interessante. Se ci sono n diversi byte (simboli) utilizzati nei dati non compressi, il codice Huffman sarà composto da due codici RLE (RUNA e RUNB), n – 1 codici simbolo e un codice di fine flusso. A causa del risultato combinato delle codifiche MTF e RLE nei due passaggi precedenti, non è mai necessario fare riferimento esplicito al primo simbolo nella tabella MTF (sarebbe zero nellMTF ordinario), salvando così un simbolo per la fine- indicatore di flusso (e spiega perché solo n – 1 simboli sono codificati nellalbero di Huffman). Nel caso estremo in cui viene utilizzato un solo simbolo nei dati non compressi, non ci saranno affatto codici simbolo nellalbero di Huffman e lintero blocco sarà costituito da RUNA e RUNB (che ripetono implicitamente il singolo byte) e da una fine di Indicatore di flusso con valore 2.

0: RUNA, 1: RUNB, 2–257: valori byte 0–255, 258: fine flusso, elaborazione finale (potrebbe essere inferiore a 2).

Più tabelle di HuffmanModifica

Diverse tabelle di Huffman di dimensioni identiche possono essere utilizzate con un blocco se il guadagno derivante dal loro utilizzo è maggiore del costo dellinclusione della tabella aggiuntiva. Possono essere presenti almeno 2 e fino a 6 tabelle, con la tabella più appropriata che viene riselezionata prima di ogni 50 simboli elaborati. Questo ha il vantaggio di avere dinamiche di Huffman molto reattive senza dover fornire continuamente nuove tabelle, come sarebbe richiesto in DEFLATE. La codifica della lunghezza di esecuzione nel passaggio precedente è progettata per prendersi cura dei codici che hanno una probabilità inversa di utilizzo maggiore del codice più breve codice Huffman in uso.

Codifica unaria della selezione della tabella di HuffmanModifica

Se sono in uso più tabelle di Huffman, la selezione di ciascuna tabella (numerata da 0 a 5) viene effettuata da un elenco mediante un bit a terminazione zero eseguito tra 1 e 6 bit di lunghezza. La selezione è in un elenco MTF delle tabelle. Lutilizzo di questa funzione si traduce in unespansione massima di circa 1.015, ma generalmente inferiore. Questa espansione rischia di essere ampiamente offuscata dal vantaggio di selezionare tabelle Huffman più appropriate, e il caso comune di continuare a utilizzare la stessa tabella Huffman è rappresentato come un singolo bit. Piuttosto che una codifica unaria, in effetti questa è una forma estrema di un albero di Huffman, dove ogni codice ha la metà della probabilità del codice precedente.

Codifica delta Modifica

Le lunghezze in bit del codice di Huffman sono necessario per ricostruire ciascuna delle tabelle canoniche di Huffman utilizzate. Ogni lunghezza di bit viene memorizzata come differenza codificata rispetto alla lunghezza di bit del codice precedente. Un bit zero (0) significa che la lunghezza del bit precedente dovrebbe essere duplicata per il codice corrente, mentre un bit (1) significa che un ulteriore bit deve essere letto e la lunghezza del bit deve essere incrementata o decrementata in base a quel valore.

Nel caso comune viene utilizzato un singolo bit per simbolo per tabella e il caso peggiore, che va dalla lunghezza 1 alla lunghezza 20, richiederebbe circa 37 bit. Come risultato della precedente codifica MTF, la lunghezza del codice iniziava da 2 a 3 bit (codici usati molto frequentemente) e aumentava gradualmente, il che significa che il formato delta è abbastanza efficiente, richiedendo circa 300 bit (38 byte) per tabella Huffman completa .

Sparse bit arrayEdit

Una bitmap è usata per mostrare quali simboli sono usati allinterno del blocco e dovrebbero essere inclusi negli alberi di Huffman. È probabile che i dati binari utilizzino tutti i 256 simboli rappresentabili da un byte, mentre i dati testuali possono utilizzare solo un piccolo sottoinsieme di valori disponibili, forse coprendo lintervallo ASCII tra 32 e 126. La memorizzazione di 256 bit zero sarebbe inefficiente se fossero per lo più inutilizzati. Viene utilizzato un metodo sparse: i 256 simboli sono suddivisi in 16 intervalli e solo se i simboli vengono utilizzati allinterno di quel blocco è incluso un array a 16 bit. La presenza di ciascuno di questi 16 intervalli è indicata da un array aggiuntivo di 16 bit nella parte anteriore.

La bitmap totale utilizza tra 32 e 272 bit di memoria (4-34 byte). Per contrasto, lalgoritmo DEFLATE mostrerebbe lassenza di simboli codificando i simboli come aventi una lunghezza di bit zero con codifica run-length e codifica Huffman aggiuntiva.