Kako deluje stiskanje podatkov brez izgube | Revija Quanta

Ker vsak dan po internetu potuje več kot 9 milijard gigabajtov informacij, raziskovalci nenehno iščejo nove načine za stiskanje podatkov v manjše pakete. Najsodobnejše tehnike se osredotočajo na pristope z izgubo, ki dosežejo stiskanje z namerno "izgubo" informacij iz prenosa. Google je na primer nedavno razkril strategijo z izgubo, pri kateri računalnik pošiljatelj izpusti podrobnosti iz slike, računalnik prejemnik pa uporablja umetno inteligenco, da ugane manjkajoče dele. Celo Netflix uporablja pristop z izgubo in zniža kakovost videa, kadar koli podjetje zazna, da uporabnik gleda na napravi z nizko ločljivostjo.

Nasprotno pa se trenutno izvaja zelo malo raziskav o strategijah brez izgub, kjer so prenosi manjši, vendar se ne žrtvuje nobena snov. Razlog? Pristopi brez izgub so že izjemno učinkoviti. Poganjajo vse od slikovnega standarda JPEG do vseprisotnega programskega pripomočka PKZip. In vse to zaradi podiplomskega študenta, ki je preprosto iskal izhod iz težkega zaključnega izpita.

Pred sedemdesetimi leti je profesor na Tehnološkem inštitutu v Massachusettsu po imenu Robert Fano študentom v svojem razredu informacijske teorije ponudil izbiro: opraviti tradicionalni zaključni izpit ali izboljšati vodilni algoritem za stiskanje podatkov. Fano je lahko ali pa tudi ne obvestil svoje učence, da je avtor tega obstoječega algoritma ali da že leta išče izboljšavo. Vemo pa, da je Fano svojim študentom ponudil naslednji izziv.

Razmislite o sporočilu, sestavljenem iz črk, številk in ločil. Enostaven način kodiranja takega sporočila bi bil, da bi vsakemu znaku dodelili edinstveno binarno število. Na primer, računalnik lahko črko A predstavi kot 01000001 in klicaj kot 00100001. Posledica tega so kode, ki jih je enostavno razčleniti – vsakih osem števk ali bitov ustreza enemu unikatnemu znaku – vendar so strašno neučinkovite, ker je isto število binarnih števk se uporablja za običajne in občasne vnose. Boljši pristop bi bil nekaj podobnega Morsejevi abecedi, kjer je pogosta črka E predstavljena samo z eno samo piko, medtem ko manj običajna Q zahteva daljši in zahtevnejši pomišljaj-pomišljaj-pika-pomišljaj.

Vendar pa je tudi Morsejeva abeceda neučinkovita. Seveda so nekatere kode kratke, druge pa dolge. Ker pa se dolžine kod razlikujejo, sporočil v Morsejevi abecedi ni mogoče razumeti, razen če vključujejo kratka obdobja tišine med vsakim prenosom znakov. Dejansko brez teh dragih premorov prejemniki ne bi mogli ločiti Morsejevega sporočila pomišljaj pika-pomišljaj-pika pomišljaj pika (»trite«) od pomišljaja pika-pomišljaj-pika pika-pika-pomišljaj pika (»true« ).

Fano je rešil ta del problema. Spoznal je, da lahko uporablja kode različnih dolžin, ne da bi potreboval drage presledke, če nikoli ne uporabi istega vzorca števk kot popolno kodo in začetek druge kode. Na primer, če je bila črka S v določenem sporočilu tako pogosta, da ji je Fano dodelil izjemno kratko kodo 01, potem nobena druga črka v tem sporočilu ne bi bila kodirana z ničemer, kar se je začelo 01; kode, kot so 010, 011 ali 0101, bi bile vse prepovedane. Posledično je bilo kodirano sporočilo mogoče brati od leve proti desni, brez kakršne koli dvoumnosti. Na primer, s črko S dodeljeno 01, črko A dodeljeno 000, črko M dodeljeno 001 in črko L dodeljeno 1, lahko sporočilo 0100100011 nenadoma takoj prevedemo v besedo "majhen", čeprav je L predstavljen z eno števko, S z dvema števkama, ostale črke pa po tri.

