Shannon-Fano algoritmus

Algoritmus Shannon-Fanó je jedním z prvních kompresních algoritmů, který jako první zformulovali američtí vědci Claude Shannon a Robert Fano . Tato metoda komprese je velmi podobná Huffmanovu algoritmu , který se objevil o několik let později a je logickým pokračováním Shannonova algoritmu . Algoritmus používá kódy proměnné délky: často se vyskytující znak je zakódován kódem menší délky a zřídka se vyskytující znak kódem větší délky. Shannon-Fano kódy jsou prefixové kódy, to znamená, že žádné kódové slovo není předponou jiného. Tato vlastnost umožňuje jednoznačně dekódovat jakoukoliv sekvenci kódových slov.

Základní informace

Shannon -Fano kódování je prefixový  nejednotný kódovací algoritmus. Týká se metod pravděpodobnostní komprese (přesněji metod kontextového modelování nultého řádu ). Stejně jako Huffmanův algoritmus využívá i Shannon-Fano algoritmus redundanci zprávy, která spočívá v nerovnoměrném frekvenčním rozložení znaků její ( primární ) abecedy, tedy nahrazuje kódy častějších znaků krátkými binárními sekvence a kódy vzácnějších znaků s delšími binárními sekvencemi.

Algoritmus nezávisle vyvinul Shannon (publikoval „Mathematical Theory of Communication“, 1948) a později Fano (publikoval jako technickou zprávu).

Milníky

1. Symboly primární abecedy m 1 jsou zapsány v sestupném pořadí pravděpodobností.
2. Symboly výsledné abecedy jsou rozděleny na dvě části, jejichž celkové pravděpodobnosti symbolů jsou co nejblíže k sobě.
3. V kódu předpony je binární číslice "0" přiřazena pro první část abecedy a "1" pro druhou část.
4. Výsledné části jsou rekurzivně rozděleny a jejich částem jsou přiřazeny odpovídající binární číslice v kódu předpony.

Když se velikost dílčí abecedy rovná nule nebo jedničce, pak se předponový kód pro odpovídající znaky primární abecedy dále nerozšiřuje, takže algoritmus přiřazuje různým znakům předponové kódy různé délky. V kroku dělení abecedy existuje nejednoznačnost, protože rozdíl v celkových pravděpodobností může být stejný pro dvě možnosti rozdělení (vzhledem k tomu, že všechny znaky primární abecedy mají pravděpodobnost větší než nula).

Algoritmus pro výpočet Shannon-Fano kódů

Kód Shannon-Fano je vytvořen pomocí stromu. Stavba tohoto stromu začíná od kořene. Celá sada zakódovaných prvků odpovídá kořenu stromu (horní část první úrovně). Je rozdělena do dvou podmnožin s přibližně stejnou celkovou pravděpodobností. Tyto podmnožiny odpovídají dvěma vrcholům druhé úrovně, které jsou spojeny s kořenem. Dále je každá z těchto podmnožin rozdělena na dvě podmnožiny s přibližně stejnou celkovou pravděpodobností. Odpovídají vrcholům třetí úrovně. Pokud podmnožina obsahuje jeden prvek, pak odpovídá koncovému uzlu kódového stromu; takovou podmnožinu nelze rozdělit. Takto postupujeme, dokud nezískáme všechny koncové vrcholy. Větve stromu kódů označíme symboly 1 a 0 jako v případě Huffmanova kódu.

Při konstrukci kódu Shannon-Fano může být sada prvků rozdělena, obecně řečeno, několika způsoby. Volba rozdělení na úrovni n může zhoršit možnosti rozdělení na další úrovni (n + 1) a vést k neoptimálnímu kódu jako celku. Jinými slovy, optimální chování na každém kroku cesty ještě nezaručuje optimalitu celého souboru akcí. Proto Shannon-Fano kód není optimální v obecném smyslu, ačkoli dává optimální výsledky za určitých rozdělení pravděpodobnosti. Pro stejné rozdělení pravděpodobnosti lze obecně zkonstruovat několik Shannon-Fano kódů a všechny mohou poskytovat různé výsledky. Pokud postavíme všechny možné Shannon-Fano kódy pro dané rozdělení pravděpodobnosti, pak mezi nimi budou všechny Huffmanovy kódy, tedy optimální kódy.

Příklad stromu kódu

Zdrojové postavy:

• A (četnost výskytu 50)
• B (četnost výskytu 39)
• C (četnost výskytu 18)
• D (četnost výskytu 49)
• E (četnost výskytu 35)
• F (četnost výskytu 24)

Přijatý kód: A - 11, B - 101, C - 100, D - 00, E - 011, F - 010.

Shannon-Fano kódování je poměrně stará metoda komprese a dnes je prakticky málo zajímavá. Ve většině případů je délka sekvence komprimované tímto způsobem rovna délce komprimované sekvence pomocí Huffmanova kódování. Ale na některých sekvencích mohou být vytvořeny neoptimální Shannon-Fano kódy, takže Huffmanova metoda je považována za efektivnější.

Literatura

• A. M. Yaglom , I. M. Yaglom . Pravděpodobnost a informace. — M.: Nauka, 1973.