Shannon-Fano-algoritmi

Shannon-Fanó-algoritmi on yksi ensimmäisistä pakkausalgoritmeista, jonka ensimmäisenä muotoilivat amerikkalaiset tutkijat Claude Shannon ja Robert Fano . Tämä pakkausmenetelmä on hyvin samanlainen kuin muutama vuosi myöhemmin ilmestynyt Huffman-algoritmi , joka on looginen jatko Shannon-algoritmille . Algoritmi käyttää vaihtelevan pituisia koodeja: usein esiintyvä merkki koodataan lyhyemmällä koodilla ja harvoin esiintyvä merkki pitemmällä koodilla. Shannon-Fano-koodit ovat etuliitekoodeja, eli mikään koodisana ei ole minkään muun etuliite . Tämä ominaisuus mahdollistaa minkä tahansa koodisanojen sekvenssin yksiselitteisen purkamisen.

Perustiedot

Shannon -Fano -  koodaus on etuliite epäyhtenäinen koodausalgoritmi. Viittaa todennäköisyyspohjaisiin pakkausmenetelmiin (tarkemmin sanottuna nollan asteen kontekstuaalisiin mallinnusmenetelmiin ). Kuten Huffman-algoritmi , Shannon-Fano-algoritmi käyttää viestin redundanssia, joka johtuu sen ( ensisijaisen ) aakkosten merkkien epäyhtenäisestä taajuusjakaumasta , eli se korvaa useammin esiintyvien merkkien koodit lyhyillä binäärisillä. sekvenssit ja harvinaisempien merkkien koodit pidemmillä binäärisekvensseillä.

Algoritmin kehitti itsenäisesti Shannon (julkaistu "Mathematical Theory of Communication", 1948) ja myöhemmin Fano (julkaistu teknisenä raporttina).

Virstanpylväät

1. Ensisijaisten aakkosten m 1 symbolit on kirjoitettu todennäköisyyksien mukaan laskevassa järjestyksessä.
2. Tuloksena saadun aakkoston symbolit on jaettu kahteen osaan, joiden symbolien kokonaistodennäköisyydet ovat mahdollisimman lähellä toisiaan.
3. Etuliitteen koodissa binäärinumero "0" on määritetty aakkosten ensimmäiselle osalle ja "1" toiselle osalle.
4. Tuloksena olevat osat jaetaan rekursiivisesti ja niiden osille osoitetaan vastaavat binäärinumerot etuliitekoodissa.

Kun alaaakkosen kooksi tulee nolla tai yksi, ei ensisijaisen aakkoston vastaavien merkkien etuliitekoodia laajenneta enempää, joten algoritmi antaa eripituisia etuliitekoodeja eri merkeille. Aakkosten jakamisvaiheessa on epäselvyyttä, koska ero kokonaistodennäköisyyksien välillä voi olla sama kahdella jakovaihtoehdolla (ottaen huomioon, että ensisijaisen aakkoston kaikkien merkkien todennäköisyys on suurempi kuin nolla).

Algoritmi Shannon-Fano-koodien laskemiseen

Shannon-Fano-koodi on rakennettu puusta. Tämän puun rakentaminen alkaa juuresta. Koko koodattujen elementtien joukko vastaa puun juuria (ensimmäisen tason yläosaa). Se on jaettu kahteen osajoukkoon, joilla on suunnilleen samat kokonaistodennäköisyydet. Nämä osajoukot vastaavat kahta toisen tason kärkeä, jotka on kytketty juureen. Lisäksi kukin näistä osajoukoista on jaettu kahteen osajoukkoon, joilla on suunnilleen samat kokonaistodennäköisyydet. Ne vastaavat kolmannen tason huippuja. Jos osajoukko sisältää yhden elementin, se vastaa koodipuun loppusolmua; tällaista osajoukkoa ei voida osioida. Jatketaan tällä tavalla, kunnes saamme kaikki päätypisteet. Merkitsemme koodipuun oksat symboleilla 1 ja 0, kuten Huffman-koodin tapauksessa.

Shannon-Fano-koodia rakennettaessa elementtijoukko voidaan jakaa yleisesti ottaen useilla tavoilla. Jakamisen valinta tasolla n voi huonontaa jakovaihtoehtoja seuraavalla tasolla (n + 1) ja johtaa epäoptimaaliseen koodiin kokonaisuutena. Toisin sanoen optimaalinen käyttäytyminen polun jokaisessa vaiheessa ei vielä takaa koko toimintosarjan optimaalisuutta. Siksi Shannon-Fano-koodi ei ole optimaalinen yleisessä mielessä, vaikka se antaa optimaaliset tulokset tietyillä todennäköisyysjakaumilla. Samaan todennäköisyysjakaumaan voidaan yleensä rakentaa useita Shannon-Fano-koodeja, ja ne kaikki voivat antaa erilaisia ​​tuloksia. Jos rakennamme kaikki mahdolliset Shannon-Fano-koodit tietylle todennäköisyysjakaumalle, niin niiden joukossa on kaikki Huffman-koodit, eli optimaaliset koodit.

Esimerkki koodipuusta

Lähdehahmot:

• A (esiintymistiheys 50)
• B (esiintymistiheys 39)
• C (esiintymistiheys 18)
• D (esiintymistiheys 49)
• E (esiintymistiheys 35)
• F (esiintymistiheys 24)

Vastaanotettu koodi: A - 11, B - 101, C - 100, D - 00, E - 011, F - 010.

Shannon-Fano-koodaus on melko vanha pakkausmenetelmä, ja nykyään sillä ei ole juurikaan käytännön merkitystä. Useimmissa tapauksissa tällä menetelmällä pakatun sekvenssin pituus on yhtä suuri kuin Huffman-koodausta käyttävän kompressoidun sekvenssin pituus. Mutta joissakin sekvensseissä voidaan muodostaa ei-optimaalisia Shannon-Fano-koodeja, joten Huffman-menetelmää pidetään tehokkaampana.

Kirjallisuus

• A. M. Yaglom , I. M. Yaglom . Todennäköisyys ja tieto. - M.: Nauka, 1973.