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

Цель задания

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

Описание задания

Введение

Задача - достичь как можно большего сжатия без потерь.

Ваши архиваторы будут проверены на 5 тестовых файлах (которые неизвестны
заранее).

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

  • Арифметическое сжатие (допустим ТОЛЬКО алгоритм с нормализацией, которая
    рассмотрена на лекции).
  • Варианты PPM
  • Другие методы сжатия (LZ-арифметик, LZ-Huffman, BWT, гибридные).

Все результаты (с фамилиями авторов, естественно) будут сведены в таблицу,
отсортированную по степени сжатия.

За первое место в любой номинации (после собеседования по алгоритму) -
дополнительные баллы вплоть до экзамена автоматом.

За второе и третье место - дополнительные баллы.

Если файл не совпадает с паковавшимся, компрессор падает или работает более 3
минут, ему присваивается значение худшего результата в замере.

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

  1. Адаптивную (или блочно-адаптивную) реализацию арифметического сжатия.
  2. Подбор параметров агрессивности сжатия (возможно динамический, т.е. во время
    работы программы).
  3. Начальная инициализация таблиц вероятностей наиболее подходящими значениями.
    (Возможно - смена таблиц при изменении характера данных).
  4. Увеличение точности алгоритма арифметического сжатия (использование int64 &
    float)

  5. Если вам этого кажется мало - реализуйте PPM (как минимум простой, рассказанный
    на лекции, с любыми дополнениями, которые вы найдете в
    http://compression.ru/book/pdf/compression_methods_part1_2-4.pdf
    )

Выполнение данного задания позволяет получить баллы, необходимые для получения
высокой оценки за курс.

ВНИМАНИЕ! Из-за ваших ошибок возможно программа не заработает (такое бывает постоянно), поэтому настоятельно рекомендуется подавать ВСЕ задания. Ибо иначе вы рискуете не сдать курс.

Обязательная часть

Программа должна уметь получать на вход файл и по опции «с» - сжимать его, по
опции «d» распаковывать его.

По умолчанию должен использовать арифметический алгоритм сжатия с методом
нормализации, описанном на лекциях.

Программа должна быть консольным приложением и запускаться так:

     compress c in_file.txt  out_file.cmp ppm
     compress d out_file.txt out_file.txt
  

Т.е. тестовый файл test.bat вида:

     compress c file1     file1.cmp ari
     compress d file1.cmp file1_out
     compress c file2     file2.cmp ari
     compress d file2.cmp file2_out
     compress c file3     file3.cmp ari
     compress d file3.cmp file3_out
     compress c file4     file4.cmp ari
     compress d file4.cmp file4_out
     compress c file5     file5.cmp ari
     compress d file5.cmp file5_out
  

должен сжимать 5 тестовых файлов (file1, ... file5), причем все файлы до сжатия
(fileX) должны полностью совпадать с файлами после распаковки (fileX_out).

Общая степень сжатия замеряется по сумме размеров файлов
fileX.cmp

Дополнительная часть

Для повышения степени сжатия (и набора дополнительных баллов) можно реализовать
алгоритм PPM.

С ним ваша программа должна уметь выполнять тестовый файл
test_ppm.bat вида:

     compress c file1     file1.cmp ppm
     compress d file1.cmp file1_out
     compress c file2     file2.cmp ppm
     compress d file2.cmp file2_out
     compress c file3     file3.cmp ppm
     compress d file3.cmp file3_out
     compress c file4     file4.cmp ppm
     compress d file4.cmp file4_out
     compress c file5     file5.cmp ppm
     compress d file5.cmp file5_out
  

Рекомендуется реализовать PPM1 и PPM2 (порядок модели 1 и 2) как
минимум. Если вы реализуете больше - замечательно.

