Slik fungerer datakomprimering uten tap | Quanta Magazine

Med mer enn 9 milliarder gigabyte med informasjon som reiser på internett hver dag, leter forskere stadig etter nye måter å komprimere data til mindre pakker. Nyskapende teknikker fokuserer på tapsbaserte tilnærminger, som oppnår komprimering ved å "miste" informasjon fra en overføring med vilje. Google, for eksempel, avduket nylig en tapsbasert strategi der den avsendende datamaskinen slipper detaljer fra et bilde og mottakerdatamaskinen bruker kunstig intelligens for å gjette de manglende delene. Selv Netflix bruker en tapsbasert tilnærming, og nedgraderer videokvaliteten hver gang selskapet oppdager at en bruker ser på en enhet med lav oppløsning.

Svært lite forskning, derimot, forfølges for tiden på tapsfrie strategier, der overføringer gjøres mindre, men ingen substans blir ofret. Grunnen? Tapsfrie tilnærminger er allerede bemerkelsesverdig effektive. De driver alt fra JPEG-bildestandarden til det allestedsnærværende programvareverktøyet PKZip. Og alt er på grunn av en hovedfagsstudent som rett og slett lette etter en vei ut av en tøff avsluttende eksamen.

For XNUMX år siden tilbød en professor ved Massachusetts Institute of Technology ved navn Robert Fano studentene i informasjonsteoriklassen sin et valg: Ta en tradisjonell avsluttende eksamen, eller forbedre en ledende algoritme for datakomprimering. Fano kan ha informert studentene sine om at han var forfatter av den eksisterende algoritmen, eller at han hadde jaktet på en forbedring i årevis. Det vi vet er at Fano tilbød elevene sine følgende utfordring.

Tenk på en melding som består av bokstaver, tall og tegnsetting. En enkel måte å kode en slik melding på er å tildele hvert tegn et unikt binært tall. For eksempel kan en datamaskin representere bokstaven A som 01000001 og et utropstegn som 00100001. Dette resulterer i koder som er enkle å analysere - hvert åttende siffer, eller bit, tilsvarer ett unikt tegn - men fryktelig ineffektivt, fordi det samme tallet av binære sifre brukes for både vanlige og uvanlige oppføringer. En bedre tilnærming ville være noe sånt som morsekode, der den hyppige bokstaven E er representert med bare en enkelt prikk, mens den mindre vanlige Q krever lengre og mer arbeidskrevende bindestrek-punktstrek-punktstrek.

Likevel er morsekoden også ineffektiv. Jada, noen koder er korte og andre er lange. Men fordi kodelengdene varierer, kan ikke meldinger i morsekode forstås med mindre de inkluderer korte perioder med stillhet mellom hver tegnoverføring. Faktisk, uten disse kostbare pausene, ville mottakere ikke ha noen mulighet til å skille Morse-meldingen dash dot-dash-dot dot-dot dash dot (“bantlig”) fra dash dot-dash-dot dot-dot-dash dot (“true” ).

Fano hadde løst denne delen av problemet. Han innså at han kunne bruke koder av varierende lengde uten å trenge kostbare plass, så lenge han aldri brukte det samme mønsteret av sifre som både en komplett kode og starten på en annen kode. For eksempel, hvis bokstaven S var så vanlig i en bestemt melding at Fano tildelte den den ekstremt korte koden 01, ville ingen annen bokstav i den meldingen være kodet med noe som startet 01; Koder som 010, 011 eller 0101 vil alle være forbudt. Som et resultat kunne den kodede meldingen leses fra venstre til høyre, uten noen tvetydighet. For eksempel, med bokstaven S tildelt 01, bokstaven A tildelt 000, bokstaven M tildelt 001, og bokstaven L tildelt 1, kan plutselig meldingen 0100100011 umiddelbart oversettes til ordet "liten", selv om L er representert med en siffer, S med to sifre, og de andre bokstavene med tre hver.

