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