> 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.