Jaka jest złożoność obliczania optymalnych kodów wolnych od prefiksów, gdy częstotliwości są podobne?

Dobrze wiadomo, że istnieje najgorszy przypadek optymalnego algorytmu do obliczania kodu Huffmana w czasie . Poprawiono to na dwa ortogonalne sposoby:$\theta(n\lg n)$

1. Optymalne kody wolne od prefiksów można obliczyć szybciej, jeśli zestaw różnych częstotliwości jest mały (np. Rozmiar ): posortuj częstotliwości za pomocą [Munro i Spira, 1976], aby skorzystać z małej wartości i obliczyć drzewo Huffmana w czasie liniowym z posortowanych częstotliwości. To daje rozwiązanie wσ O ( n lg σ $\sigma$$\sigma$$O(n\lg\sigma)$

2. Istnieje algorytm do obliczania równoważnych kodów, gdzie jest liczbą różnych długości słów kodowych [Belal i Elmasry].$O(n 16^k)$$k$

Czy istnieje sposób na połączenie tych technik, aby poprawić obecną najlepszą złożoność ?$O(n\min\{16^k,\lg\sigma\})$

$O(nk)$ wynikają z STACS 2006 wydają się być błędne , Elmasry opublikowany na arXiv w 2010 roku (http://arxiv.org/abs/cs/0509015) wersja ogłaszając - $O(16^kn)$ operacje na wejściu i niesegregowanych - $O(9^k \log^{2k-1} n)$ operacji na posortowanym wejściu

1. Widzę analogię ze złożonością obliczania płaskiego wypukłego kadłuba, gdzie algorytmy w $O(n\lg n)$ (oparte na sortowaniu, jako algorytm $O(n\lg n)$ dla kodu Huffmana) i w $O(nh)$ (prezent zawijanie) zostały zastąpione przez algorytm Kirkpatrick i Seidela w $O(n\lg h)$ (później okazało się być optymalnym instancją przy złożoności formy $O(nH(n_1,\ldots,n_k)$ ). W przypadku kodów Free Prefix, $O(n\lg n)$ kontra $O(nk)$ sugeruje możliwość algorytmu o złożoności $O(n\lg k)$ , a nawet $O(nH(n_1,\ldots,n_k)$ gdzie $n_i$ jest liczbą słów kodowych o długości $i$, wykorzystując analogię krawędzi wypukłego kadłuba pokrywającego $n_i$ wskazuje na długość kodu pokrywającą symbole $n_i$ .

2. Prosty przykład pokazuje, że sortowanie (zaokrąglonych) wartości logarytmicznych częstotliwości (w czasie liniowym w modelu pamięci RAM „ $\theta(\lg n)$ ) nie daje optymalnego wolnego kodu w czasie liniowym:

   • Dla $n=3$ , $f_1=1/2-\varepsilon$ i $f_2=f_3=1/4+\varepsilon$
   • $\lceil\lg f_i\rceil=2$ więc sortowanie logów nie zmienia kolejności
   • jeszcze dwa kody z trzech kosztują $n/4$ bity więcej niż optymalne.

3. Innym interesującym pytaniem byłoby zmniejszenie złożoności, gdy $k$ jest duże, tj. Wszystkie kody mają różne długości:

   • na przykład gdy wszystkie częstotliwości mają odrębną wartość logarytmiczną. W takim przypadku można posortować częstotliwości w czasie liniowym w słowie RAM i obliczyć kod Huffmana w czasie liniowym (ponieważ sortowanie ich wartości logów wystarczy do posortowania wartości), co daje ogólny czas liniowy , znacznie lepiej niż z algorytmu Belala i Elmasry'ego.θ ( lg n ) n $k=n$$\theta(\lg n)$$n^2$

Zajęło to kilka lat (pięć!), Ale oto częściowa odpowiedź na pytanie:

http://arxiv.org/abs/1602.00023

Optymalne darmowe kody z częściowym sortowaniem z prefiksem Jérémy Barbay (przesłane 29 stycznia 2016)

Opisujemy algorytm obliczający optymalny kod wolny od prefiksu dla n niesortowanych wag dodatnich w czasie w obrębie O (n (1 + lgα)) ⊆O (nlgn), gdzie przemienność α∈ [1..n − 1] mierzy ilość sortowanie wymagane przez obliczenia. Ta asymptotyczna złożoność mieści się w stałym współczynniku optymalnym w modelu obliczeniowym algebraicznego drzewa decyzyjnego, w najgorszym przypadku we wszystkich przypadkach wielkości n i przemienności α. Takie wyniki udoskonalają najnowocześniejszą złożoność Θ (nlgn) w najgorszym przypadku w porównaniu z przypadkami wielkości n w tym samym modelu obliczeniowym, co stanowi przełom w kompresji i kodowaniu od 1952 r., Przez samą kombinację algorytmu van Leeuwena w celu obliczenia optymalnego prefiksu darmowe kody z posortowanych wag (znane od 1976 r.), z odroczoną strukturą danych, aby częściowo posortować multiset w zależności od zapytań (znanych od 1988 r.).