Arbre de Huffman et profondeur maximale

9

Connaissant les fréquences de chaque symbole, est-il possible de déterminer la hauteur maximale de l'arbre sans appliquer l'algorithme de Huffman? Existe-t-il une formule qui donne cette hauteur d'arbre?

trees coding-theory user7060
la source
1
Essayez de jouer avec quelques exemples et voyez si vous pouvez trouver un critère utile. C'est ce que je ferais si j'essayais de répondre à votre question, mais il vaut probablement mieux que vous le fassiez vous-même ...
Yuval Filmus
Oui, j'ai déjà essayé avec beaucoup d'exemples, mais je recherche une expression littérale, par exemple une borne asymptotique, fonction du nombre de symboles ...
user7060
1
En termes de nombre de symboles, vous ne pouvez rien faire de mieux que d'une part, et d'autre part. ⌈ log 2 n ⌉n−1⌈log2⁡n⌉
Yuval Filmus
Désolé. Je pensais au nombre de symboles et à leurs fréquences. Par exemple, peut-être est-il possible de donner la profondeur maximale en regardant simplement la fréquence la plus basse parmi tous les symboles? n−1 est une borne rought sur la profondeur, je suis intéressé par une borne serrée.
user7060
J'essaierais de regarder max−log2⁡pi et voir si c'est lié à la profondeur. Vous pouvez également essayer de trouver la récursivité correspondant à l'algorithme réel et voir si cela vous donne quelque chose.
Yuval Filmus

Réponses:

2

Le codage de Huffman (asymptotiquement) se trouve à moins d'un bit de l'entropie de la séquence. Cela signifie que si vous calculez l' entropie de vos fréquences de symboles, vous serez (asymptotiquement) à moins d'un bit de la longueur moyenne (c'est-à-dire la hauteur) de votre code. Vous pouvez utiliser cette moyenne pour délimiter la longueur la plus longue (en moyenne), ou vous pouvez utiliser des méthodes combinatoires pour obtenir des limites déterministes.

Ari Trachtenberg
la source
0

Le cas pathologique serait lorsque la fréquence du symbole trié ressemble à celle de la séquence de Fibonacci. N: = # de symboles. pour N> 2, hauteur maximale possible: N-1. pour N == 1 ou 2: 1

Bill Liu
la source
1
Ce n'est pas ce que demande la question.
Tom van der Zanden
En effet. La question demande de toute façon si vous parlez du pire des cas.
Raphael