Kuidas andmete kadudeta pakkimine töötab | Ajakiri Quanta

Kuna Internetis liigub iga päev rohkem kui 9 miljardit gigabaiti teavet, otsivad teadlased pidevalt uusi viise andmete tihendamiseks väiksemateks pakettideks. Tipptasemel tehnikad keskenduvad kadudeta lähenemisviisidele, mis saavutavad tihendamise, teadlikult "kaotades" edastusest pärinevat teavet. Näiteks Google avalikustas hiljuti kadudega strateegia, kus saatev arvuti viskab pildilt üksikasju ja vastuvõttev arvuti kasutab puuduvate osade ära arvamiseks tehisintellekti. Isegi Netflix kasutab kadudeta lähenemist, vähendades video kvaliteeti alati, kui ettevõte tuvastab, et kasutaja vaatab madala eraldusvõimega seadmes.

Seevastu väga vähe uuritakse praegu kadudeta strateegiaid, kus ülekandeid muudetakse väiksemaks, kuid sisu ei ohverdata. Põhjus? Kadudeta lähenemisviisid on juba märkimisväärselt tõhusad. Need toidavad kõike alates JPEG-pildistandardist kuni kõikjal kasutatava tarkvarautiliidi PKZip-ni. Ja see kõik on tänu magistrandile, kes lihtsalt otsis väljapääsu raskest lõpueksamist.

Seitsekümmend aastat tagasi pakkus Massachusettsi Tehnoloogiainstituudi professor Robert Fano oma teabeteooriatunnis õpilastele valikut: tehke traditsiooniline lõpueksam või täiustage juhtivat andmete tihendamise algoritmi. Fano võis oma õpilasi teavitada, aga võib-olla mitte, et ta oli selle olemasoleva algoritmi autor või et ta oli aastaid jahtinud selle parandamist. Mida me teame, on see, et Fano pakkus oma õpilastele järgmist väljakutset.

Mõelge sõnumile, mis koosneb tähtedest, numbritest ja kirjavahemärkidest. Lihtne viis sellise sõnumi kodeerimiseks oleks määrata igale tähemärgile kordumatu kahendnumber. Näiteks võib arvuti tähistada A-tähte kui 01000001 ja hüüumärki kui 00100001. Selle tulemuseks on koodid, mida on lihtne sõeluda – iga kaheksa numbrit või bitti vastab ühele kordumatule märgile –, kuid kohutavalt ebaefektiivne, sest sama number Kahendnumbrit kasutatakse nii tavaliste kui ka ebatavaliste kirjete jaoks. Parem lähenemine oleks midagi morsekoodi sarnast, kus sagedast E-tähte tähistab vaid üks punkt, samas kui vähem levinud Q nõuab pikemat ja töömahukamat kriips-kriips-punkt-kriips.

Kuid ka morsekood on ebaefektiivne. Muidugi, mõned koodid on lühikesed ja teised pikad. Kuid kuna koodi pikkused on erinevad, ei saa morsekoodi sõnumeid mõista, kui need ei sisalda lühikesi vaikuseperioode iga märgi edastamise vahel. Tõepoolest, ilma nende kulukate pausideta ei oleks adressaatidel mingit võimalust eristada Morse sõnumit kriips punkt-kriips-punkt täpp-punkt kriipspunkt (“triit”) kriipspunktist punkt-kriips-punkt punkt-punkt-kriipspunkt (“tõene” ).

Fano oli selle osa probleemist lahendanud. Ta mõistis, et saab kasutada erineva pikkusega koode ilma kulukaid tühikuid vajamata, kui ta ei kasuta kunagi sama numbrimustrit nii täieliku koodi kui ka teise koodi algusena. Näiteks kui S-täht oli konkreetses sõnumis nii levinud, et Fano määras sellele ülilühikese koodi 01, siis ei kodeerita selles sõnumis ühtegi teist tähte, mis algab 01-ga; koodid nagu 010, 011 või 0101 oleksid kõik keelatud. Selle tulemusel sai kodeeritud sõnumit lugeda vasakult paremale, ilma igasuguse kahemõttelisuseta. Näiteks kui tähele S on määratud 01, tähele A on määratud 000, tähele M on omistatud 001 ja tähele L on määratud 1, saab äkitselt sõnumi 0100100011 kohe tõlkida sõnaks "väike", kuigi L on tähistatud ühega. numbrit, S kahekohalist ja ülejäänud tähti kolm.

