bzip2

Bzip2 gebruikt verschillende lagen compressietechnieken die op elkaar zijn gestapeld, die in de volgende volgorde optreden tijdens compressie en in omgekeerde volgorde tijdens decompressie:

1. Run-length-codering (RLE) van initiële gegevens.
2. Burrows-Wheeler-transformatie (BWT) of bloksortering.
3. Move-to-front (MTF) -transformatie.
4. Run-length codering (RLE) van MTF-resultaat.
5. Huffman-codering.
6. Selectie tussen meerdere Huffman-tabellen.
7. Unaire base-1-codering van Huffman-tabelselectie.
8. Delta-codering (Δ) van Huffman-code bitlengtes.
9. Dunne bitarray die laat zien welke symbolen worden gebruikt.

Initiële run-length codering Bewerken

Elke reeks van 4 tot 255 opeenvolgende dubbele symbolen wordt vervangen door de eerste 4 symbolen en een herhalingslengte tussen 0 en 251. Dus de reeks AAAAAAABBBBCCCD is vervangen door AAAA\3BBBB\0CCCD, waarbij \3 en \0 vertegenwoordigen byte-waarden 3 en 0 respectievelijk. Symboolreeksen worden altijd getransformeerd na 4 opeenvolgende symbolen, zelfs als de run-lengte is ingesteld op nul, om de transformatie omkeerbaar te houden.

In het ergste geval kan het een uitbreiding van 1,25 veroorzaken, en in in het beste geval een verlaging tot < 0,02. Hoewel de specificatie theoretisch toelaat dat runs met lengte 256-259 worden gecodeerd, zal de referentie-encoder dergelijke uitvoer niet produceren.

De auteur van bzip2 heeft verklaard dat de RLE-stap een historische fout was en alleen bedoeld was om de originele BWT-implementatie te beschermen tegen pathologische gevallen.

Burrows-Wheeler-transformatie Bewerken

Dit is de omkeerbare bloksortering die vormt de kern van bzip2. Het blok is volledig op zichzelf staand, met invoer- en uitvoerbuffers die dezelfde grootte blijven – in bzip2 is de operationele limiet voor deze fase 900 kB. Voor de bloksortering wordt een (fictieve) matrix gemaakt, waarin rij i de volledige buffer bevat, geroteerd om te beginnen vanaf het i-de symbool. Na rotatie worden de rijen van de matrix in alfabetische (numerieke) volgorde gesorteerd. Een 24-bit pointer wordt opgeslagen die de startpositie markeert voor wanneer het blok niet getransformeerd is. In de praktijk is het niet nodig om de volledige matrix te construeren; in plaats daarvan wordt het sorteren uitgevoerd met behulp van pointers voor elke positie in de buffer. De uitvoerbuffer is de laatste kolom van de matrix; dit bevat de hele buffer, maar opnieuw gerangschikt zodat het waarschijnlijk grote series identieke symbolen bevat.

Move-to-front transformEdit

Nogmaals, deze transformatie verandert de grootte van het verwerkte blok niet. Elk van de symbolen die in het document worden gebruikt, wordt in een array geplaatst. Wanneer een symbool wordt verwerkt, wordt het vervangen door zijn locatie (index) in de array en dat symbool wordt naar de voorkant van de array geschud. Het effect is dat onmiddellijk terugkerende symbolen worden vervangen door nul-symbolen (lange runs van elk willekeurig symbool worden dus series van nul-symbolen), terwijl andere symbolen opnieuw worden toegewezen op basis van hun lokale frequentie.

Veel “natuurlijke” gegevens bevat identieke symbolen die binnen een beperkt bereik terugkeren (tekst is een goed voorbeeld). Omdat de MTF-transformatie lage waarden toewijst aan symbolen die vaak opnieuw verschijnen, resulteert dit in een datastroom met veel symbolen in het lage gehele bereik, waarvan er vele identiek zijn (verschillende terugkerende invoersymbolen kunnen feitelijk worden toegewezen aan hetzelfde uitvoersymbool). Dergelijke gegevens kunnen zeer efficiënt worden gecodeerd door elke oudere compressiemethode.

Run-length codering van MTF resultEdit

Lange reeksen nullen in de uitvoer van de move-to-front-transformatie ( die afkomstig zijn van herhaalde symbolen in de uitvoer van de BWT) worden vervangen door een reeks van twee speciale codes, RUNA en RUNB, die de run-length vertegenwoordigen als een binair getal. Werkelijke nullen worden nooit gecodeerd in de uitvoer; een eenzame nul wordt RUNA. (Deze stap wordt in feite op hetzelfde moment gedaan als MTF; wanneer MTF nul zou produceren, verhoogt het in plaats daarvan een teller om vervolgens te coderen met RUNA en RUNB.)

De reeks 0, 0, 0, 0, 0, 1 zou worden weergegeven als RUNA, RUNB, 1; RUNA, RUNB vertegenwoordigt de waarde 5 zoals hieronder wordt beschreven. De run-length code wordt beëindigd door een ander normaal symbool te bereiken. Dit RLE-proces is flexibeler dan de initiële RLE-stap, omdat het in staat is om willekeurig lange gehele getallen te coderen (in de praktijk wordt dit meestal beperkt door de blokgrootte, zodat deze stap niet een run van meer dan 900.000 bytes codeert). De run-length wordt op deze manier gecodeerd: door plaatswaarden van 1 toe te wijzen aan de eerste bit, 2 aan de tweede, 4 aan de derde, enz. In de reeks, vermenigvuldig elke plaatswaarde in een RUNB-spot met 2 en tel alle de resulterende plaatswaarden (zowel voor RUNA- als RUNB-waarden) samen. Dit is vergelijkbaar met base-2 bijectieve nummering.De reeks RUNA, RUNB resulteert dus in de waarde (1 + 2 × 2) = 5. Als een ingewikkelder voorbeeld:

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