Da bi dejansko določil kode, je Fano zgradil binarna drevesa in vsako potrebno črko postavil na konec vizualne veje. Koda vsake črke je bila nato definirana s potjo od zgoraj navzdol. Če se je pot odcepila v levo, je Fano dodal 0; desne veje so dobile 1. Drevesna struktura je Fanu olajšala izogibanje tem nezaželenim prekrivanjem: ko je Fano postavil črko v drevo, bi se ta veja končala, kar pomeni, da se nobena prihodnja koda ne bi mogla začeti na enak način.

Da bi se odločil, katere črke bodo kje, bi lahko Fano izčrpno preizkusil vse možne vzorce za največjo učinkovitost, vendar bi bilo to nepraktično. Namesto tega je razvil približek: za vsako sporočilo bi ustrezne črke organiziral po pogostosti in nato črke dodelil vejam, tako da so bile črke na levi v katerem koli danem paru vej uporabljene v sporočilu približno enako število krat kot črke na desni. Na ta način bi pogosto uporabljeni znaki končali na krajših, manj gostih vejah. Majhno število visokofrekvenčnih črk bi vedno uravnotežilo neko večje število nižjefrekvenčnih.

Rezultat je bila izjemno učinkovita kompresija. A bil je le približek; obstajati je morala boljša strategija stiskanja. Zato je Fano izzval svoje študente, naj ga najdejo.

Fano je svoja drevesa zgradil od vrha navzdol, pri čemer je ohranil čim večjo simetrijo med vejami v paru. Njegov študent David Huffman je obrnil proces na glavo in zgradil iste vrste dreves, vendar od spodaj navzgor. Huffmanov vpogled je bil, da bi morala imeti v učinkoviti kodi dva najmanj pogosta znaka dve najdaljši kodi, karkoli se že zgodi. Tako je Huffman identificiral dva najmanj pogosta znaka, ju združil kot razvejani par in nato ponovil postopek, tokrat pa iskal dva najmanj pogosta vnosa med preostalimi znaki in parom, ki ga je pravkar zgradil.

Razmislite o sporočilu, kjer pristop Fano zataji. V »šolski sobi« se O pojavi štirikrat, S/C/H/L/R/M pa po enkrat. Fanov pristop k uravnoteženju se začne z dodelitvijo O in ene druge črke levi veji, pri čemer pet skupnih uporab teh črk uravnoteži pet pojavov preostalih črk. Nastalo sporočilo zahteva 27 bitov.

Nasprotno pa Huffman začne z dvema neobičajnima črkama - recimo R in M ​​- in ju združi skupaj, tako da par obravnava kot eno črko.

Njegov posodobljen frekvenčni diagram mu nato ponudi štiri možnosti: O, ki se pojavi štirikrat, novo kombinirano vozlišče RM, ki se funkcionalno uporablja dvakrat, in posamezne črke S, C, H in L. Huffman ponovno izbere dve najmanj pogosti možnosti, ki se ujemata (recimo) H z L.

Grafikon se znova posodobi: O ima še vedno težo 4, RM in HL imata zdaj vsak težo 2, črki S in C pa sta samostojni. Huffman nadaljuje od tam, pri čemer v vsakem koraku združi dve najmanj pogosti možnosti in nato posodobi drevo in frekvenčni grafikon.

Navsezadnje "šolarka" postane 11101111110000110110000101, s čimer se nekoliko zmanjša Fanov pristop od zgoraj navzdol.

En košček morda ne zveni veliko, vendar se celo majhni prihranki izjemno povečajo, če jih povečamo na milijarde gigabajtov.

Dejansko se je Huffmanov pristop izkazal za tako močnega, da danes skoraj vsaka strategija stiskanja brez izgube v celoti ali delno uporablja Huffmanov vpogled. Potrebujete PKZip za stiskanje Wordovega dokumenta? Prvi korak vključuje še eno pametno strategijo za prepoznavanje ponavljanja in s tem stiskanje velikosti sporočila, drugi korak pa je vzeti nastalo stisnjeno sporočilo in ga izvesti skozi Huffmanov proces. Shraniti sliko kot JPEG? Vaš računalnik najprej prevede sliko v predstavitev, ki temelji na besedilu, nato pa ponovno uporabi Huffmanovo kodiranje za stiskanje tega besedila.

Ni slabo za projekt, ki ga je prvotno motivirala želja podiplomskega študenta, da bi preskočil zaključni izpit.