1 Энтропийная оценка средней длины кода

Учебное пособие Редактор А. В. Крейцер Издательство спбгэту «лэти» 1 97376, С. Петербург, ул. Проф. Попова, 5
2. Деревья поиска Идеально сбалансированные бинарные деревья
2 Случайные бинарные деревья поиска
Абракадабра!, содержащий 12 символов, включая специальный символ !
Задача кодирования сообщений. Префиксные коды и деревья Пусть задан алфавит
1 Код Фано-Шеннона
1 Метод Хаффмана
1 Реализация алгоритмов кодирования
1 Доказательство оптимальности кода Хаффмана Лемма 1
1 Энтропийная оценка средней длины кода
1 Динамическое кодирование по Хаффману
Абракадабра!, содержащий 12 символов, включая специальный символ !
Абракадабра!, содержащий 12 символов, включая специальный символ !
А. Ю. Алексеев с. А. Ивановский д. В. Куликов
При обучении программированию особую трудность вызывает работа с динамическими структурами данных
2. стеки и очереди спецификация стека и очереди
3 Определения дерева, леса, бинарного дерева. Скобочное представление
Примечания и библиографические указания
Списки
Задача о порядке перемножения матриц
С. А. Ивановский разработкакорректныхпрограм м санкт-Петербург 2003
Программирования
Разработка, доказательство корректности и анализ алгоритма
2. основы аналитической верификации программ основные правила аналитической верификации программ
3. индуктивные функции на последовательностях
4. корректность программ при работе с массивами
5. поиск в массиве линейный поиск
Разработка, доказательство корректности
Шень А. Программирование: теоремы и задачи: Учеб пособие

скачать doc

1.8. Энтропийная оценка средней длины кода
Рассмотрим зависимость оптимального значения L_min(W) от входного набора

. Здесь удобно использовать вероятностную интерпретацию: p_i – вероятность появления символа _i во входном потоке, а L(p, l) = _i_=1.._n p_i l_i – математическое ожидание длины кода случайно выбранного символа. Оптимальное значение L(p, l) обозначим как L_min(p).

Определение. Энтропия распределения вероятностей

есть

(считаем, что

).

Лемма 1. Для любых распределений вероятностей p и

справедливо неравенство

.

Неравенство переходит в равенство тогда и только тогда, когда

для всех

.

Доказательство.







.

Так как функция

строго выпукла и касательной к кривой

в точке (0, 0) служит прямая y = x, то справедливо неравенство

, причём при

имеем даже

. Поэтому

, ч. т. д.

Утверждение. Пусть

для

и L_min(p) – средняя длина слова некоторого оптимального префиксного кода с априорным распределением p. Тогда

.

Доказательство. 1) Докажем левое неравенство

. Пусть

 длины кодовых слов некоторого оптимального префиксного кода. Положим

. Можно рассматривать

как некоторое распределение вероятностей. Из неравенства Крафта следует, что Q  1, а поэтому log₂Q  0. Из леммы вытекает, что

.

В случае, когда Q = 1 и

для всех i, получим

. Это, следовательно, имеет место, если

, т. е.

.

2) Перейдём к доказательству правого неравенства

. В общем случае

. Поэтому выберем

. Отсюда вытекает, что

и, в частности,

. Тогда

, т. е. для набора

выполняется неравенство Крафта, а следовательно, существует префиксный код с длинами кодовых слов

. Итак,

, ч. т. д.

Следствие из теоремы:

.

Приведенное доказательство позволяет сделать конструктивный вывод: если взять

и построить, исходя из неравенства Крафта, префиксный код для набора

, то этот код будет достаточно хорошим, поскольку для него

.

Отметим, что для существенно неравномерного распределения p энтропия H(p) достаточно мала и средняя длина кода окажется тоже малой. Для равномерного распределения вероятностей

для всех i и энтропия есть

. Если же рассмотреть неравномерное распределение, например такое, что

для i 1..n 1 и

, то для него

. Например, при n =1024 получим

, тогда как при равномерном распределении H(p) = 10.

Интерпретация в терминах задачи поиска (см. 1.3)

Учащимся

Учителям