Энтропия Шеннона 0,922, 3 различных значения

14

Учитывая строку значений энтропии Шеннона в логарифм  приходит к 0,922 . Из того, что я понимаю, в базе  2 энтропия Шеннона, округленная в большую сторону, является минимальным числом битов в двоичном коде, чтобы представить одно из значений.AAAAAAAABC20.9222

Взято из введения на этой странице википедии:

https://en.wikipedia.org/wiki/Entropy_%28information_theory%29

Итак, как три значения могут быть представлены одним битом? A  может быть  1 , B  может быть  0 ; но как вы могли бы представлять  C ?

Заранее спасибо.

Шон С
источник

Ответы:

16

Вы вычислили энтропию не для конкретной строки, а для случайного источника символов, который генерирует с вероятностью  и и  с вероятностью  каждый без корреляции между последовательными символами. Рассчитанная энтропия для этого распределения означает, что вы не можете представлять строки, сгенерированные из этого распределения, используя в менее битов на символ.A810BC1100.9220.922

Может быть довольно сложно разработать код, который достиг бы такой скорости. * Например, кодирование Хаффмана будет выделять коды , и  к , и  , соответственно, в течение в среднем  бит на символ. Это довольно далеко от энтропии, хотя все же намного лучше, чем наивное кодирование двух битов на символ. Любая попытка лучше кодирования , вероятно , будет использовать тот факт , что даже пробег десять раз подряд s более вероятно (вероятность ) , чем один  .01011ABC1.2A0,107В


* Оказывается, что нетрудно подобраться так близко, как вы хотите - посмотрите другие ответы!

Дэвид Ричерби
источник
18

Вот конкретная кодировка, которая может представлять каждый символ в среднем менее чем 1 бит:

Сначала разбейте входную строку на пары последовательных символов (например, AAAAAAAABC становится AA | AA | AA | AA | BC). Затем закодируйте AA как 0, AB как 100, AC как 101, BA как 110, CA как 1110, BB как 111100, BC как 111101, CB как 111110, CC как 111111. Я не сказал, что произойдет, если будет нечетное количество символов, но вы можете просто закодировать последний символ, используя произвольную кодировку, на самом деле не имеет значения, когда ввод длинный.

Это код Хаффмана для распределения независимых пар символов, который соответствует выбору в ответе Ювала. Больший приведет к еще лучшим кодам (приближаясь к энтропии Шеннона в пределе, как он упоминал).n=2n

Среднее число битов в паре символов для вышеуказанной кодировки равно т. бита на символ, не так далеко от энтропии Шеннона на самом деле для такого простого кодирования.

8108101+38101103+1108104+41101106=1.92
1.92/2=0,96

nomadictype
источник
13

Пусть будет следующим распределением по : если то и .D{A,B,C}XDPr[X=A]=4/5Pr[X=B]=Pr[X=C]=1/10

Для каждого мы можем построить префиксные коды такие, что nCn:{A,B,C}n{0,1}

limnEX1,,XnD[Cn(X1,,Xn)]n=H(D).

Словом, если мы кодируем большое количество независимых выборок из , то в среднем нам нужно бит на выборку. Наглядно, поэтому мы можем сделать с меньшими затратами , чем один бит, что каждый отдельный образец вполне может быть .DH(D)0.922A

Это реальное значение энтропии, и оно показывает, что вычисление «энтропии» строки является довольно бессмысленным упражнением.A8BC

Юваль Фильмус
источник