Дерево хаффмана
Автор Костя Соколов задал вопрос в разделе Другие языки и технологии
Метод Хаффмана и получил лучший ответ
Ответ от Макс Пушкарев[гуру]
Принцип кодирования по Хаффману
Сжатие данных производится в два этапа. На первом этапе считываются данные, которые должны подвергнуться сжатию; на втором определяется частота встречаемости отдельных байтов данных, которые могут принимать значения от 0 до 255.
Рассмотрим пример. Пусть требуется сжать словосочетание:
ПРОГРАММИРОВАНИЕ КОМПРЕССИИ БЕЗ ПОТЕРЬ
До сжатия данных каждая буква представляется числом, которое лежит между 0 и 255. Если применяется так называемая альтернативная кодовая таблица (содержащая знаки русского алфавита) , то буквы имеют значения между 128 и 159 (а-я) , между 160 и 175 (а-п) и между 224 и 239 (Р-я) , а пробел - значение 32. Запись приведенного словосочетания потребовала бы 38 байт - по одному байту на букву или пробел. Чтобы снизить размеры файла при записи, определим вначале частоту встречаемости отдельных букв:
Источник: Если надо полное решение в Excele пиши на мало!
смысл алгоритма в том, что наиболее часто встречающиеся байты кодируются меньшим числом бит
плохо гуглил,
Считаете частоту появления букв, потом сортируете их (частоту) по возрастанию.
Потом строите дерево - берете две самые редкие буквы, обьединяете в узел двоичного дерева и присваеваете ему суммарный вес, вставляете его обратно. Продолжаете пока не останется только один узел. Обходите Все дерево и для каждого листа-буквы строите код хаффмана (из нулей-лево и единиц-право). Записываете на выход дерево, и по битам читаете входной файл и пишете на выход строки из 0 и 1, которые посчитали на предыдущем шаге.