bzip2 (Norsk)

Bzip2 bruker flere lag med komprimeringsteknikker stablet oppå hverandre, som forekommer i følgende rekkefølge under komprimering og omvendt rekkefølge under dekompresjon:

1. Kjørelengdekoding (RLE) av innledende data.
2. Burrows – Wheeler transform (BWT), eller blokkeringssortering.
3. Move-to-front (MTF) transform.
4. Run-length encoding (RLE) of MTF result.
5. Huffman-koding.
6. Valg mellom flere Huffman-tabeller.
7. Unary base-1-koding av Huffman-tabellvalg.
8. Delta-koding (Δ) av Huffman-kodebitlengder.
9. Sparsom bitmatrise som viser hvilke symboler som brukes.

Initial run-length encodingEdit

Enhver sekvens på 4 til 255 påfølgende dupliserte symboler erstattes av de første 4 symbolene og en repeteringslengde mellom 0 og 251. Dermed blir sekvensen AAAAAAABBBBCCCD erstattes med AAAA\3BBBB\0CCCD, der \3 og \0 representerer henholdsvis byteverdiene 3 og 0. Kjør av symboler blir alltid transformert etter fire påfølgende symboler, selv om løpetiden er satt til null, for å holde transformasjonen reversibel.

I verste fall kan det føre til en utvidelse på 1,25, og i i beste fall en reduksjon til < 0,02. Mens spesifikasjonen teoretisk tillater at kodinger av lengden 256–259 kan kodes, vil ikke referansekoderen produsere slik utdata.

Forfatteren av bzip2 har uttalt at RLE-trinnet var en historisk feil og bare var ment for å beskytte den opprinnelige BWT-implementeringen mot patologiske tilfeller.

Burrows – Wheeler transformEdit

Dette er den reversible blokk-typen som er kjernen i bzip2. Blokken er helt selvstendig, med inngangs- og utgangsbuffere som er av samme størrelse – i bzip2 er driftsgrensen for dette trinnet 900 kB. For blokksorteringen opprettes en (teoretisk) matrise, der rad i inneholder hele bufferen, rotert for å starte fra i-th-symbolet. Etter rotasjon sorteres radene i matrisen i alfabetisk (numerisk) rekkefølge. Det lagres en 24-bit peker som markerer startposisjonen for når blokken ikke er transformert. I praksis er det ikke nødvendig å konstruere hele matrisen; Sorteringen utføres heller ved hjelp av pekere for hver posisjon i bufferen. Utgangsbufferen er den siste kolonnen i matrisen; denne inneholder hele bufferen, men omorganisert slik at den sannsynligvis vil inneholde store kjøringer av identiske symboler.

Move-to-front transformEdit

Igjen, denne transformasjonen endrer ikke størrelsen på den behandlede blokken. Hvert av symbolene som brukes i dokumentet er plassert i en matrise. Når et symbol behandles, erstattes det av plasseringen (indeksen) i matrisen, og det symbolet blandes til fronten av matrisen. Effekten er at umiddelbart tilbakevendende symboler blir erstattet av null-symboler (lange kjøringer av ethvert vilkårlig symbol blir dermed kjøringer av null-symboler), mens andre symboler blir kartlagt i henhold til deres lokale frekvens.

Mye «naturlige» data inneholder identiske symboler som går igjen innen et begrenset område (tekst er et godt eksempel). Ettersom MTF-transformasjonen tildeler lave verdier til symboler som dukker opp ofte, resulterer dette i en datastrøm som inneholder mange symboler i det lave heltallområdet, hvor mange av dem er identiske (forskjellige tilbakevendende inngangssymboler kan faktisk tilordnes til det samme utgangssymbolet). Slike data kan kodes veldig effektivt med en hvilken som helst eldre komprimeringsmetode.

Kodelengde-koding av MTF resultEdit

Lange strenger av nuller i utgangen av flytt-til-front-transformasjonen ( som kommer fra gjentatte symboler i utgangen av BWT) blir erstattet av en sekvens av to spesialkoder, RUNA og RUNB, som representerer løpetiden som et binært tall. Faktiske nuller blir aldri kodet i utdataene; en ensom null blir RUNA. (Dette trinnet gjøres faktisk på samme tid som MTF er; når MTF produserer null, øker det i stedet en teller for deretter å kode med RUNA og RUNB.)

Sekvensen 0, 0, 0, 0, 0, 1 vil bli representert som RUNA, RUNB, 1; RUNA, RUNB representerer verdien 5 som beskrevet nedenfor. Kjørelengdekoden avsluttes ved å nå et annet normalt symbol. Denne RLE-prosessen er mer fleksibel enn det opprinnelige RLE-trinnet, da den er i stand til å kode vilkårlig lange heltall (i praksis er dette vanligvis begrenset av blokkstørrelsen, slik at dette trinnet ikke koder for en kjøring på mer enn 900000 byte). Kjørelengden er kodet på denne måten: tilordne stedverdier 1 til den første biten, 2 til den andre, 4 til den tredje osv. I sekvensen, multipliser hver stedverdi i et RUNB-sted med 2, og legg til alle de resulterende stedverdiene (for RUNA og RUNB-verdier likt) sammen. Dette ligner på base-2 bijektiv nummerering.Dermed resulterer sekvensen RUNA, RUNB i verdien (1 + 2 × 2) = 5. Som et mer komplisert eksempel:

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

