Quelle est la manière la plus efficace (*) de construire un arbre canonnier huffman?

Question

Supposons que A est un tableau où A [0] contient la fréquence de la lettre 0 de l'alphabet. Quel est le moyen le plus efficace (*) pour calculer les longueurs de code? Pas sûr, mais je suppose que l'efficacité peut être en termes d'utilisation de la mémoire ou des mesures requises. Tout ce qui m'intéresse, c'est le tableau L où L[0] contient les longueurs de code (nombre de bits) de la lettre 0 de l'alphabet, où le code provient de l'arbre de Huffman canonique construit à partir d'un tableau de fréquences.

Answer 1

Si les fréquences forment une séquence monotone, c.-à-d. A [0] < = A [1] < = ... < = A [n-1] ou A [0]> = A [1]> = ...> = A [n-1], alors vous peut générer une longueur de code optimale en temps O (n) et O (1) espace supplémentaire. Cet algorithme nécessite seulement 2 passes simples sur le tableau et c'est très rapide. Une description complète est donnée dans [1].

Si vos fréquences ne sont pas triées, vous devez d'abord les trier puis appliquer l'algorithme ci-dessus. Dans ce cas, la complexité temporelle est O (n log n) et un tableau auxiliaire de n entiers est nécessaire pour stocker la complexité de l'ordre ordonné trié O (n).

[1]: In-Place Calcul des codes minimum Redondance par Alistair Moffat et Jyrki Katajainen, disponible en ligne: http://www.diku.dk/~jyrki/Paper/WADS95.pdf