Drzewo Huffmana i maksymalna głębokość

9

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
1
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
1
Pod względem liczby symboli z jednej strony nie można zrobić nic lepszego niż az drugiej strony . n−1⌈log2⁡n⌉
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
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−log2⁡pi
Yuval Filmus

Odpowiedzi:

2

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
0

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
1
Nie o to pyta pytanie.
Tom van der Zanden
W rzeczy samej. Pytanie dotyczy każdego przypadku, gdy mówisz o najgorszym przypadku.
Raphael