saitsharipov/zipmehuffman

🗃 My implementation of archive compression using the Huffman algorithm. The course "Information theory and coding theory" by I.V. Chizhov at CMC MSU. 🌱 Spring 2022.

🗃 Использование оптимальных кодов для сжатия данных: ZIPmeHuffman

🎓 Курс: Теория информации и теория кодирования
👨🏼‍🏫 Преподаватель: Чижов Иван Владимирович
👨🏻‍💻 Выполнил: Шарипов Саит, группа 519/2

---

📝 Краткое описание задания:

Требуется реализовать программу сжатия данных по методу Хаффмана. Программа должна работать в двух режимах:

1. На вход подаётся бинарный файл. Программа сжимает файл и сохраняет его в расширении zmh.
2. На вход подаётся файл с расширением zmh. Программа выполняет разархивирование файла.

🔗 Подробное описание задания и принцип его оценивания.

---

✅ Решение:

Примечание: по согласованию с Иваном Владимировичем использовалась внешняя библиотека bitarray.

📄 Описание формата zmh:

При архивировании в выходном файле кроме сжатой версии исходного файла file_bytes требуется также хранить построенный код Хаффмена, который представляет собой словарь: {byte_val: byte_code}, где byte_val обозначает значение байта, а byte_code обозначает код Хаффмена для этого байта.

При разархивировании нужно будет отличать байты сжатой версии file_bytes от байтов словаря. Для этого можно хранить число, равное размеру одного из них. Так как различных byte_val не более 256, то выгоднее хранить кол-во записей в словаре в виде одного байта size_dict, а всё что после словаря считать сжатым представлением исходного файла.

При разархивировании для правильной обработки каждой записи словаря {byte_val: byte_code} требуется знать, сколько бит занимает byte_code. Для этого для каждой такой записи предлагается также хранить байт size_byte_code, соответствующий числу значащих битов в byte_code. Одного байта хватит, так как длина byte_code <= 255 битов (т.к. даже в случае наличия в исходном файле всех различных byte_val длина максимального byte_code будет 255 бит).

Для того чтобы учесть, что последний байт сжатого представления исходного файла может быть неполным, будем перед file_bytes хранить байт size_last_byte, который кодирует число битов в последнем байте file_bytes.

Кроме того нужно хранить расширение extension_name исходного файла. Для этого будем кодировать длину имени расширения в байтах с помощью одного байта size_byte_extension, а после него хранить extension_name.

📟 Команды ZIPmeHuffman:

• Запуск ZIPmeHuffman в режиме сжатия:
  • python3 main.py -f test_data/WarAndPeace.txt -m 1
• Запуск ZIPmeHuffman в режиме разархивирования:
  • python3 main.py -f test_data/WarAndPeace.zmh -m 2
• Запуск ZIPmeHuffman в режиме тестирования:
  • В этом режиме входной файл сначала сжимается в архив, а затем происходит его разархивирование в новый файл к имени которого прибавляется _new. Происходит проверка того, что входной и выходной файлы полностью совпадают.
  • python3 main.py -f test_data/WarAndPeace.txt -m 3

⌨️ Команды других архиваторов:

Первая команда для архивирования, а вторая для разархивирования.

• ZIP:
  • time zip WarAndPeace.zip WarAndPeace.txt
  • time unzip WarAndPeace.zip
• 7z:
  • time 7za a WarAndPeace.7z WarAndPeace.txt
  • time 7za e -y WarAndPeace.7z
• RAR:
  • time rar a WarAndPeace.rar WarAndPeace.txt
  • echo y | time unrar e WarAndPeace.rar
• TAR:
  • time tar -cf WarAndPeace.tgz WarAndPeace.txt
  • time tar -xf WarAndPeace.tgz

📈 Сравнение архиваторов по размеру сжатия:

🔗 CSV с результатами.

Примечание: На графике не изображены последние три файла из таблицы для того, чтобы была лучше видна разница файлах среднего размера.

Filename	Input size (bytes)	ZMH size (bytes)	ZIP size	7z size	RAR size	TAR size
📚 empty_file.txt	0	4	178	106	72	1536
📚 one_byte_file.txt	1	10	185	143	76	2048
📚 equal_bytes.txt	44000	5509	241	216	110	45568
📚 mom_frame.txt	26	43	200	160	97	2048
📚 WarAndPeace.txt	1267920	672654	357466	265711	297584	1269760
📚 file_without_extension	148	77	210	180	111	2048
🌇 msu_small.jpeg	9659	10431	9690	9657	9692	11264
🌇 msu_big.jpeg	1023245	1023093	1008911	1011313	1010414	1025024
🎵 music_examle.mp3	3755407	3698357	3575468	3586433	3581309	3757056
🎵 bon_jovi_its_my_life.mp3	8987211	8950991	8914829	8945927	8987211	8989184
🎥 video_short.mp4	4072587	4070770	4043617	4044041	4072587	4074496

