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.
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 .
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?
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?
To pytanie zostało zainspirowane pytaniem TCS Stackexchange .
źródło
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ść2−q q+k 2q−1 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 jestq 2q+k−1 q+k q+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).p 2q±1/2 q∈Z.
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/2–√≤128,maxA∈ZA A=52,B=76 52 2−6.5 76 2−7.5
Następnie , podczas gdy kod Huffmana osiąga ( 52 ⋅ 0,5 - 76 ⋅ 0,5 ) /H(X)=(52⋅6.5+76⋅7.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(52⋅0.5−76⋅0.5)/128≈0.99436 Q . Używając go, odkryłem kilka dni temu, prowadzi do ściślejszych dwustronnych granic Chernoffa, jak widać na Wikipedii dla granic Chernoffa).D(P∥Q)=∑pilogpiqi+∑(1−pi)log1−pi1−qi
źródło