Drzewo Huffmana i maksymalna głębokość

Znając częstotliwości każdego symbolu, czy można określić maksymalną wysokość drzewa bez zastosowania algorytmu Huffmana? Czy istnieje wzór, który określa wysokość tego drzewa?

trees coding-theory

— użytkownik7060
źródło

Spróbuj pobawić się kilkoma przykładami i sprawdź, czy możesz znaleźć jakieś przydatne kryterium. Tak postąpiłbym, gdybym próbował odpowiedzieć na twoje pytanie, ale prawdopodobnie lepiej, żebyś zrobił to sam ...

— Yuval Filmus

Tak, próbowałem już z wieloma przykładami, ale szukam wyrażenia literalnego, na przykład asymptotycznego wiązania, funkcji liczby symboli ...

— user7060

Pod względem liczby symboli z jednej strony nie można zrobić nic lepszego niż az drugiej strony .

n - 1

$n-1$

⌈ \log_{2} n ⌉

$\lceil \log_2 n \rceil$

— Yuval Filmus

Przepraszam. Myślałem o liczbie symboli i ich częstotliwości. Na przykład, czy możliwe jest podanie maksymalnej głębokości, patrząc po prostu na najniższą częstotliwość spośród wszystkich symboli? jest zaciętą pułapką na głębokości, interesuje mnie ścisła granica.

n - 1

$n-1$

— user7060

Spróbowałbym spojrzeć na i sprawdzić, czy jest to związane z głębią. Możesz także spróbować wymyślić rekurencję odpowiadającą rzeczywistemu algorytmowi i sprawdzić, czy coś ci to daje.

max - \log_{2} p_{i}

$\max -\log_2 p_i$

— Yuval Filmus

Odpowiedzi:

Kodowanie Huffmana (asymptotycznie) wchodzi w jeden bit entropii sekwencji. Oznacza to, że jeśli obliczysz entropię częstotliwości symboli, będziesz (asymptotycznie) w granicach jednego bitu średniej długości (tj. Wysokości) swojego kodu. Możesz użyć tej średniej, aby związać najdłuższą długość (średnio), lub możesz użyć metod kombinatorycznych, aby uzyskać granice deterministyczne.

— Ari Trachtenberg
źródło

Przypadek patologiczny miałby miejsce, gdy posortowana częstotliwość symboli przypomina częstotliwość sekwencji Fibonacciego. N: = liczba symboli. dla N> 2, maksymalna możliwa wysokość: N-1. dla N == 1 lub 2: 1

— Bill Liu
źródło

Nie o to pyta pytanie.

— Tom van der Zanden

W rzeczy samej. Pytanie dotyczy każdego przypadku, gdy mówisz o najgorszym przypadku.

— Raphael