Jak dobry jest kod Huffmana, gdy nie ma dużych liter prawdopodobieństwa?

21

Kod Huffmana dla rozkładu prawdopodobieństwa jest kodem prefiksu o minimalnej średniej ważonej długości słowa kodowego , gdzie jest długością tego słowa kluczowego. Jest dobrze znanym twierdzeniem, że średnia długość na symbol kodu Huffmana zawiera się między a , gdzie jest entropią Shannona rozkładu prawdopodobieństwa.ppiiiiH(p)H(p)+1H(p)=ipilog2pi

Kanoniczny zły przykład, w którym średnia długość przekracza entropię Shannona o prawie 1, jest rozkładem prawdopodobieństwa, takim jak , gdzie entropia wynosi prawie 0, a średnia długość słowa kodowego wynosi 1. To daje przerwa między entropią a długością słowa kodowego wynosząca prawie .{.999,.001}1

Ale co się dzieje, gdy istnieje największe prawdopodobieństwo w rozkładzie prawdopodobieństwa? Załóżmy na przykład, że wszystkie prawdopodobieństwa są mniejsze niż . Największa luka, jaką mogłem znaleźć w tym przypadku, dotyczy rozkładu prawdopodobieństwa, takiego jak , gdzie entropia jest nieco większa niż 1, a średnia długość słowa kodowego jest nieco mniejsza niż 1,5, co daje przerwa zbliża się do . Czy to najlepsze, co możesz zrobić? Czy możesz podać górną granicę odstępu, która jest ściśle mniejsza niż 1 w tym przypadku?12{.499,.499,.002}0.5

Rozważmy teraz przypadek, w którym wszystkie prawdopodobieństwa są bardzo małe. Załóżmy wybrać rozkład prawdopodobieństwa nad literami, każda o prawdopodobieństwo . W takim przypadku największa luka występuje, jeśli wybierzesz . Tutaj masz lukę około Czy to najlepsze, co możesz zrobić w sytuacji, gdy wszystkie prawdopodobieństwa są małe?M1/MM2kln2

1+lnln2ln2ln20.08607.

To pytanie zostało zainspirowane pytaniem TCS Stackexchange .

Peter Shor
źródło

Odpowiedzi:

19

Istnieje wiele prac, które dokładnie omawiają wspomniany problem. Pierwszym z serii jest artykuł Gallagera „Wariacje na temat Huffmana”, IEEE-IT, vol. 24, 1978, s. 668–674. Udowadnia, że ​​różnica między średnią długością słowa kodowego kodu Huffmana a entropią (nazywa tę ilość „redundancją”) jest zawsze ściśle mniejsza niż (= największe prawdopodobieństwo w rozkładzie prawdopodobieństwa), w przypadku , i jest mniejsza niż , jeśli . Lepsze granice są znane, można je znaleźć w licznych artykułach cytujących pracę Gallagera.P 1 / 2 P + 0,086 P < 1 / 2pp1/2p+0.086p<1/2

Ugo
źródło
2
Optymalna granica została znaleziona przez Manstetten, Tight ogranicza nadmiarowość kodów Huffmana .
Yuval Filmus,
2

Sądząc po granicy , uważam, że zamierzałeś zadać inne pytanie ... lub po prostu nie określiłeś, jak przyjmujesz „średnią”. Więc odpowiem na oba. Odpowiedź jest przecząca na oba pytania.H(p)H(p)+1

Po pierwsze, jeśli zdefiniujesz średnią długość kodu za pomocą jednolitego rozkładu na słowa kodowe i weź jako górną granicę prawdopodobieństwa dowolnego elementu, to rozważ kod o długości q + k, gdzie 2 q - 1 słowa kodowe mają długość2qq+k2q1 a pozostałe 2 q + k - 1 mają długość q + k . Dla rozkładu doskonale zakodowanego przez ten kod średnia długość zbliża się do q + k , chyba że masz również dolną granicę prawdopodobieństwa jednego elementu, podczas gdy entropia jestq2q+k1q+kq+k .q+k2

