Czy kodowanie Huffmana jest zawsze optymalne?

9

Wymóg, aby kodowanie było wolne od prefiksów, skutkuje dużymi drzewami, ponieważ drzewo musi być kompletne. Czy istnieje próg, w którym niekodowane przechowywanie danych o stałej długości byłoby bardziej wydajne niż kodowanie danych?

information-theory data-compression Kaveh
źródło
Ogólnie „nie”. Dla średnich danych częstotliwość każdego znaku wynosiłaby> 1 i dobrze jest używać kodowania Huffmana zamiast kodów o stałej długości
@arunmoezhi Czy możesz podać przykład, który podałem powyżej? Częstotliwość każdego znaku jest większa niż 1, ale stała długość jest bardziej optymalna.
Ten przykład jest interesujący. Ale czy możesz podać taki scenariusz z prawdopodobieństwem każdej postaci zamiast częstotliwości i upewnić się, że prawdopodobieństwa wszystkich postaci
@arunmoezhi Uwzględniłem prawdopodobieństwa postaci i sumują się one do 1.

Odpowiedzi:

4

Entropia H(A)tego problemu jest 1.998. Zarówno kodowanie Huffmana, jak i kodowanie o stałej długości dla tego problemu ma średnią długość słowa kodowego jako 2. I FYI kodowanie, które masz przy użyciu kodowania Huffmana jest nieprawidłowe. Kodowanie Huffmana generuje również kody podobne do stałej długości dla tego problemu. Używa chciwego podejścia. Więc anie dostaje kodu jako, 0ale zamiast tego dostaje 00. Przerób drzewo generowane za pomocą kodowania Huffmana. Drzewo, które powinieneś zdobyć to:wprowadź opis zdjęcia tutaj

arunmoezhi
źródło
Dziękuję Ci. Czy możesz podać jakiś dowód na to, że kodowanie Huffmana jest zawsze bardziej optymalne niż stała długość, lub przynajmniej odnieść się do jednego?
1
Możesz się odwołać Introduction to Algorithmsprzez CLRS. W rozdziale, który mówi greedy algorithms, możesz uzyskać formalny dowód Huffman algorithm. Jest to długi dowód i wymaga cierpliwości do czytania.
8

Kodowanie Huffmana przybliża rozkład populacji z potęgami dwóch prawdopodobieństw. Jeśli prawdziwy rozkład składa się z potęg dwóch prawdopodobieństw (a symbole wejściowe są całkowicie nieskorelowane), kodowanie Huffmana jest optymalne. Jeśli nie, możesz lepiej radzić sobie z kodowaniem zakresu. Jest jednak optymalny spośród wszystkich kodowań, które przypisują określone zestawy bitów do określonych symboli na wejściu.

Antymon
źródło
Co rozumiesz przez „przybliżony rozkład populacji”?
3
Istnieje teoretycznie prawdziwy rozkład wiadomości, który można hipotetycznie wysłać. Idealnie byłoby, gdyby każda wiadomość była kodowana w sposób proporcjonalny do logu jej prawdopodobieństwa, ale ponieważ kody Huffmana są liczbą całkowitą bitów, która domyślnie odpowiada prawdopodobieństwom równym potęgom dwóch. Stąd przybliżenie. Odszukaj twierdzenie o kodowaniu Shannonsa.
8

Tak, zawsze jest optymalne.

Nie, nie ma progu, w którym zużywałoby mniej miejsca do korzystania z niekodowanych danych o stałej długości.

Znalazłem wiele dowodów w Internecie, ale jest wystarczająca dyskusja w artykule w Wikipedii Kodowanie Huffmana .

Obejmuje to również inne techniki, które osiągają wyższą kompresję (praca poza przestrzenią, dla której kod Huffmana jest optymalny).

Cade Roux
źródło