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

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. $p$ $\sum p_i \ell_i$ $\ell_i$ $i$ $H(p)$ $H(p)+1$ $H(p) = -\sum_i \, p_i \log_2 p_i$

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? $\frac{1}{2}$ $\{.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? $M$ $1/M$ $M \approx 2^k \ln 2$

\frac{1 + \ln \ln 2 - \ln 2}{\ln 2} \approx 0.08607.

$\frac{1 + \ln \ln 2 - \ln 2}{\ln 2} \approx 0.08607.$

To pytanie zostało zainspirowane pytaniem TCS Stackexchange .

optimization it.information-theory coding-theory

— Peter Shor
źródło

Odpowiedzi:

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$ $p\geq 1/2$ $p+0.086$ $p<1/2$

— Ugo
źródło

Optymalna granica została znaleziona przez Manstetten, Tight ogranicza nadmiarowość kodów Huffmana .

— Yuval Filmus,

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) \leq \ldots \leq 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 gdzie słowa kodowe mają długość $2^{-q}$ $q+k$ $2^{q-1}$ a pozostałe mają długość . Dla rozkładu doskonale zakodowanego przez ten kod średnia długość zbliża się do , chyba że masz również dolną granicę prawdopodobieństwa jednego elementu, podczas gdy entropia jest $q$ $2^{q+k-1}$ $q+k$ $q+k$ . $q+\frac{k}{2}$

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 do(Elementowi końcowemu przypisuje się wszelkie pozostałe prawdopodobieństwo, ale nie spowoduje asymptotycznej różnicy). $p$ $2^{q\pm 1/2}$ $q \in {\mathbb Z}.$

Rozważmy na przykład Następnie $q = 7.$

daje. Nasz rozkład obejmujeelementy z prawdopodobieństwem ,z prawdopodobieństwem , a jeden element otrzymuje resztki. $A + B = 128, A\sqrt{2}+B/\sqrt{2}\leq 128, \max_{A \in {\mathbb Z}} A$ $A = 52, B = 76$ $52$ $2^{-6.5}$ $76$ $2^{-7.5}$

Następnie , podczas gdy kod Huffmana osiąga $H(X) = (52\cdot 6.5 + 76 \cdot 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 : dywergencja Kullbacka-Lieblera $(52 \cdot 0.5 - 76 \cdot 0.5)/128 \approx 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\Vert Q) = \sum p_i \log \frac{p_i}{q_i} + \sum (1-p_i) \log \frac{1-p_i}{1-q_i}$

— Carl
źródło

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.

- \log_{2} p_{i}

$-\log_2 p_i$

— Peter Shor

I rzeczywiście masz rację. Chciałem zapytać o oczekiwaną długość słowa kodowego w rozkładzie prawdopodobieństwa

p

$p$

— Peter Shor,

Ups, przeliczyłem się na temat

A

$A$ vs.

. Nadal chcemy

B

$B$

nieco mniej niż

, ale coś w rodzaju

, aby zmusić mniejsze wpisy do dolnego rzędu. To daje

A \sqrt{2} + B / \sqrt{2}

$A\sqrt{2}+B/\sqrt{2}$

2^{k}

$2^k$

A + 2 B = 2^{k}

$A+2B=2^k$

A = \frac{2 - 1 / \sqrt{2}}{\sqrt{2} - 1} B .

$A = \frac{2-1/\sqrt{2}}{\sqrt{2}-1}B.$

— 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

. Więc zamiast

2 A + B

$2A+B$

2

$2$

\sqrt{2}

$\sqrt{2}$

możemy rozważyć, np.

dla połowy kodu Huffmana i

dla reszty, dając

wpisów ...

1 / \sqrt{2}

$1/\sqrt{2}$

(1 + x) / 2^{k}

$(1+x)/2^k$

(1 - x) / 2^{k + 1}

$(1-x)/2^{k+1}$

3 * 2^{k}

$3*2^k$

— 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

ma entropii

. Zamiast tego zmień to na

wpisy z prawdopodobieństwem

64

$64$

1 / 128

$1/128$

128

$128$

1 / 256

$1/256$

7.5

$7.5$

64

$64$

wpisów z prawdopodobieństwem

1 / 128 \sqrt{2}

$1/128\sqrt{2}$

128

$128$

. Entropia tego rozkładu wynosi

1 / 256 (2 - 1 / \sqrt{2})

$1/256(2-1/\sqrt{2})$

, co daje 6.4023, podczas gdy entropia kodu Huffmana 7,5 podstawie jednolitych, a

Więc jeśli nie przeliczyłem (i robię to często), daje to lukę około

1 / (2 \sqrt{2}) * 7.5 + (1 - 1 / (2 \sqrt{(} 2))) * 5.802

$1/(2\sqrt{2})*7.5+(1-1/(2\sqrt(2)))*5.802$

(1 - 2^{- 1.5}) * 7 + 2^{- 1.5} * 8 = 7.3535.

$(1-2^{-1.5})*7+2^{-1.5}*8 = 7.3535.$

0.95

$0.95$

— Carl