Koodide tegelikuks määramiseks ehitas Fano kahendpuud, asetades iga vajaliku tähe visuaalse haru lõppu. Seejärel määrati iga tähe kood ülalt alla teega. Kui tee hargnes vasakule, lisas Fano 0; Paremad oksad said 1. Puu struktuur tegi Fanol nende soovimatute kattumiste vältimise lihtsaks: kui Fano puusse tähe asetas, lõppes see haru, mis tähendab, et ükski tulevane kood ei saa alata samamoodi.

Et otsustada, millised tähed kuhu lähevad, oleks Fano võinud ammendavalt katsetada kõiki võimalikke mustreid maksimaalse efektiivsuse saavutamiseks, kuid see oleks olnud ebapraktiline. Selle asemel töötas ta välja ligikaudse lähenemisviisi: iga sõnumi jaoks korraldas ta asjakohased tähed sageduse järgi ja määras seejärel tähed harudele nii, et mis tahes harupaari vasakpoolseid tähti kasutati sõnumis ligikaudu sama palju kordi kui sõnumis. tähed paremal. Nii satuksid sageli kasutatavad märgid lühematele ja vähem tihedatele okstele. Väike arv kõrgsageduslikke tähti tasakaalustaks alati suurema arvu madalama sagedusega tähti.

Tulemuseks oli märkimisväärselt tõhus kompressioon. Kuid see oli vaid ligikaudne; pidi olema parem tihendusstrateegia. Nii esitas Fano oma õpilastele väljakutse see üles leida.

Fano oli oma puud ehitanud ladvast alla, säilitades võimalikult palju sümmeetriat paarisharude vahel. Tema õpilane David Huffman pööras protsessi pea peale, ehitades sama tüüpi puid, kuid alt üles. Huffmani arusaam oli, et mis iganes muu ka ei juhtuks, peaksid tõhusas koodis kahel kõige vähem levinud märgil olema kaks kõige pikemat koodi. Nii tuvastas Huffman kaks kõige vähem levinud tegelast, rühmitas need hargneva paarina ja kordas seejärel protsessi, otsides seekord kahte kõige vähem levinud kirjet ülejäänud tegelaste ja äsja loodud paari hulgast.

Mõelge sõnumile, kus Fano lähenemine kõigub. Kooliruumis kuvatakse O neli korda ja S/C/H/L/R/M üks kord. Fano tasakaalustamisviis algab O-tähe ja ühe teise tähe määramisega vasakpoolsele harule, kusjuures nende tähtede viis kogukasutust tasakaalustavad ülejäänud tähtede viis välimust. Saadud sõnum nõuab 27 bitti.

Seevastu Huffman alustab kahe ebatavalise tähega - näiteks R ja M - ning rühmitab need kokku, käsitledes paari kui ühte tähte.

Seejärel pakub tema uuendatud sagedustabel talle nelja valikut: O, mis ilmub neli korda, uus kombineeritud RM-sõlm, mida funktsionaalselt kasutatakse kaks korda, ja üksikud tähed S, C, H ja L. Huffman valib taas kaks kõige vähem levinud valikut, sobitades (öelge) H koos L-ga.

Tabelit värskendatakse uuesti: O kaal on endiselt 4, RM ja HL on nüüd mõlema kaal 2 ning tähed S ja C on eraldiseisvad. Huffman jätkab sealt, igas etapis rühmitades kaks kõige vähem sagedast valikut ja seejärel värskendades nii puud kui ka sagedustabelit.

Lõppkokkuvõttes muutub „kooliruum” numbriks 11101111110000110110000101, mis kaotab Fano ülalt-alla lähenemisviisi.

Üks tükk ei pruugi tunduda palju, kuid isegi väikesed säästud kasvavad tohutult, kui seda suurendatakse miljardite gigabaitide võrra.

Tõepoolest, Huffmani lähenemine on osutunud nii võimsaks, et tänapäeval kasutab peaaegu iga kadudeta tihendusstrateegia täielikult või osaliselt Huffmani ülevaadet. Kas vajate Wordi dokumendi tihendamiseks PKZipi? Esimene samm hõlmab veel ühte nutikat strateegiat korduste tuvastamiseks ja seeläbi sõnumi suuruse tihendamiseks, kuid teine ​​samm on saadud tihendatud sõnumi võtmine ja selle läbi Huffmani protsess. Kas salvestada pilt JPEG-vormingus? Teie arvuti tõlgib esmalt pildi tekstipõhiseks esituseks ja seejärel jällegi kasutab selle teksti tihendamiseks Huffmani kodeeringut.

Pole paha projekti kohta, mis oli algselt ajendatud kraadiõppuri soovist lõpueksam vahele jätta.