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

Начало: 05 октября 2006 года.
Конец: 22 октября 2006 года

Цель задания

Необходимо написать программу, которая умеет сжимать файл и распаковывать его, используя классический алгоритм арифметического сжатия, описанный на лекциях, и простой вариант 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-архив с исходными текстами и исполняемыми файлами, названный по схеме GGG_Z_V_nnnnnnnn.zip (где G - трехзначный номер группы, Z - номер задания, V - номер версии задания, nnnnnnnn - номер студенческого билета) присылайте на

Например, студент 306 группы с номером студенческого билета 05015042, сдающий обновленную (вторую) версию программы по первому заданию, должен прислать архив с именем 306_1_2_05015042.zip.

Также смотрите здесь, какие файлы нам присылать и как их оформить

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