Постройте дерево Хаффмана для следующих сообщений: a) СОБАКА КОРМ-КОРМ КОРОТ б) РОЗА ПЕЩЕРА ХВОСТ в) КАША КОТ КРАСАН

Yana

61

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

Давайте решим эту задачу по шагам.

a) СОБАКА КОРМ-КОРМ КОРОТ:
- Определяем частоту появления каждого символа:

Символ Частота
С 1
О 2
Б 1
А 2
К 4
Р 1
М 1
- Создаем узлы дерева для каждого символа и сортируем их:

Узел Частота
Р 1
М 1
Б 1
С 1
О 2
А 2
К 4
- Объединяем два узла с наименьшей частотой (Р и М) и создаем новый узел с суммарной частотой:

Узел Частота
Р+М 2
-
Остальные узлы:
Узел Частота
Б 1
С 1
О 2
А 2
К 4
- Повторяем объединение узлов:
Узел Частота
Б 1
С 1
Р+М 2
А 2
К 4
-
Узел Частота
Б+С 2
Р+М 2
А 2
К 4
-
Узел Частота
Б+С+Р+М 4
А 2
К 4
-
Узел Частота
Б+С+Р+М+А 6
К 4
- Наконец, объединяем оставшиеся узлы:

Узел Частота
К+Б+С+Р+М+А 10

- Построим дерево Хаффмана для данного сообщения:
К+Б+С+Р+М+А
/ \
К+Б+С+Р+М А
/ \
К+Б+С+Р+М К
/ \
Б+С Р+М
/ \ / \
Б С Р М

- Теперь определим коды каждого символа:
Символ Код
К 00
Б 010
С 011
Р 10
М 110
А 111

b) РОЗА ПЕЩЕРА ХВОСТ:
- Определяем частоту появления каждого символа:

Символ Частота
Р 1
О 1
З 1
А 1
П 1
Е 1
Щ 1
Е 1
Р 1
А 1
Х 1
В 1
О 1
С 1
Т 1
- Создаем узлы дерева для каждого символа и сортируем их:

Узел Частота
Р 2
О 2
А 2
С 2
З 1
П 1
Е 2
Щ 1
Х 1
В 1
Т 1
- Объединяем два узла с наименьшей частотой (Щ и Т) и создаем новый узел с суммарной частотой:

Узел Частота
Щ+Т 2
-
Остальные узлы:
Узел Частота
З 1
П 1
В 1
Х 1
Р 2
О 2
А 2
С 2
Е 2
Щ+Т 2
- Повторяем объединение узлов:
Узел Частота
З 1
П 1
В 1
Х 1
Щ+Т 2
Р 2
О 2
А 2
С 2
Е 2
-
Узел Частота
З+П 2
В 1
Х 1
Щ+Т 2
Р 2
О 2
А 2
С 2
Е 2
-
Узел Частота
З+П+В 3
Х 1
Щ+Т 2
Р 2
О 2
А 2
С 2
Е 2
-
Узел Частота
З+П+В+Х 4
Щ+Т 2
Р 2
О 2
А 2
С 2
Е 2
- Наконец, объединяем оставшиеся узлы:

Узел Частота
Р+О+А+С+Е 10
З+П+В+Х+Щ+Т 8

- Построим дерево Хаффмана для данного сообщения:
РОАС+Е
/ \
Р+О+А+С+Е З+П+В+Х+Щ+Т
- Теперь определим коды каждого символа:
Символ Код
Р 00
О 01
А 10
С 11
З 010
П 011
Е 10
Щ 011
Х 100
В 101
Т 110

в) КАША КОТ КРАСАН КОКОшка:
- Определяем частоту появления каждого символа:

Символ Частота
К 2
А 4
Ш 1
О 3
Т 2
Р 1
С 1
Н 1
К 1
К 1
К 1
Ш 1
А 4
- Создаем узлы дерева для каждого символа и сортируем их:

Узел Частота
Ш 2
Р 1
С 2
Н 1
К 9
А 8
О 3
Т 2

- Объединяем два узла с наименьшей частотой (Ш и Р) и создаем новый узел с суммарной частотой:

