Tøm luft - Deflate

Denne artikel handler om datakomprimeringsalgoritmen. For anden anvendelse, se Deflation (disambiguation) .

I computing er Deflate et tabsfrit datakomprimeringsfilformat , der bruger en kombination af LZSS- og Huffman -kodning . Det blev designet af Phil Katz til version 2 af hans PKZIP -arkiveringsværktøj. Deflate blev senere specificeret i RFC 1951 (1996).

Katz designet også den originale algoritme, der blev brugt til at konstruere Deflate -strømme. Denne algoritme blev patenteret som US patent 5.051.745 og tildelt PKWARE, Inc. Som anført i RFC -dokumentet blev en algoritme, der producerer Deflate -filer, bredt antaget at kunne implementeres på en måde, der ikke er omfattet af patenter. Dette førte til dens udbredte anvendelse - for eksempel i gzip -komprimerede filer og PNG -billedfiler ud over ZIP -filformatet, som Katz oprindeligt designede det til. Patentet er siden udløbet.

Stream format

En Deflate -strøm består af en række blokke. Hver blok går forud for et 3- bit header:

  • Første bit: Sidste-blok-i-stream markør:
    • 1: Dette er den sidste blok i strømmen.
    • 0: Der er flere blokke, der skal behandles efter denne.
  • Anden og tredje bit: Kodningsmetode, der bruges til denne bloktype:
    • 00: En lagret (også kaldet rå eller bogstavelig) sektion, mellem 0 og 65.535 bytes i længden
    • 01: En statisk Huffman- komprimeret blok ved hjælp af et på forhånd aftalt Huffman-træ defineret i RFC
    • 10: En komprimeret blok komplet med det medfølgende Huffman -bord
    • 11: Reserveret - brug ikke.

Den lagrede blokindstilling tilføjer minimal overhead og bruges til data, der er inkomprimerbare.

De fleste komprimerbare data vil ende med at blive kodet ved hjælp af metode 10, den dynamiske Huffman -kodning, som producerer et optimeret Huffman -træ, der er tilpasset hver blok af data individuelt. Instruktioner til at generere det nødvendige Huffman -træ følger straks blokhovedet. Den statiske Huffman-indstilling bruges til korte beskeder, hvor den faste besparelse opnået ved at udelade træet opvejer det procentvise komprimeringstab på grund af brug af en ikke-optimal (altså ikke teknisk Huffman) kode.

Kompression opnås gennem to trin:

  • Matchning og udskiftning af dublerede strenge med pointers.
  • Udskiftning af symboler med nye, vægtede symboler baseret på brugsfrekvens.

Bitreduktion

Hovedartikel: Huffman -kodning

Det andet komprimeringstrin består i at erstatte almindeligt anvendte symboler med kortere repræsentationer og mindre almindeligt anvendte symboler med længere repræsentationer. Den anvendte metode er Huffman-kodning, der skaber et ikke-præfikseret træ med ikke-overlappende intervaller, hvor længden af ​​hver sekvens er omvendt proportional med logaritmen for sandsynligheden for, at dette symbol skal kodes. Jo mere sandsynligt det er, at et symbol skal kodes, jo kortere vil bit-sekvensen være.

Der oprettes et træ, der indeholder plads til 288 symboler:

  • 0–255: repræsenterer de bogstavelige bytes/symboler 0–255.
  • 256: blokens slutning - stop behandlingen, hvis den sidste blok, ellers start behandlingen af ​​den næste blok.
  • 257–285: kombineret med ekstra-bits, en matchlængde på 3–258 bytes.
  • 286, 287: ikke brugt, forbeholdt og ulovligt, men stadig en del af træet.

En matchlængdekode vil altid blive efterfulgt af en afstandskode. Baseret på den aflæste afstandskode kan yderligere "ekstra" bits læses for at producere den endelige afstand. Afstandstræet indeholder plads til 32 symboler:

  • 0–3: distancer 1-4
  • 4–5: distancer 5–8, 1 ekstra bit
  • 6–7: distancer 9–16, 2 ekstra bits
  • 8–9: distancer 17–32, 3 ekstra bits
  • ...
  • 26–27: afstande 8.193–16.384, 12 ekstra bits
  • 28–29: afstande 16.385–32.768, 13 ekstra bits
  • 30–31: ikke brugt, forbeholdt og ulovligt, men stadig en del af træet.

Bemærk, at for matchafstandssymbolerne 2–29 kan antallet af ekstra bits beregnes som .

