Hvordan fungerer filkomprimering?
Programvareingeniører har alltid utviklet nye måter å tilpasse mye data til i et lite rom. Det var sant da harddiskene våre var små, og adventen til internett har nettopp gjort det mer kritisk. Filkomprimering spiller en stor rolle i å forbinde oss, slik at vi sender mindre data nedover linjen, slik at vi kan få raskere nedlastinger og tilpasse flere tilkoblinger til travle nettverk.
Så hvordan fungerer det?
Å svare på det spørsmålet ville innebære å forklare noen svært kompliserte matte, sikkert mer enn vi kan dekke i denne artikkelen, men du trenger ikke å forstå nøyaktig hvordan det fungerer matematisk for å forstå det grunnleggende.
De mest populære bibliotekene for komprimering av tekst er avhengige av to komprimeringsalgoritmer, og bruker begge samtidig for å oppnå svært høye kompresjonsforhold. Disse to algoritmene er "LZ77" og "Huffman-koding." Huffman-koding er ganske komplisert, og vi kommer ikke til å gå i detalj på den her. Først og fremst bruker den litt fancy matte til å tildele kortere binære koder til individuelle bokstaver, krympende filstørrelser i prosessen. Hvis du vil lære mer om det, sjekk ut denne artikkelen om hvordan koden fungerer, eller dette forklarer av Computerphile.
LZ77, derimot, er relativt enkelt og er hva vi snakker om her. Det søker å fjerne dupliserte ord og erstatte dem med en mindre "nøkkel" som representerer ordet.
Ta dette korte teksten til for eksempel:
LZ77-algoritmen ville se på denne teksten, innse at den gjentar "howtogeek" tre ganger, og endre den til dette:
Da, når den vil lese teksten tilbake, vil den erstatte alle forekomster av (h) med "howtogeek", og bringe oss tilbake til den opprinnelige setningen.
Vi kaller kompresjon som denne "lossless" -dataene du legger inn er det samme som dataene du kommer ut. Ingenting er tapt.
I virkeligheten bruker LZ77 ikke en liste over nøkler, men erstatter i stedet den andre og tredje forekomsten med en link tilbake i minnet:
Så nå, når det kommer til (h), vil det se tilbake til "howtogeek" og lese det i stedet.
Hvis du er interessert i en mer detaljert forklaring, er denne videoen fra Computerphile ganske nyttig.
Nå er dette et idealisert eksempel. I virkeligheten er mest tekst komprimert med taster så små som bare noen få tegn. For eksempel vil ordet "the" bli komprimert, selv når det vises i ord som "der", "deres" og "da." Med gjentatt tekst kan du få noen sprø kompresjonsforhold. Ta denne tekstfilen med ordet "howtogeek" gjentatt 100 ganger. Den opprinnelige tekstfilen er tre kilobytes i størrelse. Når komprimert, tar det bare opp 158 byte. Det er nesten 95% komprimering.
Nå er det åpenbart et ganske ekstremt eksempel siden vi bare hadde samme ord gjentatt om og om igjen. I vanlig praksis får du sannsynligvis 30-40% komprimering ved hjelp av et komprimeringsformat som ZIP på en fil som mest er tekst.
Denne LZ77-algoritmen gjelder for alle binære data, forresten, og ikke bare tekst, men tekst er generelt lettere å komprimere på grunn av hvor mange gjentatte ord de fleste språk bruker. Et språk som kinesisk kan være litt vanskeligere å komprimere enn engelsk, for eksempel.
Hvordan fungerer bilde- og videokomprimering?
Video- og lydkomprimering fungerer veldig annerledes. I motsetning til tekst der du kan ha lossless komprimering, og ingen data går tapt, med bilder har vi det som kalles "Lossy Compression" hvor du mister noen data. Og jo mer du komprimerer, jo flere data du mister.
Dette er det som fører til de fryktelige utseende JPEGene som folk har lastet opp, delt og skjermdumpet flere ganger. Hver gang bildet blir komprimert, mister det noen data.
Her er et eksempel. Dette er et skjermbilde jeg tok som ikke har blitt komprimert i det hele tatt.
Jeg tok det skjermbildet og kjørte det gjennom Photoshop flere ganger, hver gang jeg eksporterte det som en lavkvalitets JPEG. Her er resultatet.
Ser ganske dårlig ut, ikke sant?
Vel, dette er bare et worst case scenario, eksporterer med 0% JPEG kvalitet hver gang. Til sammenligning, her er en 50% kvalitets JPEG, som nesten ikke skiller seg fra kilde PNG-bildet, med mindre du blåser det opp og tar en nærmere titt.
PNG for dette bildet var 200 KB i størrelse, men denne 50% kvalitets JPEG er bare 28 KB.
Så hvordan sparer det så mye plass? Vel, JPEG-algoritmen er en teknikk. De fleste bilder lagrer en liste med tall, med hvert tall som representerer en enkelt piksel.
JPEG gjør ingen av dette. I stedet lagrer den bilder ved hjelp av noe som kalles en diskret kosinettransform, som er en samling av sinusbølger lagt sammen i varierende intensiteter. Den bruker 64 forskjellige ligninger, men de fleste av disse blir ikke brukt. Dette er hva kvalitetsskyven for JPEG i Photoshop og andre bildeapp gjør - velg hvor mange likninger du skal bruke. Appene bruker deretter Huffman-koding for å redusere filstørrelsen enda lenger.
Dette gir JPEGer et sinnsykt høyt kompresjonsforhold, noe som kan redusere en fil som vil være flere megabyte ned til et par kilobytes, avhengig av kvaliteten. Selvfølgelig, hvis du bruker det for mye, slutter du med dette:
Det bildet er fryktelig. Men mindre mengder JPEG-komprimering kan ha betydelig innvirkning på filstørrelsen, og dette gjør JPEG veldig nyttig for bildekomprimering på nettsteder. De fleste bildene du ser på nettet, blir komprimert for å lagre nedlastingstider, spesielt for mobile brukere med dårlige datatilkoblinger. Faktisk er alle bildene på How-To Geek komprimert for å gjøre siden lastes raskere, og du har sannsynligvis aldri lagt merke til.
Videokomprimering
Video fungerer litt annerledes enn bilder. Du tror at de bare ville komprimere hver ramme med video ved hjelp av JPEG, og de gjør det sikkert, men det er en bedre metode for video.
Vi bruker noe som heter "interframe-komprimering", som beregner endringene mellom hver ramme og bare lagrer dem. Så hvis du for eksempel har et relativt stille bilde som tar opp flere sekunder i en video, blir mye plass lagret fordi komprimeringsalgoritmen ikke trenger å lagre alle ting i scenen som ikke endres. Interramkomprimering er hovedårsaken til at vi har digital tv og nettvideo i det hele tatt. Uten det ville videoene være hundrevis av gigabyte, mer enn den gjennomsnittlige harddiskstørrelsen i 2005 da YouTube startet.
Også siden interframekomprimering fungerer best med det meste stasjonær video, er det derfor konfetti ødelegger videokvaliteten.
Merk: GIF gjør ikke dette, og derfor er animerte GIF ofte svært korte og små, men har fortsatt en ganske stor filstørrelse.
En annen ting å huske på video er bitrate-mengden data tillatt i hvert sekund. Hvis bitraten din er 200 kb / s, vil videoen din se ganske dårlig ut. Kvaliteten går opp ettersom bithastigheten går opp, men etter et par megabyte per sekund får du avtagende avkastning.
Dette er en zoomet ramme tatt fra en video av en maneter. Den til venstre er 3Mb / s, og den til høyre er 100Mb / s.
En 30x økning i filstørrelse, men ikke mye økning i kvalitet. Vanligvis er YouTube-videoer sitte rundt 2-10Mb / s avhengig av tilkoblingen din, som noe mer sannsynligvis ikke ville bli lagt merke til.
Denne demoen virker bedre med den faktiske videoen, så hvis du vil sjekke det selv, kan du laste ned de samme bitrate testvideoene som brukes her.
Lydkomprimering
Lydkomprimering fungerer på samme måte som tekst og bildekomprimering. Hvor JPEG fjerner detaljene fra et bilde som du ikke vil se, gjør lydkomprimering det samme for lyder. Du trenger kanskje ikke å høre gitarspissen på strengen hvis den faktiske gitaren er mye, mye høyere.
MP3 bruker også bithastighet, fra den lave enden på 48 og 96 kbps (den lave enden) til 128 og 240kbps (ganske bra) til 320kbps (high-end lyd), og du vil sannsynligvis bare høre forskjellen med svært gode hodetelefoner ( og ører).
Det er også lossless komprimeringskodinger for lyd-den viktigste er FLAC-som bruker LZ77-koding for å levere helt tabellsløs lyd. Noen sverger ved FLACs perfekte lydkvalitet, men med forekomsten av MP3 ser det ut til at folk flest ikke kan fortelle eller ikke bry seg om forskjellen.