bzip2 (Magyar)

A Bzip2 egymásra helyezett többféle tömörítési technikát használ, amelyek a következő sorrendben fordulnak elő a tömörítés során, és fordított sorrendben a dekompresszió során:

1. A kezdeti adatok futási hosszúságú kódolása (RLE).
2. Burrows – Wheeler transzformáció (BWT) vagy blokkválogatás.
3. Áthelyezés elõre (MTF) transzformáció.
4. Az MTF eredmény futási hosszúságú kódolása (RLE).
5. Huffman-kódolás.
6. Választás több Huffman-táblázat között.
7. Unáris alap-1 kódolás a Huffman-táblázat választékából.
8. Huffman-kód bithosszak delta kódolása (Δ).
9. Ritka bit tömb, amely bemutatja, hogy mely szimbólumokat használják.

Kezdeti futási hosszúságú encodingEdit

Bármely 4–255 egymást követő duplikális szimbólum sorozatát az első 4 szimbólum és az ismétlés hossza 0 és 251 között váltja fel. Így a AAAAAAABBBBCCCD helyébe AAAA\3BBBB\0CCCD lép, ahol \3 és \0 a 3. és a 0 bájt értéket képviseli. A szimbólumfuttatások mindig átalakulnak 4 egymást követő szimbólum után, még akkor is, ha a futás hossza nullára van állítva, hogy az átalakítás visszafordítható maradjon.

Legrosszabb esetben 1,25-ös bővítést okozhat, és a legjobb esetben redukció < 0,02-re. Míg a specifikáció elméletileg lehetővé teszi a 256–259 hosszúságú futtatások kódolását, a referencia kódoló nem hoz létre ilyen kimenetet.

A bzip2 szerzője kijelentette, hogy az RLE lépés történelmi hiba volt, és csak azt szánta hogy megvédje az eredeti BWT implementációt a kóros esetektől.

Burrows – Wheeler transformEdit

Ez a visszafordítható blokk-rendezés a bzip2 lényege. A blokk teljesen önálló, a bemeneti és kimeneti pufferek azonos méretűek maradnak – a bzip2-ben ennek a fokozatnak a működési határa 900 kB. A blokk-rendezéshez létrejön egy (elméleti) mátrix, amelyben az i sor a puffer egészét tartalmazza, elforgatva, hogy az i-edik szimbólumból induljon. A forgatás után a mátrix sorait ábécé (numerikus) sorrendbe rendezzük. Egy 24 bites mutató tárolódik, jelezve a kiindulási helyzetet, amikor a blokk nincs átalakítva. A gyakorlatban nem szükséges a teljes mátrix felépítése; a rendezés inkább a puffer minden pozíciójára mutató mutatók segítségével történik. A kimeneti puffer a mátrix utolsó oszlopa; ez tartalmazza a teljes puffert, de átrendezve úgy, hogy valószínűleg nagyszámú azonos szimbólumot tartalmaz.

Áthelyezés elõre transformEdit

Ez a transzformáció megint nem változtatja meg a feldolgozott blokk méretét. A dokumentumban használt szimbólumok mindegyike egy tömbbe kerül. Ha egy szimbólum feldolgozásra kerül, akkor helyét (indexét) a tömbben leváltja, és ez a szimbólum a tömb elejére kerül. Ennek az a következménye, hogy az azonnal ismétlődő szimbólumokat nulla szimbólum váltja fel (bármely tetszőleges szimbólum hosszú futása így nulla szimbólum futtatásává válik), míg más szimbólumokat helyi frekvenciájuknak megfelelően újrarendeznek.

Sok “természetes” adat azonos szimbólumokat tartalmaz, amelyek korlátozott tartományon belül ismétlődnek (a szöveg jó példa). Mivel az MTF transzformáció alacsony értékeket rendel a gyakran újra megjelenő szimbólumokhoz, ez egy olyan adatfolyamot eredményez, amely sok szimbólumot tartalmaz az alacsony egész tartományban, sok közülük azonos (a különböző visszatérő bemeneti szimbólumok tulajdonképpen ugyanahhoz a kimeneti szimbólumhoz tudnak hozzárendelni). Ezeket az adatokat nagyon hatékonyan kódolhatja bármilyen régi tömörítési módszer.

Az MTF resultEdit futási hosszúságú kódolása

Hosszú nullákból álló húrok az előtérbe történő transzformáció kimenetében ( amelyek a BWT kimenetén ismétlődő szimbólumokból származnak) két speciális kód, a RUNA és a RUNB sorozata váltja fel, amelyek bináris számként jelentik a futás hosszát. A tényleges nullákat soha nem kódoljuk a kimenetbe; a magányos nulla RUNA lesz. (Ez a lépés valójában ugyanabban az időben történik, mint az MTF; amikor az MTF nulla értéket produkál, ehelyett növeli a számlálót, majd a RUNA és a RUNB kódolással jár.)

A RUNA, RUNB, 1; A RUNA, RUNB az alábbiakban leírt 5. értéket képviseli. A futási hosszúságú kód egy másik normál szimbólum elérésével szűnik meg. Ez az RLE folyamat rugalmasabb, mint a kezdeti RLE lépés, mivel képes önkényesen hosszú egész számok kódolására (a gyakorlatban ezt általában a blokk mérete korlátozza, így ez a lépés nem kódol 900 000 bájtnál nagyobb futást). A futási hossz így van kódolva: az első bithez 1, 2 a másodikhoz, 4 a harmadikhoz stb. Hozzárendeljük a sorrendben a helyértékeket, megszorozzuk a RUNB pont minden helyértékét 2-vel, és hozzáadjuk az összes az eredményül kapott helyértékeket (RUNA és RUNB értékekhez egyaránt) együtt. Ez hasonló az alap-2 bijektív számozáshoz.Így a RUNA, RUNB sorozat az (1 + 2 × 2) = 5 értéket eredményezi. Bonyolultabb példaként:

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

