Qual é a complexidade da computação de códigos livres de prefixo ideal, quando as frequências são semelhantes?

É sabido que existe um algoritmo ideal para o pior caso para calcular o código de Huffman no tempo $\theta(n\lg n)$ . Isso é aprimorado de duas formas ortogonais:

1. Os códigos livres de prefixo ideal podem ser calculados mais rapidamente se o conjunto de frequências distintas for pequeno (por exemplo, de tamanho $\sigma$ ): classifique as frequências usando [Munro e Spira, 1976], de modo a tirar proveito do pequeno valor de $\sigma$ e calcule o Huffman árvore em tempo linear a partir das frequências ordenadas. Isso produz uma solução em $O(n\lg\sigma)$

2. Existe um algoritmo $O(n 16^k)$ para calcular códigos equivalentes em que $k$ é o número de comprimentos distintos de palavras de código [Belal e Elmasry].

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

O RESULTADO DE STACS 2006 parecem ser errados$O(nk)$ O ( 16 k n ) O ( 9 k log 2 k - 1 n ) , Elmasry publicado no arXiv em 2010 (http://arxiv.org/abs/cs/0509015) uma versão anunciando - operações na entrada não triados e - operações na entrada classificada$O(16^kn)$$O(9^k \log^{2k-1} n)$

1. Vejo uma analogia com a complexidade da computação do casco plano convexo, em que algoritmos em (com base na classificação, como o algoritmo para o código de Huffman) e em (presente foram substituídos pelo algoritmo de Kirkpatrick e Seidel em (mais tarde provou ser uma instância ideal com complexidade do formato ). versus sugere a possibilidade de um algoritmo com complexidade ou mesmo que é o número de palavras de código de comprimentoO ( n lg n ) O ( n h ) O ( n lg h ) O ( n H ( n 1 , … , n k ) O ( n lg n ) 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$, usando a analogia de uma aresta do casco convexo que cobre aponta para um comprimento de código que cobre símbolos.$n_i$$n_i$

2. Um exemplo simples mostra que a classificação dos valores logarítmicos (arredondados) das frequências (em tempo linear no modelo de RAM word ) não fornece um código livre ideal do prefixo em tempo linear: $\theta(\lg n)$

   • Para , e$n=3$$f_1=1/2-\varepsilon$$f_2=f_3=1/4+\varepsilon$
   • $\lceil\lg f_i\rceil=2$ para que a classificação dos logs não mude de ordem
   • no entanto, dois códigos em cada três custam bits mais do que o ideal.$n/4$

3. Outra questão interessante seria reduzir a complexidade quando for grande, ou seja, todos os códigos têm comprimentos distintos:$k$

   • por exemplo, quando as frequências têm todos valores de log distintos. Nesse caso, pode-se classificar as freqüências em tempo linear na RAM palavra e calcular o código de Huffman em tempo linear (porque classificar seus valores de log é suficiente para classificar os valores), resultando em tempo linear geral , muito melhor que o do algoritmo de Belal e Elmasry.$k=n$$\theta(\lg n)$$n^2$

Demorou alguns anos (cinco!), Mas aqui está uma resposta parcial à pergunta:

http://arxiv.org/abs/1602.00023

Códigos gratuitos de prefixo ideal com classificação parcial Jérémy Barbay (Enviado em 29 Jan 2016)

Descrevemos um algoritmo que calcula um código livre de prefixo ideal para n pesos positivos não classificados no tempo dentro de O (n (1 + lgα)) ⊆O (nlgn), onde a alternância α∈ [1..n − 1] mede a quantidade de classificação exigida pelo cálculo. Essa complexidade assintótica está dentro de um fator constante do ideal no modelo computacional da árvore de decisão algébrica, na pior das hipóteses em todas as instâncias de tamanho n e alternância α. Tais resultados refinam a complexidade do estado da arte de Θ (nlgn) na pior das hipóteses sobre instâncias de tamanho n no mesmo modelo computacional, um marco na compactação e codificação desde 1952, pela mera combinação do algoritmo de van Leeuwen para calcular o prefixo ideal códigos livres de pesos classificados (conhecidos desde 1976), com o Deferred Data Structures para classificar parcialmente um multiset, dependendo das consultas nele (conhecidas desde 1988).