Hoe werkt bestandscompressie?

Software-ingenieurs hebben altijd nieuwe manieren ontwikkeld om veel gegevens in een kleine ruimte te passen. Het was waar wanneer onze harde schijven klein waren, en de komst van het internet heeft het alleen maar kritischer gemaakt. Bestandscompressie speelt een grote rol bij het verbinden van ons, waardoor we minder gegevens langs de lijn kunnen verzenden, zodat we snellere downloads kunnen maken en meer verbindingen kunnen leggen op drukke netwerken.

Dus hoe werkt het?

Om die vraag te beantwoorden zou het gaan om het uitleggen van een aantal zeer gecompliceerde wiskunde, zeker meer dan we in dit artikel kunnen bespreken, maar je hoeft niet precies te begrijpen hoe het wiskundig werkt om de basis te begrijpen.

De meest populaire bibliotheken voor het comprimeren van tekst zijn gebaseerd op twee compressiealgoritmen, die beide tegelijkertijd gebruiken om zeer hoge compressieverhoudingen te bereiken. Deze twee algoritmen zijn "LZ77" en "Huffman-codering". Huffman-codering is behoorlijk gecompliceerd, en we zullen hier niet in detail op deze ingaan. In de eerste plaats gebruikt het enkele fancy wiskunde om korter toe te wijzen binaire codes naar individuele letters, waardoor bestandsgroottes in het proces kleiner worden. Als je er meer over wilt weten, bekijk dan dit artikel over hoe de code werkt, of deze uitlegger door Computerphile.

LZ77, aan de andere kant, is relatief eenvoudig en dat is waar we het hier over zullen hebben. Het probeert dubbele woorden te verwijderen en te vervangen door een kleinere "sleutel" die het woord vertegenwoordigt.

Neem dit korte stuk tekst bijvoorbeeld:

Het LZ77-algoritme zou naar deze tekst kijken, zich realiseren dat het drie keer "howtogeek" herhaalt en dit als volgt verandert:

Als het vervolgens de tekst terug wil lezen, vervangt het elke instantie van (h) door 'howtogeek', waardoor we teruggaan naar de oorspronkelijke zin.

We noemen compressie als dit "verliesloos" - de gegevens die u invoert, zijn hetzelfde als de gegevens die u eruit haalt. Er gaat niets verloren.

In werkelijkheid gebruikt LZ77 geen lijst met toetsen, maar vervangt in plaats daarvan het tweede en derde exemplaar door een koppeling terug in het geheugen:

Dus nu, wanneer het tot (h) komt, zal het terugkijken naar "howtogeek" en dat in plaats daarvan lezen.

Als je geïnteresseerd bent in een meer gedetailleerde uitleg, is deze video van Computerphile erg handig.

Dit is een geïdealiseerd voorbeeld. In werkelijkheid is de meeste tekst gecomprimeerd met sleutels zo klein als slechts enkele tekens. Het woord 'de' zou bijvoorbeeld worden gecomprimeerd, zelfs als het wordt weergegeven in woorden als 'there', 'their' en 'then'. Met herhaalde tekst kunt u enkele gekke compressieverhoudingen krijgen. Neem dit tekstbestand met het woord "howtogeek" 100 keer herhaald. Het originele tekstbestand is drie kilobytes groot. Als het wordt gecomprimeerd, kost het echter slechts 158 bytes. Dat is bijna 95% compressie.

Dat is overduidelijk een extreem voorbeeld, want we hadden hetzelfde woord steeds opnieuw herhaald. In de praktijk zul je waarschijnlijk ongeveer 30-40% compressie krijgen met behulp van een compressie-indeling zoals ZIP op een bestand dat voornamelijk uit tekst bestaat.

Dit LZ77-algoritme is overigens van toepassing op alle binaire gegevens, en niet alleen op tekst, hoewel tekst over het algemeen gemakkelijker te comprimeren is vanwege het aantal herhaalde woorden dat de meeste talen gebruiken. Een taal als Chinees kan bijvoorbeeld iets moeilijker te comprimeren zijn dan Engels.

Hoe werkt compressie van afbeeldingen en video's?

Video- en audiocompressie werkt heel anders. In tegenstelling tot tekst waarbij u compressie zonder gegevensverlies kunt hebben en er geen gegevens verloren gaan, hebben we bij afbeeldingen 'Lossy Compression', waarbij u wel wat gegevens verliest. En hoe meer u comprimeert, hoe meer gegevens u verliest.

Dit is wat leidt tot die vreselijk ogende JPEG's die mensen meerdere keren hebben geüpload, gedeeld en screenshots. Elke keer dat de afbeelding wordt gecomprimeerd, verliest deze wat gegevens.

Hier is een voorbeeld. Dit is een screenshot dat ik heb gemaakt en dat helemaal niet is gecomprimeerd.

Vervolgens nam ik dat screenshot en liep het meerdere keren door Photoshop, telkens als JPEG van lage kwaliteit. Dit is het resultaat.

Ziet er behoorlijk slecht uit, toch??