Huffman codingEdit

Ez a folyamat a 0–258 tartományban rögzített hosszúságú szimbólumokat váltja ki a használat gyakorisága alapján változó hosszúságú kódokkal. A gyakran használt kódok rövidebbek (2–3 bitek), míg a ritka kódok akár 20 bitet is lefoglalhatnak. A kódokat gondosan választják ki, hogy egyetlen bit kódja sem keverhető össze egy másik kódnál.

A stream vége kód különösen érdekes. Ha n különféle bájt (szimbólum) van a tömörítetlen adatokban, akkor a Huffman-kód két RLE-kódból (RUNA és RUNB), n – 1 szimbólumkódból és egy adatfolyam végi kódból áll. Az előző két lépés MTF és RLE kódolásának együttes eredménye miatt soha nincs szükség arra, hogy kifejezetten hivatkozzunk az MTF táblázat első szimbólumára (a szokásos MTF-ben nulla lenne), így egy szimbólumot spórolunk a végére. of-stream marker (és elmagyarázza, hogy miért csak n – 1 szimbólum van kódolva a Huffman-fában). Szélsőséges esetben, amikor a tömörítetlen adatokban csak egy szimbólumot használnak, a Huffman-fában egyáltalán nem lesznek szimbólumkódok, és az egész blokk RUNA-ból és RUNB-ből áll (implicit módon ismételve az egyetlen bájtot) és egy végéből. -stream marker 2-es értékkel.

0: RUNA, 1: RUNB, 2–257: bájtértékek 0–255, 258: a stream vége, a feldolgozás befejezése (akár 2 is lehet).

Több Huffman-táblaEdit

Több egyforma méretű Huffman-tábla használható blokkkal, ha azok használatának nyeresége meghaladja az extra tábla bekerülésének költségét. Legalább 2 és legfeljebb 6 asztal lehet jelen, a legmegfelelőbb táblázatot minden 50 szimbólum feldolgozása előtt újból kiválasztják. Ennek az az előnye, hogy nagyon érzékeny Huffman-dinamikával rendelkezik, anélkül, hogy folyamatosan új táblákat kellene szolgáltatnia, amire a DEFLATE-ben szükség lenne. Az előző lépésben a futási hosszúságú kódolás célja az olyan kódok gondozása, amelyek fordított felhasználási valószínűsége nagyobb, mint a legrövidebb használatban lévő Huffman kód.

A Huffman tábla selectionEdit

Ha több Huffman-tábla van használatban, akkor az egyes táblák (0–5-ig számozott) kiválasztása egy listából történik, nulla végű, 1 és 6 bit közötti bitfuttatással. A kiválasztás a táblázatok MTF-listájába kerül. Ennek a szolgáltatásnak a használata maximális terjeszkedést eredményez 1,015 körül, de általában kevesebbet. Ezt a terjeszkedést valószínűleg nagyon árnyékolja a megfelelőbb Huffman-táblák kiválasztásának előnye, és ugyanazon Huffman-tábla használatának gyakori esete egyetlen bitként van ábrázolva. Az unárikus kódolás helyett ez gyakorlatilag a Huffman fa szélsőséges formája, ahol minden kódnak a fele a valószínűsége az előző kódnak.

Delta encodingEdit

A Huffman-kód bithossza: szükséges a használt kanonikus Huffman-táblák rekonstruálásához. Minden bithossz kódolt különbségként kerül tárolásra az előző kód bithosszával szemben. A nulla bit (0) azt jelenti, hogy az előző bit hosszúságát meg kell másolni az aktuális kódhoz, míg az egy bit (1) azt jelenti, hogy egy további bitet kell olvasni, és a bit hosszát növelni vagy csökkenteni kell az érték alapján.

A gyakori esetben táblánként szimbólumenként egyetlen bitet használnak, és a legrosszabb esetben – az 1-től a 20-ig terjedve – hozzávetőlegesen 37 bitre lenne szükség. A korábbi MTF-kódolás eredményeként a kód hossza 2-3 bit hosszúságú lenne (nagyon gyakran használt kódok) és fokozatosan növekedne, ami azt jelenti, hogy a delta formátum meglehetősen hatékony, és kb. 300 bitre (38 bájt) van szükség teljes Huffman-táblánként. .

Sparse bit arrayEdit

Egy bittérkép segítségével meg lehet mutatni, hogy a blokkban milyen szimbólumokat használnak, és ezeket bele kell foglalni a Huffman-fákba. A bináris adatok valószínűleg mind a 256 bájt által reprezentálható szimbólumot használják, míg a szöveges adatok csak a rendelkezésre álló értékek kis részhalmazát használhatják fel, esetleg lefedik az ASCII tartományt 32 és 126. között. A 256 nulla bit tárolása nem hatékony, ha azokat többnyire nem használják. Ritka módszert alkalmaznak: a 256 szimbólum 16 tartományra van felosztva, és csak akkor, ha szimbólumokat használnak az adott blokkon belül, akkor egy 16 bites tömböt is tartalmaz. E 16 tartomány mindegyikének jelenlétét egy további 16 bites tömb jelzi az elején.

A teljes bittérkép 32 és 272 bit közötti tárhelyet (4–34 bájt) használ. Ezzel szemben a DEFLATE algoritmus a szimbólumok hiányát mutatná meg azzal, ha a szimbólumokat nulla bithosszúsággal, futás hosszúságú kódolással és további Huffman-kódolással kódolják.