Huffman-Baum und maximale Tiefe

Ist es bei Kenntnis der Häufigkeit der einzelnen Symbole möglich, die maximale Höhe des Baums zu bestimmen, ohne den Huffman-Algorithmus anzuwenden? Gibt es eine Formel, die diese Baumhöhe angibt?

trees coding-theory user7060
quelle

Versuchen Sie, mit ein paar Beispielen herumzuspielen, und prüfen Sie, ob Sie ein nützliches Kriterium finden. Das würde ich tun, wenn ich versuchen würde, Ihre Frage zu beantworten, aber es ist wahrscheinlich besser für Sie, es selbst zu tun ...

Yuval Filmus

Ja, ich habe es bereits mit vielen Beispielen versucht, aber ich suche nach einem Wurfausdruck, zum Beispiel einer asymptotischen Bindung, Funktion der Anzahl der Symbole ...

user7060

In Bezug auf die Anzahl der Symbole kann man nichts besseres tun als

n - 1

$n-1$ einerseits und

⌈ \log_{2} n ⌉

$\lceil \log_2 n \rceil$ andererseits.

Yuval Filmus

Es tut uns leid. Ich habe über die Anzahl der Symbole und ihre Häufigkeit nachgedacht. Vielleicht ist es zum Beispiel möglich, die maximale Tiefe anzugeben, indem man einfach die niedrigste Frequenz unter allen Symbolen betrachtet?

n - 1

$n-1$ ist ein Gedanken, der an die Tiefe gebunden ist, ich interessiere mich für eine enge Grenze.

user7060

max - \log_{2} p_{i}

$\max -\log_2 p_i$

Antworten:

Die Huffman-Codierung (asymptotisch) liegt innerhalb eines Bits der Entropie der Sequenz. Dies bedeutet, dass Sie sich (asymptotisch) innerhalb eines Bits der durchschnittlichen Länge (dh Höhe) Ihres Codes befinden , wenn Sie die Entropie Ihrer Symbolfrequenzen berechnen . Sie können diesen Durchschnitt verwenden, um die längste Länge (im Durchschnitt) zu begrenzen, oder Sie können kombinatorische Methoden verwenden , um deterministische Grenzen zu erhalten.

Ari Trachtenberg
quelle

Der pathologische Fall wäre, wenn die sortierte Symbolfrequenz der der Fibonacci-Sequenz ähnelt. N: = Anzahl der Symbole. für N> 2 maximal mögliche Höhe: N-1. für N == 1 oder 2: 1

Bill Liu
quelle

Dies ist nicht das, was die Frage stellt.

Tom van der Zanden

Tatsächlich. Die Frage fragt nach jedem Fall, während Sie über den schlimmsten Fall sprechen.

Raphael