Datacompressie uitgelegd

Elke webpagina die je laadt, elk ZIP-bestand en elke PNG-afbeelding is gecomprimeerd: kleiner gemaakt zonder één bit te verliezen, en bij aankomst weer uitgepakt. De methoden erachter zijn verrassend eenvoudig. Ze zoeken naar dingen die zich herhalen, en zeggen “hetzelfde als eerder” in plaats van het opnieuw te zeggen. Hoe ver dat idee reikt, en waar het ophoudt, is een van de mooiste verhalen uit de informatica.

Een regel tekst waarin herhaalde stukken zijn vervangen door pijlen die terugwijzen naar hun eerste voorkomen, naast staven met de oorspronkelijke en de gecomprimeerde grootte
Een regel tekst waarin herhaalde stukken zijn vervangen door pijlen die terugwijzen naar hun eerste voorkomen, naast staven met de oorspronkelijke en de gecomprimeerde grootte

Verliesvrij en met verlies

Compressie bestaat in twee soorten. Verliesvrije compressie geeft precies het origineel terug, wat essentieel is voor tekst, programma's, spreadsheets en alles waarbij één verkeerde bit ertoe doet. Compressie met verlies, gebruikt voor foto's, muziek en video, gooit details weg die mensen nauwelijks waarnemen en bereikt veel kleinere groottes, maar het origineel is voorgoed weg. Deze pagina en de demonstrator gaan over verliesvrije compressie, die werkt door redundantie te vinden en te verwijderen: de delen van de gegevens die voorspeld hadden kunnen worden.

Run-length encoding

De eenvoudigste methode vervangt een reeks identieke symbolen door een aantal en het symbool: twaalf witte pixels worden 12W. Faxapparaten, vroege bitmapformaten en het afbeeldingsformaat PCX gebruikten haar, omdat gescande pagina's en eenvoudige tekeningen vol lange reeksen zitten. Bij gewone tekst is ze nutteloos, zelfs schadelijk: reeksen zijn zeldzaam, en voor elke losse letter een aantal schrijven verdubbelt de grootte. Run-length encoding leeft nog voort binnen andere methoden, voor reeksen nullen die overblijven na een eerste transformatie.

LZ77: terugwijzen

In 1977 publiceerden Abraham Lempel en Jacob Ziv, twee onderzoekers aan het Technion in Israël, een methode die het vakgebied veranderde. De encoder houdt een venster bij met de tekst die hij net heeft verwerkt. Als de volgende tekens al in het venster voorkwamen, schrijft hij een paar: hoe ver terug de eerdere kopie begint en hoe lang die is. Anders schrijft hij het teken zelf. De decoder heeft helemaal geen woordenboek nodig, alleen de tekst die hij al heeft herbouwd. Een verwijzing mag zelfs overlappen met de tekst die ze oplevert, zodat een reeks van 100 identieke letters één letter en één verwijzing is.

Abraham Lempel, die in 1977 aan het Technion samen met Jacob Ziv de venster-en-verwijzingsmethode publiceerde die nu LZ77 heet.
Abraham Lempel, die in 1977 aan het Technion samen met Jacob Ziv de venster-en-verwijzingsmethode publiceerde die nu LZ77 heet.

LZW: een woordenboek leren

De tweede methode van Lempel en Ziv, LZ78, bouwt een woordenboek op in plaats van terug te kijken in een venster. De verfijning die Terry Welch er in 1984 van maakte, LZW, begint met alle 256 bytewaarden, verstuurt bij elke stap het nummer van de langste tekenreeks die het al kent, en voegt die reeks plus het volgende teken toe als nieuw item. De decoder herbouwt hetzelfde woordenboek uit alleen de nummers. LZW was snel en eenvoudig, en het kwam terecht in het Unix-commando compress, het afbeeldingsformaat GIF en TIFF-bestanden, tot patenten erop in de jaren 90 een langdurig conflict veroorzaakten.

Deflate, ZIP en verder

