Насколько хорош код Хаффмана, когда нет больших букв вероятности?

Код Хаффмана для распределения вероятности - это код префикса с минимальной средневзвешенной длиной кодового слова , где - длина го кодового слова. Хорошо известна теорема о том, что средняя длина каждого символа кода Хаффмана находится между и , где - энтропия Шеннона. распределения вероятностей. $p$ $\sum p_i \ell_i$ $\ell_i$ $i$ $H(p)$ $H(p)+1$ $H(p) = -\sum_i \, p_i \log_2 p_i$

Плохой канонический пример, где средняя длина превышает энтропию Шеннона почти на 1, - это распределение вероятностей, такое как $\{.999, .001\}$ , где энтропия равна почти 0, а средняя длина кодового слова равна 1. Это дает разрыв между энтропией и длиной кодового слова почти $1$ .

Но что происходит, когда существует предел наибольшей вероятности в распределении вероятностей? Предположим, например, что все вероятности меньше, чем $\frac{1}{2}$ . Самый большой пробел, который я мог найти в этом случае, относится к распределению вероятностей, например $\{.499, .499, .002\}$ , где энтропия чуть больше 1, а средняя длина кодового слова чуть меньше 1,5, что дает разрыв приближается к $0.5$ . Это лучшее, что вы можете сделать? Можете ли вы дать верхнюю границу зазора, которая строго меньше 1 для этого случая?

Теперь рассмотрим случай, когда все вероятности очень малы. Предположим , вы выбираете распределение вероятностей $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.$ Это лучшее, что вы можете сделать в ситуации, когда все вероятности малы?

Этот вопрос был вдохновлен этим вопросом TCS Stackexchange .

optimization it.information-theory coding-theory Питер Шор
источник

Ответы:

Есть много статей, в которых изучается именно та проблема, которую вы упоминаете. Первой в серии является статья Галлагера "Вариации на тему Хаффмана", IEEE-IT, том. 24, 1978, с. 668-674. Он доказывает, что разница между средней длиной кодового слова кода Хаффмана и энтропией (он называет это количество «избыточностью») всегда строго меньше (= наибольшая вероятность в распределении вероятностей), в случае , и это меньше, чем , если . Лучшие оценки известны, их можно найти в многочисленных статьях, в которых цитируется работа Галлагера. $p$ $p\geq 1/2$ $p+0.086$ $p<1/2$

Ugo
источник

Оптимальная оценка была найдена Манстеттеном, Туго ограничивает избыточность кодов Хаффмана .

Юваль Фильмус

Судя по ограничению , я думаю, что вы намеревались задать другой вопрос ... или вы просто не указали, как вы берете "среднее". Поэтому я отвечу на оба. Ответ нет на оба вопроса. $H(p) \leq \ldots \leq H(p)+1$

Во-первых, если вы определяете среднюю длину кода, используя равномерное распределение по кодовым словам, и берете в качестве верхней границы вероятности любого одного элемента, то рассмотрите код длины где кодовые слова имеют длину а остальные имеют длину . Для распределения, идеально закодированного этим кодом, средняя длина приближается к , если только у вас нет нижней границы для вероятности одного элемента, тогда как энтропия равна . $2^{-q}$ $q+k$ $2^{q-1}$ $q$ $2^{q+k-1}$ $q+k$ $q+k$ $q+\frac{k}{2}$

Теперь давайте рассмотрим «среднюю длину», означающую среднюю длину кодового слова, когда код Хаффмана используется для кодирования . Здесь граница жесткая, и пример распределения, достигающего ее в пределе, - это случай, в котором каждый элемент встречается с вероятностью для(Последнему элементу назначается любая оставшаяся вероятность, но она не будет иметь никакого значения асимптотически). $p$ $2^{q\pm 1/2}$ $q \in {\mathbb Z}.$

Например, рассмотрим Тогда $q = 7.$

$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}$

Тогда , в то время как код Хаффмана достигает потерь энтропии. (Между прочим, потеря энтропии имеет имя, независимо от того, используете ли вы кодирование Хаффмана или произвольное кодирование для : расхождение Кульбака-Либлера . Использование этого, как я обнаружил несколько дней назад, приводит к более жестким двусторонним границам Чернова, как вы можете видеть в Википедии для границ Черноффа.) $H(X) = (52\cdot 6.5 + 76 \cdot 7.5)/128 = 7.09375$ $(52 \cdot 0.5 - 76 \cdot 0.5)/128 \approx 0.99436$ $Q$ $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}$

деревенщина
источник

Я несколько озадачен этим вторым примером. Если у вас 128 кодовых слов, то есть код со средней длиной слова 7 (на самом деле все длины слова имеют 7), что противоречит вашему утверждению о том, что энтропия равна 7.09375. Энтропия этого распределения (которую вы получите, взяв средневзвешенное значение а не среднее), составляет 6,88, а средняя длина кода Хаффмана равна 7. Это дает разрыв (или расхождение Кульбака-Либлера) около 0,12, что, кажется, немного лучше, чем мой пример, но не близко к 1.

- \log_{2} p_{i}

$-\log_2 p_i$

Питер Шор

И действительно, вы правы. Я намеревался спросить об ожидаемой длине кодового слова при распределении вероятности .

p

$p$

Питер Шор

К сожалению, я просчитался о против . Мы все еще хотим, чтобы немного меньше , но что-то вроде , чтобы заставить меньшие записи в нижней строке. Это дает

A

$A$

B

$B$

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.$

Карл

На самом деле это было бы ... но эта система уравнений не имеет положительного решения - кажется, мы не можем заставить все быть полуцелыми степенями . Таким образом, вместо и мы можем рассмотреть, например, для половины кода Хаффмана и для остальных, давая записей ...

2 A + B

$2A+B$

2

$2$

\sqrt{2}

$\sqrt{2}$

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$

Карл

Итак, попробуйте это (не оптимально - я полагаю, это зависит от того, как вы решили округлить вверх или вверх). записи с вероятностью и записей с вероятностью имеют энтропию . Вместо этого измените это на записи с вероятностью и записей с вероятностью . Энтропия этого распределения равна что дает 6,4023, в то время как энтропия кода Хаффмана равна 7,5 при равномерном, иТак что, если я не просчитался (и я делаю часто), это дает пробел около

64

$64$

1 / 128

$1/128$

128

$128$

1 / 256

$1/256$

7.5

$7.5$

64

$64$

1 / 128 \sqrt{2}

$1/128\sqrt{2}$

128

$128$

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

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

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$ .

Карл