Kuinka häviötön tietojen pakkaus toimii | Quanta-lehti

Internetissä liikkuu päivittäin yli 9 miljardia gigatavua tietoa, joten tutkijat etsivät jatkuvasti uusia tapoja pakata dataa pienempiin paketteihin. Huipputekniikat keskittyvät häviöllisiin lähestymistapoihin, jotka saavat aikaan pakkaamisen tarkoituksellisesti "menettämällä" tiedot lähetyksestä. Esimerkiksi Google julkisti äskettäin häviöllisen strategian, jossa lähettävä tietokone pudottaa kuvasta yksityiskohtia ja vastaanottava tietokone arvaa puuttuvat osat tekoälyn avulla. Jopa Netflix käyttää häviöllistä lähestymistapaa ja heikentää videon laatua aina, kun yritys havaitsee, että käyttäjä katselee matalaresoluutioisella laitteella.

Sen sijaan häviöttömistä strategioista, joissa lähetyksiä pienennetään, mutta ainesta ei uhrata, tutkitaan tällä hetkellä hyvin vähän. Syy? Häviöttömät lähestymistavat ovat jo huomattavan tehokkaita. Ne tarjoavat kaiken tehon JPEG-kuvastandardista kaikkialla olevaan ohjelmistoapuohjelmaan PKZip. Ja kaikki johtuu jatko-opiskelijasta, joka vain etsi ulospääsyä vaikeasta loppukokeesta.

Seitsemänkymmentä vuotta sitten Massachusetts Institute of Technologyn professori Robert Fano tarjosi informaatioteoriakurssinsa opiskelijoille vaihtoehtoa: Suorita perinteinen loppukoe tai paranna johtavaa tietojen pakkausalgoritmia. Fano on ehkä ilmoittanut opiskelijoilleen, että hän oli tuon olemassa olevan algoritmin kirjoittaja tai että hän oli etsinyt parannusta vuosia. Tiedämme, että Fano tarjosi oppilailleen seuraavan haasteen.

Ajattele viestiä, joka koostuu kirjaimista, numeroista ja välimerkeistä. Yksinkertainen tapa koodata tällainen viesti olisi määrittää jokaiselle merkille yksilöllinen binäärinumero. Esimerkiksi tietokone saattaa edustaa A-kirjainta 01000001 ja huutomerkkiä 00100001. Tämä johtaa helposti jäsennettäviin koodeihin – joka kahdeksan numeroa tai bittiä vastaa yhtä yksilöllistä merkkiä – mutta hirvittävän tehotonta, koska sama numero Binäärinumeroista käytetään sekä yleisiä että epätavallisia merkintöjä. Parempi lähestymistapa olisi jotain morsekoodin kaltaista, jossa yleistä kirjainta E edustaa vain yksi piste, kun taas vähemmän yleinen Q vaatii pidemmän ja työläämmän viiva-viiva-piste-viiva.

Silti morsekoodi on myös tehoton. Tietysti jotkut koodit ovat lyhyitä ja toiset pitkiä. Mutta koska koodin pituudet vaihtelevat, morsekoodin viestejä ei voida ymmärtää, elleivät ne sisällä lyhyitä hiljaisuusjaksoja kunkin merkin lähetyksen välillä. Ilman näitä kalliita taukoja vastaanottajat eivät todellakaan pysty erottamaan Morsen sanomaa viiva piste-viiva-piste piste-piste katkoviiva ("trite") viiva piste-viiva-piste piste-piste-viiva pisteestä ("tosi" ).

Fano oli ratkaissut tämän osan ongelmasta. Hän tajusi, että hän voisi käyttää eripituisia koodeja ilman kalliita välilyöntejä, kunhan hän ei koskaan käyttänyt samaa numeromallia sekä täydellisenä koodina että toisen koodin alussa. Esimerkiksi, jos S-kirjain oli niin yleinen tietyssä viestissä, että Fano antoi sille erittäin lyhyen koodin 01, silloin mitään muuta kirjainta tässä viestissä ei koodata millään 01-alkuisella kirjaimella; koodit, kuten 010, 011 tai 0101, olisivat kaikki kiellettyjä. Tämän seurauksena koodattu viesti voitiin lukea vasemmalta oikealle ilman epäselvyyttä. Esimerkiksi kun S-kirjaimella on 01, A-kirjaimella on 000, M-kirjaimella on 001 ja L-kirjaimella on 1, yhtäkkiä viesti 0100100011 voidaan kääntää välittömästi sanaksi "pieni", vaikka L:tä edustaa yksi. numero, S kahdella numerolla ja muut kirjaimet kolmella.

Määrittääkseen koodit Fano rakensi binääripuita asettamalla jokaisen tarvittavan kirjaimen visuaalisen haaran loppuun. Kunkin kirjaimen koodi määriteltiin sitten polulla ylhäältä alas. Jos polku haarautui vasemmalle, Fano lisäsi 0; oikeat oksat saivat 1. Puurakenteen ansiosta Fanon oli helppo välttää noita ei-toivottuja päällekkäisyyksiä: Kun Fano asetti kirjaimen puuhun, se oksa päättyi, eli mikään tuleva koodi ei voinut alkaa samalla tavalla.

