Задание №1 "Универсальный архиватор"

Содержание

Описание
Правила игры
Сборка

Unix
Windows
Docker

Запуск
Описание репозитория

Описание

Вам необходимо реализовать архиватор. Задача — достичь как можно большей степени сжатия без потерь.

Замер будет проводиться в трех номинациях:

Арифметическое сжатие (допустим только алгоритм с нормализацией)
PPM
BWT

Для повышения степени сжатия своего архиватора рекомендуется использовать следующие методы:

Адаптивная (или блочно-адаптивная) реализация арифметического сжатия.
Подбор параметров агрессивности сжатия (возможно динамически, т.е. во время исполнения программы).
Начальная инициализация таблиц вероятностей наиболее подходящими значениями (возможно — смена таблиц при изменении характера данных).
Увеличение точности алгоритма арифметического сжатия (использование int64_t и double).
Если вам этого кажется мало — реализуйте PPM (как минимум простой, рассказанный на лекции, с любыми дополнениями, которые вы можете найти в книге Методы сжатия данных).

Правила игры

За использование чужих исходных текстов или совместное написание — работы всех причастных будут сниматься с замеров, и им будет присуждаться 0 баллов. Подробнее — читайте Stanford CS Honor Code.
Если разархивированный файл не совпадает с исходным, компрессор падает или работает более 3 минут, ему присваивается значение худшего результата в замере.
За первые три места в любой номинации (после собеседования по алгоритму) — дополнительные баллы.

Сборка

Unix

В примере используется пакетный менеджер APT, который по умолчанию стоит на Ubuntu. На macOS можно пользоваться Homebrew, и тогда на 1-2 этапах будет использоваться команда brew вместо apt.

Обновляем package list:
```
sudo apt update
```
Устанавливаем всё необходимое.
```
sudo apt install -y cmake g++ python3
```
Распаковываем архив.
Заходим в папку compressor, создаём папку build и заходим в неё:
```
mkdir build
cd build
```
Теперь конфигурируем проект с помощью CMake, указав ../src как папку с исходниками, а после ключа -G — формат проекта, который мы хотим получить. Например, эта команда сгенерирует самый обыкновенный Makefile:
```
cmake -G "Unix Makefiles" ../src
```
А эта — проект для CodeBlocks:
```
cmake -G "CodeBlocks - Unix Makefiles" ../src
```
Все поддерживаемые форматы можно найти в справке cmake --help. В дальнейшем вам не нужно будет конфигурировать проект повторно.
Собираем проект удобным образом, например:
```
make  # нужно быть в папке compressor/build
```
Проверяем папку compressor/build на наличие исполняемого файла compress.
Тестируем шаблон:
```
cd ..  # поднимаемся из build в папку compressor
python3 tests/run.py
```
После успешного выполнения тестов в папке compression появится файл results.csv, который можно открыть и посмотреть, что тестирование действительно прошло успешно.
Ура, всё получилось! Вы готовы создавать лучший в мире архиватор.

Windows

Эпиграф:

— Надо было ставить Linux!

Cтавим CMake.
Для тестирующего скрипта ставим интерпретатор Python 3.
На всякий случай ставим MinGW по этой ссылке.
Запускаем Windows PowerShell.
Распаковываем архив.
Заходим в папку compressor, создаём папку build и заходим в неё:
```
mkdir build
cd build
```
Теперь конфигурируем проект с помощью CMake, указав ../src как папку с исходниками, а после ключа -G — формат проекта, который мы хотим получить. Например, эта команда сгенерирует MinGW Makefile:
```
cmake -G "MinGW Makefiles" ../src
```
А эта — проект для CodeBlocks:
```
cmake -G "CodeBlocks - MinGW Makefiles" ../src
```
Все поддерживаемые форматы можно найти в справке cmake --help. В дальнейшем вам не нужно будет конфигурировать проект повторно.
Собираем проект удобным образом, например:
```
mingw32-make  # нужно быть в папке compressor/build
```
Проверяем папку compressor/build на наличие исполняемого файла compress.exe.
Тестируем шаблон:
```
cd ..  # поднимаемся из build в папку compression
python tests/run.py
```
После успешного выполнения тестов в папке compression появится файл results.csv, который можно открыть и посмотреть, что тестирование действительно прошло успешно.
Ура, всё получилось! Вы готовы создавать лучший в мире архиватор.

