bzip2 (Dansk)

Bzip2 bruger flere lag af kompressionsteknikker stablet oven på hinanden, som forekommer i følgende rækkefølge under kompression og omvendt rækkefølge under dekompression:

1. Kørelængdekodning (RLE) af indledende data.
2. Burrows – Wheeler-transformation (BWT) eller bloksortering.
3. Move-to-front (MTF) transform.
4. Kodning af runlængde (RLE) af MTF-resultat.
5. Huffman-kodning.
6. Valg mellem flere Huffman-tabeller.
7. Unary base-1-kodning af Huffman-tabelvalg.
8. Delta-kodning (Δ) af Huffman-kodebitlængder.
9. Sparse bitarray, der viser hvilke symboler der bruges.

Indledende kørelængdekodning Rediger

Enhver sekvens på 4 til 255 på hinanden følgende duplikatsymboler erstattes af de første 4 symboler og en gentagelængde mellem 0 og 251. Således sekvensen AAAAAAABBBBCCCD erstattes med AAAA\3BBBB\0CCCD, hvor \3 og \0 repræsenterer byteværdierne henholdsvis 3 og 0. Kør af symboler transformeres altid efter 4 på hinanden følgende symboler, selvom løbetiden er sat til nul, for at holde transformationen reversibel.

I værste fald kan det forårsage en udvidelse på 1,25 og i i bedste fald en reduktion til < 0,02. Mens specifikationen teoretisk giver mulighed for at køre kørsler med længden 256–259, producerer referencekoderen ikke sådan output.

Forfatteren af bzip2 har udtalt, at RLE-trinnet var en historisk fejl og kun var beregnet til for at beskytte den oprindelige BWT-implementering fra patologiske tilfælde.

Burrows – Wheeler transformEdit

Dette er den reversible blocksorter, der er kernen i bzip2. Blokken er helt selvstændig, med input- og outputbuffere, der forbliver af samme størrelse – i bzip2 er driftsgrænsen for dette trin 900 kB. For bloksorteringen oprettes en (notionel) matrix, hvor række i indeholder hele bufferen, roteret for at starte fra det i-th symbol. Efter rotation sorteres matrixens rækker i alfabetisk (numerisk) rækkefølge. En 24-bit markør er gemt, der markerer startpositionen for når blokken ikke er transformeret. I praksis er det ikke nødvendigt at konstruere den fulde matrix; snarere udføres sorteringen ved hjælp af markører for hver position i bufferen. Outputbufferen er den sidste kolonne i matrixen; denne indeholder hele bufferen, men omorganiseret, så den sandsynligvis indeholder store kørsler af identiske symboler.

Flyt til front transformEdit

Igen ændrer denne transformation ikke størrelsen på den behandlede blok. Hvert af de anvendte symboler i dokumentet placeres i en matrix. Når et symbol behandles, erstattes det af dets placering (indeks) i arrayet, og dette symbol blandes til fronten af arrayet. Effekten er, at øjeblikkeligt tilbagevendende symboler erstattes af nul symboler (lange kørsler af ethvert vilkårligt symbol bliver således kørsler af nul symboler), mens andre symboler omkortes i henhold til deres lokale frekvens.

Meget “naturlige” data indeholder identiske symboler, der gentages inden for et begrænset interval (tekst er et godt eksempel). Da MTF-transformeringen tildeler lave værdier til symboler, der ofte vises igen, resulterer dette i en datastrøm, der indeholder mange symboler i det lave heltal, hvor mange af dem er identiske (forskellige tilbagevendende input-symboler kan faktisk kortlægges til det samme output-symbol). Sådanne data kan kodes meget effektivt ved hjælp af en hvilken som helst ældre komprimeringsmetode.

Kodelængde-kodning af MTF resultEdit

Lange strenge af nuller i output fra flyt til front-transformation ( som kommer fra gentagne symboler i output af BWT) erstattes af en række af to specielle koder, RUNA og RUNB, som repræsenterer løbetiden som et binært tal. Faktiske nuller er aldrig kodet i output; et ensomt nul bliver RUNA. (Dette trin udføres faktisk på samme tid som MTF er; hver gang MTF ville producere nul, øger det i stedet en tæller til derefter at kode med RUNA og RUNB.)

Sekvensen 0, 0, 0, 0, 0, 1 ville blive repræsenteret som RUNA, RUNB, 1; RUNA, RUNB repræsenterer værdien 5 som beskrevet nedenfor. Kørelængdekoden afsluttes ved at nå et andet normalt symbol. Denne RLE-proces er mere fleksibel end det oprindelige RLE-trin, da den er i stand til at kode vilkårligt lange heltal (i praksis er dette normalt begrænset af blokstørrelsen, så dette trin ikke koder for en kørsel på mere end 900.000 byte). Kørelængden er kodet på denne måde: tildeler stedværdier 1 til den første bit, 2 til den anden, 4 til den tredje osv. I sekvensen, gang hver stedværdi i et RUNB-sted med 2 og tilføj alle de resulterende stedværdier (for både RUNA- og RUNB-værdier) sammen. Dette svarer til base-2 vedektiv numerering.Således resulterer sekvensen RUNA, RUNB i værdien (1 + 2 × 2) = 5. Som et mere kompliceret eksempel:

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

