Постройте дерево Хаффмана для следующих сообщений: а) КОСА КОРКА КОРА б) ТРОС КРОТ ТОСТ в) КОВКА КОНКА КОКОН . Также

Конечно, давайте решим задачу построения дерева Хаффмана для каждого сообщения:

а) "КОСА КОРКА КОРА"

1. Подсчитаем частоту встречаемости каждого символа в сообщении:
"К" - 1 раз
"О" - 3 раза
"С" - 1 раз
"А" - 1 раз
"Р" - 1 раз

2. Создадим первоначальные узлы для каждого символа и их частоты:
"К" - 1
"О" - 3
"С" - 1
"А" - 1
"Р" - 1

3. Объединим два узла с наименьшей частотой в новый узел и укажем суммарную частоту:
"К" и "С" -> 2
"А" и "Р" -> 2
"КС" и "АР" -> 4

4. Повторим шаг 3 до тех пор, пока все узлы не объединятся в один конечный узел:
"О" и "КСАР" -> 5
"ОКСАР" -> 8

5. Построим дерево Хаффмана:

ОКСАР
/ \
ОКС АР
/ \
О КС
/ \
С К

6. Присвоим код каждому символу. Единице будем присваивать "0", а другим узлам будем присваивать "1", при проходе по левым веткам будем добавлять "0", а по правым веткам - "1":
"О" - 1
"К" - 00
"С" - 01
"А" - 10
"Р" - 11

7. Расшифруем кодировку для первого сообщения:
"КОСА КОРКА КОРА" -> 0110 1 01 10 0110 1 00 10 0110 1 00 11 1

Таким образом, код для каждого символа:
"К" = 00
"О" = 1
"С" = 01
"А" = 10
"Р" = 11

Вес первого сообщения равен 25 символов (5 символов * 5 повторений), а вес закодированного сообщения равен 19 символов. То есть коэффициент сжатия составляет \( \frac{19}{25} = 0.76 \) (округленно до двух десятичных знаков).

б) "ТРОС КРОТ ТОСТ"

1. Подсчитаем частоту встречаемости каждого символа в сообщении:
"Т" - 3 раза
"Р" - 1 раз
"О" - 3 раза
"С" - 1 раз
"К" - 2 раза

2. Создадим первоначальные узлы для каждого символа и их частоты:
"Т" - 3
"Р" - 1
"О" - 3
"С" - 1
"К" - 2

3. Объединим два узла с наименьшей частотой в новый узел и укажем суммарную частоту:
"Р" и "С" -> 2
"К" и "Т" -> 5

4. Повторим шаг 3 до тех пор, пока все узлы не объединятся в один конечный узел:
"О" и "РС" -> 5
"ОРС" и "КТ" -> 10

5. Построим дерево Хаффмана:

ОРСКТ
/ \
ОРС КТ
/ \
О РС
/ \
Р С

6. Присвоим код каждому символу:
"О" - 0
"Р" - 10
"С" - 11
"К" - 01
"Т" - 11

7. Расшифруем кодировку для второго сообщения:
"ТРОС КРОТ ТОСТ" -> 110 10 0 11 01 110 10 01 0 11 01 0 11 11 11

Таким образом, код для каждого символа:
"О" = 0
"Р" = 10
"С" = 11
"К" = 01
"Т" = 110

Вес второго сообщения равен 26 символов (5 символов * 4 повторения + 6 символов * 2 повторения), а вес закодированного сообщения равен 18 символов. Коэффициент сжатия составляет \( \frac{18}{26} = 0.69 \) (округленно до двух десятичных знаков).

в) "КОВКА КОНКА КОКОН"

1. Подсчитаем частоту встречаемости каждого символа в сообщении:
"К" - 6 раз
"О" - 6 раз
"В" - 1 раз
"А" - 1 раз
"Н" - 1 раз
"К" - 1 раз

2. Создадим первоначальные узлы для каждого символа и их частоты:
"К" - 6
"О" - 6
"В" - 1
"А" - 1
"Н" - 1
"К" - 1

3. Объединим два узла с наименьшей частотой в новый узел и укажем суммарную частоту:
"В" и "А" -> 2
"Н" и "К" -> 2
"ОК" и "ВАН" -> 12

4. Повторим шаг 3 до тех пор, пока все узлы не объединятся в один конечный узел:
"ОВАНК" и "ОК" -> 14
"ОВАНКОК" -> 26

5. Построим дерево Хаффмана:

ОВАНКОК
/ \
ОК ОВАНК
/ \
ОВ АНК
/ \
А НК

6. Присвоим код каждому символу:
"О" - 1
"В" - 00
"А" - 010
"Н" - 011
"К" - 10

7. Расшифруем кодировку для третьего сообщения:
"КОВКА КОНКА КОКОН" -> 101 1 00 10 010 1 10 010 10 010 1 10 1 011 1

Таким образом, код для каждого символа:
"О" = 1
"В" = 00
"А" = 010
"Н" = 011
"К" = 10

Вес третьего сообщения равен 26 символов (5 символов * 5 повторений + 6 символов * 3 повторения), а вес закодированного сообщения равен 19 символов. Коэффициент сжатия составляет \( \frac{19}{26} = 0.73 \) (округленно до двух десятичных знаков).

Итак, мы решали задачи построения дерева Хаффмана для трех сообщений: "КОСА КОРКА КОРА", "ТРОС КРОТ ТОСТ" и "КОВКА КОНКА КОКОН". Всего кодировали 57 символов (25 + 26 + 26). Закодированные сообщения составляли 56 символов (19 + 18 + 19). Коэффициент сжатия равен \( \frac{56}{57} = 0.98 \) (округленно до двух десятичных знаков). Обратите внимание, что коды символов в каждом сообщении уникальны и не пересекаются.