bzip2 - bzip2

"Bzip" omdirigerer her. For proteindomænet, se bZIP -domæne .

bzip2
Bzip2-logo.svg
Originale forfatter (er) Julian Seward
Udvikler (er) Mark Wielaard, Federico Mena , Micah Snyder
Første udgivelse 18. juli 1996 ; 25 år siden ( 1996-07-18 )
Stabil udgivelse
1.0.8 / 13. juli 2019 ; 2 år siden ( 2019-07-13 )
Depot 1.0: https://sourceware.org/git/bzip2.git
1.1+: https://gitlab.com/bzip2/bzip2/
Operativ system På tværs af platforme
Type Datakomprimering
Licens BSD-lignende licens
Internet side sourceware .org /bzip2 /
bzip2
Filnavn udvidelse
.bz2
Internetmedietype
application/x-bzip2
Skriv kode Bzp2
Uniform Type Identifier (UTI) public.archive.bzip2
Magisk nummer BZh
Udviklet af Julian Seward
Type format Datakomprimering
Åbent format ? Ja

bzip2 er et gratis og open source - filkomprimeringsprogram, der bruger Burrows – Wheeler-algoritmen . Det komprimerer kun enkeltfiler og er ikke en filarkiver . Det blev udviklet af Julian Seward , og vedligeholdt af Mark Wielaard og Micah Snyder.

Historie

Seward offentliggjorde den første offentlige udgivelse af bzip2, version 0.15, i juli 1996. Kompressorens stabilitet og popularitet voksede i løbet af de næste flere år, og Seward udgav version 1.0 i slutningen af ​​2000. Efter en ni-års pause i opdateringer til projektet siden 2010 , den 4. juni 2019 accepterede Federico Mena vedligeholdelse af bzip2 -projektet. Siden juni 2021 er vedligeholder Micah Snyder.

Implementering

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

  1. Run-length encoding (RLE) af indledende data.
  2. Burrows – Wheeler -transformation (BWT) eller bloksortering.
  3. Move-to-front (MTF) transformering.
  4. Run-length encoding (RLE) for MTF-resultat.
  5. Huffman -kodning .
  6. Valg mellem flere Huffman -borde.
  7. Unary base-1 kodning af Huffman bordvalg.
  8. Delta-kodning (Δ) af Huffman-kode bitlængder.
  9. Sparsomt bit array, der viser, hvilke symboler der bruges.

Enhver sekvens med 4 til 255 på hinanden følgende dubletsymboler erstattes af de første 4 symboler og en gentagelseslængde mellem 0 og 251. Således bliver sekvensen AAAAAAABBBBCCCDerstattet med AAAA\3BBBB\0CCCD, hvor \3og \0repræsenterer byteværdier henholdsvis 3 og 0. Kørsler 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 ekspansion på 1,25, og i bedste fald en reduktion til <0,02. Selvom specifikationen teoretisk set tillader kørsler af længde 256–259 at blive kodet, vil referencekoderen ikke producere sådan output.

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

Burrows – Wheeler-transformen er den reversible blok-sort, der er kernen i bzip2. Blokken er helt selvstændig, med input- og outputbuffere tilbage af samme størrelse-i bzip2 er driftsgrænsen for dette trin 900 kB. Til blok -sorteringen oprettes en (fiktionel) matrix, hvor række i indeholder hele bufferen, roteret for at starte fra i -symbolet. Efter rotation sorteres matrixens rækker i alfabetisk (numerisk) rækkefølge. Der gemmes en 24-bit markør, der markerer startpositionen for, når blokken er utransformeret. I praksis er det ikke nødvendigt at konstruere den fulde matrix; sorteringen udføres snarere ved hjælp af pointer til hver position i bufferen. Outputbufferen er matrixens sidste kolonne; denne indeholder hele bufferen, men genbestilles, så den sandsynligvis vil indeholde store kørsler af identiske symboler.

Flyt-til-front-transformationen ændrer igen ikke størrelsen på den behandlede blok. Hver af de symboler, der bruges i dokumentet, er placeret i en matrix. Når et symbol behandles, erstattes det af dets placering (indeks) i arrayet, og det symbol blandes til forsiden af ​​arrayet. Virkningen er, at umiddelbart tilbagevendende symboler er erstattet med nul symboler (lang løber af enhver vilkårlig symbol således bliver kørsler med nul symboler), mens andre symboler er optegnes ny karakteristik ifølge deres lokale frekvens.

Meget "naturlige" data indeholder identiske symboler, der går igen inden for et begrænset område (tekst er et godt eksempel). Da MTF -transformationen tildeler lave værdier til symboler, der ofte vises igen, resulterer dette i en datastrøm, der indeholder mange symboler i det lave heltalsområde, hvoraf mange er identiske (forskellige tilbagevendende input -symboler kan faktisk knyttes til det samme output -symbol). Sådanne data kan kodes meget effektivt ved enhver ældre komprimeringsmetode.

