В данном задании вам предстоит реализовать архиватор посредством алгоритма Хаффмана.
Программа-архиватор должна иметь следующий интерфейс командной строки:
archiver -c archive_name file1 [file2 ...]
- заархивировать файлыfil1, file2, ...
и сохранить результат в файлarchive_name
.archiver -d archive_name
- разархивировать файлы из архиваarchive_name
и положить в текущую директорию. Имена файлов должны сохраняться при архивации и разархивации.archiver -h
- вывести справку по использованию программы.
Алгоритм сжатия устроен следующим образом:
- Подсчитывается частотность 8-битных символов в файле. Кроме содержимого файла надо учесть частоты символов в имени файла, а также добавить три служебных символа
FILENAME_END=256
,ONE_MORE_FILE=257
,ARCHIVE_END=258
с частотами 1. Назначение этих символов будет описано позже. Таким образом, для кодирования расширенного алфавита необходимо 9 бит. - Строится бинарный бор кодирования следующей процедурой:
- Для каждого символа алфавита добавляется соответствующая вершина в очередь с приоритетом. Упорядочение вершин в очереди осуществляется по неубыванию частот символов в файле (в "начале" очереди всегда вершина с символом с наименьшей встречаемостью в файле).
- Пока в очереди больше одного элемента, из нее последовательно извлекаются две вершины A и B с минимальными приоритетами. Создается новая вершина С, детьми которой являются вершины A и B. Вершина C помещается в очередь с приоритетом, равным сумме приоритетов вершин A и B.
- По окончанию процедуры в очереди остается ровно одна вершина, которая является корнем построенного бора. Листовые вершины являются терминальными. В каждой терминальной вершине записан символ из исходного файла. Каждая нетерминальная вершина дерева содержит два ребра: левое и правое, которые помечаются битами 0 и 1 соответственно. Каждой терминальной вершине соответствует битовая последовательность, получающаяся спуском из корня бора к терминальной вершине и выписыванием битов всех пройденных ребер. Для наглядности можно воспользоваться следующими иллюстрациями:
- Всем символам ставится в соответствие бинарная кодовая последовательность посредством построенного бора.
- Код приводится к канонической форме. Каноническая форма кода отличается тем, что позволяет однозначно восстановить коды по списку символов и длинам кодов для них. Алгоритм восстановления канонического кода есть в википедии.
- Все символы файла заменяются на соответствующие кодовые бинарные последовательности, и результ записывается вместе со вспомогательной информацией в файл. Формат файла архива описан ниже.
Алгоритм декодирования в целом обратен алгоритму кодирования и устроен следующим образом:
- Из файла восстанавливается таблица кодирования (соответствие между сиволами и их кодами).
- По таблице кодирования строится бинарный бор.
- По бинарным последовательностям, прочитанным из входного файла, производится трассировка по бору от корня к листовым вершинам. При достижении очередной листовой вершины бора определяется соответсвующий ей символ, который записывается в выходной файл.
Девятибитные значения записываются в формате "от младшего к старшему" (аналог little-endian для битов). Т.е. сначала идет бит, соответствующий 2^0
, затем - 2^1
и т.д. до бита, соответствующего 2^8
. Чтобы программа была портируемой, нельзя полагаться на то, что порядок битов в файле соответствует порядку битов в бинарном представлении чисел в памяти.
Файл с архивом должен иметь следующий формат:
- 9 бит - количество символов в алфавите
SYMBOLS_COUNT
- Блок данных для восстановления канонического кода
SYMBOLS_COUNT
значений по 9 бит - символы алфавита в порядке следования канонических кодов- Список из
MAX_SYMBOL_CODE_SIZE
значений по 9 бит, i-й (при нумерации с 0) элемент которого - это количество символов с длиной кодаi+1
.MAX_SYMBOL_CODE_SIZE
- максимальная длина кода в текущем кодировании. Канонические коды соответствуют по порядку символам из предыдущего пункта.MAX_SYMBOL_CODE_SIZE
не записывается явным образом в файл, т.к. его можно восстановить по имеющимся данным.
- Закодированное имя файла
- Закодированный служебный символ
FILENAME_END
- Закодированное содержимое файла
- Если в архиве есть ещё фалы, то закодированный служебный символ
ONE_MORE_FILE
и кодировка продолжается с п.1. - Закодированный служебный символ
ARCHIVE_END
.
Старайтесь делать все компоненты программы по возможности более универсальными и не привязанными к специфике конкретной задачи. Например, алгоритмы кодирования и декодирования должны работать с потоками ввода-вывода, а не файлами.
Програма должна корректно обрабатывать очень большие (во много раз превосходящие по объему оперативную память) файлы. Это означает, что при работе программы данные не должны накапливаться в памяти.
Файлы с форматом, не соответствующим спецификации, не должны приводить к "падению" программы. Все исключительные ситуации должны корректно обрабатываться с выводом понятного пользователю сообщения об ошибке.
Скорее всего, вам понадобятся следующие компоненты:
- Обертки над потоками ввода-вывода, позволяющие читать и писать значения по 1 и 9 бит.
- Бор с интерфейсом, позволяющим удобно его обходить.
- Очередь с приоритетами.
Подробный дизайн программы рекомендуется обсудить с преподавателем на семинарах.
Проект проверяется преподавателями без использования системы автоматической проверки. Все сдачи будут проходить код ревью.
Вам предстоит написать всю программу с нуля, включая файлы CMakeLists.txt
.
В отличие от обычных домашних заданий, проект надо коммитить/пушить в репозиторий вручную, без использования скрипта submit.py
.
Для сдачи проекта надо завести новую ветку projects/archiver
(выполняется один раз, при повторных отправках кода создавать ветку не нужно):
git checkout -b projects/archiver
Чтобы закоммитить изменения в ветку, используйте команды git add
и git commit
. Чтобы отправить изменения в удаленный репозиторий, выполните команду git push student projects/archiver
. Старайтесь писать осмысленные пояснения к коммитам.
После загрузки кода в удаленный репозиторий создайте в нем merge request из ветки projects/archiver
в main
и установите в качестве ревьюера вашего преподавателя.
В интернете много материалов по работе с git, например этот туториал.
Базовая реализация программы предусматривает максимальную оценку в 8 баллов.
Больше баллов можно получить, если:
- Самостоятельно реализовать очередь с приоритетами без использования стандартных очередей, алгоритмов и коллекций, обеспечивающих сортированность. Реализация должна быть алгоритмически эффективной, т.е. иметь сложность вставки и извлечения не более O(logN), где N - число элементов в очереди.
- Покрыть юнит тестами все критичные компоненты. Ваш семинарист поможет с определением достаточности покрытия.
23:59 6 октябрая 2021