Hur fungerar filkomprimering?

Programvarutekniker har alltid utvecklat nya sätt att anpassa mycket data till ett litet utrymme. Det var sant när våra hårddiskar var små, och tillkomsten av internet har just gjort det mer kritiskt. Filkomprimering spelar en stor roll för att ansluta oss, så att vi skickar mindre data ner i raden så att vi kan få snabbare nedladdningar och passa fler anslutningar till upptagna nätverk.

Så hur fungerar det?

Att svara på den frågan skulle innebära att man förklarar lite väldigt komplicerad matte, säkert mer än vad vi kan täcka i den här artikeln, men du behöver inte förstå exakt hur det fungerar matematiskt för att förstå grunderna.

De mest populära biblioteken för komprimering av text är beroende av två komprimeringsalgoritmer, samtidigt som de används för att uppnå mycket höga kompressionsförhållanden. Dessa två algoritmer är "LZ77" och "Huffman kodning." Huffman kodning är ganska komplicerat, och vi kommer inte att gå in i detalj på den här här. För det första använder den lite fancy matematik för att tilldela kortare binära koder till enskilda bokstäver, krympande filstorlekar i processen. Om du vill lära dig mer om det, kolla in den här artikeln om hur koden fungerar, eller det här förklaras av Computerphile.

LZ77, å andra sidan, är relativt enkelt och det är vad vi ska prata om här. Det försöker ta bort dubbla ord och ersätta dem med en mindre "nyckel" som representerar ordet.

Ta till exempel den här korta texten:

LZ77-algoritmen skulle se på denna text, inse att den upprepar "howtogeek" tre gånger och ändra den till detta:

Då, när den vill läsa texten tillbaka, skulle den ersätta varje förekomst av (h) med "howtogeek", vilket ger oss tillbaka till den ursprungliga frasen.

Vi kallar komprimering som den här "lossless" -datan du lägger in är densamma som de data du får ut. Ingenting går förlorat.

I verkligheten använder LZ77 inte en lista med nycklar, utan ersätter istället den andra och tredje händelsen med en länk i minnet:

Så nu när det kommer till (h), kommer det att se tillbaka till "howtogeek" och läsa det istället.

Om du är intresserad av en mer detaljerad förklaring, är den här videon från Computerphile ganska hjälpsam.

Nu är det här ett idealiserat exempel. I själva verket komprimeras de flesta texter med nycklar så små som bara några tecken. Till exempel skulle ordet "the" komprimeras även när det visas i ord som "där", "deras" och "då". Med upprepad text kan du få några galen kompressionsförhållanden. Ta denna textfil med ordet "howtogeek" upprepad 100 gånger. Den ursprungliga textfilen är tre kilobytes i storlek. När det komprimeras tar det emellertid bara upp 158 byte. Det är nästan 95% kompression.

Nu är det självklart ett ganska extremt exempel eftersom vi bara hade samma ord upprepade om och om igen. I allmän praxis får du förmodligen runt 30-40% komprimering med ett komprimeringsformat som ZIP på en fil som oftast är text.

Denna LZ77-algoritm gäller för alla binära data, förresten, och inte bara text, men text är i allmänhet lättare att komprimera på grund av hur många upprepade ord de flesta språk använder. Ett språk som kinesiska kan vara lite svårare att komprimera än engelska, till exempel.

Hur fungerar bild- och videokomprimering?

Video och ljudkomprimering fungerar väldigt annorlunda. Till skillnad från text där du kan ha förlustfri komprimering och ingen data går förlorad, med bilder har vi det som kallas "Lossy Compression" där du förlorar vissa data. Och ju mer du komprimerar desto mer data förlorar du.

Det här leder till de hemska JPEG-bilderna som folk har laddat upp, delat och skärmdumpade flera gånger. Varje gång bilden komprimeras, förlorar den viss data.

Här är ett exempel. Detta är en skärmdump jag tog som inte har komprimerats alls.

Jag tog den skärmdumpen och körde den genom Photoshop flera gånger, varje gång jag exporterade den som en lågkvalitativ JPEG. Här är resultatet.

Ser ganska dåligt ut?

Jo, det här är bara ett worst case-scenario, som exporterar med 0% JPEG-kvalitet varje gång. För jämförelse, här är en 50% kvalitets JPEG, som nästan kan skilja sig från källkällans PNG-bild om du inte blåser upp den och tittar på dig.