Nou, dit is slechts een worst-case scenario, het exporteren op 0% JPEG-kwaliteit elke keer. Ter vergelijking: hier is een JPEG van 50% kwaliteit, die bijna niet te onderscheiden is van het PNG-bronbeeld, tenzij je hem opblaast en goed kijkt.

De PNG voor deze afbeelding was 200 kB groot, maar deze 50% -kwaliteit JPEG is slechts 28 kB.

Dus hoe bespaart het zo veel ruimte? Welnu, het JPEG-algoritme is een staaltje van techniek. De meeste afbeeldingen slaan een lijst met getallen op, waarbij elk nummer een enkele pixel vertegenwoordigt.

JPEG doet niets hiervan. In plaats daarvan worden afbeeldingen opgeslagen met de naam Discrete Cosine Transform, een verzameling sinusgolven die met verschillende intensiteiten aan elkaar zijn toegevoegd. Het gebruikt 64 verschillende vergelijkingen, maar de meeste hiervan worden niet gebruikt. Dit is wat de kwaliteits-schuifregelaar voor JPEG in Photoshop en andere afbeeldingen-apps doet - kies het aantal vergelijkingen dat moet worden gebruikt. De apps gebruiken vervolgens Huffman-codering om de bestandsgrootte nog verder te verkleinen.

Dit geeft JPEG's een waanzinnig hoge compressieratio, waardoor een bestand dat meerdere megabytes tot een paar kilobytes kan verkleinen, afhankelijk van de kwaliteit wordt verminderd. Natuurlijk, als je het te veel gebruikt, krijg je dit:

Dat beeld is vreselijk. Maar kleine hoeveelheden JPEG-compressie kunnen een grote invloed hebben op de bestandsgrootte, en dit maakt JPEG erg handig voor beeldcompressie op websites. De meeste afbeeldingen die u online ziet, zijn gecomprimeerd om downloadtijden te besparen, vooral voor mobiele gebruikers met slechte gegevensverbindingen. In feite zijn alle afbeeldingen op How-To Geek gecomprimeerd om het laden van pagina's sneller te maken, en je hebt het waarschijnlijk nooit gemerkt.

Video compressie

Video werkt een beetje anders dan afbeeldingen. Je zou denken dat ze elk videoframe gewoon zouden comprimeren met JPEG, en dat doen ze zeker, maar er is een betere methode voor video.

We gebruiken iets genaamd "interframe-compressie", dat de veranderingen tussen elk frame berekent en alleen die opslaat. Dus als u bijvoorbeeld een relatief stilstaande opname heeft die enkele seconden duurt in een video, wordt er veel ruimte bespaard omdat het compressiealgoritme niet alle spullen in de scène hoeft op te slaan die niet veranderen. Interframecompressie is de belangrijkste reden waarom we digitale tv en webvideo hebben. Zonder dit zouden video's honderden gigabytes zijn, meer dan de gemiddelde harde schijf in 2005 toen YouTube werd gelanceerd.

Aangezien interframe-compressie het beste werkt met voornamelijk stationaire video, is dit de reden waarom confetti videokwaliteit schaadt.

Opmerking: GIF doet dit niet, daarom zijn geanimeerde GIF's vaak erg kort en klein, maar hebben ze nog steeds een vrij grote bestandsgrootte.

Een ander ding om in gedachten te houden over video is de bitrate - de hoeveelheid gegevens die per seconde is toegestaan. Als je bitrate bijvoorbeeld 200 kb / s is, ziet je video er slecht uit. De kwaliteit stijgt naarmate de bitsnelheid toeneemt, maar na een paar megabytes per seconde neemt het rendement af.

Dit is een ingezoomd kader uit een video van een kwal. De enige links is 3Mb / s en de rechterkant is 100Mb / s.

Een 30x toename in bestandsgrootte, maar niet veel toename in kwaliteit. Over het algemeen zitten YouTube-video's rond 2-10 MB / s, afhankelijk van je verbinding, omdat er waarschijnlijk niet veel meer wordt opgemerkt.

Deze demo werkt beter met de feitelijke video, dus als je het zelf eens wilt bekijken, kun je dezelfde bitrate-testvideo's als hier gebruikt downloaden.

Audiocompressie

Audiocompressie werkt op dezelfde manier als tekst- en beeldcompressie. Waar JPEG details uit een afbeelding verwijdert die u niet ziet, doet audiocompressie hetzelfde voor geluiden. Het is misschien niet nodig om het kraken van de plectrum op de snaar te horen als de eigenlijke gitaar veel, veel luider is.

MP3 gebruikt ook bitrate, variërend van het lage eind van 48 en 96 kbps (het lage eind) tot 128 en 240 kbps (redelijk goed) tot 320 kbps (high-end audio), en je zult waarschijnlijk het verschil alleen horen met uitzonderlijk goede koptelefoons ( en oren).

Er zijn ook verliesloze compressie-codecs voor audio - de belangrijkste is FLAC - die LZ77-codering gebruikt om volledig verliesloos geluid te leveren. Sommige mensen zweren bij de perfecte geluidskwaliteit van FLAC, maar met de prevalentie van MP3 lijkt het erop dat de meeste mensen het verschil niet kunnen zien of niet erg vinden.