> shannon | fano | entropi <
// Shannon-Fano – Top-down-entropikodning för datakomprimering
Entropibaserad
Använder informationsteori för att skapa effektiva koder med variabel längd.
Top-down-metod
Delar rekursivt in symboler i grupper med liknande sannolikhet.
Historisk algoritm
Banbrytande metod som påverkat många moderna komprimeringsalgoritmer.
>> teknisk information
Hur Shannon-Fano fungerar:
Shannon-Fano-kodning sorterar symboler efter frekvens och delar dem sedan rekursivt i två grupper med så lika total sannolikhet som möjligt. Varje delning lägger till en bit i koden (0 till vänster, 1 till höger). Resultatet är en prefixkod med variabel längd.
Kodningsprocess:
Text: "AAABBCD" Frekvenser: A:3, B:2, C:1, D:1 Uppdelning: [A] | [B,C,D] Koder: A: 0 B: 10 C: 110 D: 111 Kodat: 0 0 0 10 10 110 111
Varför använda Shannon-Fano:
- >Enkel att implementera
- >Bra komprimeringsgrad
- >Historisk betydelse
- >Pedagogiskt värde
- >Prefixkoder
>> vanliga frågor
Vad är Shannon-Fano-kodning?
Shannon-Fano-kodning är en entropikodningsteknik som utvecklades på 1940-talet av Claude Shannon och Robert Fano. Den var en av de första algoritmerna som använde koder med variabel längd baserade på symbolers sannolikhet.
Shannon-Fano eller Huffman?
Båda skapar koder med variabel längd, men Huffman är optimal och ger kortast möjliga genomsnittlig kodelängd. Shannon-Fano är enklare men kan ge något längre koder. Huffman bygger trädet nerifrån och upp, Shannon-Fano uppifrån och ner.
Hur fungerar uppdelningen av symboler?
Symbolerna sorteras efter frekvens och delas upp i två grupper med så lik total sannolikhet som möjligt. Processen upprepas rekursivt tills varje grupp bara innehåller en symbol.
Används Shannon-Fano fortfarande?
Shannon-Fano används idag mest som historiskt och pedagogiskt exempel. I praktiken har det till stor del ersatts av Huffman-kodning, som garanterar optimala koder. Det är ändå värdefullt för att förstå grunderna i komprimering.
// Genomgånget exempel
| Symbol | Freq | Code | Bits |
|---|---|---|---|
| A | 15 | 00 | 2 |
| B | 7 | 01 | 2 |
| C | 6 | 10 | 2 |
| D | 6 | 110 | 3 |
| E | 5 | 111 | 3 |
// Kodexempel
Frequencies A=15 B=7 C=6 D=6 E=5 (39 symbols)
1. Sort symbols by frequency (descending).
2. Split the list where the two halves' totals are closest:
{A,B}=22 | {C,D,E}=17 -> first bit 0 / 1
3. Recurse on each half until single symbols remain:
{A}|{B} -> 00, 01 {C}|{D,E} -> 10, 11.. then {D}|{E} -> 110, 111
Total 15*2 + 7*2 + 6*2 + 6*3 + 5*3 = 89 bits
Huffman on the same data: A=1 bit, others 3 bits -> 87 bits
>> Fler frågor
F: Hur skiljer sig Shannon-Fano från Huffman?
S: Shannon-Fano delar den sorterade listan uppifrån och ned i två halvor med så lika frekvenssumma som möjligt; Huffman bygger trädet nedifrån genom att slå ihop de ovanligaste symbolerna. Huffman är bevisat optimal, Shannon-Fano inte alltid.
F: Är Shannon-Fano alltid optimal?
S: Nej. I exemplet krävs 89 bitar mot Huffmans 87. Båda ger prefixfria koder, men Shannon-Fanos delningsregel kan välja ogynnsamma snitt.
F: Var används Shannon-Fano?
S: Främst som historisk och pedagogisk metod (Claude Shannon och Robert Fano, 1948/49). En variant finns i IMPLODE-algoritmen i ZIP; moderna kompressorer använder Huffman eller aritmetisk kodning.