Bzip2 käyttää useita kerroksia pakkaustekniikoita päällekkäin, joita esiintyy seuraavassa järjestyksessä pakkauksen aikana ja päinvastaisessa järjestyksessä purkamisen aikana:
- Lähtötietojen koodaus (RLE).
- Burrows – Wheeler-muunnos (BWT) tai lohkojen lajittelu.
- Siirrä eteenpäin (MTF) -muunnos.
- MTF-tuloksen run-length encoding (RLE).
- Huffman-koodaus.
- Valinta useiden Huffman-taulukoiden välillä.
- Unary base-1 -koodaus Huffman-taulukon valinnasta.
- Huffman-koodin bittipituuksien delta-koodaus (Δ).
- Harvinainen bittiryhmä, joka näyttää käytettävät symbolit.
Alkuperäinen juoksupituuden koodausMuokkaa
Mikä tahansa 4 – 255 peräkkäisen kaksoissymbolin sekvenssi korvataan neljällä ensimmäisellä symbolilla ja toistopituudella välillä 0 ja 251. Sekvenssi AAAAAAABBBBCCCD korvataan sanoilla AAAA\3BBBB\0CCCD, missä \3 ja \0 edustavat tavuarvoja 3 ja 0 vastaavasti. Symbolien ajo muunnetaan aina 4 peräkkäisen symbolin jälkeen, vaikka ajon pituus olisi asetettu nollaksi, jotta muunnos pysyy palautuvana.
Pahimmassa tapauksessa se voi aiheuttaa laajennuksen 1,25 ja parhaassa tapauksessa pienennys arvoon < 0,02. Vaikka määrittely teoriassa sallii pituuksien 256–259 koodaamisen, referenssikooderi ei tuota tällaista lähtöä.
bzip2: n kirjoittaja on todennut, että RLE-vaihe oli historiallinen virhe ja oli tarkoitettu vain suojaamaan alkuperäinen BWT-toteutus patologisilta tapauksilta.
Burrows – Wheeler transformEdit
Tämä on käännettävä lohkolajittelu, joka on bzip2: n ydin. Lohko on täysin itsenäinen, ja tulo- ja lähtöpuskurit ovat edelleen samankokoisia – bzip2: ssa tämän vaiheen toimintaraja on 900 kt. Lohkolajittelua varten luodaan (kuvitteellinen) matriisi, jossa rivi i sisältää koko puskurin, joka on käännetty aloitettavaksi i: nnestä symbolista. Kiertämisen jälkeen matriisin rivit lajitellaan aakkosjärjestykseen (numeeriseen). 24-bittinen osoitin on tallennettu merkitsemällä lähtöasento, kun lohko ei ole muunnettu. Käytännössä koko matriisin rakentaminen ei ole välttämätöntä; pikemminkin lajittelu suoritetaan käyttämällä osoittimia kullekin puskurin sijainnille. Lähtöpuskuri on matriisin viimeinen sarake; tämä sisältää koko puskurin, mutta järjestetty uudelleen siten, että se sisältää todennäköisesti suuria määriä identtisiä symboleja.
Siirrä eteenpäin transformEdit
Tämä muunnos ei taaskään muuta käsitellyn lohkon kokoa. Jokainen asiakirjassa käytetty symboli sijoitetaan taulukkoon. Kun symboli on käsitelty, se korvataan sen sijainnilla (hakemisto) taulukossa ja symboli sekoitetaan ryhmän eteen. Seurauksena on, että välittömästi toistuvat symbolit korvataan nollasymboleilla (minkä tahansa mielivaltaisen symbolin pitkistä ajoista tulee siten nollasymbolien ajo), kun taas muut symbolit määritetään uudelleen niiden paikallisen taajuuden mukaan.
Paljon ”luonnollista” dataa sisältää identtisiä symboleja, jotka toistuvat rajoitetulla alueella (teksti on hyvä esimerkki). Kun MTF-muunnos määrittää matalat arvot symboleille, jotka ilmestyvät usein uudelleen, tuloksena on datavirta, joka sisältää monia symboleja matalalla kokonaislukualueella, joista monet ovat identtisiä (erilaiset toistuvat tulosymbolit voivat itse asiassa liittyä samaan lähtösymboliin). Tällaiset tiedot voidaan koodata erittäin tehokkaasti millä tahansa vanhalla pakkausmenetelmällä.
MTF resultEdit -nopeuskoodaus resultEdit
Pitkät nollan merkkijonot eteenpäin -muunnoksen lähdössä ( jotka tulevat toistuvista symboleista BWT: n lähdössä) korvataan kahden erikoiskoodin, RUNA ja RUNB, jotka edustavat ajon pituutta binäärilukuna, jaksolla. Todellisia nollia ei koskaan koodata lähdössä; yksinäisestä nollasta tulee RUNA. (Tämä vaihe tehdään itse asiassa samaan aikaan kuin MTF on; aina kun MTF tuottaisi nollan, se sen sijaan kasvattaa laskuria ja koodaa sitten RUNA: lla ja RUNB: lla.)
Sekvenssi 0, 0, 0, 0, 0, 1 esitettäisiin nimellä RUNA, RUNB, 1; RUNA, RUNB edustaa arvoa 5 alla kuvatulla tavalla. Ajonopeuden koodi lopetetaan saavuttamalla toinen normaali symboli. Tämä RLE-prosessi on joustavampi kuin alkuperäinen RLE-vaihe, koska se pystyy koodaamaan mielivaltaisesti pitkiä kokonaislukuja (käytännössä tätä yleensä rajoittaa lohkon koko, joten tämä vaihe ei koodaa yli 900000 tavun ajoa). Ajon pituus on koodattu tällä tavalla: osoittamalla sekvenssin ensimmäiselle bitille 1, 2 toiselle, 4 kolmannelle jne. Järjestettävät paikka-arvot, kerro jokainen RUNB-pisteen paikka-arvo kahdella ja lisää kaikki saadut paikan arvot (RUNA- ja RUNB-arvoille) yhdessä. Tämä on samanlainen kuin perus-2 bijektiivinen numerointi.Siten sekvenssi RUNA, RUNB johtaa arvoon (1 + 2 × 2) = 5. Monimutkaisempana esimerkkinä:
RUNA RUNB RUNA RUNA RUNB (ABAAB) 1 2 4 8 16 1 4 4 8 32 = 49
Huffman codingEdit
Tämä prosessi korvaa kiinteän pituuden symbolit alueella 0–258 vaihtelevan pituisilla koodeilla käytön taajuuden perusteella. Useimmin käytetyt koodit ovat lyhyempiä (2-3 bittiä), kun taas harvinaisia koodeja voidaan varata jopa 20 bittiä. Koodit valitaan huolellisesti, jotta yhtään bittisarjaa ei voida sekoittaa eri koodiin.
Streamin loppukoodi on erityisen mielenkiintoinen. Jos pakkaamattomassa datassa on käytetty n erilaista tavua (symbolia), Huffman-koodi koostuu kahdesta RLE-koodista (RUNA ja RUNB), n – 1 symbolikoodista ja yhdestä loppupään koodista. Kahden edellisen vaiheen MTF- ja RLE-koodausten yhdistetyn tuloksen takia ei ole koskaan tarvetta viitata nimenomaisesti MTF-taulukon ensimmäiseen symboliin (olisi nolla tavallisessa MTF: ssä), mikä säästää yhden symbolin loppuosaa varten. of stream -merkki (ja selittää miksi vain n – 1 symbolia koodataan Huffman-puuhun). Äärimmäisessä tapauksessa, kun pakkaamattomassa datassa käytetään vain yhtä symbolia, Huffman-puussa ei ole ollenkaan symbolikoodeja, ja koko lohko koostuu RUNA: sta ja RUNB: sta (implisiittisesti toistamalla yhden tavun) ja loppu -virtamerkki arvolla 2.
0: RUNA, 1: RUNB, 2–257: tavuarvot 0–255, 258: virran loppu, käsittelyn loppuun saattaminen (voi olla jopa 2).
Useita Huffman-taulukoitaEdit
Lohkossa voidaan käyttää useita saman kokoisia Huffman-taulukoita, jos niiden käytöstä saatu voitto on suurempi kuin ylimääräisen taulukon sisällyttämisen hinta. Vähintään 2 ja enintään 6 taulukkoa voi olla läsnä, sopivin taulukko valitaan uudelleen ennen jokaista 50 käsiteltyä symbolia. Tällä on se etu, että sillä on erittäin herkkä Huffman-dynamiikka tarvitsematta jatkuvasti toimittaa uusia taulukoita, kuten DEFLATE-sovelluksessa vaaditaan. Aikaisempi koodaus edellisessä vaiheessa on suunniteltu huolehtimaan koodeista, joiden käänteinen käyttötodennäköisyys on suurempi kuin lyhin käytössä oleva Huffman-koodi.
Huffman-taulukon unary-koodaus selectionEdit
Jos käytössä on useita Huffman-taulukoita, kunkin taulukon (numeroitu 0-5) valinta tehdään luettelosta nollapäätteisellä bitillä, jonka pituus on 1-6 bittiä. Valinta on taulukoiden MTF-luettelossa. Tämän ominaisuuden käyttäminen saa aikaan maksimilaajennuksen noin 1,015, mutta yleensä vähemmän. Tämä laajentuminen on todennäköisesti suuresti varjostettu sopivampien Huffman-taulukoiden valitsemisen edulla, ja yleinen tapaus jatkaa saman Huffman-taulukon käyttöä on esitetty yhtenä bittinä. Yksinkertaisen koodauksen sijaan tämä on käytännössä Huffman-puun äärimmäinen muoto, jossa jokaisella koodilla on puolet edellisen koodin todennäköisyydestä.
Delta encodingEdit
Huffman-koodin bittipituudet ovat tarvitaan kaikkien käytettyjen kanonisten Huffman-taulukoiden rekonstruoimiseksi. Jokainen bittipituus tallennetaan koodattuna erona edellisen koodin bittipituuteen nähden. Nollabitti (0) tarkoittaa, että edellinen bittipituus tulisi kopioida nykyiselle koodille, kun taas yksi bitti (1) tarkoittaa, että seuraava bitti tulisi lukea ja bittipituutta kasvattaa tai vähentää tämän arvon perusteella.
Tavallisessa tapauksessa käytetään yhtä bittiä per symboli per taulukko ja pahimmassa tapauksessa – siirtymällä pituudesta 1 pituuteen 20 – tarvitaan noin 37 bittiä. Aikaisemman MTF-koodauksen seurauksena koodin pituudet alkavat 2-3 bitin pituisina (hyvin usein käytettävät koodit) ja kasvavat vähitellen, mikä tarkoittaa, että delta-muoto on melko tehokas ja vaatii noin 300 bittiä (38 tavua) kutakin Huffman-taulukkoa kohden .
Sparse bit arrayEdit
Bittikarttaa käytetään osoittamaan, mitä symboleja lohkon sisällä käytetään ja jotka tulisi sisällyttää Huffman-puihin. Binaaritiedoissa käytetään todennäköisesti kaikkia 256 merkkiä, joita tavu edustaa, kun taas tekstidatassa voidaan käyttää vain pientä osajoukkoa käytettävissä olevista arvoista, mikä saattaa kattaa ASCII-alueen välillä 32 ja 126. 256 nollabitin tallentaminen olisi tehotonta, jos niitä ei enimmäkseen käytetä. Käytetään harvaa menetelmää: 256 symbolia on jaettu 16 alueeseen, ja vain, jos lohkossa käytetään symboleja, mukana on 16-bittinen taulukko. Jokaisen näistä 16 alueesta läsnäolo ilmaistaan 16-bittisellä lisätaulukolla etupuolella.
Kokonaisbittikartta käyttää 32 – 272 tallennustilabittiä (4–34 tavua). Sitä vastoin DEFLATE-algoritmi osoittaisi symbolien puuttumisen koodaamalla symbolit siten, että niillä on nollabittipituus juoksupituuskoodauksella ja ylimääräisellä Huffman-koodauksella.