Original
Sparet

Metode

Mere om komprimering

Komprimeringsdemonstrator

Hvordan kan en fil blive mindre uden at miste et eneste bogstav? Ved at lægge mærke til, at den gentager sig selv. Indsæt en tekst, eller vælg et eksempel, og se tre klassiske metoder i aktion: LZ77 peger tilbage på tidligere tekst, LZW lærer en ordbog over tegnfølger, mens den læser, og run-length encoding tæller serier af det samme tegn. Hver metode dekomprimeres igen for at vise, at intet gik tabt, og en graf sammenligner dem med ZIP og med entropigrænsen. Skriv eller indsæt en tekst, eller vælg et eksempel, og vælg en metode. LZ77 erstatter gentagelser med henvisninger til tidligere tekst: klik på en fremhævet del for at se, hvad den kopierer. LZW opbygger en ordbog over tegnfølger, mens den læser, og sender deres numre. RLE presser serier af det samme tegn sammen. Grafen sammenligner hver metode med ZIP og med entropigrænsen, og appen dekomprimerer resultatet igen for at kontrollere, at intet er gået tabt.

Sådan virker det

  1. Skriv eller indsæt en tekst, eller vælg et eksempel: et afsnit, en sang med omkvæd, en række pixels, en datatabel, tilfældige bogstaver eller DNA.
  2. Vælg LZ77, LZW eller RLE. For LZ77 kan du indstille, hvor langt tilbage den må kigge, og klikke på en fremhævet henvisning for at se den tidligere tekst, den kopierer.
  3. Sammenlign størrelserne i felterne og grafen med ZIP og med entropigrænsen; kontrollen under teksten bekræfter, at dekomprimeringen giver originalen tilbage.

Gentagelser er nøglen

Tabsfri komprimering virker, fordi rigtige data gentager sig selv. LZ77 holder et vindue med den tekst, den lige har læst; hver gang de næste tegn allerede forekom i vinduet, skriver den en kort henvisning i stedet for selve tegnene: gå så langt tilbage, og kopiér så mange tegn. En henvisning koster et fast antal bit, uanset hvor lang kopien er, så lange og hyppige gentagelser sparer mest. LZW opnår samme effekt på en anden måde: den opbygger en ordbog over hver ny tegnfølge, den møder, og sender derefter tegnfølgens nummer.

Hvorfor nogle data ikke skrumper

En metode, der gør nogle filer mindre, må gøre andre større: der er færre korte filer end lange, så de kan ikke alle blive kortere. Komprimering vinder på data med mønstre, såsom tekst, tabeller og enkle billeder, og taber på data uden mønstre. Tilfældige bogstaver, krypterede data og filer, der allerede er komprimeret, giver metoderne intet at pege tilbage på, og outputtet bliver lige så stort som inputtet eller større. Run-length encoding viser det tydeligst: på tekst uden serier fordobler den størrelsen.

Ofte stillede spørgsmål

Hvad er forskellen på tabsfri og tabsgivende komprimering?

Tabsfri komprimering giver præcis originalen tilbage, bit for bit; den er nødvendig til tekst, programmer og data, og denne demonstrator viser kun tabsfri metoder. Tabsgivende komprimering, som i JPEG-fotos, MP3-musik og video, smider detaljer væk, som folk knap bemærker, og giver meget mindre filer, men originalen kan ikke genskabes.

Hvordan komprimerer ZIP filer?

ZIP og gzip bruger deflate, som først kører LZ77 med et vindue på 32 KB og derefter skriver literaler og henvisninger med Huffman-koder: korte koder for almindelige værdier og lange for sjældne. Det andet trin er grunden til, at ZIP som regel slår det simple LZ77, der vises her, og som bruger et fast antal bit på hvert token.

Kan LZ77 komme under entropien?

Den viste entropi tæller tegnene ét ad gangen, uden kontekst. LZ77 og LZW bruger kontekst, fordi en henvisning kopierer et helt stykke tidligere tekst, så på tekst med mange gentagelser kan de slå det tal med god margin. De kan aldrig slå kildens sande entropi, som tager al kontekst i betragtning.

Hvorfor afviger størrelserne fra en rigtig ZIP-fil?

Demonstratoren tæller kun bittene i de kodede data. En rigtig ZIP-fil tilføjer headere, filnavnet, en kontrolsum og Huffman-tabellerne, som gør meget små filer større snarere end mindre.

Bliver min tekst sendt nogen steder hen?

Nej. Alle metoder, også sammenligningen med ZIP, kører i din browser, og din tekst bliver i denne browsers lokale lager.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Gå til Editor