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

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

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

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

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

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

Вы вычислили энтропию не для конкретной строки, а для случайного источника символов, который генерирует с вероятностью  и и  с вероятностью  каждый без корреляции между последовательными символами. Рассчитанная энтропия для этого распределения означает, что вы не можете представлять строки, сгенерированные из этого распределения, используя в менее битов на символ.$A$$\tfrac{8}{10}$$B$$C$$\tfrac1{10}$$0.922$$0.922$

Может быть довольно сложно разработать код, который достиг бы такой скорости. ^* Например, кодирование Хаффмана будет выделять коды , и  к , и  , соответственно, в течение в среднем  бит на символ. Это довольно далеко от энтропии, хотя все же намного лучше, чем наивное кодирование двух битов на символ. Любая попытка лучше кодирования , вероятно , будет использовать тот факт , что даже пробег десять раз подряд s более вероятно (вероятность ) , чем один  .$0$$10$$11$$A$$B$$C$$1.2$$A$$0.107$$B$

---

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

Вот конкретная кодировка, которая может представлять каждый символ в среднем менее чем 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 = 2$$n$

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

$$\frac{8}{10} \cdot \frac{8}{10} \cdot 1 + 3 \cdot \frac{8}{10} \cdot \frac{1}{10} \cdot 3 + \frac{1}{10} \cdot \frac{8}{10} \cdot 4 + 4 \cdot \frac{1}{10} \cdot \frac{1}{10} \cdot 6 = 1.92$$ $1.92/2 = 0.96$

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

Для каждого мы можем построить префиксные коды такие, что $n$$C_n\colon \{A,B,C\}^n \to \{0,1\}^*$

$$\lim_{n\to\infty} \frac{\operatorname*{\mathbb{E}}_{X_1,\ldots,X_n \sim \mathcal{D}}[C_n(X_1,\ldots,X_n)]}{n} = H(\mathcal{D}).$$

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

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