De to koder (288-symbolets længde/bogstavelige træ og 32-symbolets afstandstræ) er selv kodet som kanoniske Huffman-koder ved at angive bitlængden af ​​koden for hvert symbol. Bitlængderne er i sig selv kodet med længde for at frembringe en så kompakt repræsentation som muligt. Som et alternativ til at inkludere trærepræsentationen giver indstillingen "statisk træ" faste faste Huffman -træer. Den komprimerede størrelse ved hjælp af de statiske træer kan beregnes ved hjælp af den samme statistik (antallet af gange hvert symbol vises), som bruges til at generere de dynamiske træer, så det er let for en kompressor at vælge den, der er mindre.

Elimination af dubletter af strenge

Hovedartikler: LZ77 og LZ78 og LZSS

Inden komprimerede blokke, hvis en dublet serie af bytes er plettet (en gentagen streng), derefter en ryg- henvisning indsættes, der forbinder til den tidligere placering af den identiske streng i stedet. En kodet match til en tidligere streng består af en 8-bit længde (3–258 bytes) og en 15-bit afstand (1–32.768 bytes) til begyndelsen af ​​dubletten. Relative bagreferencer kan foretages på tværs af et vilkårligt antal blokke, så længe afstanden vises inden for de sidste 32  KiB ukomprimerede data afkodet (kaldet glidevinduet ).

Hvis afstanden er mindre end længden, overlapper kopien sig selv, hvilket angiver gentagelse. For eksempel kan en kørsel på 10 identiske bytes kodes som en byte efterfulgt af en duplikat med længde 9, der begynder med den forrige byte.

Søgning efter den foregående tekst efter dublerede substrater er den mest beregningsmæssigt dyre del af DEFLATE -algoritmen, og den handling, som indstillinger for komprimeringsniveau påvirker.

Encoder/kompressor

Under komprimeringsfasen er det encoderen, der vælger den tid, der skal bruges på at lede efter matchende strenge. Zlib/gzip referenceimplementeringen gør det muligt for brugeren at vælge fra en glidende skala af sandsynligt resulterende komprimeringsniveau i forhold til kodningshastighed. Indstillinger spænder fra 0(prøv ikke komprimering, bare gem ukomprimeret) til at 9repræsentere den maksimale kapacitet for referenceimplementeringen i zlib/gzip.

Andre Deflate -encodere er blevet produceret, som alle også vil producere en kompatibel bitstream, der kan dekomprimeres af enhver eksisterende Deflate -dekoder. Forskellige implementeringer vil sandsynligvis producere variationer af den endelige kodede bitstrøm, der produceres. Fokus med ikke-zlib-versioner af en encoder har normalt været at producere en mere effektivt komprimeret og mindre kodet strøm.

Deflate64/Enhanced Deflate

Deflate64, angivet af PKWARE, er en proprietær variant af Deflate. Det er grundlæggende den samme algoritme. Det, der har ændret sig, er stigningen i ordbogstørrelse fra 32 KB til 64 KB, en udvidelse af afstandskoderne til 16 bit, så de kan adressere et område på 64 KB, og længdekoden, som udvides til 16 bit, så den kan definere længder på tre til 65.538 bytes. Dette fører til, at Deflate64 har en længere komprimeringstid og muligvis et lidt højere komprimeringsforhold end Deflate. Flere gratis og/eller open source-projekter understøtter Deflate64, f.eks. 7-Zip , mens andre, f.eks. Zlib , ikke gør det på grund af procedurens proprietære karakter og den meget beskedne ydelsesstigning i forhold til Deflate.

Brug af Deflate i ny software

Implementeringer af Deflate er frit tilgængelige på mange sprog. C -programmer bruger typisk zlib -biblioteket (licenseret under zlib -licensen , som tillader brug med både gratis og proprietær software). Programmer skrevet med Borland -dialekter fra Pascal kan bruge paszlib; et C ++ bibliotek er inkluderet som en del af 7-Zip / AdvanceCOMP . Java inkluderer support som en del af standardbiblioteket (i java.util.zip). Microsoft .NET Framework 2.0 basisklassebibliotek understøtter det i System.IO.Compression -navneområdet . Programmer i Ada kan bruge Zip-Ada (ren) eller ZLib-Ada tyk binding til zlib.

