Datakomprimering forklaret
Hver webside, du indlæser, hver ZIP-fil og hvert PNG-billede er blevet komprimeret: gjort mindre uden at miste en eneste bit og pakket ud igen ved ankomsten. Metoderne bag er overraskende enkle. De leder efter ting, der gentager sig, og siger »det samme som før« i stedet for at sige det igen. Hvor langt den idé rækker, og hvor den stopper, er en af de fineste historier i datalogien.
Tabsfri og tabsgivende
Komprimering findes i to slags. Tabsfri komprimering giver præcis originalen tilbage, hvilket er afgørende for tekst, programmer, regneark og alt, hvor én forkert bit betyder noget. Tabsgivende komprimering, der bruges til fotos, musik og video, smider detaljer væk, som folk knap opfatter, og når langt mindre størrelser, men originalen er væk for altid. Denne side og demonstratoren handler om tabsfri komprimering, som virker ved at finde og fjerne redundans: de dele af data, der kunne have været forudsagt.
Run-length encoding
Den enkleste metode erstatter en serie af ens symboler med et antal og symbolet: tolv hvide pixels bliver til 12W. Faxmaskiner, tidlige bitmapformater og billedformatet PCX brugte den, fordi scannede sider og enkle tegninger er fulde af lange serier. På almindelig tekst er den nytteløs, ja skadelig: serier er sjældne, og at skrive et antal for hvert enkelt bogstav fordobler størrelsen. Run-length encoding lever stadig videre inde i andre metoder, til serier af nuller, der er tilbage efter en første transformation.
LZ77: at pege tilbage
I 1977 offentliggjorde Abraham Lempel og Jacob Ziv, to forskere ved Technion i Israel, en metode, der ændrede feltet. Koderen holder et vindue med den tekst, den lige har behandlet. Hvis de næste tegn allerede forekom i vinduet, skriver den et par: hvor langt tilbage den tidligere kopi begynder, og hvor lang den er. Ellers skriver den selve tegnet. Dekoderen behøver slet ingen ordbog, kun den tekst, den allerede har genopbygget. En henvisning må endda overlappe den tekst, den frembringer, så en serie på 100 ens bogstaver er ét bogstav og én henvisning.
LZW: at lære en ordbog
Lempels og Zivs anden metode, LZ78, opbygger en ordbog i stedet for at kigge tilbage i et vindue. Terry Welchs forfining fra 1984, LZW, starter med alle 256 byteværdier, sender ved hvert trin nummeret på den længste tegnfølge, den allerede kender, og tilføjer den tegnfølge plus det næste tegn som en ny post. Dekoderen genopbygger den samme ordbog alene ud fra numrene. LZW var hurtig og enkel, og den kom med i Unix-kommandoen compress, billedformatet GIF og TIFF-filer, indtil patenter på den udløste en lang strid i 1990'erne.
Deflate, ZIP og videre
Phil Katz' deflate-metode, introduceret med PKZIP 2 i 1993, kombinerer LZ77 med Huffman-kodning: når gentagelserne er fundet, giver den de mest almindelige literaler, længder og afstande de korteste bitkoder. Deflate bruges i ZIP, gzip, PNG-billeder og komprimering af websider, og det er den metode, demonstratoren måler med browserens egen komprimering. Nyere metoder som Zstandard, Brotli og xz bruger større vinduer, smartere søgning efter match og mere præcis entropikodning og presser typiske filer yderligere 10 til 30 % sammen.
Hvorfor ikke alt kan skrumpe
Ingen metode kan gøre alle filer mindre. Der findes 2ⁿ filer på n bit, men kun 2ⁿ − 1 filer, der er kortere, så hvis en metode formindskede dem alle, ville to ende med at blive ens og kunne ikke begge genskabes: skuffeprincippet. Ethvert komprimeringsprogram forstørrer derfor nogle input, som regel data, der ser tilfældige ud, såsom krypterede filer, allerede komprimerede filer og støj. Det er også en test for tilfældighed: data, som intet komprimeringsprogram kan gøre mindre, ser tilfældige ud.
Entropigrænsen
Claude Shannon viste i 1948, at entropien af en kilde er det mindst mulige gennemsnitlige antal bit pr. symbol for enhver tabsfri kode. Talt bogstav for bogstav har engelsk tekst en entropi på omkring 4 bit pr. bogstav, halvdelen af de 8 bit, den gemmes i. Metoder, der bruger kontekst, som LZ77, kommer under dette tal for enkeltbogstaver på tekst med mange gentagelser, fordi en henvisning står for et helt stykke på én gang. De bedste moderne komprimeringsprogrammer, som forudsiger hvert bogstav ud fra alt, hvad der kom før, får engelsk ned under 2 bit pr. bogstav.
Udforsk det
Åbn komprimeringsdemonstratoren for at køre LZ77, LZW og run-length encoding på et afsnit, en sang med omkvæd, en række pixels, en datatabel, tilfældige bogstaver eller DNA, eller på din egen tekst. Klik på en LZ77-henvisning for at se, hvad den kopierer, se LZW-ordbogen vokse, og sammenlign alle metoder med ZIP og entropigrænsen.
Ofte stillede spørgsmål
Hvad betyder et komprimeringsforhold på 3 : 1?
At originalen er tre gange så stor som den komprimerede version, så den komprimerede fil fylder en tredjedel af pladsen og sparer to tredjedele. Tekst når typisk 2 : 1 til 4 : 1 med ZIP; data med mange gentagelser, såsom logfiler, ofte langt mere.
Hvorfor hjælper det ikke at komprimere en ZIP-fil igen?
Første omgang har allerede fjernet gentagelserne, og dens output ser næsten tilfældigt ud. En anden omgang finder intet at pege tilbage på og lægger kun sit eget overhead til, så filen forbliver lige så stor eller vokser en smule.
Hvorfor er et større LZ77-vindue bedre?
Et større vindue lader koderen finde gentagelser, der ligger længere tilbage, som et omkvæd, der vender tilbage efter flere vers. Prisen er, at hver afstand kræver flere bit at skrive, og at søgningen tager længere tid; derfor stopper deflate ved 32 KB, mens nyere metoder tillader megabyte.
Er komprimering det samme som kryptering?
Nej. Komprimering gør data mindre, og enhver kan pakke dem ud igen; kryptering gør data ulæselige uden en nøgle. De kombineres ofte, og så skal data komprimeres først: krypterede data ser tilfældige ud og kan ikke længere komprimeres.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Åbn komprimeringsdemonstratoren