Необходимо написать программу, которая умеет сжимать файл и распаковывать его,
используя классический алгоритм арифметического сжатия, описанный на лекциях, и
простой вариант PPM.
Задача - достичь как можно большего сжатия без потерь.
Ваши архиваторы будут проверены на 5 тестовых файлах (которые неизвестны
заранее).
Замер будет проводиться в трех номинациях:
-
Арифметическое сжатие (допустим ТОЛЬКО алгоритм с нормализацией, которая
рассмотрена на лекции).
-
Варианты PPM
-
Другие методы сжатия (LZ-арифметик, LZ-Huffman, BWT, гибридные).
Все результаты (с фамилиями авторов, естественно) будут сведены в таблицу,
отсортированную по степени сжатия.
За первое место в любой номинации (после собеседования по алгоритму) -
дополнительные баллы вплоть до экзамена автоматом.
За второе и третье место - дополнительные баллы.
Если файл не совпадает с паковавшимся, компрессор падает или работает более 3
минут, ему присваивается значение худшего результата в замере.
Для повышения степени сжатия своего архиватора рекомендуется
использовать следующие методы:
-
Адаптивную (или блочно-адаптивную) реализацию арифметического сжатия.
-
Подбор параметров агрессивности сжатия (возможно динамический, т.е. во время
работы программы).
-
Начальная инициализация таблиц вероятностей наиболее подходящими значениями.
(Возможно - смена таблиц при изменении характера данных).
-
Увеличение точности алгоритма арифметического сжатия (использование int64 &
float)
-
Если вам этого кажется мало - реализуйте 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) как
минимум. Если вы реализуете больше - замечательно.
-
Настоятельно рекомендуется найти книгу "Методы сжатия данных." Диалог-МИФИ
(Ватолин, Ратушняк, Смирнов, Юкин) Ссылки на интернет-магазины, в которых она
есть:
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
-
Для написания программы с 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.
|