Encoder implementeringer

  • PKZIP : den første implementering, oprindeligt udført af Phil Katz som en del af PKZip.
  • zlib / gzip : standardreferenceimplementering, der bruges i en enorm mængde software, på grund af offentlig tilgængelighed af kildekoden og en licens, der tillader inkludering i anden software.
  • Crypto ++ : indeholder en offentlig domæneimplementering i C ++, der hovedsageligt er rettet mod at reducere potentielle sikkerhedsrisici . Forfatteren, Wei Dai udtaler " Denne kode er mindre klog, men forhåbentlig mere forståelig og vedligeholdelig [end zlib] ".
  • 7-Zip / AdvanceCOMP : skrevet af Igor Pavlov i C ++ , denne version er frit licenseret og har en tendens til at opnå højere komprimering end zlib på bekostning af CPU-brug. Har mulighed for at bruge DEFLATE64 lagringsformat.
  • PuTTY 'sshzlib.c': en standalone implementering, i stand til fuld afkode, men statisk træ kun skabelse, af Simon Tatham. MIT licenseret .
  • Plan 9 fra Bell Labs -operativsystemets libflate -implementerer deflate -komprimering .
  • Hyperbac : bruger sit eget proprietære tabsfri komprimeringsbibliotek (skrevet i C ++ og Assembly) med mulighed for at implementere DEFLATE64 -lagringsformatet.
  • Zopfli : C -implementering fra Google, der opnår den højeste komprimering på bekostning af CPU -brug. ZopfliPNG er en variant af Zopfli til brug med PNG'er . Apache licenseret .
  • igzip, en encoder skrevet i x86 -samling frigivet af Intel under MIT -licensen. 3x hurtigere end zlib -1. Nyttig til komprimering af genomiske data.

AdvanceCOMP bruger versionen med højere komprimeringsforhold af Deflate som implementeret af 7-Zip (eller eventuelt Zopfli i nyere versioner) for at muliggøre rekomprimering af gzip- , PNG- , MNG- og ZIP- filer med mulighed for at opnå mindre filstørrelser, end zlib maksimalt kan indstillinger.

Hardwarekodere

  • AHA361-PCIX/AHA362-PCIX fra Comtech AHA . Comtech producerede et PCI-X- kort (PCI-ID 193f:0001:), der er i stand til at komprimere streams ved hjælp af Deflate med en hastighed på op til 3,0 Gbit/s (375 MB/s) til indgående ukomprimerede data. Ledsager til Linux-kernel- driveren til AHA361-PCIX er et " ahagzip" værktøj og tilpasset " mod_deflate_aha" i stand til at bruge hardware-komprimering fra Apache . Hardwaren er baseret på en Xilinx Virtex FPGA og fire brugerdefinerede AHA3601 ASIC'er . AHA361/AHA362 -kortene er begrænset til kun at håndtere statiske Huffman -blokke og kræver, at software ændres for at tilføje support - kortene kunne ikke understøtte den fulde Deflate -specifikation, hvilket betyder, at de kun pålideligt kunne afkode deres eget output (en strøm, der ikke indeholder enhver dynamisk Huffman type 2 -blok).
  • StorCompress 300 / MX3 fra Indra Networks . Dette er en række PCI (PCI-ID 17b4:0011:) eller PCI-X-kort med mellem en og seks kompressionsmotorer med påståede behandlingshastigheder på op til 3,6 Gbit/s (450 MB/s). En version af kortene er tilgængelige med det separate mærke WebEnhance, der er specielt designet til web-servering i stedet for SAN eller backup. en PCIe revision, den MX4E fremstilles også.
  • AHA363-PCIe / AHA364-PCIe / AHA367-PCIe . I 2008 begyndte Comtech at producere to PCIe -kort ( PCI-ID: 193f:0363/ 193f:0364) med en ny hardware AHA3610 encoder -chip. Den nye chip blev designet til at være i stand til en vedvarende 2,5 Gbit/s. Ved hjælp af to af disse chips kan AHA363-PCIe-kortet behandle Deflate med en hastighed på op til 5,0 Gbit/s (625 MB/s) ved hjælp af de to kanaler (to kompression og to dekomprimering). AHA364-PCIe-varianten er en version kun af kode designet til udgående belastningsbalancere og har i stedet flere registersæt til at tillade 32 uafhængige virtuelle kompressionskanaler, der fodrer to fysiske kompressionsmotorer. Linux-, Microsoft Windows- og OpenSolaris -kerneenhedsdrivere er tilgængelige til begge de nye kort sammen med et modificeret zlib -systembibliotek, så dynamisk linkede applikationer automatisk kan bruge hardwaresupporten uden intern ændring. AHA367-PCIe-kortet ( PCI-ID: 193f:0367) ligner AHA363-PCIe, men bruger fire AHA3610-chips til en vedvarende komprimeringshastighed på 10 Gbit/s (1250 MB/s). I modsætning til AHA362-PCIX er decompressionsmotorerne på AHA363-PCIe og AHA367-PCIe-kortene fuldt ud deflate-kompatible.
  • Nitrox og OCTEON processorer fra Cavium, Inc. indeholder højhastigheds-hardware deflatere og pump motorer kompatibel med både ZLIB og GZIP med nogle enheder i stand til at håndtere flere samtidige datastrømme.
  • HDL-Deflate GPL FPGA implementering.
  • ZipAccel-C fra CAST Inc . Dette er en Silicon IP -kerne, der understøtter Deflate, Zlib og Gzip -komprimering . ZipAccel-C kan implementeres i ASIC- eller FPGA'er , understøtter både dynamiske og statiske Huffman-tabeller og kan levere overførsler på over 100 Gbps. Virksomheden tilbyder referencedesign til kompression/dekomprimering af acceleratorkort til Intel FPGA ( ZipAccel-RD-INT ) og Xilinx FPGA'er ( ZipAccel-RD-XIL ).
  • Intel Communications Chipset 89xx Series (Cave Creek) til Intel Xeon E5-2600 og E5-2400 Processorserien (Sandy Bridge-EP/EN) understøtter hardwarekompression og dekomprimering ved hjælp af QuickAssist Technology. Afhængigt af chipsættet er kompressions- og dekomprimeringshastigheder på 5 Gbit/s, 10 Gbit/s eller 20 Gbit/s tilgængelige.