Lange strenge af nuller i outputtet fra den fremadgående transformation (som kommer fra gentagne symboler i BWT-output) erstattes af en sekvens af to specielle koder, RUNA og RUNB, der repræsenterer kørelængden som en binært tal. Faktiske nuller er aldrig kodet i output; en ensom nul bliver RUNA. (Dette trin udføres faktisk på samme tid som MTF er; når MTF ville producere nul, øger det i stedet en tæller for derefter at kode med RUNA og RUNB.)

Sekvensen 0, 0, 0, 0, 0, 1ville være repræsenteret som RUNA, RUNB, 1; RUNA, RUNBrepræ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 første 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 end900 000  bytes ). Kørelængden er kodet på denne måde: Tildeling af stedværdier på 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 ligner base-2 bijective numeration . Således RUNA, RUNBresulterer sekvensen 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

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

Slut-of-stream-koden er særligt interessant. Hvis der bruges n forskellige bytes (symboler) i de ukomprimerede data, vil Huffman-koden bestå af to RLE-koder (RUNA og RUNB), n -1 symbolkoder og en ende-af-stream-kode. På grund af det kombinerede resultat af MTF- og RLE-kodningerne i de to foregående trin, er der aldrig behov for eksplicit at referere til det første symbol i MTF-tabellen (ville være nul i den almindelige MTF) og dermed gemme et symbol til slut- of-stream markør (og forklarer, hvorfor kun n -1 symboler er kodet i Huffman-træet). I det ekstreme tilfælde, hvor der kun bruges et symbol 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 af -strømsmarkør med værdi 2.

0: RUNA,
1: RUNB,
2–257: byteværdier 0–255,
258: slut på strøm, færdig behandling (kan være så lav som 2).

Flere Huffman -borde i samme størrelse kan bruges med en blok, hvis gevinsten ved at bruge dem er større end omkostningerne ved at inkludere det ekstra bord. Der kan være mindst 2 og op til 6 tabeller, hvor den mest passende tabel vælges igen før hver 50 symbol, der behandles. Dette har fordelen ved at have en meget lydhør Huffman -dynamik uden kontinuerligt at skulle levere nye tabeller, som det ville være nødvendigt i DEFLATE . Kørelængdekodning i det foregående trin er designet til at tage sig af koder, der har en omvendt sandsynlighed for brug højere end den korteste kode Huffman-kode i brug.

Hvis flere Huffman-tabeller er i brug, foretages valget af hver tabel (nummereret 0 til 5) fra en liste med en nul-afsluttet bitkørsel mellem 1 og 6 bit i længden. Valget er på en MTF -liste over tabellerne. Brug af denne funktion resulterer i en maksimal ekspansion på omkring 1.015, men generelt mindre. Denne udvidelse vil sandsynligvis blive stærkt overskygget af fordelen ved at vælge mere passende Huffman-borde, og den almindelige sag om fortsat brug af det samme Huffman-bord er repræsenteret som en enkelt bit. I stedet for unary kodning er dette effektivt en ekstrem form for et Huffman -træ, hvor hver kode har halvdelen af ​​sandsynligheden for den tidligere kode.

Huffman-kode bitlængder er nødvendige for at rekonstruere hver af de brugte kanoniske Huffman-tabeller . Hver bitlængde gemmes som en kodet forskel i forhold til den tidligere kodes bitlængde. En nulbit (0) betyder, at den tidligere bitlængde skal duplikeres for den aktuelle kode, mens en bit (1) betyder, at en yderligere bit skal læses og bitlængden øges eller reduceres baseret på denne værdi. I det almindelige tilfælde bruges en enkelt bit pr. Symbol pr. Tabel, og det værste tilfælde - fra længde 1 til længde 20 - ville kræve cirka 37 bit. Som et resultat af den tidligere MTF -kodning ville kodelængder starte med 2-3 bit lange (meget ofte anvendte koder) og gradvist stige, hvilket betyder, at delta -formatet er ret effektivt, hvilket kræver omkring 300 bit (38 bytes) pr. Fuld Huffman -tabel .

Et bitmap bruges til at vise, hvilke symboler der bruges inde i blokken og skal inkluderes i Huffman -træerne. Binære data vil sandsynligvis bruge alle 256 symboler, der repræsenteres med en byte, hvorimod tekstdata kun må bruge et lille undersæt af tilgængelige værdier, der måske dækker ASCII -området mellem 32 og 126. Lagring af 256 nul bits ville være ineffektivt, hvis de for det meste var ubrugte. En sparsom metode bruges: De 256 symboler er opdelt i 16 intervaller, og kun hvis der bruges symboler inden for denne blok, er der inkluderet et 16-bit array. Tilstedeværelsen af ​​hvert af disse 16 områder er angivet med en yderligere 16-bit bit array foran. Den samlede bitmap bruger mellem 32 og 272 bit lager (4–34 bytes). For kontrast ville DEFLATE- algoritmen vise fravær af symboler ved at kode symbolerne for at have en nul bitlængde med kodning af kørelængde og yderligere Huffman-kodning.

