Задача Задача №3438795
А
А
Добры бобры идут в боры сожми эту скороговорку с помощью алгоритма Хаффмана и найди коэффициент сжатия
Ниже — упрощённое решение задачи на основе частотного кодирования Хаффмана для строки: "Добры бобры идут в боры".
- Подсчёт частот символов
- Д: 1
- о: 3
- б: 4
- р: 3
- ы: 3
- пробел: 4
- и: 1
- д: 1
- у: 1
- т: 1
- в: 1
Всего символов: 23.
- Построение дерева Хаффмана и кодирование символов Один из возможных вариантов кодов, полученных при стандартном построении дерева (лево=0, право=1):
- Д (Д uppercase) — 0000
- и — 0001
- д — 0010
- у — 0011
- т — 0100
- в — 0101
- о — 011
- р — 100
- ы — 101
- пробел — 110
- б — 111
Где длины кодов: 4 бита для символов с частотой 1, 3 бита для символов с частотой 3 и 3 бита для пробела и буквы «б».
- Закодированная строка (битовая последовательность) Разбиваем по исходным символам, используя приведённые выше коды:
- Д: 0000
- о: 011
- б: 111
- р: 100
- ы: 101
- : 110
- б: 111
- о: 011
- б: 111
- р: 100
- ы: 101
- : 110
- и: 0001
- д: 0010
- у: 0011
- т: 0100
- : 110
- в: 0101
- : 110
- б: 111
- о: 011
- р: 100
- ы: 101
Итого длина зашифрованной строки: 75 бит.
- Коэффициент сжатия
- Оригинальный размер: 23 символа × 8 бит = 184 бита (предполагаем кодировку 8 бит на символ).
- Сжатый размер: 75 бит.
Коэффициент сжатия (отношение сжатого размера к исходному):
- R = 75 / 184 ≈ 0.4087
Обратный коэффициент (как много раз больше оригинал по размеру после сжатия, иногда его требуют):
- 184 / 75 ≈ 2.45
Прессинг по строке даёт примерно 40.9% сохраняемого объёма от исходного размера (около 59.1% экономии).
- Примечания
- Данная конфигурация кодов Хаффмана зависит от порядка соединения равных частот. Другие варианты дерева могут дать немного иные коды, но общая средняя длина битов близка к 3.26 бит/символ при данных частотах.
- Если использовать другую кодировку на входе (например, UTF-8, где кириллица может занимать 2 байта и выше), оригинальный размер будет другим (например, 46 байт = 368 бит), и коэффициенты будут соответствующим образом изменены.
Хочешь, могу привести альтернативный набор кодов Хаффмана (при другой последовательности объединения узлов) и показать, как меняются отдельные кодовые слова и итоговый битовый размер?
