Архиватор

Архиватор реализован на основе алгоритма Хаффмана.

Программа-архиватор имеет следующий командный интерфейс:

• archiver -c archive_path file1 [file2 ...] - заархивировать файлы file1, file2, ... и сохранить результат в файл archive_path.
• archiver -d archive_path - разархивировать файлы из архива archive_path и положить в текущую директорию.
• archiver -h - вывести справку по использованию программы.

Имена файлов (без дополнительного пути) сохраняются при архивации и разархивации.

Алгоритм

Алгоритм сжатия устроен следующим образом:

1. Подсчитывается частотность 8-битных символов в файле и символов в имени файла. Также добавляются три служебных символа FILENAME_END=256, ONE_MORE_FILE=257, ARCHIVE_END=258 с частотами 1. Таким образом, для кодирования расширенного алфавита используется 9 бит.
2. Строится бинарный бор кодирования следующей процедурой:
   1. Для каждого символа алфавита добавляется соответствующая вершина в очередь с приоритетом. Упорядочение вершин в очереди осуществляется по неубыванию частот символов в файле (в "начале" очереди всегда вершина с символом с наименьшей встречаемостью в файле), а при равенстве частот - по возрастанию символов (для вершин, не являющихся листьями, в качестве символа для сравнения используется наименьший из символов их потомков).
   2. Пока в очереди больше одного элемента, из нее последовательно извлекаются две вершины A и B с минимальными приоритетами. Создается новая вершина С, детьми которой являются вершины A и B. Вершина C помещается в очередь с приоритетом, равным сумме приоритетов вершин A и B.
   3. По окончанию процедуры в очереди остается ровно одна вершина, которая является корнем построенного бора. Листовые вершины являются терминальными. В каждой терминальной вершине записан символ из исходного файла. Каждая нетерминальная вершина дерева содержит два ребра: левое и правое, которые помечаются битами 0 и 1 соответственно. Каждой терминальной вершине соответствует битовая последовательность, получающаяся спуском из корня бора к терминальной вершине и выписыванием битов всех пройденных ребер. Наглядные иллюстрации:
   • gif demo
   • gif demo
   • graphic demo.
3. Всем символам ставится в соответствие бинарная кодовая последовательность посредством построенного бора.
4. Код приводится к канонической форме.
5. Все символы файла заменяются на соответствующие кодовые бинарные последовательности, и результат записывается вместе со вспомогательной информацией в файл. Формат файла архива описан ниже.

Алгоритм декодирования в целом обратен алгоритму кодирования и устроен следующим образом:

1. Из файла восстанавливается таблица кодирования.
2. По таблице кодирования строится бинарный бор.
3. По бинарным последовательностям, прочитанным из входного файла, производится трассировка по бору от корня к листовым вершинам. При достижении очередной листовой вершины бора определяется соответсвующий ей символ, который записывается в выходной файл.

Формат файла

Для обеспечения кросс-платформенной совместимости байт значение читаем и записываем начиная со старшего бита до младшего.

Пример: дана последовательность unsigned char {1, 3, 7, }. Требуется прочитать из неё два 9-битных значения a и b. Представление на битовом уровне:

10000000 11000000 11100000
aaaaaaaa abbbbbbb bb

Следовательно, a = 257, b = 259.

Файл с архивом должен иметь следующий формат:

1. 9 бит - количество символов в алфавите SYMBOLS_COUNT
2. Блок данных для восстановления канонического кода
   1. SYMBOLS_COUNT значений по 9 бит - символы алфавита в порядке следования канонических кодов
   2. Список из MAX_SYMBOL_CODE_SIZE значений по 9 бит, i-й (при нумерации с 0) элемент которого - это количество символов с длиной кода i+1. MAX_SYMBOL_CODE_SIZE - максимальная длина кода в текущем кодировании. Канонические коды соответствуют по порядку символам из предыдущего пункта. MAX_SYMBOL_CODE_SIZE не записывается явным образом в файл, т.к. его можно восстановить по имеющимся данным.
3. Закодированное имя файла
4. Закодированный служебный символ FILENAME_END
5. Закодированное содержимое файла
6. Если в архиве есть ещё фалы, то закодированный служебный символ ONE_MORE_FILE и кодировка продолжается с п.1.
7. Закодированный служебный символ ARCHIVE_END.

Реализация

BitReader и BitWriter, которые позволяют считывать поток и записывать в поток побитово. Архиватор использует FileBitReader и FileBitWriter, которые уже работают с файлами.

Для удобного взаимодействия с командами, был написан парсер командной строки.

Код Хаффмана хранится в LongCode размера 258 бит, хотя на практике такой длинный код может сгенерироваться, только если сжимать файл астрономического размера :)

В интерфейсе также показывается время архивации и коэффициент сжатия.

Доработки

• Возможность архивировать папки (в том числе пустые и вложенные)
• Progress bar во время архивирования/разархивирования
• Ускорение архивации/разархивации