Sådan fungerer tabsfri datakomprimering | Quanta Magasinet

Med mere end 9 milliarder gigabyte information, der rejser på internettet hver dag, leder forskere konstant efter nye måder at komprimere data til mindre pakker. Avancerede teknikker fokuserer på tilgange med tab, som opnår komprimering ved bevidst at "tabe" information fra en transmission. Google, for eksempel, afslørede for nylig en tabsstrategi, hvor den afsendende computer taber detaljer fra et billede, og den modtagende computer bruger kunstig intelligens til at gætte de manglende dele. Selv Netflix bruger en tabsgivende tilgang og nedgraderer videokvaliteten, når virksomheden opdager, at en bruger ser på en enhed med lav opløsning.

Der forfølges derimod meget lidt forskning i tabsfrie strategier, hvor transmissioner gøres mindre, men ingen substans ofres. Grunden? Tabsfri tilgange er allerede bemærkelsesværdigt effektive. De driver alt fra JPEG-billedstandarden til det allestedsnærværende softwareværktøj PKZip. Og det er alt sammen på grund af en kandidatstuderende, der simpelthen ledte efter en vej ud af en hård afsluttende eksamen.

For XNUMX år siden tilbød en professor ved Massachusetts Institute of Technology ved navn Robert Fano eleverne i sin informationsteoriklasse et valg: Tag en traditionel afsluttende eksamen eller forbedre en førende algoritme til datakomprimering. Fano har måske eller måske ikke informeret sine elever om, at han var forfatter til den eksisterende algoritme, eller at han havde ledt efter en forbedring i årevis. Hvad vi ved er, at Fano tilbød sine elever følgende udfordring.

Overvej en besked, der består af bogstaver, tal og tegnsætning. En ligetil måde at kode en sådan besked på ville være at tildele hvert tegn et unikt binært tal. For eksempel kan en computer repræsentere bogstavet A som 01000001 og et udråbstegn som 00100001. Dette resulterer i koder, der er nemme at parse - hvert ottende cifre eller bit svarer til ét unikt tegn - men frygtelig ineffektivt, fordi det samme tal af binære cifre bruges til både almindelige og ualmindelige indtastninger. En bedre tilgang ville være noget i retning af morsekode, hvor det hyppige bogstav E er repræsenteret ved blot en enkelt prik, hvorimod det mindre almindelige Q kræver det længere og mere besværlige bindestreg-streg-punktstreg.

Alligevel er morsekoden også ineffektiv. Selvfølgelig er nogle koder korte, og andre er lange. Men fordi kodelængder varierer, kan beskeder i morsekode ikke forstås, medmindre de inkluderer korte perioder med stilhed mellem hver karaktertransmission. Uden disse dyre pauser ville modtagerne faktisk ikke have nogen mulighed for at skelne Morse-beskeden bindestreg dot-dash-dot dot-dot tankestreg prik ("banal") fra bindestreg dot-dash-dot dot-dot-dash prik ("sand" ).

Fano havde løst denne del af problemet. Han indså, at han kunne bruge koder af varierende længde uden at have brug for dyre pladser, så længe han aldrig brugte det samme mønster af cifre som både en komplet kode og starten på en anden kode. For eksempel, hvis bogstavet S var så almindeligt i en bestemt besked, at Fano tildelte det den ekstremt korte kode 01, så ville intet andet bogstav i den besked være kodet med noget, der startede 01; Koder som 010, 011 eller 0101 ville alle være forbudte. Som et resultat kunne den kodede meddelelse læses fra venstre mod højre uden nogen tvetydighed. For eksempel, med bogstavet S tildelt 01, bogstavet A tildelt 000, bogstavet M tildelt 001 og bogstavet L tildelt 1, kan meddelelsen 0100100011 pludselig oversættes til ordet "lille", selvom L er repræsenteret af en ciffer, S med to cifre, og de andre bogstaver med tre hver.

