Hoe bestandscompressie werkt

In ons vorige voorbeeld hebben we alle herhaalde woorden eruit gepikt en die in een woordenboek gezet. Voor ons is dit de meest voor de hand liggende manier om een woordenboek te schrijven. Maar een compressieprogramma ziet dat heel anders: Het heeft geen concept van afzonderlijke woorden — het zoekt alleen naar patronen. En om het bestand zo klein mogelijk te maken, selecteert het zorgvuldig welke patronen het in het woordenboek opneemt.

Als we de zin vanuit dit perspectief benaderen, krijgen we een heel ander woordenboek.

Als het compressieprogramma de zin van Kennedy zou scannen, zou de eerste redundantie die het zou tegenkomen slechts een paar letters lang zijn. In “ask not what your,” is er een herhaald patroon van de letter “t” gevolgd door een spatie — in “not” en “what.” Als het compressieprogramma dit in het woordenboek zou schrijven, zou het een “1” kunnen schrijven elke keer als een “t” gevolgd wordt door een spatie. Maar in deze korte zin komt dit patroon niet vaak genoeg voor om het de moeite waard te maken, dus het programma zou het uiteindelijk overschrijven.

Het volgende dat het programma zou kunnen opvallen is “ou,” dat zowel in “jouw” als in “land” voorkomt. Als dit een langer document was, zou dit patroon in het woordenboek veel ruimte kunnen besparen — “ou” is een vrij gebruikelijke combinatie in de Engelse taal. Maar als het compressieprogramma deze zin doorwerkt, ontdekt het al snel een betere keuze voor een woordenboekingang: Niet alleen wordt “ou” herhaald, maar de woorden “your” en “country” worden beide herhaald, en ze worden zelfs samen herhaald, als de zin “your country”. In dit geval zou het programma de woordenboekingang voor “ou” overschrijven met de ingang voor “jouw land.”

De zin “kan doen voor” wordt ook herhaald, een keer gevolgd door “jouw” en een keer gevolgd door “jij”, waardoor we een herhaald patroon krijgen van “kan doen voor jou.” Dit laat ons toe 15 karakters (spaties inbegrepen) met één cijferwaarde te schrijven, terwijl “uw land” ons slechts 13 karakters (spaties inbegrepen) met één cijferwaarde laat schrijven, zodat het programma de invoer “uw land” zou overschrijven als enkel “r land,” en dan een afzonderlijke invoer zou schrijven voor “kan doen voor u”. Het programma gaat op deze manier te werk, door alle herhaalde stukjes informatie op te pikken en dan te berekenen welke patronen het naar het woordenboek moet schrijven. Dit vermogen om het woordenboek te herschrijven is het “adaptieve” deel van het LZ adaptieve woordenboek-gebaseerde algoritme. De manier waarop een programma dit feitelijk doet is vrij gecompliceerd, zoals je kunt zien in de discussies op Data-Compression.com.

Hoe je de specifieke methode ook gebruikt, met dit diepgaande zoeksysteem kun je het bestand veel efficiënter comprimeren dan wanneer je er alleen woorden uit zou pikken. Met behulp van de patronen die we hierboven hebben uitgezocht, en door “__” toe te voegen voor spaties, krijgen we dit grotere woordenboek:

En deze kleinere zin: “1not__2345__–__12354”

De zin neemt nu 18 geheugeneenheden in beslag, en ons woordenboek 41 eenheden. Dus we hebben de totale bestandsgrootte gecomprimeerd van 79 eenheden naar 59 eenheden! Dit is slechts één manier om de zin te comprimeren, en niet noodzakelijkerwijs de meest efficiënte. (Kijk of je een betere manier kunt vinden!)

Dus hoe goed is dit systeem? De bestandsreductie is afhankelijk van een aantal factoren, waaronder bestandstype, bestandsgrootte en compressieschema.

In de meeste talen van de wereld komen bepaalde letters en woorden vaak samen voor in hetzelfde patroon. Vanwege deze hoge mate van redundantie kunnen tekstbestanden zeer goed worden gecomprimeerd. Een reductie van 50 procent of meer is typisch voor een tekstbestand van goede omvang. De meeste programmeertalen zijn ook erg redundant omdat ze een relatief kleine verzameling commando’s gebruiken, die vaak samen in een vast patroon voorkomen. Bestanden met veel unieke informatie, zoals grafische bestanden of MP3-bestanden, kunnen met dit systeem niet veel worden gecomprimeerd, omdat ze niet veel patronen herhalen (meer hierover in de volgende sectie).

Als een bestand veel herhaalde patronen heeft, neemt de verkleiningsfactor doorgaans toe met de bestandsgrootte. Je kunt dit zien door naar ons voorbeeld te kijken — als we meer toespraken van Kennedy hadden, zouden we vaker naar de patronen in ons woordenboek kunnen verwijzen, en dus meer uit de bestandsruimte van elk item kunnen halen. Ook zouden in het langere werk meer doordringende patronen naar voren kunnen komen, waardoor we een efficiënter woordenboek zouden kunnen maken.

Deze efficiency hangt ook af van het specifieke algoritme dat door het compressieprogramma wordt gebruikt. Sommige programma’s zijn bijzonder geschikt om patronen in bepaalde soorten bestanden op te pikken, en kunnen deze dus beknopter comprimeren. Andere hebben woordenboeken binnen woordenboeken, die efficiënt kunnen comprimeren voor grotere bestanden, maar niet voor kleinere. Hoewel alle compressieprogramma’s van dit type werken met hetzelfde basisidee, is er eigenlijk heel wat variatie in de manier van uitvoering. Programmeurs proberen altijd een beter systeem te bouwen.