Huffman Codierung

[tobias]

Hallo

auf dieser Seite (http://www.iti.fh-flensburg.de/lang/algorithmen/code/huffman/huffman.htm) wird die Huffman Codierung eigentlich gut erklärt aber ich verstehe nicht wieso die Reihenfolge gerade so dargestellt ist:

emwchunit-s

Wiso nicht nach Häufigkeit sortiert?
Und nach welchen Kriterien wird der Baum gebaut damit sich die Kanten nicht überschneiden. Kann mir das jemand erklären?

mfg Tobias (http://www.tubias.de)

[DarkTom]

Ganz einfach, er wusste schon, wie der Baum aussieht, und hat die Reihenfolge so gewählt, dass er keine Positionen mehr vertauschen muss, um am Ende den Baum schön (d.h. ohne Überschneidungen) hingemalt zu haben. Die einzigen Bedingungen bei der Konstruktion des Baumes sind die auf der Seite genannten.

[tobias]

Hallo

ah ja. Wäre interessant wie man das programmtechnisch lösen könnte wenn man den Baum zeichnen wollte.

mfg Tobias (http://www.tubias.de)

[DarkTom]

Ist es ernsthaft ein Problem für dich, einen Baum zu zeichnen?

[eViL_oNe]

Hallo

ah ja. Wäre interessant wie man das programmtechnisch lösen könnte wenn man den Baum zeichnen wollte.

mfg Tobias (http://www.tubias.de)

hat jetzt nicht viel mit Huffman-Codierung zu tun, aber sicherlich interessant. Ich vermute aber, dass das Problem NP-vollständig ist

[DarkTom]

OMG.

Baumkonstruktion in O(n log n),
Baum malen in O(n). Von wegen NP-vollständig...

Muss ich euch wirklich Baum-Mal-Code für einen Binären Baum raussuchen?

[Jan Krüger]

Liegt es nicht in der Natur der Sache, dass Huffman-Bäume tendenziell unbalanciert sind? Ich glaube irgendwie eher an O(n²) im allgemeinen Fall.

[Mr.Homm]

Liegt es nicht in der Natur der Sache, dass Huffman-Bäume tendenziell unbalanciert sind? Ich glaube irgendwie eher an O(n²) im allgemeinen Fall.
Nur wenn der Baum unbalanciert ist, kann mit Huffman Platz gespart werden. Bei nicht komprimierbaren Signalen ist der Baum ausgeglichen.

[eViL_oNe]

OMG.

Baumkonstruktion in O(n log n),
Baum malen in O(n). Von wegen NP-vollständig...

Muss ich euch wirklich Baum-Mal-Code für einen Binären Baum raussuchen?

wer redet denn von einem simplen Baum-Malen? Ich meinte, die Optimierung der Baumkanten resp. möglichst wenigen Überschneidungen

[Scavi]

wer redet denn von einem simplen Baum-Malen? Ich meinte, die Optimierung der Baumkanten resp. möglichst wenigen Überschneidungen Häh? Na das ist doch auch nicht weiter kompliziert. Vorallem: was für Überschneidungen? Je breiter ein Baum wird, desto breiter muss du ihn halt malen.

[DarkTom]

Liegt es nicht in der Natur der Sache, dass Huffman-Bäume tendenziell unbalanciert sind? Ich glaube irgendwie eher an O(n²) im allgemeinen Fall.Geht es um das Aufbauen? Du baust den ja "von unten" auf, indem du immer die Wurzeln von zwei Bäumen im Wald an eine neue gemeinsame Wurzel hängst. Dafür brauchst du n-1 Schritte. Die beiden gewählten Bäume sind die, mit dem geringsten Wert. Das lässt sich z.B. mit einem MinHeap in O(log n) realisieren. (Genauer: O(1) für das Entnehmen der beiden Bäume, O(log n) für das Einfügen des neu entstandenen). Insgesamt O(n log n)

Das Zeichnen des ganzen Baumes mit n Blättern, also 2n-1 Knoten und 2n-2 Kanten in O(n).


wer redet denn von einem simplen Baum-Malen? Ich meinte, die Optimierung der Baumkanten resp. möglichst wenigen ÜberschneidungenDu meinst also, die optimale Anordnung der Buchstaben zu finden, so dass sich die Kanten nicht überschneiden? Das war aber doch schon beantwortet. Dazu konstruiere ich erst den Baum, traversiere ihn und lasse mir dabei die besuchten Blätter der Reihe nach ausgeben. Oder salopp formuliert Baum-Basteln, Baum-Malen, Ablesen.
Deshalb hatte ich tobias Frage eher auf das tatsächliche Zeichnen bezogen.

[eViL_oNe]

vielleicht war ich gestern schon zu überarbeitet *g*

traversieren == Durchlaufen des Baums (etwa mit Visitor)?

[DarkTom]

traversieren == Durchlaufen des Baums (etwa mit Visitor)?Ja.

[tobias]

Ja, hatte das zeichnen auf den "Bildschirm" gemeint. Bei dem oben angegebenen Link sind die Buchstaben ja nicht nach der Häufigkeit gezeichnet.

mfg tobias