> shannon | fano | entropi <
// Shannon-Fano – Top-down-entropikoding for datakompresjon
Entropibasert
Bruker informasjonsteori til å lage effektive koder med variabel lengde.
Top-down-tilnærming
Deler symboler rekursivt i grupper med lignende sannsynlighet.
Historisk algoritme
Banebrytende metode som har påvirket moderne komprimeringsteknikker.
>> teknisk informasjon
Hvordan Shannon-Fano fungerer:
Shannon-Fano-koding sorterer symboler etter frekvens og deler dem rekursivt i to grupper med så lik total sannsynlighet som mulig. Hver deling legger til ett bit i koden (0 til venstre, 1 til høyre). Resultatet er en prefikskode med variabel lengde.
Kodeprosess:
Tekst: "AAABBCD" Frekvenser: A:3, B:2, C:1, D:1 Oppdeling: [A] | [B,C,D] Koder: A: 0 B: 10 C: 110 D: 111 Kodet: 0 0 0 10 10 110 111
Hvorfor bruke Shannon-Fano:
- >Enkel å implementere
- >God komprimeringsgrad
- >Historisk betydning
- >Nyttig i undervisning
- >Prefikskoder
>> vanlige spørsmål
Hva er Shannon-Fano-koding?
Shannon-Fano-koding er en entropikodingsteknikk utviklet på 1940-tallet av Claude Shannon og Robert Fano. Det var en av de første algoritmene som brukte koder med variabel lengde basert på sannsynligheten til symbolene.
Shannon-Fano eller Huffman?
Begge produserer koder med variabel lengde, men Huffman er optimal og gir kortest mulig gjennomsnittlig kodelengde. Shannon-Fano er enklere, men kan gi noe lengre koder. Huffman bygger treet nedenfra og opp, Shannon-Fano ovenfra og ned.
Hvordan fungerer oppdelingen av symboler?
Symbolene sorteres etter frekvens og deles i to grupper med så lik total sannsynlighet som mulig. Prosessen gjentas rekursivt til hver gruppe bare inneholder ett symbol.
Brukes Shannon-Fano fortsatt?
Shannon-Fano brukes i dag hovedsakelig som et historisk og pedagogisk eksempel. I praksis er det stort sett erstattet av Huffman-koding, som gir optimale koder. Det er likevel nyttig for å forstå grunnleggende komprimeringskonsepter.
// Gjennomregnet eksempel
| Symbol | Freq | Code | Bits |
|---|---|---|---|
| A | 15 | 00 | 2 |
| B | 7 | 01 | 2 |
| C | 6 | 10 | 2 |
| D | 6 | 110 | 3 |
| E | 5 | 111 | 3 |
// Kodeeksempler
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
>> Flere spørsmål
S: Hvordan skiller Shannon-Fano seg fra Huffman?
S: Shannon-Fano deler den sorterte listen ovenfra og ned i to halvdeler med så lik frekvenssum som mulig; Huffman bygger treet nedenfra ved å slå sammen de sjeldneste symbolene. Huffman er bevist optimal, Shannon-Fano ikke alltid.
S: Er Shannon-Fano alltid optimal?
S: Nei. I eksempelet trenger den 89 bit mot Huffmans 87. Begge gir prefiksfrie koder, men Shannon-Fanos delingsregel kan velge ugunstige snitt.
S: Hvor brukes Shannon-Fano?
S: Særlig som historisk og pedagogisk metode (Claude Shannon og Robert Fano, 1948/49). En variant finnes i IMPLODE-algoritmen i ZIP; moderne kompressorer bruker Huffman eller aritmetisk koding.