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

21

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

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

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

Теперь рассмотрим случай, когда все вероятности очень малы. Предположим , вы выбираете распределение вероятностей M букв, каждая из которых имеет вероятность 1/M . В этом случае самый большой разрыв возникает, если вы выберете M2kln2 . Здесь вы получите разрыв около

1+lnln2ln2ln20.08607.
Это лучшее, что вы можете сделать в ситуации, когда все вероятности малы?

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

Питер Шор
источник

Ответы:

19

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

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

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

Во-первых, если вы определяете среднюю длину кода, используя равномерное распределение по кодовым словам, и берете в качестве верхней границы вероятности любого одного элемента, то рассмотрите код длины где кодовые слова имеют длину а остальные имеют длину . Для распределения, идеально закодированного этим кодом, средняя длина приближается к , если только у вас нет нижней границы для вероятности одного элемента, тогда как энтропия равна . q + k 2 q - 1 q 2 q + k - 1 q + k q + k q + k2qq+k2q1q2q+k1q+kq+kq+k2

Теперь давайте рассмотрим «среднюю длину», означающую среднюю длину кодового слова, когда код Хаффмана используется для кодирования . Здесь граница жесткая, и пример распределения, достигающего ее в пределе, - это случай, в котором каждый элемент встречается с вероятностью для(Последнему элементу назначается любая оставшаяся вероятность, но она не будет иметь никакого значения асимптотически).2 д ± 1 / 2 кв Z .p2q±1/2qZ.

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

A=52,B=76522 - 6,5 762 - 7,5A+B=128,A2+B/2128,maxAZA дает . Наше распределение имеет элемента с вероятностью , с вероятностью , и один элемент получает остатки.A=52,B=765226.57627.5

Тогда , в то время как код Хаффмана достигает потерь энтропии. (Между прочим, потеря энтропии имеет имя, независимо от того, используете ли вы кодирование Хаффмана или произвольное кодирование для : расхождение Кульбака-Либлера . Использование этого, как я обнаружил несколько дней назад, приводит к более жестким двусторонним границам Чернова, как вы можете видеть в Википедии для границ Черноффа.)( 52 0,5 - 76 0,5 ) / 128 0,99436 Q D ( P | | Q ) = Σ р я войти р IH(X)=(526.5+767.5)/128=7.09375(520.5760.5)/1280.99436QD(PQ)=pilogpiqi+(1pi)log1pi1qi

деревенщина
источник
1
Я несколько озадачен этим вторым примером. Если у вас 128 кодовых слов, то есть код со средней длиной слова 7 (на самом деле все длины слова имеют 7), что противоречит вашему утверждению о том, что энтропия равна 7.09375. Энтропия этого распределения (которую вы получите, взяв средневзвешенное значение а не среднее), составляет 6,88, а средняя длина кода Хаффмана равна 7. Это дает разрыв (или расхождение Кульбака-Либлера) около 0,12, что, кажется, немного лучше, чем мой пример, но не близко к 1.log2pi
Питер Шор
И действительно, вы правы. Я намеревался спросить об ожидаемой длине кодового слова при распределении вероятности . p
Питер Шор
К сожалению, я просчитался о против . Мы все еще хотим, чтобы немного меньше , но что-то вроде , чтобы заставить меньшие записи в нижней строке. Это даетB A AB 2kA+2B=2kA= 2 - 1 / A2+B/22kA+2B=2kA=21/221B.
Карл
На самом деле это было бы ... но эта система уравнений не имеет положительного решения - кажется, мы не можем заставить все быть полуцелыми степенями . Таким образом, вместо и мы можем рассмотреть, например, для половины кода Хаффмана и для остальных, давая записей ...2 2A+B2 1/2 (1+x)/2k(1-x)/2 k + 1 32k1/2(1+x)/2k(1x)/2k+132k
Карл
Итак, попробуйте это (не оптимально - я полагаю, это зависит от того, как вы решили округлить вверх или вверх). записи с вероятностью и записей с вероятностью имеют энтропию . Вместо этого измените это на записи с вероятностью и записей с вероятностью . Энтропия этого распределения равна что дает 6,4023, в то время как энтропия кода Хаффмана равна 7,5 при равномерном, иТак что, если я не просчитался (и я делаю часто), это дает пробел около641/1281281/2567.5641/12821281/256(21/2)1/(22)7.5+(11/(2(2)))5.802(121.5)7+21.58=7.3535.0.95 .
Карл