For faktisk å bestemme kodene, bygde Fano binære trær, og plasserte hver nødvendig bokstav på slutten av en visuell gren. Hver bokstavs kode ble deretter definert av banen fra topp til bunn. Hvis banen forgrenet seg til venstre, la Fano til en 0; høyre grener fikk 1. Trestrukturen gjorde det enkelt for Fano å unngå de uønskede overlappingene: Når Fano plasserte en bokstav i treet, ville den grenen ende, noe som betyr at ingen fremtidig kode kunne begynne på samme måte.

For å bestemme hvilke bokstaver som skulle gå hvor, kunne Fano ha uttømmende testet alle mulige mønstre for maksimal effektivitet, men det ville vært upraktisk. Så i stedet utviklet han en tilnærming: For hver melding ville han organisere de relevante bokstavene etter frekvens og deretter tilordne bokstaver til grener slik at bokstavene til venstre i et gitt grenpar ble brukt i meldingen omtrent like mange ganger som bokstaver til høyre. På denne måten ville ofte brukte tegn havne på kortere, mindre tette grener. Et lite antall høyfrekvente bokstaver vil alltid balansere ut et større antall laverefrekvente bokstaver.

Resultatet var bemerkelsesverdig effektiv kompresjon. Men det var bare en tilnærming; en bedre kompresjonsstrategi måtte eksistere. Så Fano utfordret elevene sine til å finne den.

Fano hadde bygget sine trær fra toppen og ned, og opprettholdt så mye symmetri som mulig mellom sammenkoblede grener. Eleven hans David Huffman snudde prosessen på hodet, og bygde de samme typer trær, men fra bunnen og opp. Huffmans innsikt var at uansett hva annet som skjer, i en effektiv kode bør de to minst vanlige tegnene ha de to lengste kodene. Så Huffman identifiserte de to minst vanlige karakterene, grupperte dem sammen som et forgreningspar, og gjentok deretter prosessen, denne gangen på jakt etter de to minst vanlige oppføringene blant de gjenværende karakterene og paret han nettopp hadde bygget.

Tenk på en melding der Fano-tilnærmingen vakler. I «skolerommet» vises O fire ganger, og S/C/H/L/R/M hver vises én gang. Fanos balanserende tilnærming starter med å tilordne O og en annen bokstav til venstre gren, med de fem totale brukene av disse bokstavene som balanserer ut de fem utseendet til de resterende bokstavene. Den resulterende meldingen krever 27 biter.

Huffman, derimot, starter med to av de uvanlige bokstavene - for eksempel R og M - og grupperer dem sammen, og behandler paret som en enkelt bokstav.

Hans oppdaterte frekvensdiagram gir ham da fire valg: O som vises fire ganger, den nye kombinerte RM-noden som funksjonelt brukes to ganger, og enkeltbokstavene S, C, H og L. Huffman velger igjen de to minst vanlige alternativene, og matcher (si) H med L.

Kartet oppdateres igjen: O har fortsatt en vekt på 4, RM og HL har nå hver vekt på 2, og bokstavene S og C står alene. Huffman fortsetter derfra, i hvert trinn grupperer de to minst hyppige alternativene og oppdaterer deretter både treet og frekvensdiagrammet.

Til syvende og sist blir «skolerom» 11101111110000110110000101, noe som barberer Fano ovenfra og ned-tilnærmingen litt.

En bit høres kanskje ikke så mye ut, men selv små besparelser vokser enormt når de skaleres med milliarder av gigabyte.

Faktisk har Huffmans tilnærming vist seg å være så kraftig at i dag bruker nesten hver tapsfri komprimeringsstrategi Huffman-innsikten helt eller delvis. Trenger du PKZip for å komprimere et Word-dokument? Det første trinnet innebærer enda en smart strategi for å identifisere gjentakelse og dermed komprimere meldingsstørrelse, men det andre trinnet er å ta den resulterende komprimerte meldingen og kjøre den gjennom Huffman-prosessen. Lagre et bilde som en JPEG? Datamaskinen din oversetter først bildet til en tekstbasert representasjon og bruker deretter igjen Huffman-koding for å komprimere den teksten.

Ikke verst for et prosjekt som opprinnelig var motivert av en avgangsstudents ønske om å hoppe over en avsluttende eksamen.