Узел Частота
Ш+Р 3
-
Остальные узлы:
Узел Частота
С 2
Н 1
К 9
А 8
О 3
Т 2
- Повторяем объединение узлов:
Узел Частота
С 2
Н 1
Ш+Р 3
А 8
О 3
Т 2
-
Узел Частота
С+Н 3
Ш+Р 3
А 8
О 3
Т 2
-
Узел Частота
С+Н+Ш+Р 6
А 8
О 3
Т 2
-
Узел Частота
С+Н+Ш+Р+О 9
А 8
Т 2
-
Узел Частота
С+Н+Ш+Р+О+А 17
Т 2
-
- Построим дерево Хаффмана для данного сообщения:
С+Н+Ш+Р+О+А
/ \
С+Н+Ш+Р+О Т
/ \
С+Н+Ш+Р А
/ \
С+Н Ш+Р
/ \ / \
С Н Ш Р

- Теперь определим коды каждого символа:
Символ Код
С 00
Н 01
Ш 10
Р 11
О 000
А 001
Т 01

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

Давайте рассчитаем коэффициент сжатия для каждого сообщения:

a) СОБАКА КОРМ-КОРМ КОРОТ:
- Подсчитаем длину сообщения:
Длина сообщения = 16 символов

- Подсчитаем длину закодированного сообщения:
Длина закодированного сообщения:
С = 1 * 4 бит = 4 бит
О = 2 * 3 бита = 6 бит
Б = 1 * 5 бит = 5 бит
А = 2 * 3 бита = 6 бит
К = 4 * 2 бита = 8 бит
Р = 1 * 4 бита = 4 бита
М = 1 * 5 бита = 5 бит
Итого: 4 + 6 + 5 + 6 + 8 + 4 + 5 = 38 бит

- Вычисляем коэффициент сжатия:
Коэффициент сжатия = (длина сообщения в битах) / (длина закодированного сообщения в битах)
Коэффициент сжатия = 16 / 38 = 0.421

b) РОЗА ПЕЩЕРА ХВОСТ:
- Подсчитаем длину сообщения:
Длина сообщения = 12 символов

- Подсчитаем длину закодированного сообщения:
Длина закодированного сообщения:
Р = 2 * 2 бита = 4 бита
О = 2 * 2 бита = 4 бита
А = 2 * 2 бита = 4 бита
С = 2 * 2 бита = 4 бита
З = 1 * 3 бита = 3 бита
П = 1 * 3 бита = 3 бита
Е = 2 * 2 бита = 4 бита
Щ = 1 * 3 бита = 3 бита
Х = 1 * 4 бита = 4 бита
В = 1 * 4 бита = 4 бита
Т = 1 * 4 бита = 4 бита
Итого: 4 + 4 + 4 + 4 + 3 + 3 + 4 + 3 + 4 + 4 + 4 = 45 бит

- Вычисляем коэффициент сжатия:
Коэффициент сжатия = (длина сообщения в битах) / (длина закодированного сообщения в битах)
Коэффициент сжатия = 12 / 45 = 0.267

в) КАША КОТ КРАСАН КОКОшка:
- Подсчитаем длину сообщения:
Длина сообщения = 17 символов

- Подсчитаем длину закодированного сообщения:
Длина закодированного сообщения:
К = 2 * 2 бита = 4 бита
А = 4 * 3 бита = 12 бит
Ш = 1 * 4 бита = 4 бита
О = 3 * 2 бита = 6 бит
Т = 2 * 3 бита = 6 бит
Р = 1 * 3 бита = 3 бита
С = 1 * 3 бита = 3 бита
Н = 1 * 3 бита = 3 бита
Ш = 1 * 4 бита = 4 бита
А = 4 * 3 бита = 12 бит
Итого: 4 + 12 + 4 + 6 + 6 + 3 + 3 + 3 + 4 + 12 = 57 бит

- Вычисляем коэффициент сжатия:
Коэффициент сжатия = (длина сообщения в битах) / (длина закодированного сообщения в битах)
Коэффициент сжатия = 17 / 57 ≈ 0.298

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