код хаффмана



Дерево хаффмана

Автор Костя Соколов задал вопрос в разделе Другие языки и технологии

Метод Хаффмана и получил лучший ответ

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

Ответ от Wind in the wild[гуру]
смысл алгоритма в том, что наиболее часто встречающиеся байты кодируются меньшим числом бит

Ответ от Ёерый[гуру]
плохо гуглил,

Ответ от Alexey N[гуру]
Считаете частоту появления букв, потом сортируете их (частоту) по возрастанию.
Потом строите дерево - берете две самые редкие буквы, обьединяете в узел двоичного дерева и присваеваете ему суммарный вес, вставляете его обратно. Продолжаете пока не останется только один узел. Обходите Все дерево и для каждого листа-буквы строите код хаффмана (из нулей-лево и единиц-право). Записываете на выход дерево, и по битам читаете входной файл и пишете на выход строки из 0 и 1, которые посчитали на предыдущем шаге.

Ответ от 3 ответа[гуру]
Привет! Вот подборка тем с ответами на Ваш вопрос: Метод Хаффмана

перечислите и охарактеризуйте основные алгоритмы сжатия данных
Алгоритмы сжатия данных
[править] Алгоритмы сжатия без потерь

* Преобразование
подробнее...
Код Хаффмана на Википедии
Посмотрите статью на википедии про Код Хаффмана
 

Ответить на вопрос:

Имя*

E-mail:*

Текст ответа:*
Проверочный код(введите 22):*