> shannon | fano | entropie <
// Shannon-Fano – Top-down-Entropiecodierung für Datenkompression
Entropiebasiert
Verwendet Informationstheorie, um effiziente Codes mit variabler Länge zu erzeugen.
Top-down-Verfahren
Teilt Symbole rekursiv in Gruppen mit ähnlicher Wahrscheinlichkeit.
Historischer Algorithmus
Frühes Verfahren, das moderne Kompressionsmethoden beeinflusst hat.
>> technische infos
Wie Shannon-Fano funktioniert:
Bei der Shannon-Fano-Codierung werden Symbole nach Häufigkeit sortiert und dann rekursiv in zwei Mengen mit möglichst ähnlicher Gesamtwahrscheinlichkeit geteilt. Jeder Split fügt dem Code ein Bit hinzu (0 links, 1 rechts). Das Ergebnis ist ein präfixfreier Code mit variabler Länge.
Kodierprozess:
Text: "AAABBCD" Häufigkeiten: A:3, B:2, C:1, D:1 Aufteilung: [A] | [B,C,D] Codes: A: 0 B: 10 C: 110 D: 111 Kodiert: 0 0 0 10 10 110 111
Warum Shannon-Fano verwenden:
- >Einfach zu implementieren
- >Gute Kompressionsraten
- >Historisch wichtig
- >Didaktischer Wert
- >Präfixfreie Codes
>> häufig gestellte fragen
Was ist die Shannon-Fano-Codierung?
Die Shannon-Fano-Codierung ist ein Entropie-Codierungsverfahren, das in den 1940er Jahren von Claude Shannon und Robert Fano entwickelt wurde. Es war eines der ersten Verfahren, das Codes variabler Länge anhand von Symbolwahrscheinlichkeiten erzeugt.
Shannon-Fano vs. Huffman?
Beide erzeugen Codes mit variabler Länge, aber Huffman ist optimal und liefert die kürzeste mittlere Codelänge. Shannon-Fano ist einfacher, kann aber etwas längere Codes erzeugen. Huffman arbeitet von unten nach oben, Shannon-Fano von oben nach unten.
Wie funktioniert die Aufteilung?
Die Symbole werden nach Häufigkeit sortiert und dann in zwei Gruppen mit möglichst ähnlicher Gesamtwahrscheinlichkeit geteilt. Dieser Prozess wiederholt sich rekursiv, bis jede Gruppe nur noch ein Symbol enthält.
Wird Shannon-Fano heute noch verwendet?
Shannon-Fano hat heute vor allem historischen und didaktischen Wert. In der Praxis wurde es weitgehend von der Huffman-Codierung abgelöst, weil diese optimale Codewörter garantiert. Dennoch bleibt Shannon-Fano wichtig, um Kompressionskonzepte zu erklären.
// Durchgerechnetes Beispiel
| Symbol | Freq | Code | Bits |
|---|---|---|---|
| A | 15 | 00 | 2 |
| B | 7 | 01 | 2 |
| C | 6 | 10 | 2 |
| D | 6 | 110 | 3 |
| E | 5 | 111 | 3 |
// Codebeispiele
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
>> Weitere Fragen
F: Worin unterscheidet sich Shannon-Fano von Huffman?
A: Shannon-Fano teilt die sortierte Symbolliste von oben nach unten in zwei möglichst gleich häufige Hälften, Huffman baut den Baum von unten nach oben durch Zusammenfassen der seltensten Symbole. Huffman ist nachweislich optimal, Shannon-Fano nicht immer.
F: Ist Shannon-Fano immer optimal?
A: Nein. Im Beispiel braucht Shannon-Fano 89 Bit, Huffman nur 87. Beide erzeugen präfixfreie Codes, aber die Teilungsregel von Shannon-Fano kann ungünstige Aufteilungen wählen.
F: Wo wird Shannon-Fano verwendet?
A: Hauptsächlich als historisches und didaktisches Verfahren (Claude Shannon und Robert Fano, 1948/49). Eine Variante steckt im IMPLODE-Algorithmus des ZIP-Formats; moderne Kompressoren nutzen Huffman oder arithmetische Kodierung.