Вопрос: Постройте дерево Хаффмана для сообщения:
а) КОСА КОРКА КОРА
б) ТРОС КРОТ ТОСТ
в) КОВКА КОНКА КОКОН
Для построения дерева Хаффмана, следует выполнить следующие шаги:
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, что означает, что использование дерева Хаффмана не приводит к сжатию данных.