Päättääkseen, mitkä kirjaimet menevät minne, Fano olisi voinut testata perusteellisesti kaikki mahdolliset mallit maksimaalisen tehokkuuden saavuttamiseksi, mutta se olisi ollut epäkäytännöllistä. Sen sijaan hän kehitti likiarvon: Jokaiselle viestille hän järjesti asiaankuuluvat kirjaimet frekvenssin mukaan ja osoitti sitten kirjaimet haaroihin siten, että minkä tahansa haaraparin vasemmalla olevia kirjaimia käytettiin viestissä suunnilleen yhtä monta kertaa kuin kirjaimet oikealla. Tällä tavalla usein käytetyt merkit päätyisivät lyhyempiin, vähemmän tiheisiin oksiin. Pieni määrä korkeataajuisia kirjaimia tasapainottaisi aina suuremman määrän matalataajuisia kirjaimia.

Tuloksena oli erittäin tehokas puristus. Mutta se oli vain likimääräinen; parempi pakkausstrategia oli olemassa. Joten Fano haastoi oppilaitaan löytämään sen.

Fano oli rakentanut puunsa ylhäältä alas pitäen mahdollisimman paljon symmetriaa parillisten oksien välillä. Hänen oppilaansa David Huffman käänsi prosessin päälaelleen rakentaen samantyyppisiä puita, mutta alhaalta ylöspäin. Huffmanin näkemys oli, että tapahtuipa mitä tahansa, tehokkaassa koodissa kahdella vähiten yleisimmällä merkillä tulisi olla kaksi pisintä koodia. Joten Huffman tunnisti kaksi vähiten yleistä hahmoa, ryhmitti ne yhteen haarautuneiksi pariksi ja toisti sitten prosessin etsien tällä kertaa kahta vähiten yleistä merkintää jäljellä olevien hahmojen ja juuri rakentamansa parin joukosta.

Harkitse viestiä, jossa Fanon lähestymistapa horjuu. Kouluhuoneessa O näkyy neljä kertaa ja S/C/H/L/R/M kukin kerran. Fanon tasapainotustapa alkaa määrittämällä O-kirjain ja yksi muu kirjain vasemmalle haaralle, jolloin näiden kirjainten viisi käyttökertaa tasapainottavat jäljellä olevien kirjainten viisi ulkonäköä. Tuloksena oleva viesti vaatii 27 bittiä.

Huffman sitä vastoin aloittaa kahdella epätavallisella kirjaimella - esimerkiksi R:llä ja M:llä - ja ryhmittelee ne yhteen pitäen paria yhtenä kirjaimena.

Päivitetty taajuuskaavio tarjoaa hänelle neljä vaihtoehtoa: O, joka näkyy neljä kertaa, uusi yhdistetty RM-solmu, jota käytetään toiminnallisesti kahdesti, ja yksittäiset kirjaimet S, C, H ja L. Huffman valitsee jälleen kaksi vähiten yleistä vaihtoehtoa, jotka sopivat yhteen. (sano) H ja L.

Kaavio päivittyy jälleen: O:n paino on edelleen 4, RM:n ja HL:n paino on nyt kumpikin 2, ja kirjaimet S ja C ovat itsenäisiä. Huffman jatkaa sieltä, jokaisessa vaiheessa ryhmittelemällä kaksi vähiten esiintyvää vaihtoehtoa ja päivittämällä sitten sekä puun että taajuuskaavion.

Lopulta "kouluhuoneesta" tulee 11101111110000110110000101, mikä eroaa Fanon ylhäältä alas -lähestymistavasta.

Yksi bitti ei ehkä kuulosta paljolta, mutta pienetkin säästöt kasvavat valtavasti, kun niitä skaalataan miljardeilla gigatavuilla.

Todellakin, Huffmanin lähestymistapa on osoittautunut niin tehokkaaksi, että nykyään lähes jokainen häviötön pakkausstrategia käyttää Huffmanin näkemystä kokonaan tai osittain. Tarvitsetko PKZipin Word-asiakirjan pakkaamiseen? Ensimmäinen vaihe sisältää vielä yhden taitavan strategian toiston tunnistamiseksi ja siten viestin koon pakkaamiseksi, mutta toinen vaihe on ottaa tuloksena oleva pakattu viesti ja suorittaa se Huffman-prosessin läpi. Tallennetaanko kuva JPEG-muodossa? Tietokoneesi kääntää ensin kuvan tekstipohjaiseksi esitykseksi ja käyttää sitten Huffman-koodausta tekstin pakkaamiseen.

Ei huono projektille, jonka alun perin motivoi jatko-opiskelija halu ohittaa loppukoe.