Huffman codingEdit

Denne prosessen erstatter symboler med fast lengde i området 0–258 med koder med variabel lengde basert på bruksfrekvensen. Oftere brukte koder ender kortere (2–3 bits), mens sjeldne koder kan tildeles opptil 20 bits. Kodene velges nøye slik at ingen sekvens av bits kan forveksles med en annen kode.

End-of-stream-koden er spesielt interessant. Hvis det er n forskjellige byte (symboler) som brukes i de ukomprimerte dataene, vil Huffman-koden bestå av to RLE-koder (RUNA og RUNB), n – 1 symbolkoder og en slutt-av-stream-kode. På grunn av det kombinerte resultatet av MTF- og RLE-kodingene i de to foregående trinnene, er det aldri noe behov for å eksplisitt henvise til det første symbolet i MTF-tabellen (ville være null i den vanlige MTF), og dermed lagre ett symbol til slutt- of-stream markør (og forklarer hvorfor bare n – 1 symboler er kodet i Huffman-treet). I ekstreme tilfeller der bare ett symbol brukes i de ukomprimerte dataene, vil det ikke være noen symbolkoder i det hele tatt i Huffman-treet, og hele blokken vil bestå av RUNA og RUNB (implisitt gjentakelse av enkeltbyten) og en slutt på -strømmerker med verdi 2.

0: RUNA, 1: RUNB, 2–257: byteverdier 0–255, 258: slutten av strømmen, ferdigbehandlingen (kan være så lav som 2).

Flere Huffman-tabeller Rediger

Flere Huffman-tabeller med samme størrelse kan brukes med en blokk hvis gevinsten ved å bruke dem er større enn kostnaden for å inkludere ekstrabordet. Minst 2 og opptil 6 bord kan være til stede, og den mest hensiktsmessige tabellen blir valgt ut igjen før hvert 50 symbol behandles. Dette har fordelen av å ha veldig responsiv Huffman-dynamikk uten å måtte levere kontinuerlig nye tabeller, slik det ville være nødvendig i DEFLATE. Løpslengde-koding i forrige trinn er designet for å ta vare på koder som har en omvendt sannsynlighet for bruk høyere enn den korteste koden Huffman-koden i bruk.

Unary koding av Huffman-tabellvalg Rediger

Hvis flere Huffman-tabeller er i bruk, blir valget av hver tabell (nummerert 0 til 5) gjort fra en liste med en nullterminert bit som går mellom 1 og 6 bits i lengden. Valget er i en MTF-liste over tabellene. Bruk av denne funksjonen resulterer i en maksimal utvidelse på rundt 1.015, men generelt mindre. Denne utvidelsen vil sannsynligvis bli sterkt overskygget av fordelen ved å velge mer passende Huffman-tabeller, og det vanlige tilfellet med å fortsette å bruke den samme Huffman-tabellen er representert som en enkeltbit. I stedet for unarisk koding, er dette effektivt en ekstrem form av et Huffman-tre, der hver kode har halv sannsynligheten for den forrige koden.

Delta kodingEdit

Huffman-kodebitlengder er kreves for å rekonstruere hvert av de brukte kanoniske Huffman-bordene. Hver bitlengde lagres som en kodet forskjell mot den forrige kodebitlengden. En nullbit (0) betyr at den forrige bitlengden skal dupliseres for den gjeldende koden, mens en bit (1) betyr at en ytterligere bit skal leses og bitlengden økes eller reduseres basert på den verdien.

I vanlige tilfeller brukes en enkelt bit per symbol per tabell, og i verste fall – fra lengde 1 til lengde 20 – vil det kreve omtrent 37 bits. Som et resultat av den tidligere MTF-kodingen, ville kodelengdene starte på 2-3 bits lange (veldig ofte brukte koder) og gradvis øke, noe som betyr at deltaformatet er ganske effektivt, og krever rundt 300 bits (38 byte) per full Huffman-tabell .

Sparse bit arrayEdit

En bitmap brukes til å vise hvilke symboler som brukes inne i blokken og skal inkluderes i Huffman-trærne. Binære data bruker sannsynligvis alle 256 symboler som kan representeres av en byte, mens tekstdata bare bruker et lite delsett av tilgjengelige verdier, som kanskje dekker ASCII-området mellom 32 og 126. Lagring av 256 nullbiter ville være ineffektiv hvis de stort sett ikke var i bruk. En sparsom metode brukes: 256 symboler er delt opp i 16 områder, og bare hvis symboler brukes i den blokken, er en 16-bit matrise inkludert. Tilstedeværelsen av hvert av disse 16 områdene er indikert av en ekstra 16-biters matrise foran.

Den totale bitmappen bruker mellom 32 og 272 bit lagring (4-34 byte). I motsetning til dette vil DEFLATE-algoritmen vise fraværet av symboler ved å kode symbolene som å ha en nullbitlengde med løpetidkoding og ytterligere Huffman-koding.