Bureaublad
Data Compressie
De eerste vorm van digitale compressie was de uitvinding van morsecode in 1838. In die tijd was er nog geen sprake van digitaal opgeslagen informatie in de vorm van bits, maar de tekst werd wel door signalen die twee waarden aan konden nemen verzonden. Er is wel een verschil met bits, want eigenlijk was er nog een derde signaal, namelijk de rust. Daarmee kan het einde van een signaal aangegeven worden. Dat dat een groot verschil is, zal bij het kopje Werking worden uitgelegd. De compressie in morse code zat hem in het feit dat letters die het meeste voor kwamen de kortste code kregen. Morse code was een vorm van compressie die het meest geschikt was voor de Engelse taal. Er konden natuurlijk ook andere talen mee verstuurd worden, maar dat ging op een minder efficiënte manier.Na morse code was het een hele tijd stil, op het gebied van datacompressie. Totdat de computers kwamen, was het ook helemaal niet mogelijk om data te comprimeren. In 1949, twee jaar nadat de eerste transistor werd uitgevonden en digitale dataopslag grootschalig begon te worden, vonden Claude Shannon en Robert Fano een manier om informatie te comprimeren, door gebruik te maken van de waarschijnlijkheid dat bepaalde stukjes informatie voorkwamen. David Huffman heeft dat verder uitgewerkt en vond de optimale manier om zo informatie te coderen. Zijn methode heet de Huffman-codering, waarover meer wordt verteld onder het kopje: Categorieën. Claude Shannon was overigens een jaar eerder ook al bezig geweest met digitale compressie, toen hij de informatietheorie opstelde. Daarmee kon het minimale aantal bits dat voor een bepaalde boodschap nodig was bepaald worden. Onder het kopje 'Werking is ook daarover meer informatie te vinden.
De volgende grote innovatie op het gebied van digitale compressie kwam met de introductie van de LZ-codering. Abraham Lempel en Jacob Ziv bedachten in 1977 dat je ook per bestand de waarschijnlijkheid van bepaalde berichten of stukjes informatie vast kunt stellen. Zo ontstaat er per bestand een min of meer optimale codering. In 1984 verbeterde Terry Welch de LZ-codering en zo ontstond de LZW-codering. Deze codering wordt net als de Huffman codering nog steeds veel gebruikt. Plaatjes die opgeslagen zijn in het GIF formaat (Bijvoorbeeld: Vakantiefoto.gif), zijn gecodeerd met de LZW-codering.
Eind jaren tachtig werd het steeds gebruikelijker om plaatjes digitaal op te slaan en dus nam de vraag naar compressie voor dat soort bestanden toe. Er kwamen verschillende soorten coderingen op de markt, die steeds werden verbeterd. De formaten die nu veel gebruikt worden zijn: GIF, JPEG, BMP, PNG en TIFF.
In de tijd dat men compressiemethoden voor plaatjes bedacht, begon men ook te proberen geluid en video kleiner op te slaan. Het duurde enkele jaren voordat dat ook lukte. In 1994 werd de MPEG-1 standaard voor het comprimeren van videobeelden geïntroduceerd. Twee jaar later werd daar de verbeterde versie (MPEG-2) van geïntroduceerd. Op basis daarvan werd er ook een coderingsstandaard voor geluid (muziek) ontworpen. Dat is het beroemde MP3 formaat dat in de jaren na 1999 razend populair is geworden, omdat het normale geluidsbestanden wel 12 maal kleiner kan maken. Er zijn op het moment tientallen formaten om muziek op te slaan, maar MP3 wordt nog steeds veel gebruikt, onder andere voor het opslaan van muziek op draagbare mp3-spelers.
Voordat we verder kunnen met de manier waarop dingen gecomprimeerd worden, moeten er eerst een paar termen gedefinieerd worden. In de inleiding ben je al een paar keer de term 'informatie' tegengekomen. Daarmee worden niet alleen harde feiten bedoeld, maar alles dat onder bepaalde omstandigheden voor bepaalde mensen betekenis heeft. Dat kan een spreadsheet zijn, maar ook een vakantiefoto, een brief, een recept, een computerspel, een liedje of zelfs een erotische film. Dat maakt helemaal geen barst uit. Het gaat er om dat er digitaal iets met een bepaalde waarde is vastgelegd. Dát wordt in deze tekst met 'informatie' bedoeld. Die informatie bestaat uit een serie van één of meer berichten. In deze tekst zouden die berichten de letters waaruit deze tekst bestaat zijn. In een plaatje zijn dat de pixels waaruit het plaatje bestaat. Verreweg de meeste informatie bestaat uit meerdere berichten. Een stuk tekst met maar één letter heeft voor ons bijna nooit betekenis, tenzij je afspreekt met de ontvanger, dat een ‘a’ bijvoorbeeld betekent dat je morgen komt eten, en een ‘b’ betekent dat je het te druk hebt om langs te komen. Maar dan ben je eigenlijk zelf al bezig met het comprimeren van een stuk tekst.
Terug naar hoe digitale compressie werkt. Hoewel het in de praktijk lijkt alsof alle bestanden comprimeerbaar zijn, is dat niet zo. Als je er over nadenkt, kom je er ook achter dat dat nooit zo kan zijn. Stel je hebt een boodschap die beschreven wordt door 3 bits. Die boodschap kan 2*2*2 = 8 waarden aannemen. Het is nooit mogelijk om al die 8 waarden met 2 bits te beschrijven, want 2 bits kunnen samen niet meer dan 4 waarden aan nemen. Wil je dan toch sommige waarden met twee bits beschrijven, dan moet je andere waarden met 4 bits gaan beschrijven. Het is soms wel handig om sommige waarden met minder bits te beschrijven dan andere, maar dat wordt later uitgelegd.
Omdat we niet zomaar alle bestanden kunnen comprimeren, moeten programma’s die informatie comprimeren aannemen, dat uit alle mogelijke berichten, bepaalde berichten meer voor komen dan andere. Bijvoorbeeld dat de kans dat er in een tekst een bepaalde klinker voor komt groter is dan dat er een bepaalde medeklinker voorkomt. (a’s komen vaker voor dan q’s) Of dat een plaatje eerder bestaat uit vlakken van kleuren die veel op elkaar lijken, dan uit een verzameling pixels die willekeurig gekozen is. Daarom heeft compressie alles met kans te maken. De kans dat bepaalde berichten of schakelingen van berichten in bepaalde informatie vaker voor komen ligt meestal al vast in het soort bestand waar de informatie uit bestaat. Daarom gebruiken we ook verschillende compressiemethoden voor verschillende soorten bestanden. Het heeft bijvoorbeeld geen zin om een foto als mp3 bestand op te slaan. Als je dat doet zal het plaatje in ‘gecomprimeerde’ vorm hoogstwaarschijnlijk groter zijn, dan het bestand waar je mee begon.
Informatietheorie
Om te begrijpen hoe goed bepaalde informatie gecomprimeerd kan worden zullen we nu eerst kijken naar de informatietheorie. Deze theorie laat zien hoe de distributie van de kans van verschillende berichten in relatie staat tot de hoeveelheid informatie die het bevat en de hoeveelheid bits die er voor nodig is om het te coderen. Deze theorie voorspelt hoeveel bits er minimaal nodig zijn om bijvoorbeeld een stuk informatie te coderen dat uit een achtdelige serie van 4 mogelijke berichten bestaat. Daarvoor moet de kans dat een bepaald bericht in die serie voor komt wel bekend zijn.
De informatietheorie gaat er van uit dat een stuk informatie uit een serie van berichten bestaat. Die berichten kunnen een bekend aantal waarden aan nemen. Bijvoorbeeld: de zin “de zon schijnt op deze winterdag” bestaat uit 32 berichten, die elk 27 waarden aan kunnen nemen, namelijk de zesentwintig letters van het alfabet en de spatie. Ook zegt de informatietheorie, dat een bericht minder informatief is, als de kans groot is dat het in de informatie zit. Dat is een beetje verwarrend. Het zit zo: Als het bericht jou bereikt dat het morgen in het tropisch regenwoud warm zal zijn en zal gaan regenen, zal je daar minder van op kijken dan als er wordt beweerd dat het er zal gaan vriezen en sneeuwen. Een ander voorbeeld: Stel je hebt een lot uit de staatsloterij. Als op nieuwjaarsdag blijkt dat je niks hebt gewonnen zal dat je niet erg verbazen. De kans dat je zou winnen is immers erg klein. Maar als blijkt dat je de jackpot hebt gewonnen, zal je dat nauwelijks kunnen geloven. Zo zit het ook met de informativiteit van een bericht. Hoe groter de kans op een bericht, hoe minder informatief.
Zoals je zult begrijpen is een heel informatief bericht minder comprimeerbaar dan een bericht dat niet zo informatief is. Dat is eigenlijk heel gunstig, want de meeste informatie die van waarde is voor mensen is eigenlijk heel oninformatief. Een voorbeeld is onze taal. Een groot deel van de lettercombinaties die met ons alfabet mogelijk zijn hebben voor ons geen betekenis. Ook is de kans dat er een klinker in een woord zit zeer groot. Zo heb je dus een hele hoop letters en lettercombinaties die een grotere kans op voorkomen hebben en dus zelf minder informatief zijn. Daardoor zijn ze beter comprimeerbaar.
Eén eigenschap van de informatietheorie is dus dat een bericht meer informatie bevat als de kans dat dat bericht zich voor doet erg klein is. De volgende eigenschap is dat de informativiteit van twee berichten die elkaar niet kunnen beïnvloeden gelijk is aan de informativiteit van de afzonderlijke berichten bij elkaar opgeteld. De laatste eigenschap is dat de informativiteit van een bericht gelijk is aan het minimale aantal te gebruiken bits voor dat bericht. Daarbij moet er rekening mee gehouden worden dat een bit slechts twee waarden aan kan nemen, namelijk de 0 en de 1. Zo komen we op de volgende formule:
Daarin is i(b) de informativiteit van een bepaald bericht en p(b) de kans dat dat bericht zich zal voor doen. Zoals je ziet wordt er van die kans de reciproque waarde genomen. Er moet namelijk een grotere waarde uit komen als de kans kleiner is. In deze formule komt een logaritmische bewerking met grondtal 2 voor. Dat komt omdat de informativiteit wordt uitgedrukt in het aantal benodigde bits. Bij iedere bit die je extra gebruikt om een boodschap te coderen verdubbelt het aantal mogelijke berichten dat met die bits gecodeerd kan worden. Bijvoorbeeld: met vier bits zijn 2*2*2*2 = 16 berichten te coderen, terwijl met 5 bits 2*2*2*2*2 = 32 berichten te coderen zijn. Het grondtal van het logaritme is 2, omdat een bit twee waarden kan aannemen. Had een bit drie mogelijke waarden gehad, dan was het grondtal 3 geweest.
De informatietheorie gaat nog verder dan dit. We hebben het namelijk alleen nog maar over de informativiteit van één mogelijk bericht in een stuk informatie gehad. Om het geschatte aantal bits dat minimaal nodig is om een stuk informatie te coderen, moeten we de informativiteit van het hele stuk informatie kunnen berekenen. Dat gaat als volgt: stel je hebt een stuk informatie dat uit één bericht bestaat. Er zijn een aantal mogelijke berichten B waar het stuk informatie uit zou kunnen bestaan. Dan is de informativiteit (of de informatie entropie, zoals het officieel heet) van het stuk informatie een gewogen gemiddelde van de informativiteit van de verschillende berichten. Eigenlijk is het gewoon de verwachtingswaarde van de informativiteit van het stuk informatie. Dit wordt zo opgeschreven:
Hierin is i(B) de informativiteit van het stuk informatie en p(b) weer de kans dat een bepaald bericht voor komt. De hoofdletter sigma betekent dat je voor ieder mogelijk bericht b de bewerking die er achter staat uit moet voeren en de uitkomsten bij elkaar op moet tellen. Hoe dit allemaal gaat zal nu in een voorbeeld worden uitgelegd. We willen de informativiteit van een stuk informatie dat uit één van de berichten z, y, x, w, of v kan bestaan berekenen. De kans dat de informatie uit bericht z bestaat is 0,2. De kan dat hij uit y bestaat is 0,45, de kans op x is 0,05, de kans op w is eveneens 0,05 en v heeft een kans van 0,25. In een tabel:
|
z
|
y
|
x
|
w
|
v
|
|
0,2
|
0,45
|
0,05
|
0,05
|
0,25
|
y: 2log(1/0,45) = 1,1520
x: 2log(1/0,05) = 4,3219
w: 2log(1/0,05) = 4,3219
v: 2log(1/0,25) = 2
Als laatste berekenen we de informativiteit van het hele bericht:
In formule is dat p(z) * i(z) + p(y) * i(y) + p(x) * i(x) + p(v) * i(v) + p(w) * i(w)
Als je dat invult krijg je: 0,2 * 2,3219 + 0,45 * 1,1520 + 0,05 * 4,3219 + 0,05 * 4,3219 + 0,25 * 2 = 1,91497
De informativiteit van het stuk informatie is dus 1,91497.
Het is niet moeilijk te bedenken dat als de informatie bestaat uit twee berichten, die allebei de waarden z,y,x,w,v met de daarbij behorende kansen kunnen aannemen, de informativiteit twee maal 1,91497 = 3,82994 zal zijn. Een voorwaarde is hierbij, dat de berichten elkaar niet kunnen beïnvloeden. Dat betekent bijvoorbeeld dat als het eerste bericht een z is, dat het tweede bericht dan niet een hogere (of juist lagere) kans heeft om een x te zijn. Bij de Nederlandse taal geldt die voorwaarden niet. Als je iedere letter in een woord beschouwt als een bericht dat 26 waarden aan kan nemen, dan worden die berichten door elkaar beïnvloed. Je hebt bijvoorbeeld na een q een veel hogere kans om een u tegen te komen, dan op een willekeurige plaats in het woord.
Goed, nu weten we hoe klein je een bepaalde boodschap in theorie zou kunnen coderen, maar dan zijn we er nog niet. Vervolgens moet er ook nog een slimme manier bedacht worden om de informatie zo klein mogelijk op te slaan. Over het algemeen zijn er twee manieren waarop dat gedaan wordt. De eerste is door het weglaten van overbodige berichten, zoals hoge en lage tonen in een muziekbestandje die wij toch niet kunnen horen. Hierbij kan de originele informatie dus niet exact weer gereconstrueerd worden. Daarom is die methode ook niet geschikt voor alle soorten bestanden. De tweede manier is door berichten die vaak voor komen een kortere code te geven dan berichten die niet zo vaak voor komen. Dat is niet zo simpel als het lijkt. Het is namelijk niet mogelijk sommige berichten een kortere code te geven, zonder andere berichten een langere code te geven. Aan de hand van het volgende voorbeeld zal dat duidelijk gemaakt worden: Er zijn vier berichten - a, b, c en d - waar een stuk informatie uit kan bestaan. Ze worden gecodeerd door twee bits, de mogelijkheden zijn:
a: 11, b: 10, c: 01 en d: 00.
Voor de compressie wil je de eerste code in plaats van met twee bits, met één bit coderen. Je zou zeggen dat de codes er dan zo uit kwamen te zien:
a: 1, b: 10, c: 01 en d: 00.
Maar stel je hebt een stuk informatie dat uit de tekenreeks “b d c” bestaat. De codering zou dan 100001 zijn. Maar bij het ‘uitpakken’ zou die code twee dingen kunnen betekenen: 1, 00, 00, 1 (adda) of 10, 00, 01 (bdc). Er moeten dus coderingen komen die ieder afzonderlijk te onderscheiden zijn. Dat betekent dat er twee letters met drie bits gecodeert moeten worden! De codering zou zijn:
a: 1, b: 01, c: 001 en d: 000
Op die manier kan elke tekenreeks afzonderlijk gecodeerd worden, zonder dat er verwarring ontstaat bij het uitpakken. De boodschap ‘bdc’ is dan 01000001. Maar dat is weer langer dan 10-00-01, wat het geweest was als het niet ‘gecomprimeerd’ zou zijn. Hier krijg je dus te maken met het feit dat sommige berichten vaker voor moeten komen dan andere, om compressie mogelijk te maken. Als gegeven is dat de codering a: 1, b: 01, c: 001 en d: 000 gemiddeld gezien compressie oplevert, dan kan je uitrekenen dat de kans dat c of d voor komt, kleiner moet zijn dan de kans dat b voor komt en de kans dat b voor komt moet kleiner zijn dan de kans dat a voor komt. Bij de kansverdeling a: 1/3, b: 1/3, c: 1/6, d: 1/6, kom je precies op een gemiddelde van 2 bits, net als met de originele codering. De kans op bericht a moet dus groter dan 1/3 zijn en de gecombineerde kans van c en d kleiner dan 1/3.
We hebben nu kunnen zien, dat compressie alleen mogelijk is als er sommige berichten of schakelingen van berichten gemiddeld vaker voor komen dan andere berichten of schakelingen daarvan. Maar waarom slaan we niet automatisch alle digitale informatie die zo’n kansverdeling heeft in gecomprimeerde vorm op? Dat zou toch wel zo praktisch zijn. Dat komt omdat gecomprimeerde informatie vaak heel onhandelbaar is. Computers kunnen over het algemeen niet goed met gecomprimeerde data overweg. Bij sommige gecomprimeerde bestanden zit bijvoorbeeld een woordenboek dat je nodig hebt om de gecomprimeerde informatie te ontcijferen. Of je hebt informatie aan het begin van het bestand nodig om de dingen aan het eind te kunnen ontcijferen. Het kost dan ook tijd om de informatie te comprimeren (in te pakken) en te decomprimeren (uit te pakken). Bij sommige compressiemethoden duurt dat wat langer dan bij andere compressiemethoden, maar over het algemeen geldt dat hoe beter je het wil comprimeren hoe meer tijd en rekenkracht er voor nodig is. Voor de normale verwerking en opslag wordt dus geen optimale compressie gebruikt, omdat de computer er dan erg moeilijk mee kan werken of omdat het meer energie kost dan nodig is. Pas als de informatie zo klein mogelijk opgeslagen of over het internet verstuurt moet worden gebruikt men compressie.
Zoals bij de uitleg over de werking van digitale compressie duidelijk werd, worden over het algemeen twee verschillende soorten digitale compressie onderscheiden. De eerste heet lossless data compressie, waarbij het originele stuk informatie kan worden gereconstrueerd uit het gecomprimeerde bestand en de tweede, genaamd lossy datacompressie, waarbij altijd een deel van de originele informatie verloren gaat. Dat laatste is niet altijd erg. Bij een hoop digitale bestanden is het namelijk zo dat er een hele hoop informatie in zit die wij, als mensen, toch nooit zouden kunnen waarnemen. Neem bijvoorbeeld een digitale foto. Je hebt bestandsformaten die iedere pixel meer dan vier miljard kleurnuances kunnen geven. Het menselijk oog zou het verschil tussen vier miljard en bijvoorbeeld zestien miljoen kleurnuances nooit kunnen waarnemen, terwijl het ontzettend veel scheelt in het aantal bits dat nodig is om zo’n plaatje op te slaan. Ook is het voorbeeld van de uiterst hoge en lage tonen in een muziekbestand, die het menselijk oor niet kan horen, al genoemd. Zo zijn er nog wel meer voorbeelden van bestandstypen waarbij het helemaal niet erg is als er een beetje informatie verloren gaat. Eventueel is er nog een derde type te onderscheiden: de transformatie. Daarmee wordt een schakeling van berichten op een andere manier opgeschreven, zodat die makkelijker te comprimeren valt. Met de transformatie zelf wordt echter geen compressie gerealiseerd.
Toch zijn er ook bestandstypen, waarbij het niet gewenst is dat er informatie verloren gaat. Bedenk bijvoorbeeld maar eens wat er zou gebeuren als bestanden waarin mensen hun wachtwoorden op slaan, zomaar een cijfertje weg lieten. Meestal wordt door de mens bepaald of een bestand geschikt is voor lossless of lossy compressie. Het hangt ook van de situatie af, of er voor lossless of lossy compressie wordt gekozen. Als je een foto via e-mail wil versturen zal je eerder voor lossy kiezen, dan wanneer je een foto op je harde schijf wil opslaan, waar toch nog genoeg ruimte op vrij is.
Hieronder zullen nu eerst een aantal lossless compressietechnieken besproken worden. Daarmee wordt begonnen, omdat ze het meeste voorkomen. Soms in hun eentje, soms in combinatie met andere lossless technieken en soms in combinatie met lossy compressiemethoden. Over het algemeen zit in lossy compressiemethoden ook altijd een stuk lossless coderen.
Lossless coderingen:
Huffman codering
David Huffman was de eerste die een optimale manier vond, voor het coderen van berichten die een bepaalde kans van voorkomen hebben. Zijn codering wordt veel gebruikt, door verschillende compressieprogramma’s. Zoals we al eerder gezien hebben berust lossless compressie op maken van een kleinere code voor berichten die veel voorkomen. Daarbij werd het probleem aangekaart, dat wanneer je codes van verschillende lengten neemt, je bij sommige schakelingen de code op verschillende manieren kan interpreteren. Dat is natuurlijk niet de bedoeling. Iedere schakeling van verschillende codes moet bij het ontcijferen een unieke uitkomst hebben. Meneer Huffman heeft dus een manier van coderen gevonden, die ieder bericht in het stuk informatie dat je wilt comprimeren, een optimaal korte code geeft die ook nog uniek te ontcijferen is. Zijn manier van coderen gaat zo: je zet alle mogelijke berichten met de kans dat ze voorkomen op een rijtje. Dan verbind je de twee kleinste kansen met twee lijntjes. Waar de twee lijnen bij elkaar komen zet je de opgetelde kans van die twee berichten neer. Nu behandel je die opgetelde kans als een mogelijk bericht en begin je weer bij stap één, totdat alle kansen gecombineerd zijn en je, als het goed is, aan het begin het getal één hebt. Nu heb je dus een hele boomstructuur van vertakkingen en kansen. Dan geef je bij iedere splitsing de ene lijn een 1 en de andere lijn een 0. Als laatste volg je voor ieder bericht vanuit de ‘stam’ van de boom de weg naar het bericht en bij iedere splitsing die je tegen komt noteer je of je de 1-lijn of de 0-lijn hebt. Zo krijg je voor ieder bericht een optimale code. Dit wordt nu even voorgedaan met een voorbeeld uit 'de vorige pagina. Daarbij waren de kansen voor 5 berichten zo verdeeld:
|
z
|
y
|
x
|
w
|
v
|
|
0,2
|
0,45
|
0,05
|
0,05
|
0,25
|
|
stap 1
|
stap 2
|
|
|
|
|
|
|
|
stap 3
|
stap 4
|
|
|
|
|
|
|
|
stap 5
|
stap 6
|
|
|
|
Zoals je misschien al gezien had, staat de afkorting LZW voor de achternamen van de bedenkers: Lempel, Ziv en Welch. Het is een verbetering op de, door Lempel en Ziv eerder bedachte, LZ-codering. In tegenstelling tot de Huffman codering heeft de LZW codering geen van te voren bepaalde kans voor de mogelijke berichten nodig. Het is een zogenaamde woordenboek-codering. In dat woordenboek worden veel voorkomende schakelingen van berichten opgeslagen. Het speciale van deze soort codering, is dat het woordenboek zelf, niet met de gecodeerde informatie mee gestuurd hoeft te worden, omdat het bij het decoderen uit het bericht gereconstrueerd word. De LZW codering kan bijvoorbeeld voor tekst gebruikt worden. Het woordenboek begint dan met 256 waarden, voor alle mogelijke karakters één. Het eerste bericht kan gewoon met zo’n woord uit het woordenboek opgeslagen worden. Maar tegelijkertijd wordt er een nieuw woord aan het woordenboek toegevoegd dat bestaat uit dat karakter plus het karakter dat er achter staat. Als voorbeeld kijken we naar de volgende zin:
ik-denk-dat-ik-dat-ben
Het is een zin van 22 tekens, waarbij de spaties voor de duidelijkheid vervangen zijn door streepjes. Gecomprimeerd zou de zin er dan zo uit zien:
(i) (k) (-) (d) (e) (n) [2] (d) (a) (t) (-) [1] [3] [9] (-) (b) [5]
Daarbij zijn de tekens tussen haakjes de tekens die standaard in het woordenboek zitten. De tekens tussen de vierkante haakjes zijn de woorden die aan het woordenboek zijn toegevoegd. Deze tekenreeks is 17 tekens lang, dus er is een compressie van 100 - (17 * 100 / 21) = 19%. Het woordenboek ziet er zo uit:
[1=ik] [2=k-] [3=-d] [4=de] [5=en] [6=nk] [7=k-d] [8=da] [9=at] [10=t-] [11=-i] [12=ik-] [13=-da] [14=at-] [15=-b] [16=be]
De behaalde compressie bij deze methode hangt sterk af van de hoeveelheid herhaling die er in een stuk informatie zit. Het is natuurlijk logisch dat hoe groter het te comprimeren bestand wordt, hoe groter de kans dat op herhaling binnen dat bestand is en hoe groter daarmee de compressie.
Dit voorbeeld had met taal te maken, maar dat is niet de enige soort informatie die met deze coderingsmethode gecomprimeerd kan worden. Een ander voorbeeld is digitale foto bestanden. Het bestandsformaat GIF maakt bijvoorbeeld hoofdzakelijk gebruik van de LZW codering. Daarbij wordt per horizontale regel pixels naar herhaalde kleuren gekeken. Als een hele regel alleen maar witte pixels bevat zal dat dus veel compressie opleveren. Met herhaling in verticaal opzicht zal geen rekening worden gehouden, dus het kan gebeuren dat het bestand beter gecomprimeerd wordt als je het een kwartslag draait.
Delta codering en Run-length codering
Deze twee manieren van compressie worden samen beschreven, omdat ze vaak samen gebruikt worden, hoewel dat niet noodzakelijk is. Als ze samen gebruikt worden, wordt eerst de delta codering toegepast. Deze verandert een rij berichten in een rij van de verschillen tussen die berichten. De rij 4, 6, 8, 7, 9, 11 wordt: 4, 2, 2, -1, 2, 2. Op zich heb je dan nog geen compressie, maar dat heb je wel als je de run-length codering er achteraan gebruikt. De run-length codering zet lange rijen van dezelfde berichten om in de waarde van dat bericht plus het aantal keer dat het achter elkaar voor komt. Bijvoorbeeld de berichtenreeks aaaaaaaaaahhhhbeeeeeeeeooooooooooooo zou worden omgezet in: (10a)(4h)(1b)(8e)(13o), wat duidelijk minder ruimte inneemt dan de originele reeks. De rede dat de twee coderingen vaak samen gebruikt worden is het feit dat delta codering (als het toegepast wordt op de juiste bestanden) vaak lange reeksen van dezelfde berichten produceert. Vervolgens kunnen die reeksen door de run-length codering tot korte reeksjes omgezet worden.
Zoals begrijpelijk is, zal de delta codering (al dan niet in combinatie met run-length codering) veel gebruikt worden in situaties waarin veel berichten en/of berichtschakelingen voorkomen die veel op elkaar lijken. Daarbij kan je denken aan een grote alfabetische woordenlijst, een videofilmpje en in mindere mate aan geluidsbestanden. In de compressie van videobestanden wordt onder andere gebruik gemaakt van delta codering, omdat de meeste filmpjes die voor mensen betekenis en/of waarde hebben bestaan uit aaneenschakelingen van beelden die niet veel van elkaar verschillen. Over het algemeen hechten wij juist meer waarde aan video met zo veel mogelijk beelden per seconde en dus minder verschil tussen de beelden.
Move-to-front codering
Net als de Delta codering, is de Move-to-front codering, oftewel haal-naar-voren codering, geen compressiemethode die in zijn eentje een stuk informatie kan comprimeren. Het is alleen maar een techniek om een aaneenschakeling van vaak herhalende berichten anders ‘op te schrijven’. Dit wordt gedaan door de reeks berichten waaruit de informatie kan bestaan steeds anders op te schrijven en dan het nummer te noteren van het bericht dat je wilt coderen. Dat laat zich het makkelijkst illustreren met een voorbeeld. Stel, de pixels in een plaatje kunnen bestaan uit de volgende kleuren: rood, groen, blauw, geel, wit, oranje, grijs, paars en roze. De pixels in het plaatje dat we willen coderen zijn achtereenvolgens: blauw, geel, blauw, geel, blauw, grijs, grijs, grijs, grijs, wit. We beginnen met alle mogelijkheden op een rijtje. Iedere kleur heeft een nummer gekregen.
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
De gecodeerde reeks is dus: 3422271116. Zoals je ziet zit daar redelijk wat herhaling in en is dus met de run-length codering makkelijker te comprimeren. Het uitpakken is simpel: je neemt de reeks waarmee je begon en noteert daar de derde kleur van. Dan schuif je die kleur helemaal naar voren en neem je de vierde kleur. Die kleur schuif je helemaal naar voren en je neemt de tweede kleur. Zo ga je door totdat je alle cijfers hebt gehad. Dan heb je de originele reeks weer.
Aritmetische codering
Aritmetische codering is een vrij ingewikkelde vorm van codering, waarvan alleen het principe besproken zal worden, omdat het anders te ingewikkeld wordt. Deze codering zal een serie van berichten vertalen in een bepaald interval op een getallenlijn met waarden op het interval: [0,1). Net als met de Huffman codering is nodig om vooraf de kansen op de verschillende berichten te bepalen. Hoe preciezer die kans bepaald wordt, hoe beter de codering werkt. Het verschil met de Huffman codering is dat voor ieder bericht niet een heel aantal bits nodig is. Als de informativiteit van een bericht 0,0001 bit is, zal de Aritmetische codering daar ook (bij benadering) 0,0001 bit voor gebruiken om te coderen. Dat komt omdat niet ieder bericht een aparte code krijgt, zoals met de Huffman codering, maar de hele schakeling van berichten in een bepaald interval wordt vertaald. Dat gaat als volgt: Stel je hebt een stuk informatie dat uit drie berichten kan bestaan, namelijk x, y en z. De kans op x is 0,35; de kans op y is 0,25 en de kans op z is 0,4. Op de getallenlijn ziet dat er zo uit:
Als de informatie uit één bericht had bestaan dan was de code voor x: [0;0,35), de code voor y: [0,35;0,6) en de code voor z: [0,6,1) geweest. Hoe dat in bits vertaalt wordt zal in het belang van de eenvoud achterwegen gelaten worden. Voor een stuk informatie met meer berichten wordt als het ware ingezoomd op het interval. Stel er is een stuk informatie met als eerste bericht z, als tweede bericht y en als derde bericht x. Voor het eerste bericht is het interval: [0,6;1). Dan wordt er ingezoomd op dat interval en vervolgens wordt dat interval ook weer opgedeeld in stukken die evenredig zijn met de kansen. Het interval voor zy is dan: [0,74;0,84). Dat interval wordt weer opgedeeld in stukken evenredig met de kansen. Zo krijg je voor zyx het interval: [0,74;0,775). Het volgende plaatje laat het allemaal wat duidelijker zien:
Bij het decoderen wordt er dus eerst gekeken naar het grootste interval: Ligt het interval van het gecodeerde stuk ergens tussen de 0,6 en de 1? Zo ja, dan is het eerste bericht een z. Ligt het interval van het gecodeerde stuk binnen de 0,74 en de 0,84? Zo ja, dan is het tweede bericht een y. Is het uiteindelijke interval [0,74;0,775)? Zo ja, dan is het laatste bericht een x. Zo is de oorspronkelijke code van zyx weer tevoorschijn. Een klein ‘code-interval’ betekent dus dat er heel veel berichten in gecodeerd zitten en/of dat de berichten die er in zitten een kleine kans van voorkomen hebben. In ieder geval is de informativiteit van die code dan erg groot.
Lossy coderingen:
Zoals je aan het begin van deze tekst hebt kunnen lezen, gaat er bij lossy datacompressie een deel van de originele informatie verloren. Soms kan ervoor worden gekozen hoeveel informatie er ongeveer verloren mag gaan, en dus hoe erg het bestand gecomprimeerd mag worden. Bij veel lossy coderingen is het verlies aan informatie voor mensen nauwelijks waar te nemen.
Kwantisatie
Vooral bij het werken met digitaal beeld en geluid komt kwantisatie voor. Er zijn verschillende soorten kwantisatie, maar het principe is hetzelfde. Het probleem is dat computers alleen met hele waarden kunnen werken. Bij het opnemen van geluid komt er bijvoorbeeld een analoge stroom data binnen, die digitaal opgeslagen moet worden. In het plaatje is dat de rode golfbeweging. Die golfbeweging heeft op ieder tijdstip een unieke waarde. Een computer kan daar niet mee overweg. Bij het digitaal opslaan moet die golfbeweging opgeslagen worden in tijdvakken met een bepaalde waarde. Die tijdvakken kunnen allemaal slechts een eindig aantal waarden aannemen. In het voorbeeld zijn dat alle hele getallen tussen –12 en +12.
De mate van compressie wordt bepaald door de breedte van de tijdvakken en de precisie waarmee de y-waarden vastgelegd kunnen worden. Hoe kleiner de tijdvakken en hoe meer waarden de y as kan aannemen hoe preciezer de originele golfbeweging benaderd kan worden en hoe minder compressie er is.
Fractale compressie
Bij deze vorm van compressie worden fractals gebruikt, om zich herhalende patronen binnen een plaatje met minder bits te beschrijven. Daarbij gaat het dan vooral om foto’s en landschappen. Simpel gezegd bestaat een fractal uit een plaatje dat bestaat uit kleinere plaatjes die er hetzelfde uit zien. De compressie berust op het feit dat een fractal beschreven kan worden met een vrij simpele formule. Bij het comprimeren word er dus naar een zo simpel mogelijke formule gezocht waarmee de rest van (een deel van) een plaatje beschreven kan worden. Het nadeel van deze techniek is dat het erg lang duurt om de formules te ontdekken en dus ook om het plaatje te comprimeren. Het decomprimeren gaat wel snel. Een voorbeeld is een plaatje waar een boom op staat. De boom heeft een bepaalde structuur, die ook weer terug te vinden is in de takken. Als je dus een formule vindt om zo’n klein takje te beschrijven en daarmee dan de hele boom kunt opbouwen heb je dus het plaatje gecomprimeerd. Dat blijkt in de praktijk alleen niet zo eenvoudig.
Jpeg
De coderingen die nu volgen lijken een beetje op elkaar. Jpeg is methode om digitale plaatjes op te slaan. Daarbij wordt gebruik gemaakt van een vrij groot aantal compressiemethoden. Een van de speciale kenmerken van Jpeg compressie is dat de hoeveelheid verloren informatie door de gebruiker bepaald kan worden. De compressie verloopt in een aantal stappen. In de eerste stap worden de kleurwaarden van iedere pixel anders ‘opgeschreven’, zodat de groenwaarden veel nauwkeuriger beschreven worden dan de rood- en blauwwaarden. Het plaatje wordt daar niet groener door, zoals je zou verwachten. Dit is alleen een stap om het plaatje even scherp te houden, terwijl de kleuren minder nauwkeurig (en dus met minder bits) beschreven worden. Het menselijk oog is namelijk, als het om scherpte gaat, veel gevoeliger voor groen, dan voor andere kleuren. Dit is dus gewoon een soort van trucje. In de tweede stap worden de pixels in het plaatje verdeeld in vlakjes van 8 bij 8 pixels. Vervolgens wordt er op ieder vlakje een transformatie toegepast. Een transformatie is een manier om een aantal waarden op een andere manier op te schrijven, net als de Move-to-front en de Delta coderingen. Deze vorm van transformeren heet ‘discrete cosinus transformatie’. Zoals de naam zegt worden er met deze manier van transformeren cosinus functies gebruikt om de vlakjes van 8 bij 8 pixels te beschrijven. Vervolgens wordt er een vorm van kwantisatie toegepast. Dat is het stuk waar de gebruiker invloed heeft op de hoeveelheid compressie die wordt toegepast. Met behulp van de discrete cosinus transformatie kunnen eerst stukjes informatie worden weggelaten die de minste invloed hebben op de kwaliteit van het plaatje. Denk hierbij weer aan het plaatje van de kwantisatie.
Vervolgens kan er steeds meer informatie weggelaten worden, totdat er uiteindelijk bijna niks meer over is van het originele plaatje. De hoeveelheid informatie die weggelaten wordt hangt dus van de gebruiker af. Scherpe overgangen van kleur, oftewel contrasten, zijn door de discrete cosinus transformatie heel gevoelig voor het weglaten van informatie. Vandaar dat dat de eerste plekken zijn, waar het plaatje merkbaar in kwaliteit afneemt. Op het plaatje hier onder is dat effect goed te zien: (Het rechter plaatje is gecomprimeerd.)
Bij de volgende stappen van de Jpeg codering worden er vormen van de Delta codering en de Run-Length codering gebruikt om verschillende aspecten van de vlakjes te coderen. Aan het eind komt dan nog Huffman of Aritmetische codering.
Mpeg
Mpeg (afkorting voor Moving Pictures Experts Group) is een formaat voor het comprimeren van videobeelden. De basis van de Mpeg codering ligt bij de Jpeg codering. De beelden worden op ongeveer de zelfde wijze vastgelegd als bij Jpeg. Er is alleen wel een verschil tussen video- en fotomateriaal. Bij video is er een grote samenhang tussen de opvolgende plaatjes in het filmpje. Daar maakt Mpeg dankbaar gebruik van. Het gebruikt namelijk onder anderen een vorm van Delta codering om de verschillen tussen opeenvolgende plaatjes aan te geven, in plaats van alle plaatjes in hun geheel. Dat blijkt over het algemeen een heel effectieve manier van opslaan. Bij het comprimeren moet er echter wel gezocht worden naar bewegende dingen in het beeld, zodat die ook effectief opgeslagen kunnen worden. Dat kost nogal wat rekenkracht. Bij het decomprimeren hoeft dat echter niet. Vandaar dat het comprimeren bij Mpeg-filmpjes langer duurt dan het decomprimeren.
MP3
MP3 staat voor Mpeg audio layer 3 en is gebaseerd op het Mpeg-formaat. De grootte van een ongecomprimeerd muziekbestand hangt af van drie dingen. De lengte, de precisie waarmee de amplitude van de golfbeweging opgeslagen wordt en frequentie waarmee het geluid of de muziek bij het afspelen ‘ververst’ wordt; de zogenaamde sample-rate. Weer is het plaatje van de kwantisatie van toepassing:
De breedte van de tijdvlakjes representeert de sample-rate en de hoeveelheid horizontale lijnen representeert de precisie waarmee de amplitude kan worden vastgelegd. Mp3 doen een aantal dingen met geluid, die meestal te maken hebben met de beperkingen van het menselijk oor. Op de eerste plaats reduceert MP3 de precisie waarmee de amplitude van de geluidsgolf wordt opgeslagen en soms de sample-rate. Dat valt namelijk in de meeste gevallen voor ongetrainde oren niet op. Daarnaast kan op plaatsen waar dat wel merkbaar zou zijn, de precisie van het beschrijven van de golf groter gehouden worden. Ook slaat MP3 uiterst hoge en uiterst lage tonen, die het menselijk oor niet kan waarnemen, niet op. Een ander trucje dat MP3 toepast, is het weglaten van informatie vlak nadat er een heel hard geluid is geweest. Studies hebben bewezen, dat tonen die vlak na een hard geluid komen nauwelijks geregistreerd worden in de hersenen. Als laatste wordt er een techniek toegepast die geen ‘misbruik’ van het menselijk oor maakt. Veel geluidsbestanden worden namelijk aangeboden in stereo. Dat betekent dat er voor twee luidsprekers een apart geluidssignaal is. In principe zou dat betekenen dat het bestand twee maal zo groot zou zijn, als het bestand voor een enkele luidspreker. Er bestaat echter veel samenhang tussen het geluid voor de rechter luidspreker en het geluid voor de linker luidspreker. Daar maakt MP3 gebruik van, door het geluidssignaal maar één keer op te slaan als het geluid voor beide luidsprekers hetzelfde is.
Ook bij het MP3 formaat is het mogelijk om zelf de hoeveelheid compressie te bepalen. De hoeveelheid compressie van een geluidsbestand wordt uitgedrukt in de bitrate. De bitrate is het aantal bits dat er per seconde nodig is om dat bestand op te slaan. Veel gebruikte bitrates zijn: 64, 128, 192, 256 en 320 kilobits per seconde (kbps). Hoe hoger de bitrate, hoe hoger de kwaliteit en hoe minder compressie er is. Om inzicht te geven in de kracht van de MP3 compressie kijken we naar de hoeveelheid muziek die er op een mp3-speler met 256 megabyte (MB) geheugen kan. Een formaat dat niet comprimeert, zoals het WAV formaat heeft ongeveer 1411 kilobyte (KB) nodig voor één seconde (stereo) muziek. Dat wordt zo berekend: 44100 Hz (samplerate) * 1 seconde (duur van het geluidsbestand) * 2 kanalen (het geluid is in stereo) * 16 bits (aantal bits dat nodig is om de amplitude van de golfbeweging vast te leggen) = 1411200 bits. Per minuut heeft het WAV formaat dus 60 seconden (aantal seconden in één minuut) * 1411200 bits (bitrate van het WAV formaat) / 8 bit (aantal bit in één byte) = 10584000 byte = 10,1 MB nodig om het geluidsbestand op te slaan. Een MP3 bestand van redelijke kwaliteit heeft daarentegen slechts 128 kilobits per seconde nodig om een muziekbestand op te slaan. Dat is 128 kbps * 1024 bits (aantal bits in één kilobit) * 60 seconden (aantal seconden in één minuut) / 8 bits (aantal bits in één byte) = 983040 bytes per minuut, oftewijl 0,9375 MB per minuut. Op een mp3-speler met 256 MB aan geheugen kan dus een geluidsfragment dat maximaal ( 256 MB / 10,1 MB per minuut = ) 25,3 minuten duurt, als het niet gecomprimeerd wordt. Met MP3 compressie kan er een geluidsfragment van maarliefs (256 MB / 0,9375 MB per minuut = ) 273,1 minuten op. Dat is 10,8 maal zo lang. En in de praktijk blijkt de compressie zelfs nog beter te zijn.
Bij dit onderzoek is er gekeken naar de comprimeerbaarheid van de Nederlandse taal. Voor het Engels zijn dat soort onderzoeken al uitgevoerd, maar over het Nederlands was er op internet niet veel te vinden. Daarom was het wel aardig om met een simpel onderzoekje te bekijken hoe comprimeerbaar de Nederlandse taal is.
Het was natuurlijk mogelijk om er een ontzettend complex onderzoek van te maken, maar dat was niet de bedoeling. Daarom is er naar slechts twee soorten compressie gekeken. De eerste is de meest simpele: iedere letter krijgt een code toegewezen. De lengte van die code hangt af van de frequentie waarmee die letter voor komt. Daarmee wordt gebruik gemaakt van de Huffman codering. Met deze vorm wordt lang geen maximale compressie gerealiseerd, maar hij is wel zeer simpel, dus het comprimeren en decomprimeren duurt zeer kort. Bij de tweede manier wordt aan ieder woord een aparte code toegekend, die afhangt van de frequentie van dat woord. Dit is een veel efficiëntere manier van comprimeren, die wel meer tijd zal kosten om een bestand te (de)comprimeren.
Om dit te kunnen onderzoeken was een groot bestand met heel veel Nederlandse woorden nodig, zodat de frequentie van letters en woorden kon worden bepaald. Zo’n bestand wordt een corpus genoemd. In het Engels zijn er vele beschikbaar en in het Nederlands is er onder de naam D-coi (Dutch language COrpus Initiative) ook één met 500-miljoen woorden in ontwikkeling, maar op het moment is er nog geen enkele beschikbaar. Wel zijn er statistieken bekend over de frequentie waarmee individuele letters voor komen, maar dat onderzoek stamt nog uit 1985 en is gebaseerd op redactionele krantentekst. Dat is dus niet representatief voor de hedendaagse Nederlandse taal. Ook kon er de frequentie waarmee de woorden voorkwamen niet uit afgeleid worden. Vandaar dat er een heel nieuwe corpus samengesteld moest worden. Om het te downloaden klik je hier [752 kB]. Het bestaat uit 6 verslagen, 17 krantenartikelen, 1 scriptie, 1 wetsvoorstel, 1 officieel advies aan de minister van volksgezondheid, 1 verhaal en twee sprookjes, om een zo goed mogelijke doorsnee te geven van de Nederlandse taal.
Voor het bepalen van de letterfrequenties is het programma Word gebruikt. Om het simpel te houden zijn de speciale tekens, leestekens, cijfers en hoofdletters genegeerd. Met de compressie methode die zo gemaakt werd zou dus alleen simpele tekst gecomprimeerd kunnen worden. Het resultaat en enkele statistieken kan je hier vinden. Met het berekenen van de letterfrequenties was het nog niet af. Voor iedere letter werd de kans van voorkomen berekend, door het aantal keer dat de letter in de tekst zat te delen door het totale aantal letters. Vervolgens werd de totale informativiteit van een stuk informatie met één teken berekend, door de kansen van ieder bericht te vermenigvuldigen met de informativiteit van dat bericht ( p(b) * log(1/p(b)) / log(2) ) en al die uitkomsten op te tellen. Daar kwam een waarde van 4,069510676 uit. In theorie zou je dus ieder stuk Nederlandse tekst zonder leestekens, hoofdletters enzovoort kunnen opslaan met gemiddeld ongeveer 4,07 bits per letter. Om te kunnen nagaan of dat klopt, moest er met de Huffman codering aan iedere letter een code worden toegewezen. Het resultaat is hier te zien.Vervolgens kan er dan een stuk tekst handmatig worden gecomprimeerd. Daarmee is uit te rekenen of de theorie klopt. Laten we dat nu maar eens even doen. We nemen de tekst:
‘We nemen de bus naar huis’ (27 tekens)
Als we iedere letter de bijbehorende code toewijzen krijg je:
100000 001 011 0001 001 000001 001 0001 011 0101 001 011 110001 111001 00001 011 0001 0100 0100 1101 011 10011 111001 0101 00001 (maar dan zonder spaties)
Het gecodeerde bericht heeft 104 bits, dus dat is 104 / 27 (ongeveer 3,85) bit per karakter. Dat is dus nog lager dan de voorspelde 4,07! Echter, hoe langer het te coderen bericht is, hoe dichter het bij de 4,07 zal liggen. Neem bijvoorbeeld de zin: “In de voorstelling gaat het om het leven en of je wel wil leven als het leven dat je leeft erg hard is” en je komt uit op 4,001 bits per letter. Ook korte berichten met een aantal weinig voorkomende letters, zoals de q, x, y en z, kunnen een hogere waarde dan 4,07 bits per letter hebben. Dat hangt dus helemaal van het bericht af. Gemiddeld zal het aantal bits dat je per teken nodig hebt iets meer zijn dan de voorspelde waarde van ongeveer 4,07 omdat je ieder bericht met een heel aantal bits moet beschrijven. Het zou ideaal zijn als je ieder bericht met het aantal bits kon beschrijven dat gelijk was aan de informativiteit van dat bericht, maar dat gaat helaas niet.
De tweede manier was wat complexer dan de eerste manier, dus het was te veel werk om hem handmatig tot in hetzelfde detail als dat van de eerste uit te werken. Voor dat soort berekeningen is een computerprogramma vereist. Hoewel deze manier van comprimeren efficiënter is dan de eerste manier, zitten er ook nadelen aan. De eerste is al genoemd, hij is namelijk langzamer. De tweede is dat een woord dat niet in het corpus zit in principe ook niet gecomprimeerd kan worden. Daarom is er voor gekozen om de spaties als apart woord te behandelen, zodat als er een onbekend woord in de tekst voor komt, hij altijd nog als aaneenschakeling van éénletterwoorden behandeld kan worden. Als de spatie bij een woord in zit kan dat niet, omdat het onbekende woord dan steeds zou worden onderbroken door spaties. Het berekenen van de woordfrequenties werd door een programmaatje op internet gedaan.
De gemiddelde hoeveelheid bits per letter die met deze methode gerealiseerd wordt is (in praktijk) iets meer dan 1,907. Dat is dus twee maal zo klein als met de eerste methode! Dit getal werd als volgt berekend:
-
Bepalen van de kans van een woord, door de frequentie te delen door
het totale aantal woorden.
-
Bepalen van de informativiteit van een stuk informatie dat uit een
willekeurig bericht bestaat, door alle waarden van de kansen van de
berichten vermenigvuldigd met de informativiteit van die berichten op
te tellen.
-
Bepalen van de gemiddelde woordlengte door alle waarden van de kansen
van de berichten vermenigvuldigd met de woordlengte van die berichten
bij elkaar op te tellen.
-
Bepalen van de gemiddelde hoeveelheid bits die per letter gebruikt
moeten worden, door de informativiteit van een woord te delen door de
gemiddelde woordlengte.
Hoe verhouden deze getallen zich nu tot de werkelijkheid?
Tekst, zoals die in bijvoorbeeld Word-documenten is opgeslagen, wordt opgeslagen met een vaste lengte van 7 bits per letter. Daarmee kan gewone tekst, maar ook cijfers, hoofdletters, speciale tekens etc. opgeslagen worden. De eerste compressiemethode zou vergeleken met deze methode een compressie van ( 100 - ( 4.069510676 * 100 / 7 ) = ) 41,86% verwezenlijken. Dat betekent dat het verkregen bestand in vergelijking met het originele bestand 41,86% kleiner is geworden. De tweede manier zou een compressie van ( 100 - ( 1,90700571 * 100 / 7 ) = ) 72,76% verwezenlijken. Hoewel dat best een goed resultaat zou zijn, is dit geen goede vergelijking. In de situatie waarmee we hier gerekend hebben zijn er namelijk maar 27 mogelijke berichten (namelijk: 26 letters en de spatie) in plaats van de tientallen die je in een normaal bestand kunt gebruikten. Als er echter maar 27 mogelijkheden zouden zijn, dan zouden de tekens met slechts 5 bits (= 2^5 = 32 mogelijkheden) gecodeerd kunnen worden. In dat geval zou de eerste methode slechts een compressie van ( 100 - ( 4.069510676 * 100 / 5 ) = ) 18,61% teweeg brengen. De tweede zou het beter, maar ook niet zo goed als eerst doen: 100 - ( 1,90700571 * 100 / 5 ) = 61,86%. De tweede manier geeft dus een redelijk goede compressie, die in de praktijk best bruikbaar zou zijn, ware het niet dat er alleen de allersimpelste tekst mee gecomprimeerd zou kunnen worden en dat het een zeer beperkt ‘woordenboek’ heeft, waaruit de informatie opgesteld mag zijn. Als het corpus van 500 miljoen Nederlandse woorden op een geavanceerde manier zou kunnen worden geanalyseerd, zodat alle karakters die je normaal ook zou gebruiken geregistreerd worden, belooft dat een vrij goede compressiemethode te zijn. De vraag is alleen of het een zeer praktische methode zou zijn, omdat het programmaatje dat moet (de)comprimeren een ontzettend groot woordenboek bij zich moet hebben, en dus zelf erg groot zal zijn. Ook het comprimeren en decomprimeren zal langzaam gaan.
Je bent als het goed is al een groot aantal dingen te weten gekomen over digitale compressie. In principe is compressie dus het korter maken van de codes van berichten of schakelingen van berichten die vaak voorkomen. Met behulp van de informatietheorie is het mogelijk van te voren uit te rekenen hoeveel compressie er maximaal mogelijk is, zonder ook daadwerkelijk een programma te schrijven dat die compressie uit voert. Dat is best een fascinerend idee.
Verder zijn er twee soorten compressie: lossless en lossy compressie. Bij lossless compressie gaat er geen informatie verloren en is het oorspronkelijke stuk informatie weer in exact de zelfde vorm terug te krijgen na decompressie van het gecomprimeerde bestand. Bij lossy is dat niet zo, er gaat daarbij altijd een bepaalde hoeveelheid informatie verloren. Soms kan door de gebruiker bepaald worden hoeveel dat is. In lossy compressie wordt ook bijna altijd lossless compressie gebruikt. Beide vormen van compressie kunnen gebruik maken van (een) transformering(en) om de compressie nog groter te maken. Een transformering schrijft de informatie als het ware alleen anders op, maar zorgt zelf niet voor compressie.
Afgezien van het feit dat het bij sommige bestanden mogelijk is om bij het comprimeren van dat bestand informatie weg te laten, is er een aantal factoren dat invloed heeft op de comprimeerbaarheid van een bestand. Als eerste moeten er bepaalde berichten binnen het stuk informatie meer voor komen dan andere, zodat aan die berichten een kortere code toegewezen kan worden. Het tweede punt dat de comprimeerbaarheid beïnvloed, is de hoeveelheid herhaling die er in een bestand zit. Als er veel herhaling is, hoeft er alleen aangegeven te worden hoe vaak dat stukje voor komt en hoe het ‘er uit ziet’, in plaats van ieder element op nieuw. Ook is het handig als elementen veel op elkaar lijken. In dat geval hoeft er alleen het verschil tussen die elementen aangegeven te worden, wat meestal veel minder geheugen kost, dan het apart beschrijven van elk element. Als derde wordt de compressie bevorderd als er een samenhang is tussen bepaalde elementen in de te comprimeren informatie. Als er bijvoorbeeld na een q met grote waarschijnlijkheid een u komt, is dat makkelijker te comprimeren, dan als er na een q een even grote kans is op alle letters.
Compressie begon met de uitvinding van de morsecode, maar tegenwoordig wordt het vooral met internet en computers gebruikt. Het heeft als doel de bestanden kleiner te maken, zodat ze op een efficiëntere manier kunnen worden verstuurd en opgeslagen. Grote bestanden die van computer naar computer verstuurd moeten worden, worden meestal eerst gecomprimeerd. Een goed voorbeeld daarvan is het versturen en downloaden van muziek. Normaal zou het meer dan een uur duren om een muziekbestand van enkele minuten met een inbelverbinding te downloaden. Door die bestanden als MP3tjes te versturen zou het slechts iets langer dan vijf minuten duren. Dat is een zeer groot verschil (in telefoonkosten). Bij het opslaan van informatie op het internet, zodat iedereen met een internetverbinding die informatie kan bekijken, wordt ook vaak compressie gebruikt. Dat komt omdat de ruimte op een zogenaamde server, waar die informatie wordt opgeslagen, vaak duur en/of beperkt is. Om toch zo veel mogelijk bestanden op de server te kunnen proppen, worden bestanden zoals plaatjes vaak zo klein mogelijk gecomprimeerd.
Toch hoeft compressie niet altijd met internet te maken te hebben. Er zijn ook toepassingen die niets met internet te maken hebben. Meestal is er op de harde schijf van een computer wel voldoende ruimte om alles ‘normaal’ op te slaan, maar het kan natuurlijk gebeuren dat de harde schijf vol komt te zitten en het niet gewenst is om informatie te wissen. In zo’n geval komt compressie natuurlijk ook goed van pas. Bij het opslaan van informatie op kleinere opslag media, zoals een memory-stick of een floppy geldt dat natuurlijk ook. Computerspelletjes zijn een ander voorbeeld. In veel computerspelletjes zitten filmpjes verwerkt. Filmpjes nemen over het algemeen veel ruimte in, terwijl de ruimte op de Cd-rom, waar zo’n spelletje op staat maar beperkt is. In zo’n geval is het Mpeg formaat erg handig, want bij dat soort compressie duurt het comprimeren veel langer dan het decomprimeren. Bij het lezen van de Cd-rom, kan het filmpje dan snel gedecomprimeerd worden, terwijl het niet erg is dat het comprimeren van het filmpje langer duurt. Dat hoeft namelijk vooraf slechts één keer gedaan te worden.
Zodra je met computers werkt kom je compressie dus overal tegen. Toch gebeurt er ook veel ‘achter de schermen’ en heb je vaak niet eens door dat er compressie gebruikt wordt. Hoe het dan allemaal werkt wordt vaak al helemaal bij stil gestaan. Net als mobieltjes en koelkasten: die doen het gewoon.
Opdrachten:
begin met een tiff plaatje
noteer de maat in pixels (lxb)
bereken de oppervlakte in pixels
check bij eigenschappen hoe
groot het werkelijk is
bereken het aantal bits per pixel
check ook de grotte op schijf (afgerond op hele Kb's)
sla het
plaatje op als JPG, GIF, PNG (zonder compressie
check bij
eigenschappen hoe groot ze werkelijk zijn
experimenteer met de
verschillende formaten en hun compressietechnieken
maak een
verslag