Урок №12. Использование графов и деревьев при описании объектов и процессов окружающего мира
Ты уже знаешь о моделировании и особенностях использования графов для решения определенных задач. Сегодня ты научишься использовать графы в решении задач, связанных с кодированием. Но для начала вспомним, что тебе уже известно о кодах.
Коды бывают равномерными (кодовые слова имеют одинаковую длину) и неравномерными (кодовые слова имеют разную длину). Неравномерные коды
позволяют сократить среднюю длину кодового слова, тем самым уменьшив объем информации, необходимый для передачи сообщения. Однако при использовании неравномерных кодов возникает проблема разделения кодовых слов в сообщении, так как неизвестно, где заканчивается одно слово и начинается другое. Для решения этой проблемы можно использовать разделители между кодовыми словами или построить так называемые разделимые (префиксные) коды.
Для обеспечения однозначного и правильного декодирования сообщения без использования разделителей используют префиксный (неравномерный) код, удовлетворяющий условию Фано.
Одним из способов построения оптимальных префиксных кодов является метод Хаффмана, в котором используется двоичное дерево (связный граф, в котором каждая вершина имеет не более двух смежных вершин). Метод Хаффмана заключается в том, что по заданному алфавиту и вероятностям появления его символов в сообщении строится двоичное дерево, в котором листья соответствуют символам используемого алфавита. Ребра между метками помечают символами 0 или 1. Кодовое слово для каждого символа получается путем записи меток на ребрах, от корня дерева до соответствующего листа. Такой метод гарантирует минимальную среднюю длину кодового слова для данного алфавита.
Рассмотрим пример.
Задача 1. Дано сообщение «ИНФОРМАТИКА». По данному сообщению построй код Хаффмана. Определи количество различных букв в строке, размер получившейся закодированной строки (длина бинарного кода), коды букв в формате «буква: код» и закодированную строку.
Решение.
Вычислим частоту встречаемости букв в сообщении «ИНФОРМАТИКА». Получим следующие значения:
Построим код Хаффмана, объединяя на каждом шаге две вершины с наименьшей встречаемостью в одну вершину, помечая ребра между ними символами 0 или 1. Получим следующий граф:
Определим коды букв, следуя от листьев к корню дерева, записывая метки на ребрах. Получим следующие коды:
Выведем ответ в требуемом формате:
Количество различных букв: 9.
Размер закодированной строки: 35.
Закодированная строка: 00 100 1010 1011 1100 1101 01 1110 00 1111 01.
Задача 2.По каналу связи передаются сообщения, содержащие только пять букв: А, Б, В, Г, Д. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 0, Б — 10, В — 110. Укажи кодовое слово, которое можно использовать для буквы Г. Слово должно быть наименьшей возможной длины. Если таких слов несколько, укажи то из них, которое соответствует наименьшему возможному двоичному числу.
Решение.
Построим код Хаффмана для букв А, Б и В:
Найдем свободные ветки для размещения оставшихся букв Г и Д. Свободная ветка — 111. Можно сформировать коды 1110 и 1111. Выбираем ту ветку, которая имеет наименьшую длину и наименьшее двоичное число. Это ветка 1110, следовательно, присваиваем этот код букве Г. Букве Д присваиваем код 1111.
Ответ: 1110.
Разберем еще несколько заданий и их возможные решения.
Задача 1. У исполнителя Калькулятор три команды, которым присвоены следующие номера:
- Вычти 3;
- Умножь на 4;
- Возведи в квадрат.
Программа для исполнителя Калькулятор — последовательность команд, где первая уменьшает число на экране на 3, вторая — увеличивает его в 4 раза, третья — возводит число в квадрат. Сколько существует программ у исполнителя Калькулятор, которые число 1 преобразуют в число 256?
Эту задачу легко решить с помощью дерева, если построить все возможные операции. Выполним построение:
Из рисунка видно: чтобы получить из числа 1 число 256, нужно выполнить следующие команды:
Способ 1: выполнить команды 1-2-3-2;
Способ 2: выполнить команды 1-3-2-3;
Способ 3: выполнить команды 1-3-3-3;
Способ 4: выполнить команды 2-2-2-2;
Способ 5: выполнить команды 2-3-2-2;
Способ 6: выполнить команды 3-2-2-3;
Способ 7: выполнить команды 3-2-3-3.
Следовательно, существует семь программ, которые преобразуют число 1 в число 256.
Ответ: 7.
Но это аналитический способ решения. Можно решать эту задачу и средствами программирования.