For faktisk at bestemme koderne byggede Fano binære træer og placerede hvert nødvendigt bogstav for enden af ​​en visuel gren. Hvert bogstavs kode blev derefter defineret af stien fra top til bund. Hvis stien forgrenede sig til venstre, tilføjede Fano et 0; højre grene fik en 1. Træstrukturen gjorde det nemt for Fano at undgå disse uønskede overlapninger: Når Fano placerede et bogstav i træet, ville den gren ende, hvilket betyder, at ingen fremtidig kode kunne begynde på samme måde.

For at afgøre, hvilke bogstaver der ville gå hvorhen, kunne Fano have udtømmende testet alle mulige mønstre for maksimal effektivitet, men det ville have været upraktisk. Så i stedet udviklede han en tilnærmelse: For hver besked ville han organisere de relevante bogstaver efter frekvens og derefter tildele bogstaver til grene, så bogstaverne til venstre i et givet grenpar blev brugt i beskeden nogenlunde det samme antal gange som bogstaver til højre. På denne måde ville ofte brugte tegn ende på kortere, mindre tætte grene. Et lille antal højfrekvente bogstaver vil altid udligne et større antal af lavere frekvenser.

Resultatet var bemærkelsesværdig effektiv kompression. Men det var kun en tilnærmelse; en bedre kompressionsstrategi skulle eksistere. Så Fano udfordrede sine elever til at finde den.

Fano havde bygget sine træer oppefra og ned og bevarede så meget symmetri som muligt mellem parrede grene. Hans elev David Huffman vendte processen på hovedet og byggede de samme typer træer, men fra bunden og op. Huffmans indsigt var, at uanset hvad der ellers sker, i en effektiv kode skulle de to mindst almindelige tegn have de to længste koder. Så Huffman identificerede de to mindst almindelige karakterer, grupperede dem sammen som et forgrenet par og gentog derefter processen, denne gang på udkig efter de to mindst almindelige poster blandt de resterende karakterer og det par, han lige havde bygget.

Overvej et budskab, hvor Fano-tilgangen vakler. I "skolestue" vises O fire gange, og S/C/H/L/R/M vises hver én gang. Fano's balancerende tilgang starter med at tildele O'et og et andet bogstav til venstre gren, hvor de fem samlede anvendelser af disse bogstaver balancerer de fem forekomster af de resterende bogstaver. Den resulterende besked kræver 27 bit.

Huffman, derimod, starter med to af de ualmindelige bogstaver - f.eks. R og M - og grupperer dem sammen og behandler parret som et enkelt bogstav.

Hans opdaterede frekvensdiagram giver ham derefter fire valgmuligheder: O, der vises fire gange, den nye kombinerede RM-knude, der funktionelt bruges to gange, og de enkelte bogstaver S, C, H og L. Huffman vælger igen de to mindst almindelige muligheder, der matcher (sige) H med L.

Diagrammet opdateres igen: O har stadig en vægt på 4, RM og HL har nu hver vægt på 2, og bogstaverne S og C står alene. Huffman fortsætter derfra og grupperer i hvert trin de to mindst hyppige muligheder og opdaterer derefter både træet og frekvensdiagrammet.

I sidste ende bliver "skoleværelse" til 11101111110000110110000101, hvilket barberer Fano top-down tilgangen en smule væk.

En smule lyder måske ikke af meget, men selv små besparelser vokser enormt, når de skaleres med milliarder af gigabyte.

Faktisk har Huffmans tilgang vist sig at være så kraftfuld, at næsten enhver tabsfri komprimeringsstrategi i dag bruger Huffman-indsigten helt eller delvist. Har du brug for PKZip for at komprimere et Word-dokument? Det første trin involverer endnu en smart strategi til at identificere gentagelse og derved komprimere meddelelsesstørrelse, men det andet trin er at tage den resulterende komprimerede meddelelse og køre den gennem Huffman-processen. Vil du gemme et billede som en JPEG? Din computer oversætter først billedet til en tekstbaseret repræsentation og bruger derefter igen Huffman-kodning til at komprimere denne tekst.

Ikke dårligt for et projekt, der oprindeligt var motiveret af en kandidatstuderendes ønske om at springe en afsluttende eksamen over.