¿Cuál es la complejidad de calcular códigos libres de prefijos óptimos, cuando las frecuencias son similares?

Es bien sabido que existe un algoritmo óptimo para el peor de los casos para calcular el código Huffman en el tiempo . Esto se mejora de dos maneras ortogonales:$\theta(n\lg n)$

1. Los códigos libres de prefijos óptimos se pueden calcular más rápido si el conjunto de frecuencias distintas es pequeño (por ejemplo, de tamaño ): clasifique las frecuencias utilizando [Munro y Spira, 1976] para aprovechar el pequeño valor de σ y calcule el Huffman árbol en tiempo lineal a partir de las frecuencias ordenadas. Esto produce una solución en O ( n lg σ $\sigma$$\sigma$$O(n\lg\sigma)$

2. Existe un algoritmo para calcular códigos equivalentes donde k es el número de longitudes de palabras de código distintas [Belal y Elmasry].$O(n 16^k)$$k$

¿Hay alguna forma de combinar esas técnicas para mejorar la mejor complejidad actual de ?$O(n\min\{16^k,\lg\sigma\})$

EL RESULTADO DE DE STACS 2006 PARECE SER INCORRECTO$O(nk)$ , Elmasry publicó en ARXIV en 2010 (http://arxiv.org/abs/cs/0509015) una versión que anuncia - operaciones en entradas no ordenadas y - O ( 9 k log 2 k - 1 n ) operaciones en entrada ordenada$O(16^kn)$$O(9^k \log^{2k-1} n)$

1. Veo una analogía con la complejidad de calcular el casco convexo plano, donde los algoritmos en (basados ​​en la clasificación, como el algoritmo O ( n lg n ) para el código de Huffman) y en O ( n h ) (envoltura de regalos ) fueron reemplazados por el algoritmo de Kirkpatrick y Seidel en O ( n lg h ) (más tarde demostró ser óptimo con la complejidad de la forma O ( n H ( n 1 , ... , n $O(n\lg n)$$O(n\lg n)$$O(nh)$$O(n\lg h)$ ). En el caso de los códigos Prefix Free, O ( n lg n ) versus O ( n k ) sugiere la posibilidad de un algoritmo con complejidad O ( n lg k ) , o incluso O ( n H ( n 1 , ... , n k ) donde n i es el número de palabras de código de longitud i , usando la analogía de un borde del casco convexo que cubre n $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$$n_i$apunta a una longitud de código que cubre símbolos.$n_i$

2. Un simple ejemplo muestra que la clasificación de los (redondeado) valores logarítmicos de las frecuencias (en tiempo lineal en el modelo de palabra RAM) no da un código libre óptima prefijo en tiempo lineal: $\theta(\lg n)$

   • Para , f 1 = 1 / 2 - ε y f 2 = f 3 = 1 / 4 + $n=3$$f_1=1/2-\varepsilon$$f_2=f_3=1/4+\varepsilon$
   • por lo que la clasificación de registros no cambia el orden$\lceil\lg f_i\rceil=2$
   • Sin embargo, dos de los tres códigos cuestan bits más que lo óptimo.$n/4$

3. Otra pregunta interesante sería reducir la complejidad cuando es grande, es decir, todos los códigos tienen longitudes distintas:$k$

   • por ejemplo, cuando las frecuencias son todas de valor de registro distinto. En este caso, uno puede ordenar las frecuencias en tiempo lineal en la palabra θ ( lg n ) RAM, y calcular el código de Huffman en tiempo lineal (porque ordenar sus valores de registro es suficiente para ordenar los valores), lo que resulta en un tiempo lineal general, mucho mejor que el n 2 del algoritmo de Belal y Elmasry.$k=n$$\theta(\lg n)$$n^2$

Tomó algunos años (¡cinco!), Pero aquí hay una respuesta parcial a la pregunta:

http://arxiv.org/abs/1602.00023

Códigos gratuitos de prefijo óptimo con clasificación parcial Jérémy Barbay (Enviado el 29 de enero de 2016)

Describimos un algoritmo que calcula un código libre de prefijo óptimo para n pesos positivos sin clasificar en el tiempo dentro de O (n (1 + lgα)) ⊆O (nlgn), donde la alternancia α∈ [1..n − 1] mide la cantidad de clasificación requerida por el cálculo. Esta complejidad asintótica está dentro de un factor constante de lo óptimo en el modelo computacional de árbol de decisión algebraico, en el peor de los casos en todos los casos de tamaño ny alternancia α. Dichos resultados refinan la complejidad del estado del arte de Θ (nlgn) en el peor de los casos en casos de tamaño n en el mismo modelo computacional, un hito en compresión y codificación desde 1952, por la mera combinación del algoritmo de van Leeuwen para calcular el prefijo óptimo códigos libres de pesos ordenados (conocidos desde 1976), con estructuras de datos diferidos para ordenar parcialmente un conjunto múltiple en función de las consultas (conocido desde 1988).