Постройте дерево Хаффмана для сообщения: a) КОСА КОРКА КОРА

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

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

Также напишите код каждого символа(типо К-0110)

И определите коэффициент сжатия

Вопрос: Постройте дерево Хаффмана для сообщения: а) КОСА КОРКА КОРА б) ТРОС КРОТ ТОСТ в) КОВКА КОНКА КОКОН Для построения дерева Хаффмана, следует выполнить следующие шаги: 1. Подсчитываем частоту встречаемости каждого символа в сообщении. а) КОСА КОРКА КОРА К: 2 раза О: 3 раза С: 1 раз А: 2 раза Р: 1 раз б) ТРОС КРОТ ТОСТ Т: 3 раза Р: 1 раз О: 2 раза С: 1 раз К: 1 раз в) КОВКА КОНКА КОКОН К: 4 раза О: 3 раза Н: 1 раз В: 1 раз А: 2 раза 2. Создаем узлы для каждого символа и присваиваем им частоту встречаемости. а) К: 2, О: 3, С: 1, А: 2, Р: 1 б) Т: 3, Р: 1, О: 2, С: 1, К: 1 в) К: 4, О: 3, Н: 1, В: 1, А: 2 3. Соединяем узлы с наименьшей частотой встречаемости, чтобы создать новый узел. Сумма частот встречаемости нового узла становится его новой частотой встречаемости. а) К: 2, О: 3, С: 1, А: 2, Р: 1 - Соединяем Р и С: С+Р = 1+1 = 2 - Соединяем А и О: А+О = 2+3 = 5 - Соединяем новые узлы: 2+5 = 7, снова соединяем К с новым узлом: К+7 = 2+7 = 9 б) Т: 3, Р: 1, О: 2, С: 1, К: 1 - Соединяем Р и С: С+Р = 1+1 = 2 - Соединяем К и О: К+О = 1+2 = 3 - Соединяем новые узлы: 3+2 = 5, снова соединяем Т с новым узлом: Т+5 = 3+5 = 8 в) К: 4, О: 3, Н: 1, В: 1, А: 2 - Соединяем В и Н: В+Н = 1+1 = 2 - Соединяем А и О: А+О = 2+3 = 5 - Соединяем новые узлы: 5+2 = 7, снова соединяем К с новым узлом: К+7 = 4+7 = 11 4. Повторяем шаг 3, пока не получим одно дерево. а) 9 / \ К 7 / \ 2 С / \ Р 5 / \ А О б) 8 / \ Т 5 / \ 2 С / \ Р 3 / \ К О в) 11 / \ К 7 / \ 2 5 / \ / \ В Н А О 5. Присваиваем биты ветвям дерева Хаффмана: левой ветви - 0, правой ветви - 1. а) 9 / \ К 7 / \ 2 С / \ Р 5 / \ А О К - 0 Р - 10 А - 110 О - 111 б) 8 / \ Т 5 / \ 2 С / \ Р 3 / \ К О Т - 0 Р - 10 К - 110 С - 111 в) 11 / \ К 7 / \ 2 5 / \ / \ В Н А О К - 0 В - 10 Н - 110 А - 1110 О - 1111 6. Код каждого символа: а) К - 0, О - 111, С - 10, А - 110, Р - 1 б) Т - 0, Р - 10, О - 111, С - 11, К - 110 в) К - 0, В - 10, Н - 110, А - 1110, О - 1111 7. Вычисляем коэффициент сжатия. Для этого суммируем количество бит, необходимых для представления всех символов в сообщении до построения дерева Хаффмана, и количество бит, необходимых для представления символов после построения дерева. а) Исходное сообщение: КОСАКОРКАКОРА - Код К: 1 бит (0) - Код О: 3 бита (111) - Код С: 2 бита (10) - Код А: 3 бита (110) - Код Р: 1 бит (1) Общее количество бит до использования дерева Хаффмана: 1+3+2+3+1 = 10 бит - Код К: 1 бит (0) - Код О: 3 бита (111) - Код С: 2 бита (10) - Код А: 3 бита (110) - Код Р: 1 бит (1) Общее количество бит после использования дерева Хаффмана: 1+3+2+3+1 = 10 бит Коэффициент сжатия: 10/10 = 1 (не сжато) б) Исходное сообщение: ТРОСКРОТТОСТ - Код Т: 1 бит (0) - Код Р: 2 бита (10) - Код О: 2 бита (111) - Код С: 2 бита (11) - Код К: 3 бита (110) Общее количество бит до использования дерева Хаффмана: 1+2+2+2+3 = 10 бит - Код Т: 1 бит (0) - Код Р: 2 бита (10) - Код О: 2 бита (111) - Код С: 2 бита (11) - Код К: 3 бита (110) Общее количество бит после использования дерева Хаффмана: 1+2+2+2+3 = 10 бит Коэффициент сжатия: 10/10 = 1 (не сжато) в) Исходное сообщение: КОВКАКОНКАКОКОН - Код К: 1 бит (0) - Код О: 3 бита (111) - Код В: 2 бита (10) - Код Н: 3 бита (110) - Код А: 4 бита (1110) Общее количество бит до использования дерева Хаффмана: 1+3+2+3+4 = 13 бит - Код К: 1 бит (0) - Код О: 3 бита (111) - Код В: 2 бита (10) - Код Н: 3 бита (110) - Код А: 4 бита (1110) Общее количество бит после использования дерева Хаффмана: 1+3+2+3+4 = 13 бит Коэффициент сжатия: 13/13 = 1 (не сжато) В данном случае коэффициент сжатия равен 1, что означает, что использование дерева Хаффмана не приводит к сжатию данных.