Shannon-Fano kód je jednou z důležitých metod komprese dat, která se používá ke snížení jejich objemu bez ztráty informací. Tento algoritmus vyvinuli v roce 1948 americký matematik Claude Shannon a americký inženýr Robert Fano. Je založen na myšlence rozdělit původní zprávu na dvě části, kde každá část dostane svůj vlastní kód.
Princip fungování Shannon-Fano kódu je následující. Algoritmus nejprve analyzuje původní zprávu a určuje pravděpodobnost, že se každý znak objeví. Symboly jsou pak uspořádány v sestupném pořadí jejich pravděpodobnosti. Vytvoří se seznam, který je rozdělen na dvě části tak, aby součet pravděpodobnosti znaků v každé části byl přibližně stejný.
Pro kódování se používá binární strom, kde každá větev odpovídá symbolu. Větve, které spojují vrcholy stromu, mohou mít hodnotu 0 nebo 1. Hodnota " 0 "se používá pro větve odpovídající symbolům z první části seznamu a hodnota" 1 " pro větve odpovídající symbolům z druhé části seznamu. Každý symbol získá svůj jedinečný kód složený ze sekvence bitů hodnot větví, kterých je dosaženo.
Shannon-Fano kód: obecný koncept, význam a funkce práce
Hlavní myšlenkou Shannon-Fano kódu je, že každý symbol zdrojové zprávy je nahrazen odpovídajícím kódovým slovem, které má proměnnou délku. V tomto případě jsou kódy znaků vybrány tak, aby minimalizovaly průměrnou délku kódového slova a zajistily jednoznačné dekódování.
Jedním z hlavních rysů Shannon-Fano kódu je jeho samostatné přiřazení kódových slov symbolům. Za tímto účelem algoritmus rozděluje mnoho znaků do dvou nepřerušitelných skupin na principu minimálního rozdílu ve výši pravděpodobnosti výskytu znaků. Proces separace se pak opakuje pro každou skupinu, dokud každý znak nebude mít své kódové slovo.
Význam kódu Shannon-Fano spočívá v jeho jednoduchosti a vysoké účinnosti. Umožňuje komprimovat bezztrátová data, to znamená, že obnovení původní zprávy po kompresi probíhá bez chyb. Díky použití proměnné délky kódových slov poskytuje Shannon-Fano kód efektivnější kompresi pro znaky, které jsou běžnější.
| Znak | Pravděpodobnost | Kódové slovo |
|---|---|---|
| A | 0.4 | 0 |
| B | 0.3 | 10 |
| C | 0.2 | 110 |
| D | 0.1 | 111 |
Zvažte například kódování abecedy s pravděpodobnostmi výskytu znaků uvedených v tabulce. Podle pravidel Shannon-Fano kódu rozdělíme kódová slova tak, aby průměrná délka kódových slov byla minimální. V tomto případě bude kódování znaku A mít kódové slovo 0, znak B - 10, Znak C - 110 a znak D - 111. Původní sekvence znaků "ABBACD" by tedy byla kódována jako "100011011111".
Princip fungování Shannon-Fano kódu
Princip fungování kódu Shannon-Fano se skládá z následujících fází:
- Řazení znaků podle snížené frekvence jejich výskytu.
- Rozdělení znaků na dvě části na polovinu tak, aby celková frekvence první části byla přibližně stejná jako součet frekvence druhé části.
- Přiřazení bitu 0 symbolům první části kódu a bitu 1 symbolům druhé části.
- Opakování předchozích kroků pro každou z částí rekurzivním rozdělením znaků na dvě podskupiny, dokud nezůstane jeden znak v podskupině.
Příklad použití Shannon-Fano kódu:
Řekněme, že máme následující sekvenci znaků: A, B, C, D, D, E, E.musíme kódovat každý znak.
1. Znaky seřadíme podle sestupné frekvence výskytu: E (3), D (2), a (1), B (1), C (1).
2. Symboly rozdělíme do dvou skupin: E (3), D (2) a a (1), B (1), C (1).
3. Přiřadíme bit 0 symbolům první skupiny a bit 1 symbolům druhé skupiny: E (0), D (0) a a (1), B (1), C (1).
4. Rekurzivně opakujeme kroky 2 a 3 pro každou ze skupin, dokud nezůstane jeden znak v podskupině.
Výsledkem jsou následující kódy pro každý znak: E (00), D (01), a (100), B (101), C (110).
Nyní můžeme tyto kódy použít ke kompresi a rozbalení dat nahrazením původních znaků jejich kódy a naopak.
Shannon-Fano algoritmus a jeho aplikace
Základní myšlenkou algoritmu je přiřadit kratší kódy symbolům, které se vyskytují častěji, a delší kódy, které jsou méně běžně se vyskytujícími symboly. Za tímto účelem je původní datová sada rozdělena do dvou skupin a poté rekurzivně pokračuje dělení, dokud nebudou všechny znaky zakódovány.
Aplikace Shannon-Fano algoritmu je možná v různých oblastech, kde je vyžadována komprese dat. Algoritmus lze použít například ke kompresi textových dokumentů, obrázků nebo zvukových souborů. Umožňuje snížit objem dat, zmenšit velikost souboru a usnadnit jeho přenos nebo ukládání.
Výhody algoritmu Shannon-Fano jsou snadná implementace a relativně dobrý stupeň komprese. Má však i některé nevýhody, včetně ztráty účinnosti při práci se symboly, které se setkávají s přibližně stejnou frekvencí. Algoritmus také nezaručuje optimální kompresní poměr pro všechny typy dat.
Podrobné vysvětlení principu separace
Prvním krokem při aplikaci principu separace je analýza frekvence výskytu znaků nebo skupin znaků ve zdrojových datech. Čím častěji se konkrétní symbol nebo skupina znaků setkávají, tím méně musí být jejich kód, aby bylo dosaženo efektivnějšího kódování.
Zdrojová data jsou poté rozdělena do dvou skupin a každá skupina obdrží svůj kód. Skupiny jsou vytvořeny tak, aby celková frekvence výskytu znaků v každé skupině byla přibližně stejná nebo přibližně stejná jako polovina celkové frekvence výskytu znaků v původních datech.
Proces separace pokračuje, dokud se každá skupina nebude skládat z jednoho symbolu. Výsledkem jsou kódová slova, která se používají ke kódování zdrojových dat.
Princip separace je základem pro efektivní kompresi dat v kódu Shannon-Fano. Umožňuje minimalizovat délku kódových slov a dosáhnout optimální rovnováhy mezi frekvencí znaků a jejich kódem.
Příklad:
Zvažte sadu zdrojových dat složenou ze znaků A, B, C, D, E s následujícími frekvencemi:
Krok 1: řazení dat podle klesající frekvence výskytu:
Krok 2: Rozdělení na dvě skupiny:
Skupina 1: C, D ,A (frekvence = 15 + 11 + 10 = 36)
Skupina 2: E, B (frekvence = 8 + 5 = 13)
Krok 3: pokračování rozdělení:
Skupina 1: C (frekvence = 15)
Skupina 2: D ,a (frekvence = 11 + 10 = 21)
Skupina 3: E, B (frekvence = 8 + 5 = 13)
Krok 4: Tvorba kódových slov:
V důsledku toho získáme kódová slova pro každý znak zdrojových dat, která lze použít k jejich efektivnímu kódování.