Dekoder/dekompressor

Inflate er afkodningsprocessen, der tager en Deflate-bitstrøm til dekomprimering og korrekt producerer de originale data i fuld størrelse eller fil.

Opblæsbare implementeringer

Den normale hensigt med en alternativ Inflate-implementering er stærkt optimeret afkodningshastighed eller ekstremt forudsigelig RAM-brug til mikro-controller integrerede systemer.

  • C / C ++
    • kunzip af Michael Kohn og ikke relateret til "KZIP". Leveres med C -kildekode under GNU LGPL- licensen. Anvendes i GIMP -installationsprogrammet .
    • puff.c ( zlib ), en lille, ikke-behæftet, enkeltfilreferenceimplementering inkluderet i /contrib /puff-biblioteket i zlib-distributionen.
    • tinf skrevet af Jørgen Ibsen i ANSI C og leveres med zlib -licens. Tilføjer cirka 2k kode.
    • tinfl.c ( miniz ), Public domain Inflate -implementering indeholdt helt i en enkelt C -funktion.
  • PCDEZIP, Bob Flanders og Michael Holmes, offentliggjort i PC Magazine 1994-01-11.
  • inflate.cl af John Foderaro. Selvstændig Common Lisp- dekoder distribueret med en GNU LGPL- licens.
  • inflate.s7i / gzip.s7i , en ren- Seed7- implementering af Deflate og gzip-dekompression, af Thomas Mertes. Gjorde tilgængelig under GNU LGPL -licensen.
  • pyflate , en ren- Python- stand-alone Deflate ( gzip ) og bzip2- dekoder af Paul Sladen. Skrevet til forskning / prototyper og stillet til rådighed under BSD / GPL / LGPL / DFSG -licenser.
  • deflatelua , en ren- Lua- implementering af Deflate og gzip /zlib-dekompression, af David Manura.
  • blæs en ren- Javascript- implementering af Inflate af Chris Dickinson
  • pako : JavaScript-hastighedsoptimeret port af zlib. Indeholder separat opbygning med kun oppustning.

Hardware -dekodere

  • Seriel Inflate GPU fra BitSim. Hardwareimplementering af Inflate. En del af BitSims BADGE (Bitsim Accelerated Display Graphics Engine) controller -tilbud til integrerede systemer.
  • HDL-Deflate GPL FPGA implementering.
  • ZipAccel-D fra CAST Inc . Dette er en Silicon IP -kerne, der understøtter dekomprimering af Deflate-, Zlib- og Gzip -filer. ZipAccel-D IP-kernen, der kan implementeres i ASIC eller FPGA'er. Virksomheden tilbyder referencedesign til kompression/dekomprimering af acceleratorkort til Intel FPGA ( ZipAccel-RD-INT ) og Xilinx FPGA'er ( ZipAccel-RD-XIL ).

Se også

Referencer

eksterne links