Rozważmy teraz „średnią długość”, oznaczającą średnią długość słowa kodowego, gdy kod Huffmana jest używany do kodowania . W tym przypadku związana jest napięty, a przykład rozmieszczenia go zrealizować w granicy jest związek, w którym każdy element z prawdopodobieństwem wystąpienia 2 q ± 1 / 2 do q Z . (Elementowi końcowemu przypisuje się wszelkie pozostałe prawdopodobieństwo, ale nie spowoduje asymptotycznej różnicy).p2q±1/2qZ.

Rozważmy na przykład Następnieq=7.

dajeA=52,B=76. Nasz rozkład obejmuje52elementy z prawdopodobieństwem2 - 6,5 ,76z prawdopodobieństwem2 - 7,5 , a jeden element otrzymuje resztki.A+B=128,A2+B/2128,maxAZAA=52,B=765226.57627.5

Następnie , podczas gdy kod Huffmana osiąga ( 52 0,5 - 76 0,5 ) /H(X)=(526.5+767.5)/128=7.09375 utratę entropii. (Nawiasem mówiąc, utrata entropii ma nazwę, niezależnie od tego, czy wykonujesz kodowanie Huffmana, czy kodowanie arbitralne dla Q : dywergencja Kullbacka-Lieblera D ( P Q ) = p i(520.5760.5)/1280.99436Q . Używając go, odkryłem kilka dni temu, prowadzi do ściślejszych dwustronnych granic Chernoffa, jak widać na Wikipedii dla granic Chernoffa).D(PQ)=pilogpiqi+(1pi)log1pi1qi

Carl
źródło
1
Ten drugi przykład nieco mnie zaskakuje. Jeśli masz 128 słów kodowych, istnieje kod o średniej długości słowa 7 (w rzeczywistości wszystkie długości słów mają 7), co jest sprzeczne z twoim stwierdzeniem, że entropia wynosi 7.09375. Entropia tego rozkładu (który otrzymujesz biorąc średnią ważoną nie średnią) wynosi 6,88, podczas gdy średnia długość kodu Huffmana wynosi 7. Daje to lukę (lub dywergencję Kullbacka-Lieblera) około 0,12, co wydaje się być nieco lepsze niż mój przykład, ale nie jest zbliżone do 1.log2pi
Peter Shor
I rzeczywiście masz rację. Chciałem zapytać o oczekiwaną długość słowa kodowego w rozkładzie prawdopodobieństwa . p
Peter Shor,
Ups, przeliczyłem się na temat A vs. . Nadal chcemy A B nieco mniej niż2k, ale coś w rodzajuA+2B=2k, aby zmusić mniejsze wpisy do dolnego rzędu. To dajeA=A2+B/22kA+2B=2kA=21/221B.
Carl
W rzeczywistości byłoby to ... ale ten układ równań nie ma pozytywnego rozwiązania - wydaje się, że nie możemy zmusić wszystkiego do uzyskania potęgi równej 2 . Więc zamiast 2A+B2 i1/2 możemy rozważyć, np.(1+x)/2kdla połowy kodu Huffmana i(1-x)/2 k + 1 dla reszty, dając32kwpisów ...1/2(1+x)/2k(1x)/2k+132k
Carl
Spróbuj tego (nie optymalne - przypuszczam, że zależy to od tego, jak zdecydujesz się zaokrąglić w dół lub w górę). wpisów z prawdopodobieństwem 1 / 128 i 128 wpisów z prawdopodobieństwem 1 / 256 ma entropii 7.5 . Zamiast tego zmień to na 64 wpisy z prawdopodobieństwem641/1281281/2567.564 i128wpisów z prawdopodobieństwem1/256(21/1282128. Entropia tego rozkładu wynosi11/256(21/2), co daje 6.4023, podczas gdy entropia kodu Huffmana 7,5 podstawie jednolitych, a(1-2 - 1,5 )*7+2 - 1,5 *8=7,3535. Więc jeśli nie przeliczyłem (i robię to często), daje to lukę około0,95. 1/(22)7.5+(11/(2(2)))5.802(121.5)7+21.58=7.3535.0.95
Carl