Docker

Чтобы прогнать тесты с докером:

Установите Docker
Склонируйте ваш репозиторий
Соберите образ и запустите контейнер:

docker build . -t compressor_tests
docker run compressor_tests

Так как набирать эти 2 строчки слишком долго, в корне лежит маленький Makefile, который позволяет сократить проверку до 2х слов make tests

Внимание: задания будут проверяться именно этим способом, поэтому желательно протестировать последнюю версию вашей программы с Docker

Запуск

Общий вид:

# Unix
compress [options]

# Windows
compress.exe [options]

Опции:

--help                     = Вызов справки, аналогичной этой.
--input  <file>            = Входной файл для архивации/разархивации, по умолчанию `input.txt`.
--output <file>            = Выходной файл для архивации/разархивации, по умолчанию `output.txt`.
--mode   {c | d}           = Режим работы: `c` - архивация, `d` - разархивация; по умолчанию `c`.
--method {ari | ppm | bwt} = Метод архивации/разархивации файла, по умолчанию `ari`.

Например, если мы хотим заархивировать файл the_financier.txt в файл the_financier.cmp методом PPM, то команда будет выглядеть так:

# Unix
compress --input the_financier.txt --output the_financier.cmp --mode c --method ppm

# Windows
compress.exe --input the_financier.txt --output the_financier.cmp --mode c --method ppm

Описание репозитория

src — папка с исходными файлами:
- main.c — основной файл;
- utils.c — файл, содержащий функции, чтобы парсить аргументы командной строки;
- ari.c, ppm.c, bwt.c — файлы, которые вам нужно изменить, написав соответствующий алгоритм;
- *.h — заголовочные файлы ко всем вышеуказанным;
- CMakeLists.txt — файл, необходимый для генерации нужного вам формата прокета с помощью CMake.
Вообще говоря, никто вас не обязывает использовать именно такую архитектуру решения. Самое главное — ваше решение должно поддерживать указанный формат запуска.
test_files — папка с тестовыми файлами.
tests — папка для тестирования. Содержит:
- testing — содержит необходимые для тестирования скрипты.
- run.py — тестирующий скрипт на языке Python. Его можно использовать для тестирования вашего архиватора следующим образом:
```
python run.py [options]
```
  Опции:
```
--timeout <timeout> = Время, отведённое для тестирования каждого файла, по умолчанию 180с.
--testdir <dir>     = Папка с тестовыми файлами, по умолчанию `test_files`.
--outputdir <dir>   = Папка для выходных файлов, полученных в результате работы архиватора.
--output            = Флаг для сохранения выходных файлов. Если папка не указана с помощью ключа --outputdir, то папка по умолчанию — `output`.
```
  Скрипт сжимает и распаковывает каждый файл, находящийся в указанной папке, вычисляет размер получившихся файлов, сравнивает содержимое и записывает результат по каждому файлу в results.csv.
  
  Возможные вердикты:
  - OK — файл успешно сжат, распакован и совпадает с исходным;
  - WA — файл успешно сжат и распакован, но не совпадает с исходным;
  - RE1 — ошибка выполнения при сжатии;
  - TL1 — превышен таймаут при сжатии;
  - RE2 — ошибка выполнения при распаковке;
  - TL2 — превышен таймаут при распаковке.
- config.cfg — файл с указанием реализованных методов сжатия в формате списка JSON.
  
  Всего допускается 3 значения: "ARI", "PPM", "BWT".
  
  Пример содержимого файла:
```
["ARI", "BWT"]
```
  Этот файл необходим для тестирующего скрипта, чтобы определить, какие методы тестировать.

sadimer/compressor