Quelle est la complexité du calcul des codes libres de préfixe optimaux, lorsque les fréquences sont similaires?

Il est bien connu qu'il existe un algorithme optimal dans le pire des cas pour calculer le code Huffman dans le temps $\theta(n\lg n)$ . Ceci est amélioré de deux manières orthogonales:

1. Des codes libres de préfixe optimaux peuvent être calculés plus rapidement si l'ensemble de fréquences distinctes est petit (par exemple de taille $\sigma$ ): triez les fréquences à l'aide de [Munro et Spira, 1976] afin de tirer parti de la petite valeur de $\sigma$ , et calculez le Huffman arbre en temps linéaire à partir des fréquences triées. Cela donne une solution dans $O(n\lg\sigma)$

2. Il existe un algorithme $O(n 16^k)$ pour calculer des codes équivalents où $k$ est le nombre de longueurs de mots de code distinctes [Belal et Elmasry].

$O(n\min\{16^k,\lg\sigma\})$

LE RÉSULTAT DES STACS 2006 SEMBLE ÊTRE MAUVAIS$O(nk)$ O ( 16 k n ) O ( 9 k log 2 k - 1 n ) , Elmasry a publié sur ARXIV en 2010 (http://arxiv.org/abs/cs/0509015) une version annonçant - des opérations sur les entrées non triées et - opérations sur une entrée triée$O(16^kn)$$O(9^k \log^{2k-1} n)$

1. Je vois une analogie avec la complexité du calcul de la coque convexe planaire, où les algorithmes en (basé sur le tri, comme l' algorithme pour le code de Huffman) et en (cadeau wrapping) ont été remplacés par l'algorithme de Kirkpatrick et Seidel dans (qui s'est avéré plus tard être optimal par exemple avec la complexité de la forme ). Dans le cas des codes libres préfixés, versus suggère la possibilité d'un algorithme de complexité , voire où est le nombre de mots de code de longueurO ( n lg n ) O ( n h ) O ( n lg h ) O ( n H ( n 1 , … , n k ) O ( n lg n ) O ( n k ) O ( n lg k ) O ( n H ( n 1$O(n\lg n)$$O(n\lg n)$$O(nh)$$O(n\lg h)$$O(nH(n_1,\ldots,n_k)$$O(n\lg n)$$O(nk)$$O(n\lg k)$$O(nH(n_1,\ldots,n_k)$$n_i$$i$, en utilisant l'analogie d'un bord de la coque convexe couvrant pointe vers une longueur de code couvrant symboles.$n_i$$n_i$

2. Un exemple simple montre que le tri des valeurs logarithmiques (arrondies) des fréquences (en temps linéaire dans le $\theta(\lg n)$ modèle RAM de mot ) ne donne pas un code libre de préfixe optimal en temps linéaire:

   • Pour ,$n=3$$f_1=1/2-\varepsilon$ et$f_2=f_3=1/4+\varepsilon$
   • $\lceil\lg f_i\rceil=2$ donc le tri des journaux ne change pas l'ordre
   • pourtant, deux codes sur trois coûtent bits de plus qu'optimal.$n/4$

3. Une autre question intéressante serait de réduire la complexité lorsque est grand, c'est-à-dire que tous les codes ont des longueurs distinctes:$k$

   • par exemple, lorsque les fréquences ont toutes une valeur de log distincte. Dans ce cas on peut trier les fréquences en temps linéaire dans le θ ( $k=n$mot RAM n ) , et calculer le code Huffman en temps linéaire (car le tri de leurs valeurs logarithmiques suffit pour trier les valeurs), ce qui donne un temps linéaire global, beaucoup mieux que le n 2 de l'algorithme de Belal et Elmasry.$\theta(\lg n)$$n^2$

Cela a pris quelques années (cinq!), Mais voici une réponse partielle à la question:

http://arxiv.org/abs/1602.00023

Codes gratuits de préfixe optimal avec tri partiel Jérémy Barbay (Soumis le 29 janvier 2016)

Nous décrivons un algorithme calculant un code libre optimal de préfixe pour n poids positifs non triés dans le temps dans O (n (1 + lgα)) ⊆O (nlgn), où l'alternance α∈ [1..n − 1] mesure la quantité de tri requis par le calcul. Cette complexité asymptotique se situe dans un facteur constant de l'optimal dans le modèle de calcul de l'arbre de décision algébrique, dans le pire des cas sur toutes les instances de taille n et d'alternance α. De tels résultats affinent la complexité de l'état de l'art de Θ (nlgn) dans le pire des cas par rapport aux instances de taille n dans le même modèle de calcul, un point de repère en compression et en codage depuis 1952, par la simple combinaison de l'algorithme de van Leeuwen pour calculer le préfixe optimal codes libres à partir de poids triés (connus depuis 1976), avec des structures de données différées pour trier partiellement un multiset en fonction des requêtes qu'il contient (connus depuis 1988).