Написать программу, которая умеет упаковать-распаковать файл с использованием кодов Хаффмана.
Алфавит - 8 бит, 1 байт, 256 символов.
На входе:
- файл, который надо упаковать или распаковать
- указание, что надо сделать (или 2 отдельные программы для упаковки-распаковки)
- имя файла-результата
Построение дерева:
- начало - весь алфавит в родном порядке слева-направо
- находим самого левого самого маленького - А1
- находим самого левого самого маленького кроме А1 - А2
- строим новое дерево А3(left=А1, right=А2)
- удаляем из леса А1 и А2
- добавляем в лес А3 справа
- после построения дерева - левые связи помечаем '0', правые - '1'
Формат файла:
- первые 4 байта заполним символами 'HF16'
- следующие 1024 байта заполняем таблицей статистики исходного файла. По 4 байта на каждый из 256 символов. интерпретируется как unsigned int32 big endian.
- дальше идут собственно упакованные данные как поток бит. Т.е. /1001/ /10001/ /10/ /0/ /1001/ займет 2 байта, а не 5 и не 10. Т.е. выходной поток будет такой: /10011000/ /11001001/ а не такой: /10010000/ /10001000/ /10000000/ /0000000/ /10010000/. Последний байт, который потенциально не заполнен до конца, добиваем '0'.
Контроль целостности осуществляем по размеру (количеству байт) в исходном файле. Т.е. останавливаемся при распаковке если уже достигли нужного размера, и наоборот, если упакованный файл закончился до заполнения нужного размера - сообщаем об ошибке.