Wie der Beweis für Hoffman Algorithmus Gieriges Eigentum beginnt mit einem optimalen Baum T?

Question

in dieses Papier Anspruch 1 gibt an, dass x und y kleinste Wahrscheinlichkeit und es ist ein optimaler Codebaum, in dem diese zwei Zeichen Geschwister in der maximalen Tiefe sind .Im Beweis für diesen Anspruch beginnt der Autor mit dem Baum t , das c in der maximalen Tiefe des Baumes aufweist.Ich kann nicht verstehen, warum der Baum t optimal genannt wird, denn wenn x kleinste Wahrscheinlichkeiten aufweist, kann der Baum T nicht optimal sein, weil Hoffman nicht optimal istAlgorithmus baut keinen solchen Baum auf.Ich denke, mein Problem hier ist mit dem Verständnis, was ein optimaler Baum bedeutet.

Wenn jemand von CSLR kommt, geht es um Lemma 16.2 und den Beweis dafür.

Answer 1

Eine Codebaum ist optimal wenn die durchschnittliche Codewortlänge minimal ist. Das hat nichts mit Huffman-Algorithmus zu tun. Huffmans Algorithmus erzeugt garantiert einen optimalen Codebaum, aber es gibt andere Codebäume. Tatsächlich könnte der Huffmans Algorithmus unterschiedliche Codebäume mit unterschiedlichen Verbindungsregeln herstellen. Darüber hinaus kann nicht jeder optimale Codebaum mit Huffmansalgorithmus, selbst mit einer beliebigen anschließenden Regelung, hergestellt werden.

Hier ist eine formale Definition eines optimalen Codebaums. Lassen Sie $ \ pi $ eine Verteilung sein. Der $ \ pi $ -cost eines Codebaums ist die erwartete Länge eines Codeworts, in dem die Erwartung in Bezug auf $ \ pi $ . Ein Codebaum ist optimal für $ \ pi $ wenn der $ \ pi $ -cost ist gleich dem Minimum $ \ pi $ -Kost eines Codebaums.