> shannon | fano | entropie <
// Shannon-Fano – Top-down-entropiecodering voor gegevenscompressie
Gebaseerd op entropie
Gebruikt informatietheorie om efficiënte codes met variabele lengte te maken.
Top-down-aanpak
Deelt symbolen recursief in groepen met vergelijkbare waarschijnlijkheid.
Historisch algoritme
Pioniersmethode die moderne compressietechnieken heeft beïnvloed.
>> technische informatie
Hoe Shannon-Fano werkt:
Shannon-Fano-codering sorteert symbolen op frequentie en splitst ze vervolgens recursief in twee groepen met zo gelijk mogelijk totale waarschijnlijkheid. Elke splitsing voegt een bit toe aan de code (0 links, 1 rechts). Het resultaat is een prefixcode met variabele lengte.
Coderingsproces:
Tekst: "AAABBCD" Frequenties: A:3, B:2, C:1, D:1 Splitsing: [A] | [B,C,D] Codes: A: 0 B: 10 C: 110 D: 111 Gecodeerd: 0 0 0 10 10 110 111
Waarom Shannon-Fano gebruiken:
- >Eenvoudig te implementeren
- >Goede compressieratio’s
- >Historische relevantie
- >Handig voor educatie
- >Prefixcodes
>> veelgestelde vragen
Wat is Shannon-Fano-codering?
Shannon-Fano-codering is een entropiecoderingstechniek die in de jaren 40 werd ontwikkeld door Claude Shannon en Robert Fano. Het was een van de eerste algoritmen die codes met variabele lengte gebruikte op basis van symboolwaarschijnlijkheid.
Shannon-Fano of Huffman?
Beide produceren codes met variabele lengte, maar Huffman is optimaal en levert de kortste gemiddelde codelengte. Shannon-Fano is eenvoudiger maar kan iets langere codes opleveren. Huffman bouwt de boom van onder naar boven, Shannon-Fano van boven naar beneden.
Hoe werkt het splitsen van symbolen?
Symbolen worden op frequentie gesorteerd en gesplitst in twee groepen met zo vergelijkbaar mogelijke totale waarschijnlijkheid. Dit proces wordt recursief herhaald totdat elke groep slechts één symbool bevat.
Wordt Shannon-Fano nog gebruikt?
Shannon-Fano wordt tegenwoordig vooral gebruikt als historisch en educatief voorbeeld. In de praktijk is het grotendeels vervangen door Huffman-codering, die optimale codes garandeert. Het blijft echter nuttig om de basis van compressie te leren.
// Uitgewerkt voorbeeld
| Symbol | Freq | Code | Bits |
|---|---|---|---|
| A | 15 | 00 | 2 |
| B | 7 | 01 | 2 |
| C | 6 | 10 | 2 |
| D | 6 | 110 | 3 |
| E | 5 | 111 | 3 |
// Codevoorbeelden
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
>> Meer vragen
V: Hoe verschilt Shannon-Fano van Huffman?
A: Shannon-Fano splitst de gesorteerde lijst van boven naar beneden in twee helften met zo gelijk mogelijke frequentie; Huffman bouwt de boom van onder naar boven door de zeldzaamste symbolen samen te voegen. Huffman is bewijsbaar optimaal, Shannon-Fano niet altijd.
V: Is Shannon-Fano altijd optimaal?
A: Nee. In het voorbeeld heeft het 89 bits nodig tegenover 87 bij Huffman. Beide geven prefixvrije codes, maar de splitsregel van Shannon-Fano kan ongunstige sneden kiezen.
V: Waar wordt Shannon-Fano gebruikt?
A: Vooral als historische en didactische methode (Claude Shannon en Robert Fano, 1948/49). Een variant zit in het IMPLODE-algoritme van ZIP; moderne compressors gebruiken Huffman of rekenkundig coderen.