Метод Хаффмана

Принцип кодирования по Хаффману
Сжатие данных производится в два этапа. На первом этапе считываются данные, которые должны подвергнуться сжатию; на втором определяется частота встречаемости отдельных байтов данных, которые могут принимать значения от 0 до 255.
Рассмотрим пример. Пусть требуется сжать словосочетание:

ПРОГРАММИРОВАНИЕ КОМПРЕССИИ БЕЗ ПОТЕРЬ

До сжатия данных каждая буква представляется числом, которое лежит между 0 и 255. Если применяется так называемая альтернативная кодовая таблица (содержащая знаки русского алфавита) , то буквы имеют значения между 128 и 159 (а-я) , между 160 и 175 (а-п) и между 224 и 239 (Р-я) , а пробел - значение 32. Запись приведенного словосочетания потребовала бы 38 байт - по одному байту на букву или пробел. Чтобы снизить размеры файла при записи, определим вначале частоту встречаемости отдельных букв:

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

плохо гуглил, вот

смысл алгоритма в том, что наиболее часто встречающиеся байты кодируются меньшим числом бит