Домашнее задание №2 (HW #2)

Напишите программу, выполняющую сжатие двухпроходным алгоритмом Хаффмана.

1. Ограничения.

   • Наибольший размер входного файла — 5MB.
   • Ограничение на время выполнения — 5 секунд.

2. Требования к реализации.

   • Реализация должна быть выполнена в объектно-ориентированном стиле (например, включать классы TreeNode, HuffTree, HuffmanArchiver).
   • Для хранения элементов, там, где это уместно, должна быть использована библиотека STL (например, std::vector, а не динамический массив).
   • Ввод-вывод должен быть выполнен с помощью классов STL (iostream).
   • Должны использоваться исключения.
   • Должен быть реализован свой класс для автоматического тестирования или использована одна из библиотек (google test, doctest, etc).
   • Для методов должны быть написаны автотесты.
   • Действуют все стандартные требования.

3. Примечания.

   • Рекомендуем удостовериться, что сжатый, а затем разжатый Вами файл эквивалентен исходному.
   • Рекомендуем протестировать на больших файлах, файлах разного типа (текстовые, бинарные) и на пустом файле.
   • Рекомендуем проверить свою программу на синтетических тестах, заведомо плохо кодируемых алгоритмом Хаффмана.
   • Рекомендуем проверить свою программу на утечки памяти

4. Параметры командной строки. Значение параметра (если есть) указывается через пробел. Программа должна проверять корректность параметров и выводить сообщение об ошибке.

   • -c: архивирование
   • -u: разархивирование
   • -f, --file <путь>: имя входного файла
   • -o, --output <путь>: имя результирующего файла

5. Вывод на экран. Программа должна выводить на экран статистику сжатия/распаковки: размер исходных данных, размер полученных данных и размер, который был использован для хранения вспомогательных данных в выходном файле (например, таблицы). Не должно выводиться никакого дополнительного текста, только размеры. Все размеры в байтах.

   Например:

   $ ./huffman -c -f myfile.txt -o result.bin
   15678
   6172
   482
   

   Размер исходного файла (исходные данные): 15678 байт, размер сжатых данных (без дополнительной информации): 6172 байта, размер дополнительных данных: 482 байта. Размер всего сжатого файла: 6172 + 482 = 6654 байта.

   $ ./huffman -u -f result.bin -o myfile_new.txt
   6172
   15678
   482
   

   Размер распакованного файла (полученные данные): 15678 байт, размер сжатых данных (без дополнительной информации): 6172 байта, размер дополнительных данных: 482 байта. Размер всего исходного сжатого файла: 6172 + 482 = 6654 байта.

6. Формат сдачи. В директории hw_02 в репозитории должны быть: директория src, директория test, Makefile.

   • Директория src: main.cpp, huffman.h, huffman.cpp

   • Директория test: test.cpp (точка входа), autotest.h, autotest.cpp (реализация класса-родителя тестов), huffman_test.h, huffman_test.cpp (собственно тесты).

   • Makefile:

     • цель по умолчанию собирает исполняемый файл hw_02 и объектные файлы в директорию obj (создается при сборке, если не существует)
     • цель test собирает исполняемый файл hw_02_test и объектные файлы в директорию obj
     • цель clean очищает директорию obj

   • На выполнение задачи дается три недели и три попытки. Раз в неделю присланные решения будут проверяться. Дедлайны:

     • 21 апреля 2021, 22:59 МСК,
     • 28 апреля 2021, 22:59 МСК,
     • 12 мая 2021, 22:59 МСК.