> shannon | fano | entropi <
// Shannon-Fano – Top-down entropikodning til datakomprimering
Entropibaseret
Bruger informationsteori til at skabe effektive koder med variabel længde.
Top-down tilgang
Deler symboler rekursivt i grupper med lignende sandsynlighed.
Historisk algoritme
Banebrydende metode, der har påvirket moderne komprimeringsteknikker.
>> tekniske detaljer
Sådan fungerer Shannon-Fano:
Shannon-Fano-kodning sorterer symboler efter frekvens og deler dem derefter rekursivt i to grupper med så ens samlet sandsynlighed som muligt. Hver opdeling tilføjer et bit til koden (0 til venstre, 1 til højre). Resultatet er en præfiks-kode med variabel længde.
Kodningsproces:
Tekst: "AAABBCD" Frekvenser: A:3, B:2, C:1, D:1 Opdeling: [A] | [B,C,D] Koder: A: 0 B: 10 C: 110 D: 111 Kodet: 0 0 0 10 10 110 111
Hvorfor bruge Shannon-Fano:
- >Let at implementere
- >Gode komprimeringsforhold
- >Historisk betydning
- >God til undervisning
- >Præfiks-koder
>> ofte stillede spørgsmål
Hvad er Shannon-Fano-kodning?
Shannon-Fano-kodning er en entropikodningsteknik udviklet i 1940’erne af Claude Shannon og Robert Fano. Det var en af de første algoritmer, der brugte koder med variabel længde baseret på symbolers sandsynlighed.
Shannon-Fano vs. Huffman?
Begge producerer koder med variabel længde, men Huffman er optimal og giver den korteste gennemsnitlige kodelængde. Shannon-Fano er enklere, men kan give en smule længere koder. Huffman bygger træet nedefra og op, Shannon-Fano oppefra og ned.
Hvordan fungerer opdelingen af symboler?
Symbolerne sorteres efter frekvens og deles i to grupper med så ens samlet sandsynlighed som muligt. Processen gentages rekursivt, indtil hver gruppe kun indeholder ét symbol.
Bliver Shannon-Fano stadig brugt?
Shannon-Fano bruges i dag primært som historisk og pædagogisk eksempel. I praksis er det stort set afløst af Huffman-kodning, som garanterer optimale koder. Det er stadig nyttigt til at forstå grundlæggende komprimeringsprincipper.
// Gennemregnet 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ørgsmål
S: Hvordan adskiller Shannon-Fano sig fra Huffman?
S: Shannon-Fano deler den sorterede liste oppefra og ned i to halvdele med så lige frekvenssum som muligt; Huffman bygger træet nedefra ved at slå de sjældneste symboler sammen. Huffman er bevist optimal, Shannon-Fano ikke altid.
S: Er Shannon-Fano altid optimal?
S: Nej. I eksemplet kræver den 89 bit mod Huffmans 87. Begge giver præfiksfri koder, men Shannon-Fanos delingsregel kan vælge ugunstige snit.
S: Hvor bruges Shannon-Fano?
S: Især som historisk og pædagogisk metode (Claude Shannon og Robert Fano, 1948/49). En variant findes i IMPLODE-algoritmen i ZIP; moderne kompressorer bruger Huffman eller aritmetisk kodning.