Литература

  1. Настоятельно рекомендуется найти книгу "Методы сжатия данных." Диалог-МИФИ
    (Ватолин, Ратушняк, Смирнов, Юкин) Ссылки на интернет-магазины, в которых она
    есть:

    http://www.findbook.ru/search/d0?s=1&pvalue=%CC%E5%F2%EE%E4%FB+%F1%E6%E0%F2%E8%FF&r=1&ptype=1

  2. Для написания программы с PPM рекомендуется использовать
    compr_lossless.pdf

Требования к программе

Главное требование - выполнить обязательную часть задания.

Язык реализации – С или С++

Программа обязательно должна быть консольной (никакого интерфейса - обычный
архиватор).

За использование чужих исходных текстов или совместное написание - программы
всех участников будут сниматься с замеров, и будет выставляться 0 баллов. В
качестве альтернативы желающим все-таки получить высокую оценку будет
предложено реализовать более сложный алгоритм.

Программа должна устойчиво работать с файлами большого размера. Т.е. если
программе на вход дать файл размером 10Мб, то на Pentium4-1700 она должна
отработать за 3 минуты, не упасть и корректно распаковать архив.

Внимательно изучите требования к
сдаваемым работам
на сайте. В частности 0 баллов ставится, если вы
забудете исходные тексты.

Оформление работы

Правила организации ZIP-архива, который вы посылаете как результат вашей работы
по заданию, четко определены.

Структура следующая:

readme.txt

bin
   yourprogname.exe
    ... 
 src
   yoursource.cpp
yoursource.h
...

В корневом каталоге архиве должен быть файл readme.txt и два подкаталога: exe

и src. Оба подкаталога могут в свою очередь содержать подкаталоги.

В каталоге exe должны находится все исполняемые файлы (обычно один) и
необходимые файлы данных (Проверьте, чтобы программа работала при запуске не
из среды программирования! А еще лучше - на другой машине)

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

Если вы пользуетесь Microsoft Visual C++ 5.0/ 6.0, то в каталог srс обычно
достаточно положить файлы *.cpp, *.h, *.dsw, *.dsp, *.res, *.rc, *.ico, *.rc2 с
сохранением подкаталогов. Подкаталоги Release и Debug не нужны: вашу
скомпилированную программу нужно скопировать в каталог exe вашего архива. Как
правило, архив не должен занимать более 300-500 килобайт.

За нарушение данных требований и, следовательно, усложнение работы проверяющих
будет сниматься 1 балл.

Файл readme.txt должен быть текстовым файлом в любой кодировке. Не нужно
присылать файлы в формате MS Word или HTML. Для создания файла нужен только
Notepad.

Формат файла такой:

ФИО: [Фамилия Имя Отчество]
Группа: [номер группы] Задание: [ номер задания] / [название задания] подзадание 1: [[+/-]] подзадание 2: [[+/-]] ... подзадание M: [[+/-]] Система: [система программирования] ОС: [операционная система] Аппаратура: [конфигурация машины] Комментарии: [комментарии по реализации / пожелания и т.д.]



Подзадания указаны в формулировке задания. В файле readme.txt вы должны
указать те из них, которые вы реализовали [+] или не реализовали [-], по вашему
мнению. В поле "Аппаратура" указывайте конфигурацию машины, на
которой выполнялась работа. Внимательно заполняйте файл, - это поможет
проверяющему более оперативно проверить вашу работу,а также в случае каких-либо
недоразумений.

Вот пример правильного оформления файла readme.txt


ФИО: Иванов Василий Петрович
Группа: 203 Задание: 1 / Универсальный архиватор файлов база: [+] PPM1: [-] PPM2: [+] Система: MS VC++ ОС: Windows 2000 Аппаратура: PIII-866, 512Mb, NVidia GeForce2 Pro 64Mb Комментарии:
Дополнительно реализован новый изобретенный мной метод сжатия файлов

 

НЕ ЗАБУДЬТЕ ПОЛОЖИТЬ В АРХИВ файл readme.txt.

Для сдачи работы необходимо зарегистрироватся в системе.

© Лаборатория компьютерной графики при ВМиК МГУ