Huffman codingEdit

Denne proces erstatter symboler med fast længde i området 0-258 med koder med variabel længde baseret på brugsfrekvensen. Oftere anvendte koder ender kortere (2-3 bits), mens sjældne koder kan tildeles op til 20 bit. Koderne vælges omhyggeligt, så ingen sekvens af bits kan forveksles med en anden kode.

End-of-stream-koden er særlig interessant. Hvis der er n forskellige bytes (symboler), der bruges i de ukomprimerede data, vil Huffman-koden bestå af to RLE-koder (RUNA og RUNB), n – 1-symbolkoder og en slut-stream-kode. På grund af det kombinerede resultat af MTF- og RLE-kodningerne i de foregående to trin er der aldrig noget behov for eksplicit at henvise til det første symbol i MTF-tabellen (ville være nul i den almindelige MTF) og derved gemme et symbol til slut- of-stream markør (og forklarer, hvorfor kun n – 1 symboler er kodet i Huffman-træet). I ekstreme tilfælde, hvor kun ét symbol bruges i de ukomprimerede data, vil der slet ikke være nogen symbolkoder i Huffman-træet, og hele blokken vil bestå af RUNA og RUNB (implicit gentagelse af den enkelte byte) og en slutning på -strøm markør med værdi 2.

0: RUNA, 1: RUNB, 2-257: byteværdier 0-255, 258: slutningen af strømmen, færdigbehandlingen (kan være så lav som 2).

Flere Huffman-tabeller Rediger

Flere Huffman-tabeller med samme størrelse kan bruges med en blok, hvis gevinsten ved at bruge dem er større end prisen på at inkludere den ekstra tabel. Mindst 2 og op til 6 tabeller kan være til stede, hvor den mest passende tabel vælges igen inden hver 50 behandlede symboler. Dette har fordelen ved at have en meget lydhør Huffman-dynamik uden at skulle levere løbende nye tabeller, som det kræves i DEFLATE. Kørsel af længde i det foregående trin er designet til at tage sig af koder, der har en omvendt sandsynlighed for brug, der er højere end den korteste kode Huffman-kode, der er i brug.

Unary kodning af Huffman-tabelvalg Rediger

Hvis flere Huffman-tabeller er i brug, foretages markeringen af hver tabel (nummereret 0 til 5) fra en liste med en nultermineret bit, der kører mellem 1 og 6 bit i længden. Valget er på en MTF-liste over tabellerne. Brug af denne funktion resulterer i en maksimal udvidelse på omkring 1.015, men generelt mindre. Denne udvidelse vil sandsynligvis blive stærkt overskygget af fordelen ved at vælge mere passende Huffman-tabeller, og det almindelige tilfælde af fortsat brug af den samme Huffman-tabel er repræsenteret som en enkelt bit. I stedet for unarisk kodning er dette effektivt en ekstrem form for et Huffman-træ, hvor hver kode har halv sandsynligheden for den forrige kode.

Delta encodingEdit

Huffman-kodebitlængder er krævet for at rekonstruere hver af de anvendte kanoniske Huffman-tabeller. Hver bitlængde lagres som en kodet forskel i forhold til den tidligere kodelængde. En nulbit (0) betyder, at den foregående bitlængde skal duplikeres for den aktuelle kode, mens en bit (1) betyder, at en yderligere bit skal læses, og bitlængden skal øges eller reduceres baseret på denne værdi.

I almindelighed anvendes en enkelt bit pr. symbol pr. tabel, og i værste fald – fra længde 1 til længde 20 – ville det kræve cirka 37 bit. Som et resultat af den tidligere MTF-kodning, ville kodelængderne starte med 2-3 bits lange (meget ofte anvendte koder) og gradvist øges, hvilket betyder, at delta-formatet er ret effektivt, hvilket kræver omkring 300 bit (38 bytes) pr. Fuld Huffman-tabel .

Sparse bit arrayEdit

En bitmap bruges til at vise, hvilke symboler der bruges inde i blokken og skal inkluderes i Huffman-træerne. Binære data bruger sandsynligvis alle 256 symboler, der kan repræsenteres af en byte, hvorimod tekstdata muligvis kun bruger et lille undersæt af tilgængelige værdier, der muligvis dækker ASCII-området mellem 32 og 126. Lagring af 256 nulbit ville være ineffektivt, hvis de for det meste ikke var brugt. Der anvendes en sparsom metode: 256 symboler er opdelt i 16 områder, og kun hvis symboler bruges inden for denne blok er et 16-bit array inkluderet. Tilstedeværelsen af hvert af disse 16 områder er angivet med en yderligere 16-bit-array foran.

Den samlede bitmap bruger mellem 32 og 272 bit lager (4-34 bytes). I modsætning hertil vil DEFLATE-algoritmen vise fraværet af symboler ved at kode symbolerne som en nulbitlængde med kørelængdekodning og yderligere Huffman-kodning.