Ребятки помогите чайнику найти решение

[PAV]

Вообще говоря, противоречия тут нет. Две последовательности $\{x_n\}$ и $\{y_n\}$, такие что $x_n < y_n$ для любого $n$, легко могут стремиться к одному и тому же числу.

Иными словами, один метод кодирования может быть лучше другого (неасимптотически), при том что асимптотически они стремятся к одному и тому же.

[Егор]

Меня терзают смутные сомнения по поводу того, как понимать оптимальность Хаффмана.

1. Например, пусть один символ встречается с вероятностью 1/4, а другой - с вероятностью 3/4. Энтропия равна

$$ -\frac14\log_2\frac14-\frac34\log_2\frac34\approx 0,81. $$

Но ведь код Хаффмана будет тратить на каждый символ по одному биту, и среднее число битов на символ будет равно 1?

2. Не относится ли оптимальность всех этих Шеннонов, Хаффманов и АК лишь к ситуации, когда каждый символ независим от предыдущих? Ведь если есть зависимость от контекста, то ясно, что PPM (rar, 7zip) или хотя бы BWT с последующим сжатием (bzip2) дадут существенно более короткий код.

[PAV]

Егор писал(а):

Меня терзают смутные сомнения по поводу того, как понимать оптимальность Хаффмана.

Пусть задан набор сообщений с вероятностями их появления. Требуется каждому сообщению приписать кодовое слово (закодировать) так, чтобы было возможно обратное декодирование любой последовательности. Алгоритм Хаффмана дает код с наименьшей средней длиной кодового слова ("среднее" в смысле математического ожидания относительно заданного распределения на словах).

Стремление же к энтропийной границе будет наблюдаться, если кодировать не отдельные сообщения, а блоки из этих сообщений. Асимптотически энтропийная граница будет при стремлении длины блока к бесконечности.

[Егор]

PAV писал(а):

Стремление же к энтропийной границе будет наблюдаться, если кодировать не отдельные сообщения, а блоки из этих сообщений. Асимптотически энтропийная граница будет при стремлении длины блока к бесконечности.

Спасибо за объяснение! Интуитивно понимаю так: при кодировании по Хаффману длины кодов сообщений довольно близки к соответствующим величинам $-\log_2 p_i$. Объединение в блоки делает величины $-\log_2 p_i$ большими, а "ошибки округления" - относительно малыми. Видимо, кодирование больших блоков по Хаффману будет асимптотически оптимальным и в случае контекста фиксированной длины (т. е., к примеру, если распределение вероятностей зависит от десяти предыдущих сообщений).

[PAV]

Да, все верно. По поводу зависимостей очень похоже на правду, хотя не могу 100% сказать, что знаю это. Но наверняка это есть в любой книге по теории кодирования.

Добавлено спустя 4 минуты 28 секунд:

В принципе, в случае зависимости от контекста можно при переходе к следующему блоку пересчитывать вероятности всего следующего в зависимости от предыдущего и строить код Хаффмана для этого. Правда, это достаточно долго, так как проводить эту процедуру придется и при кодировании, и при декодировании. Но результат будет лучше.

[esperanto]

PAV писал(а):

Да, все верно. По поводу зависимостей очень похоже на правду, хотя не могу 100% сказать, что знаю это. Но наверняка это есть в любой книге по теории кодирования.
.

да, асим=ая оптимальность достигается и для марковских источников, любого конечного порядка марковости