Абракадабра!, содержащий 12 символов, включая специальный символ !

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

скачать doc

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

Перед началом кодирования и передатчик (кодировщик), и приемник (декодировщик) знают лишь используемый алфавит (набор элементарных сообщений), в том числе количество символов алфавита (это важно для кодирования первых вхождений). Рассмотрим последовательно все 12 шагов кодирования: А₁Б₂Р₃А₄К₅А₆Д₇А₈Б₉Р₁₀А₁₁!₁₂.

1) Изначально все веса равны нулю, поэтому первая буква А кодируется непосредственно специальным кодом А, а текущее дерево Хаффмана становится таким:

2) Следующий символ Б встречается впервые и кодируется по текущему дереву как 0Б (поскольку 0 – код узла !). Будем далее для краткости запис

ывать это как Б  0Б. Дерево принимает теперь вид

3) Следующий символ Р также встречается впервые, поэтому Р  00Р. Дерево Хаффмана получается заменой листа ! на поддерево с листьями ! и Р и соответствующим изменением весов. Однако здесь уже для сохранения свойства упорядоченности дерева требуется перевешивание узлов в соответствие с ранее описанным алгоритмом, что и изображено на рисунке

4) Второе вхождение символа А, поэтому А  0.

5) Первое вхождение символа К. Кодирование: К  100 К. При модификации дерева перевешивается узел Б со своим предшественником в упорядоченной последовательности.

6) А  0.

7) Первое вхождение Д  1100Д. После перевешивания получаем дерево

8) А  0. В дереве изменяется только вес узла А и корня.

9) Б  110. В дереве меняются местами узлы Б и Р.

10) Р  110. Обратите внимание, что девятый символ Б и десятый символ Р кодируются одним и тем же кодом – 110. Структура дерева не изменяется.

11) А  0. Дерево принимает вид

12) ! 1000!. Этот символ означает конец текста. Перестраивать дерево не требуется.

Итак, входная последовательность АБРАКАДАБРА! Порождает следующий код:

А0Б00Р0100К01100Д011011001000!

     

А А А Б Р А

Учащимся

Учителям