Huffman codingEdit

Dit proces vervangt symbolen met een vaste lengte in het bereik van 0–258 door codes met variabele lengte op basis van de gebruiksfrequentie. Vaker gebruikte codes worden korter (2-3 bits), terwijl zeldzame codes tot 20 bits kunnen worden toegewezen. De codes zijn zorgvuldig geselecteerd, zodat geen enkele reeks bits kan worden verward met een andere code.

De end-of-stream-code is bijzonder interessant. Als er n verschillende bytes (symbolen) worden gebruikt in de niet-gecomprimeerde gegevens, dan zal de Huffman-code bestaan uit twee RLE-codes (RUNA en RUNB), n – 1 symboolcodes en één end-of-stream-code. Vanwege het gecombineerde resultaat van de MTF- en RLE-coderingen in de vorige twee stappen, is het nooit nodig om expliciet te verwijzen naar het eerste symbool in de MTF-tabel (zou nul zijn in de gewone MTF), waardoor één symbool voor het einde wordt bewaard. of-stream marker (en uitlegt waarom alleen n – 1 symbolen worden gecodeerd in de Huffman-structuur). In het extreme geval waarin slechts één symbool wordt gebruikt in de niet-gecomprimeerde gegevens, zullen er helemaal geen symboolcodes in de Huffman-structuur staan en zal het hele blok bestaan uit RUNA en RUNB (impliciet herhalen van de enkele byte) en een einde van -streammarkering met waarde 2.

0: RUNA, 1: RUNB, 2–257: bytewaarden 0–255, 258: einde van stream, verwerking voltooien (kan zo laag zijn als 2).

Meerdere Huffman-tafels Bewerken

Verschillende Huffman-tafels van identieke grootte kunnen met een blok worden gebruikt als de winst door het gebruik ervan groter is dan de kosten van het opnemen van de extra tafel. Er kunnen minimaal 2 en maximaal 6 tafels aanwezig zijn, waarbij de meest geschikte tafel opnieuw wordt geselecteerd voordat elke 50 symbolen worden verwerkt. Dit heeft het voordeel dat het een zeer responsieve Huffman-dynamiek heeft zonder continu nieuwe tabellen te hoeven aanleveren, zoals vereist zou zijn bij DEFLATE. Runlengtecodering in de vorige stap is ontworpen om te zorgen voor codes die een omgekeerde gebruikskans hebben die hoger is dan de kortste Huffman-code die wordt gebruikt.

Unaire codering van Huffman-tabelselectie Bewerken

Als er meerdere Huffman-tabellen in gebruik zijn, wordt de selectie van elke tabel (genummerd van 0 tot 5) gedaan uit een lijst door een nul-beëindigde bitrun met een lengte van tussen de 1 en 6 bits. De selectie is in een MTF-lijst van de tabellen. Het gebruik van deze functie resulteert in een maximale uitbreiding van ongeveer 1.015, maar over het algemeen minder. Deze uitbreiding wordt waarschijnlijk sterk overschaduwd door het voordeel van het selecteren van geschiktere Huffman-tabellen, en het gebruikelijke geval van het blijven gebruiken van dezelfde Huffman-tabel wordt weergegeven als een enkele bit. In plaats van unaire codering, is dit in feite een extreme vorm van een Huffman-boom, waarbij elke code de helft van de waarschijnlijkheid heeft van de vorige code.

Delta-codering Bewerken

Huffman-code bitlengtes zijn nodig om elk van de gebruikte canonieke Huffman-tabellen te reconstrueren. Elke bitlengte wordt opgeslagen als een gecodeerd verschil ten opzichte van de bitlengte van de vorige code. Een nul bit (0) betekent dat de vorige bitlengte moet worden gedupliceerd voor de huidige code, terwijl een bit (1) betekent dat er nog een bit moet worden gelezen en dat de bitlengte moet worden verhoogd of verlaagd op basis van die waarde.

In het gewone geval wordt een enkele bit per symbool per tabel gebruikt en in het slechtste geval – van lengte 1 tot lengte 20 – zou ongeveer 37 bits nodig zijn. Als resultaat van de eerdere MTF-codering, zouden de codelengten beginnen bij 2-3 bits lang (zeer vaak gebruikte codes) en geleidelijk toenemen, wat betekent dat het delta-formaat redelijk efficiënt is en ongeveer 300 bits (38 bytes) per volledige Huffman-tabel vereist. .

Sparse bit arrayEdit

Een bitmap wordt gebruikt om te laten zien welke symbolen in het blok worden gebruikt en in de Huffman-bomen moeten worden opgenomen. Binaire gegevens gebruiken waarschijnlijk alle 256 symbolen die door een byte kunnen worden weergegeven, terwijl tekstuele gegevens slechts een kleine subset van beschikbare waarden kunnen gebruiken, die misschien het ASCII-bereik tussen 32 en 126 beslaan. Het opslaan van 256 nulbits zou inefficiënt zijn als ze grotendeels niet zouden worden gebruikt. Er wordt een spaarzame methode gebruikt: de 256 symbolen zijn onderverdeeld in 16 bereiken, en alleen als symbolen binnen dat blok worden gebruikt, wordt een 16-bits array opgenomen. De aanwezigheid van elk van deze 16 bereiken wordt aangegeven door een extra 16-bits bit-array aan de voorkant.

De totale bitmap gebruikt tussen de 32 en 272 bits opslagruimte (4-34 bytes). Als contrast zou het DEFLATE-algoritme de afwezigheid van symbolen laten zien door de symbolen te coderen met een bitlengte van nul met run-length codering en aanvullende Huffman-codering.