De deflate-methode van Phil Katz, in 1993 geïntroduceerd met PKZIP 2, combineert LZ77 met Huffmancodering: na het vinden van de herhalingen geeft ze de meest voorkomende literals, lengtes en afstanden de kortste bitcodes. Deflate wordt gebruikt in ZIP, gzip, PNG-afbeeldingen en de compressie van webpagina's, en het is de methode die de demonstrator meet met de eigen compressor van de browser. Nieuwere methoden zoals Zstandard, Brotli en xz gebruiken grotere vensters, slimmer zoeken naar overeenkomsten en nauwkeurigere entropiecodering, en maken typische bestanden nog eens 10 tot 30% kleiner.

Waarom niet alles kan krimpen

Geen enkele methode kan elk bestand kleiner maken. Er zijn 2ⁿ bestanden van n bits, maar slechts 2ⁿ − 1 bestanden die korter zijn. Als een methode ze allemaal zou verkleinen, zouden er twee hetzelfde worden die niet allebei te herstellen zijn: het ladenprincipe. Elke compressor maakt daarom sommige invoer groter, meestal willekeurig ogende gegevens zoals versleutelde bestanden, al gecomprimeerde bestanden en ruis. Dat is ook een test voor willekeurigheid: gegevens die geen enkele compressor kleiner krijgt, zien er willekeurig uit.

De entropiegrens

Claude Shannon toonde in 1948 aan dat de entropie van een bron het kleinst mogelijke gemiddelde aantal bits per symbool is voor elke verliesvrije code. Letter voor letter geteld heeft Engelse tekst een entropie van ongeveer 4 bits per letter, de helft van de 8 bits waarin hij wordt opgeslagen. Methoden die context gebruiken, zoals LZ77, komen bij repetitieve tekst onder dat getal voor losse letters, omdat een verwijzing voor een heel stuk tegelijk staat. De beste moderne compressors, die elke letter voorspellen uit alles wat ervoor komt, brengen Engels terug tot minder dan 2 bits per letter.

Claude Shannon, die in 1948 bij Bell Labs precies maakte hoeveel informatie een boodschap bevat en die in bits mat.
Claude Shannon, die in 1948 bij Bell Labs precies maakte hoeveel informatie een boodschap bevat en die in bits mat.

Probeer het zelf

Open de compressiedemonstrator om LZ77, LZW en run-length encoding los te laten op een alinea, een lied met refrein, een rij pixels, een gegevenstabel, willekeurige letters of DNA, of op je eigen tekst. Klik op een LZ77-verwijzing om te zien wat die kopieert, zie het LZW-woordenboek groeien, en vergelijk alle methoden met ZIP en de entropiegrens.

Veelgestelde vragen

Wat betekent een compressieverhouding van 3 : 1?

Dat het origineel drie keer zo groot is als de gecomprimeerde versie: het gecomprimeerde bestand neemt dus een derde van de ruimte in en bespaart twee derde. Tekst haalt met ZIP meestal 2 : 1 tot 4 : 1; gegevens met veel herhaling, zoals logbestanden, vaak veel meer.

Waarom helpt het niet om een ZIP-bestand nog eens te comprimeren?

De eerste ronde heeft de herhalingen al verwijderd, en de uitvoer ziet er bijna willekeurig uit. Een tweede ronde vindt niets om naar terug te verwijzen en voegt alleen haar eigen overhead toe, dus het bestand blijft even groot of groeit iets.

Waarom is een groter LZ77-venster beter?

Met een groter venster kan de encoder herhalingen vinden die verder terug liggen, zoals een refrein dat na een paar coupletten terugkomt. De prijs is dat elke afstand meer bits kost om te schrijven en dat zoeken langer duurt; daarom stopt deflate bij 32 KB en staan nieuwere methoden megabytes toe.

Is compressie hetzelfde als versleuteling?

Nee. Compressie maakt gegevens kleiner en iedereen kan dat ongedaan maken; versleuteling maakt gegevens onleesbaar zonder sleutel. Ze worden vaak gecombineerd, en dan moeten de gegevens eerst worden gecomprimeerd: versleutelde gegevens zien er willekeurig uit en zijn niet meer te comprimeren.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Open de compressiedemonstrator