Hur förlustfri datakomprimering fungerar | Quanta Magazine

Med mer än 9 miljarder gigabyte information som reser på internet varje dag, letar forskare ständigt efter nya sätt att komprimera data till mindre paket. Banbrytande tekniker fokuserar på förlustbaserade tillvägagångssätt, som uppnår komprimering genom att avsiktligt "förlora" information från en överföring. Google, till exempel, avslöjade nyligen en förluststrategi där den sändande datorn tappar detaljer från en bild och den mottagande datorn använder artificiell intelligens för att gissa de saknade delarna. Till och med Netflix använder en förluststrategi, och nedgraderar videokvaliteten närhelst företaget upptäcker att en användare tittar på en lågupplöst enhet.

Mycket lite forskning, däremot, bedrivs för närvarande på förlustfria strategier, där överföringar görs mindre, men ingen substans offras. Anledningen? Förlustfria tillvägagångssätt är redan anmärkningsvärt effektiva. De driver allt från JPEG-bildstandarden till det allestädes närvarande programvaruverktyget PKZip. Och allt beror på en doktorand som helt enkelt letade efter en väg ut ur ett tufft slutprov.

För sjuttio år sedan erbjöd en professor vid Massachusetts Institute of Technology vid namn Robert Fano eleverna i sin informationsteoriklass ett val: Gör ett traditionellt slutprov eller förbättra en ledande algoritm för datakomprimering. Fano kanske eller kanske inte har informerat sina elever om att han var en författare till den befintliga algoritmen, eller att han hade letat efter en förbättring i flera år. Vad vi vet är att Fano erbjöd sina elever följande utmaning.

Tänk på ett meddelande som består av bokstäver, siffror och skiljetecken. Ett enkelt sätt att koda ett sådant meddelande skulle vara att tilldela varje tecken ett unikt binärt nummer. Till exempel kan en dator representera bokstaven A som 01000001 och ett utropstecken som 00100001. Detta resulterar i koder som är lätta att tolka - var åttonde siffra, eller bitar, motsvarar ett unikt tecken - men fruktansvärt ineffektivt, eftersom samma nummer binära siffror används för både vanliga och ovanliga poster. Ett bättre tillvägagångssätt skulle vara något som morsekod, där den vanliga bokstaven E representeras av bara en enda punkt, medan det mindre vanliga Q kräver det längre och mer mödosamma streck-streck-prick-streck.

Ändå är morsekod också ineffektivt. Visst, vissa koder är korta och andra är långa. Men eftersom kodlängder varierar kan meddelanden i morsekod inte förstås om de inte innehåller korta perioder av tystnad mellan varje teckenöverföring. Utan dessa kostsamma pauser skulle mottagarna faktiskt inte ha något sätt att skilja Morse-meddelandet streck prick-streck-prick prick-prick streck-prick ("bant") från streck prick-streck-prick prick-prick-streck prick ("true" ).

Fano hade löst den här delen av problemet. Han insåg att han kunde använda koder av varierande längd utan att behöva kostsamma utrymmen, så länge han aldrig använde samma mönster av siffror som både en komplett kod och början på en annan kod. Till exempel, om bokstaven S var så vanlig i ett visst meddelande att Fano tilldelade den den extremt korta koden 01, så skulle ingen annan bokstav i meddelandet kodas med något som började 01; Koder som 010, 011 eller 0101 skulle alla vara förbjudna. Som ett resultat kunde det kodade meddelandet läsas från vänster till höger, utan någon tvetydighet. Till exempel, med bokstaven S tilldelad 01, bokstaven A tilldelad 000, bokstaven M tilldelad 001 och bokstaven L tilldelad 1, kan plötsligt meddelandet 0100100011 omedelbart översättas till ordet "liten" även om L representeras av en siffra, S med två siffror och de andra bokstäverna med tre vardera.

