Zur MathePrisma-Startseite
Zur Modul-Startseite  


Gierige Methoden (Huffman-Codes 3)
 
 
 
Huffman macht's richtig
 
 Auf den folgenden Seiten wird begründet, weshalb der Algorithmus von Huffman tatsächlich einen Codierungsbaum T mit minimalem L(T) berechnet. Entsprechend der im Kapitel Allgemein formulierten Prinzipien stellen wir dabei besonders die Eigenschaft der gierigen Wahl und die der optimalen Teilstruktur heraus.
 
neue Begriffe
 
  • L(T) heißt (gewichtete) externe Pfadlänge von T.
  • Einen Codierungsbaum T mit minimalem L(T) nennen wir optimal.
 
keiner oder zwei
 
 Zu einem Text kann es mehrere verschiedene optimale Codierungsbäume geben. Eines haben aber alle gemeinsam:
  • In einem optimalen Codierungsbaum gibt es keinen Knoten, der genau einen Sohn hat.
 
Begründung dazu
(bewege die Maus auf das Bild)
 

Gäbe es einen Knoten mit nur einem Sohn, so könnte man aus T durch 'Hochschieben' einen neuen Codierungsbaum mit kleinerer gewichteter externer Pfadlänge erzeugen. Dies kann nicht sein, denn T ist optimal.

 
Um wieviel verringert sich beim Hochschieben des Teilbaums die gewichtete externe Pfadlänge L(T)? 
Um 1
Um die gewichtete externe Pfadlänge des verschobenen Teilbaums
Um die Anzahl der Blattknoten im verschobenenTeilbaum
Um die Summe der Häufigkeiten h(z) für alle Zeichen z im verschobenen Teilbaum
 
 
 
Seite 8/10