PNG för den här bilden var 200 KB, men den här 50% kvalitets JPEG är bara 28 KB.

Så hur sparar det så mycket utrymme? Jo, JPEG-algoritmen är en prestation i teknik. De flesta bilder lagrar en lista med siffror, med varje nummer som representerar en enda bildpunkt.

JPEG gör inget av detta. Istället lagrar den bilder med något som kallas en diskret cosine-transform, vilket är en samling sinusvågor som läggs ihop i varierande intensiteter. Det använder 64 olika ekvationer, men de flesta av dessa används inte. Det här är vad kvalitetsreglaget för JPEG i Photoshop och andra bildprogram gör - välj hur många ekvationer som ska användas. Apparna använder sedan Huffman-kodning för att minska filstorleken ytterligare.

Detta ger JPEG-filer ett vanligt högt kompressionsförhållande, vilket kan minska en fil som skulle vara flera megabyte ner till ett par kilobytes, beroende på kvaliteten. Självklart, om du använder det för mycket, slutar du med det här:

Den bilden är hemsk. Men mindre mängder av JPEG-komprimering kan ha en stor inverkan på filstorleken, vilket gör JPEG väldigt användbart för bildkomprimering på webbplatser. De flesta bilder du ser online komprimeras för att spara på nedladdningstider, speciellt för mobilanvändare med dåliga dataanslutningar. Faktum är att alla bilder på How-To Geek har komprimerats så att sidan laddas snabbare, och du har nog aldrig märkt.

Videokomprimering

Video fungerar lite annorlunda än bilder. Du skulle tro att de bara skulle komprimera varje bildruta med JPEG, och de gör det säkert, men det finns en bättre metod för video.

Vi använder något som kallas "interframe compression", som beräknar ändringarna mellan varje ram och endast lagrar dem. Så om du till exempel har ett relativt stillbild som tar upp flera sekunder i en video blir mycket utrymme sparad eftersom komprimeringsalgoritmen inte behöver lagra alla saker i scenen som inte ändras. Interframe-komprimering är den främsta orsaken till att vi har digital-tv och webbvideo alls. Utan det skulle videon vara hundratals gigabyte, mer än den genomsnittliga hårddiskstorleken 2005 när YouTube startade.

Eftersom interframekomprimering fungerar bäst med mestadels stationär video, är det därför konfetti som förstör videokvalitet.

Obs! GIF gör inte det här, varför animerade GIF ofta är mycket korta och små men har fortfarande en ganska stor filstorlek.

En annan sak att tänka på om video är dess bithastighet, mängden data som tillåts i varje sekund. Om din bitrate är 200 kb / s, så kommer din video att se ganska dålig ut. Kvaliteten går upp när bitraten går upp, men efter ett par megabyte per sekund får du avtagande avkastning.

Detta är en zoomad bild som tagits från en video av en maneter. Den till vänster är 3Mb / s, och den till höger är 100Mb / s.

En 30x ökning i filstorlek, men inte mycket ökning i kvalitet. Vanligtvis ligger YouTube-videor runt 2-10 Mbps beroende på din anslutning, eftersom allting mer nog inte skulle märkas.

Denna demo fungerar bättre med aktuell video, så om du vill checka ut det själv kan du hämta samma bitrate testvideo som används här.

Ljudkomprimering

Ljudkomprimering fungerar väldigt på text- och bildkomprimering. Om JPEG tar bort detaljer från en bild som du inte kommer se, gör ljudkomprimering samma för ljud. Du kanske inte behöver höra den gnistrande gitarren på strängen om den verkliga gitarren är mycket, mycket hårdare.

MP3 använder också bitrate, från lågänden på 48 och 96 kbps (lågänden) till 128 och 240kbps (ganska bra) till 320kbps (high end audio), och du kommer sannolikt bara att höra skillnaden med exceptionellt bra hörlurar ( och öron).

Det finns också förlustfria komprimerings codecs för ljud-den främsta är FLAC-som använder LZ77-kodning för att leverera helt förlustfri ljud. Vissa människor svär på FLACs perfekta ljudkvalitet, men med utbredningen av MP3 verkar det som om de flesta inte heller kan berätta eller inte ha något emot skillnaden.