Compressiedemonstrator
Hoe kan een bestand kleiner worden zonder één letter te verliezen? Door op te merken dat het zichzelf herhaalt. Plak een tekst of kies een voorbeeld en zie drie klassieke methoden aan het werk: LZ77 verwijst terug naar eerdere tekst, LZW leert tijdens het lezen een woordenboek van tekenreeksen, en run-length encoding telt reeksen van hetzelfde teken. Elke methode wordt weer gedecomprimeerd om te laten zien dat er niets verloren ging, en een grafiek vergelijkt ze met ZIP en met de entropiegrens. Typ of plak een tekst, of kies een voorbeeld, en kies een methode. LZ77 vervangt herhalingen door verwijzingen naar eerdere tekst: klik op een gemarkeerd deel om te zien wat het kopieert. LZW bouwt tijdens het lezen een woordenboek van tekenreeksen op en verstuurt hun nummers. RLE perst reeksen van hetzelfde teken samen. De grafiek vergelijkt elke methode met ZIP en met de entropiegrens, en de app decomprimeert het resultaat weer om te controleren dat er niets verloren is gegaan.
Hoe het werkt
- Typ of plak een tekst, of kies een voorbeeld: een alinea, een lied met refrein, een rij pixels, een gegevenstabel, willekeurige letters of DNA.
- Kies LZ77, LZW of RLE. Stel bij LZ77 in hoe ver het terug mag kijken, en klik op een gemarkeerde verwijzing om de eerdere tekst te zien die ze kopieert.
- Vergelijk de groottes in de tegels en de grafiek met ZIP en met de entropiegrens; de controle onder de tekst bevestigt dat decomprimeren het origineel teruggeeft.
Herhalingen zijn de sleutel
Verliesvrije compressie werkt omdat echte gegevens zichzelf herhalen. LZ77 houdt een venster bij met de tekst die het net heeft gelezen; telkens als de volgende tekens al in dat venster voorkwamen, schrijft het een korte verwijzing in plaats van de tekens zelf: ga zoveel terug en kopieer zoveel tekens. Een verwijzing kost een vast aantal bits, hoe lang de kopie ook is, dus lange en veelvoorkomende herhalingen besparen het meest. LZW bereikt hetzelfde effect op een andere manier: het bouwt een woordenboek op van elke nieuwe tekenreeks die het tegenkomt en verstuurt vanaf dan het nummer van die reeks.
Waarom sommige gegevens niet krimpen
Een methode die sommige bestanden kleiner maakt, moet andere groter maken: er zijn minder korte bestanden dan lange, dus ze kunnen niet allemaal korter worden. Compressie wint bij gegevens met patronen, zoals tekst, tabellen en eenvoudige afbeeldingen, en verliest bij gegevens zonder patronen. Willekeurige letters, versleutelde gegevens en bestanden die al gecomprimeerd zijn, geven de methoden niets om naar terug te verwijzen, en de uitvoer wordt even groot als de invoer, of groter. Run-length encoding laat dit het duidelijkst zien: bij tekst zonder reeksen verdubbelt de grootte.
Veelgestelde vragen
Wat is het verschil tussen verliesvrije compressie en compressie met verlies?
Verliesvrije compressie geeft precies het origineel terug, bit voor bit; die is nodig voor tekst, programma's en gegevens, en deze demonstrator toont alleen verliesvrije methoden. Compressie met verlies, zoals bij JPEG-foto's, MP3-muziek en video, gooit details weg die mensen nauwelijks opmerken en levert veel kleinere bestanden op, maar het origineel is niet meer terug te halen.
Hoe comprimeert ZIP bestanden?
ZIP en gzip gebruiken deflate, dat eerst LZ77 uitvoert met een venster van 32 KB en daarna de literals en verwijzingen schrijft met Huffmancodes: korte codes voor veelvoorkomende waarden en lange voor zeldzame. Door die tweede stap verslaat ZIP meestal het eenvoudige LZ77 dat hier te zien is, dat aan elk token een vast aantal bits besteedt.
Kan LZ77 onder de entropie komen?
De getoonde entropie telt de tekens één voor één, zonder context. LZ77 en LZW gebruiken context, omdat een verwijzing een heel stuk eerdere tekst kopieert, dus bij repetitieve tekst kunnen ze dat getal ruim verslaan. De echte entropie van de bron, die alle context meeneemt, kunnen ze nooit verslaan.
Waarom verschillen de groottes van een echt ZIP-bestand?
De demonstrator telt alleen de bits van de gecodeerde gegevens. Een echt ZIP-bestand voegt headers, de bestandsnaam, een controlesom en de Huffmantabellen toe, die zeer kleine bestanden eerder groter dan kleiner maken.
Wordt mijn tekst ergens naartoe gestuurd?
Nee. Elke methode, ook de vergelijking met ZIP, draait in je browser, en je tekst blijft in de lokale opslag van deze browser.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Ga naar Editor