Datakomprimering förklarad
Varje webbsida du laddar, varje ZIP-fil och varje PNG-bild har komprimerats: gjorts mindre utan att förlora en enda bit, och packats upp igen vid ankomsten. Metoderna bakom är förvånansvärt enkla. De letar efter sådant som upprepas och säger ”samma som förut” i stället för att säga det igen. Hur långt den idén räcker, och var den tar stopp, är en av de vackraste historierna inom datavetenskapen.
Förlustfri och destruktiv
Komprimering finns i två slag. Förlustfri komprimering ger tillbaka exakt originalet, vilket är nödvändigt för text, program, kalkylblad och allt där en enda felaktig bit spelar roll. Destruktiv komprimering, som används för foton, musik och video, kastar bort detaljer som människor knappt uppfattar och når mycket mindre storlekar, men originalet är borta för gott. Den här sidan och demon handlar om förlustfri komprimering, som fungerar genom att hitta och ta bort redundans: de delar av datan som hade kunnat förutsägas.
Skurlängdskodning
Den enklaste metoden ersätter en skur av identiska symboler med ett antal och symbolen: tolv vita pixlar blir 12W. Faxmaskiner, tidiga bitmappsformat och bildformatet PCX använde den, eftersom skannade sidor och enkla teckningar är fulla av långa skurar. På vanlig text är den oanvändbar, till och med skadlig: skurar är sällsynta, och att skriva ett antal för varje enskild bokstav fördubblar storleken. Skurlängdskodning lever ändå kvar inuti andra metoder, för skurar av nollor som blir kvar efter en första transformation.
LZ77: att peka bakåt
År 1977 publicerade Abraham Lempel och Jacob Ziv, två forskare vid Technion i Israel, en metod som förändrade området. Kodaren håller ett fönster med texten den just har bearbetat. Om nästa tecken redan har förekommit i fönstret skriver den ett par: hur långt bakåt den tidigare kopian börjar och hur lång den är. Annars skriver den själva tecknet. Avkodaren behöver ingen ordbok alls, bara den text den redan har byggt upp igen. En referens kan till och med överlappa den text den skapar, så en skur av 100 identiska bokstäver blir en bokstav och en referens.
LZW: att lära sig en ordbok
Lempels och Zivs andra metod, LZ78, bygger upp en ordbok i stället för att titta bakåt i ett fönster. Terry Welchs förfining från 1984, LZW, börjar med alla 256 bytevärden och skickar i varje steg numret på den längsta sträng den redan känner till och lägger till den strängen plus nästa tecken som en ny post. Avkodaren bygger upp samma ordbok enbart utifrån numren. LZW var snabb och enkel och användes i Unix-kommandot compress, i bildformatet GIF och i TIFF-filer, tills patent på metoden ledde till en lång tvist på 1990-talet.
Deflate, ZIP och vidare
Phil Katz metod deflate, som introducerades med PKZIP 2 1993, kombinerar LZ77 med Huffmankodning: när upprepningarna är hittade ger den de vanligaste literalerna, längderna och avstånden de kortaste bitkoderna. Deflate används i ZIP, gzip, PNG-bilder och komprimeringen av webbsidor, och det är den metod som demon mäter med webbläsarens egen komprimerare. Nyare metoder som Zstandard, Brotli och xz använder större fönster, smartare matchning och mer exakt entropikodning, och krymper typiska filer med ytterligare 10–30 %.
Varför inte allt kan krympa
Ingen metod kan göra varje fil mindre. Det finns 2ⁿ filer på n bitar men bara 2ⁿ − 1 filer som är kortare än så, så om en metod krympte alla skulle två av dem bli likadana och kunde inte båda återställas: lådprincipen. Varje komprimerare gör därför vissa indata större, oftast data som ser slumpmässiga ut, som krypterade filer, redan komprimerade filer och brus. Det är också ett test av slumpmässighet: data som ingen komprimerare kan krympa ser slumpmässiga ut.
Entropigränsen
Claude Shannon visade 1948 att en källas entropi är det minsta möjliga genomsnittliga antalet bitar per symbol för en förlustfri kod. Räknat bokstav för bokstav har engelsk text en entropi på ungefär 4 bitar per bokstav, hälften av de 8 bitar den lagras i. Metoder som utnyttjar kontext, som LZ77, kommer under den siffran för enskilda bokstäver på repetitiv text, eftersom en referens står för ett helt avsnitt på en gång. De bästa moderna komprimeringsprogrammen, som förutsäger varje bokstav utifrån allt som kom före, får ner engelska till under 2 bitar per bokstav.
Utforska
Öppna komprimeringsdemon för att köra LZ77, LZW och skurlängdskodning på ett stycke, en sång med refräng, en rad pixlar, en datatabell, slumpmässiga bokstäver eller DNA, eller på din egen text. Klicka på valfri LZ77-referens för att se vad den kopierar, se LZW-ordboken växa och jämför alla metoder med ZIP och med entropigränsen.
Ofta ställda frågor
Vad betyder en komprimeringsgrad på 3 : 1?
Att originalet är tre gånger så stort som den komprimerade versionen, så den komprimerade filen tar en tredjedel av utrymmet och sparar två tredjedelar. Text når typiskt 2 : 1 till 4 : 1 med ZIP; data med mycket upprepning, som loggfiler, ofta betydligt mer.
Varför hjälper det inte att komprimera en ZIP-fil igen?
Den första omgången har redan tagit bort upprepningarna, och dess utdata ser nästan slumpmässiga ut. En andra omgång hittar ingenting att peka tillbaka på och lägger bara till sin egen extra information, så filen förblir lika stor eller växer något.
Varför är ett större LZ77-fönster bättre?
Ett större fönster låter kodaren hitta upprepningar som ligger längre bakåt, som en refräng som återkommer efter flera verser. Priset är att varje avstånd kräver fler bitar att skriva och att sökningen tar längre tid, och därför stannar deflate vid 32 KB medan nyare metoder tillåter megabyte.
Är komprimering samma sak som kryptering?
Nej. Komprimering gör data mindre och vem som helst kan återställa dem; kryptering gör data oläsliga utan en nyckel. De kombineras ofta, och då måste datan komprimeras först: krypterade data ser slumpmässiga ut och går inte längre att komprimera.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Öppna komprimeringsdemon