För att faktiskt bestämma koderna byggde Fano binära träd och placerade varje nödvändig bokstav i slutet av en visuell gren. Varje bokstavs kod definierades sedan av sökvägen från topp till botten. Om banan förgrenade sig till vänster, lade Fano till en 0; höger grenar fick en 1. Trädstrukturen gjorde det enkelt för Fano att undvika dessa oönskade överlappningar: När Fano väl placerat en bokstav i trädet skulle den grenen sluta, vilket betyder att ingen framtida kod kunde börja på samma sätt.

För att bestämma vilka bokstäver som skulle gå vart kunde Fano ha uttömmande testat alla möjliga mönster för maximal effektivitet, men det hade varit opraktiskt. Så istället utvecklade han en uppskattning: För varje meddelande skulle han organisera de relevanta bokstäverna efter frekvens och sedan tilldela bokstäver till grenar så att bokstäverna till vänster i ett givet grenpar användes i meddelandet ungefär lika många gånger som bokstäver till höger. På så sätt skulle ofta använda tecken hamna på kortare, mindre täta grenar. Ett litet antal högfrekventa bokstäver skulle alltid balansera ut ett större antal lägre frekvenser.

Resultatet var anmärkningsvärt effektiv kompression. Men det var bara en uppskattning; en bättre kompressionsstrategi måste finnas. Så Fano utmanade sina elever att hitta den.

Fano hade byggt sina träd uppifrån och ner och bibehållit så mycket symmetri som möjligt mellan parade grenar. Hans elev David Huffman vände processen på huvudet och byggde samma typer av träd men från botten och upp. Huffmans insikt var att, vad som än händer, i en effektiv kod borde de två minst vanliga tecknen ha de två längsta koderna. Så Huffman identifierade de två minst vanliga karaktärerna, grupperade dem som ett förgrenat par och upprepade sedan processen, denna gång letade han efter de två minst vanliga posterna bland de återstående karaktärerna och paret han just byggt.

Tänk på ett meddelande där Fanos synsätt vacklar. I "skolrummet" visas O fyra gånger och S/C/H/L/R/M vardera en gång. Fanos balanseringsmetod börjar med att tilldela O och en annan bokstav till den vänstra grenen, med de fem totala användningarna av dessa bokstäver som balanserar ut de fem utseendena på de återstående bokstäverna. Det resulterande meddelandet kräver 27 bitar.

Huffman, däremot, börjar med två av de ovanliga bokstäverna - säg R och M - och grupperar dem och behandlar paret som en enda bokstav.

Hans uppdaterade frekvensdiagram erbjuder honom sedan fyra val: O som visas fyra gånger, den nya kombinerade RM-noden som funktionellt används två gånger, och de enskilda bokstäverna S, C, H och L. Huffman väljer återigen de två minst vanliga alternativen, matchande (säg) H med L.

Diagrammet uppdateras igen: O har fortfarande vikten 4, RM och HL har nu vardera vikten 2, och bokstäverna S och C står ensamma. Huffman fortsätter därifrån och grupperar i varje steg de två minst frekventa alternativen och uppdaterar sedan både trädet och frekvensdiagrammet.

I slutändan blir "skolrum" 11101111110000110110000101, vilket rakar bort Fanos uppifrån-och-ned-metoden en bit.

En bit kanske inte låter så mycket, men även små besparingar växer enormt när de skalas med miljarder gigabyte.

Huffmans tillvägagångssätt har faktiskt visat sig vara så kraftfullt att i dag använder nästan varje förlustfri komprimeringsstrategi Huffmans insikt helt eller delvis. Behöver du PKZip för att komprimera ett Word-dokument? Det första steget innebär ännu en smart strategi för att identifiera upprepning och därigenom komprimera meddelandestorlek, men det andra steget är att ta det resulterande komprimerade meddelandet och köra det genom Huffman-processen. Lagra en bild som en JPEG? Din dator översätter först bilden till en textbaserad representation och använder sedan återigen Huffman-kodning för att komprimera den texten.

Inte illa för ett projekt som ursprungligen motiverades av en doktorands önskan att hoppa över ett slutprov.