Filformat

Der findes ingen formel specifikation for bzip2, selvom en uformel specifikation er blevet reverse -konstrueret fra referenceimplementeringen.

Som en oversigt .bz2består en strøm af et 4-byte header efterfulgt af nul eller flere komprimerede blokke, umiddelbart efterfulgt af en end-of-stream-markør, der indeholder en 32-bit CRC for hele tekst i almindelig tekst behandlet. De komprimerede blokke er bitjusterede, og der forekommer ingen polstring. 

.magic:16                       = 'BZ' signature/magic number
.version:8                      = 'h' for Bzip2 ('H'uffman coding), '0' for Bzip1 (deprecated)
.hundred_k_blocksize:8          = '1'..'9' block-size 100 kB-900 kB (uncompressed)

.compressed_magic:48            = 0x314159265359 (BCD (pi))
.crc:32                         = checksum for this block
.randomised:1                   = 0=>normal, 1=>randomised (deprecated)
.origPtr:24                     = starting pointer into BWT for after untransform
.huffman_used_map:16            = bitmap, of ranges of 16 bytes, present/not present
.huffman_used_bitmaps:0..256    = bitmap, of symbols used, present/not present (multiples of 16)
.huffman_groups:3               = 2..6 number of different Huffman tables in use
.selectors_used:15              = number of times that the Huffman tables are swapped (each 50 symbols)
*.selector_list:1..6            = zero-terminated bit runs (0..62) of MTF'ed Huffman table (*selectors_used)
.start_huffman_length:5         = 0..20 starting bit length for Huffman deltas
*.delta_bit_length:1..40        = 0=>next symbol; 1=>alter length
                                                { 1=>decrement length;  0=>increment length } (*(symbols+2)*groups)
.contents:2..∞                  = Huffman encoded data stream until end of block (max. 7372800 bit)

.eos_magic:48                   = 0x177245385090 (BCD sqrt(pi))
.crc:32                         = checksum for whole stream
.padding:0..7                   = align to whole byte

På grund af RLE-komprimering i første trin (se ovenfor) er den maksimale længde af ren tekst, som en enkelt 900 kB bzip2-blok kan indeholde, omkring 46 MB (45.899.236 bytes). Dette kan forekomme, hvis hele klarteksten udelukkende består af gentagne værdier (den resulterende .bz2fil i dette tilfælde er 46 bytes lang). En endnu mindre fil på 40 bytes kan opnås ved at bruge et input, der fuldstændigt indeholder værdier på 251, et tilsyneladende komprimeringsforhold på 1147480,9: 1.

De komprimerede blokke i bzip2 kan uafhængigt dekomprimeres uden at skulle behandle tidligere blokke. Det betyder, at bzip2 -filer kan dekomprimeres parallelt, hvilket gør det til et godt format til brug i big data -applikationer med cluster computing -rammer som Hadoop og Apache Spark .

Effektivitet

bzip2 komprimerer de fleste filer mere effektivt end de ældre LZW ( .Z ) og Deflate ( .zip og .gz ) komprimeringsalgoritmer, men er betydeligt langsommere. LZMA er generelt mere pladsbesparende end bzip2 på bekostning af endnu lavere komprimeringshastighed, samtidig med at den har meget hurtigere dekomprimering.

bzip2 komprimerer data i blokke af størrelse mellem 100 og 900 kB og bruger Burrows – Wheeler-transformen til at konvertere ofte tilbagevendende tegnsekvenser til strenge af identiske bogstaver. Det anvender derefter flytte-til-front-transformation og Huffman-kodning . bzip2s forfader bzip brugte aritmetisk kodning i stedet for Huffman. Ændringen blev foretaget på grund af en softwarepatentbegrænsning .

bzip2 -ydelsen er asymmetrisk, da dekomprimering er relativt hurtig. Motiveret af den store CPU-tid, der kræves til komprimering, blev der i 2003 oprettet en modificeret version kaldet pbzip2, der understøttede multi-threading , hvilket gav næsten lineære hastighedsforbedringer på multi-CPU og multi-core computere. Fra maj 2010 er denne funktionalitet ikke blevet indarbejdet i hovedprojektet.

Ligesom gzip er bzip2 kun en datakompressor. Det er ikke en arkiver som tjære eller ZIP; selve programmet har ingen faciliteter til flere filer, kryptering eller arkivopdeling, men i UNIX-traditionen er det i stedet baseret på separate eksterne hjælpeprogrammer som tjære og GnuPG til disse opgaver.

Det grep-baserede bzgrepværktøj tillader direkte søgning gennem komprimeret tekst uden at skulle komprimere indholdet først.

Se også

Referencer

eksterne links