⬇️ Сравнение архиваторов по скорости сжатия:

Filename	ZMH time	ZIP time	7z time	RAR time	TAR time
📚 empty_file.txt	0.013	0,008	0,022	0,026	0,017
📚 one_byte_file.txt	0.0073	0,009	0,025	0,027	0,009
📚 equal_bytes.txt	0.0217	0,008	0,025	0,011	0,009
📚 mom_frame.txt	0.0086	0,008	0,025	0,027	0,009
📚 WarAndPeace.txt	0.2820	0,129	0,302	0,075	0,013
📚 file_without_extension	0.0090	0,011	0,022	0,026	0,010
🌇 msu_small.jpeg	0.0130	0,008	0,021	0,027	0,009
🌇 msu_big.jpeg	0.2710	0,049	0,139	0,060	0,012
🎵 music_examle.mp3	0.9709	0,142	0,424	0,150	0,019
🎵 bon_jovi_its_my_life.mp3	2.3399	0,310	1,061	0,362	0,029
🎥 video_short.mp4	1.0675	0,128	0,487	0,169	0,019

⬆️ Сравнение архиваторов по скорости разархивирования:

Filename	ZMH time	ZIP time	7z time	RAR time	TAR time
📚 empty_file.txt	0.0005	0,007	0,029	0,008	0,008
📚 one_byte_file.txt	0.0006	0,008	0,022	0,008	0,011
📚 equal_bytes.txt	0.0051	0,007	0,023	0,011	0,008
📚 mom_frame.txt	0.0012	0,007	0,023	0,008	0,009
📚 WarAndPeace.txt	0.2849	0,016	0,040	0,018	0,011
📚 file_without_extension	0.0003	0,007	0,023	0,012	0,008
🌇 msu_small.jpeg	0.0042	0,009	0,022	0,012	0,007
🌇 msu_big.jpeg	0.3516	0,017	0,058	0,017	0,010
🎵 music_examle.mp3	1.3227	0,038	0,170	0,033	0,014
🎵 bon_jovi_its_my_life.mp3	3.1839	0,073	0,175	0,062	0,019
🎥 video_short.mp4	1.4281	0,038	0,054	0,031	0,013

🧠 Анализ результатов:

Из приведенных выше таблиц и графиков можно увидеть:

• Размер сжатого представления у различных архиваторов, включая ZIPmeHuffman совпадает на небольших и больших файлах. Различие видно на текстовом файле средней длины - русскоязычном томе "Войны и мир". На нем TAR показал аномально плохой результат, а наш архиватор проиграл оставшимся. Однако на маленьких и больших файлах наш архиватор показал конкурентноспособный результат.
• Что касается скорости сжатия и разархивирования, то наш архиватор ZIPmeHuffman показывает конкурентноспособный результат на небольших файлах, но проигрывает остальным по скорости на файлах среднего и большого размера.
• Отметим интересную разницу в поведениях архиваторов при сжатии и разжатии. Мы можем видеть, что чем больше файл, тем медленнее ZIPmeHuffman и при сжатии и при разжатии. Однако, если говорить о других архиваторах, то у них время сжатия также возрастает с увеличением размера файла, но при распаковке они демонстрируют относительно одинаковое время независимо от размера файла.
• Возможно, что остальные архиваторы лучшим образом кодируют словарь Хаффмана. Причем мы видим, что это не для того, чтобы сжать получше (на больших файлах, где скорее всего будут глубокие деревья Хаффмана и байты будут кодироваться внушительным числом битов кодировать менее выгодно чем на файлах, в которых меньшая неоднородность byte_val). Скорее эти архиваторы более эффективно кодируют словарь Хаффмана и благодаря этому могут быстрее сжимать и разжимать файлы, а также показывать хорошее качество на средних файлах. Например, они могут использовать кодирование длинных серий одинаковых битов или другие дополнитлеьные идеи.

🧑🏻‍⚖️ Выводы:

• Наш архиватор ZIPmeHuffman решает поставленную задачу. В ходе тестирования было выявлено, что если сначала сжать файл, а затем распаковать его в новый файл то входной и выходной файлы будут полностью совпадать.
• Архиватор ZIPmeHuffman корректно работает на:
  • Пустом файле.
  • Файле из одного байта.
  • Большшого файла, в котором повторяется один байт, а значит дерево Хаффмана имеет глубину 1.
  • Файла без указанного расширения. Это было важно проверить, так как в нашей реализации расширение кодируется при сжатии.
  • На примере из описания задания.
  • На большом тексте, таком как "Война и мир".
  • На изображениях.
  • Аудио.
  • Видео.
• В вопросе сжатия данных ZIPmeHuffman показал конкурентноспособный результат, но в скорости с ростом размера файла остальные архиваторы начинают обгонять наш. Вероятно это связано с различными оптимизациями или с другим кодированим словаря Хаффмана.