Второе домашнее задание. Архиватор (1127041)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Домашнее задание №2.Архиватор.Общее описание заданияЗадание направленно на знакомство с различными алгоритмами сжатия данных и наанализ качества работы указанных алгоритмов. При выполнении задания можно выделитьследующие основные этапы:1.реализация базовых алгоритмов сжатия данных на основе предложенныхшаблонов;2.реализация других алгоритмов сжатия данных (бонус);3.анализ работы реализованных алгоритмов сжатия данных;4.написание отчета, описывающего результаты всех указанных этапов.Задание выполнять в папке Autumn 2014 – Homework 2 в Вашей папке именнойпапке в Dropbox.

Задание должно быть выполнено с использованием системы контроляверсия Git (фактически, в этой папке Вы должны в самом начале создать Git репозиторий).Любые вопросы по заданию присылать по электронной почте на следующий адрес:mikle.shupletsov@gmail.com.Тема письма имеет следующий формат: [318] [Фамилия Имя] [Вопрос].Реализация базовых алгоритмов сжатия.В качестве базовых алгоритмов необходимо реализовать алгоритм арифметическогокодирования (https://en.wikipedia.org/wiki/Arithmetic_coding) с различными моделямиисточника. В качестве базовых моделей источника нужно реализовать по одному изследующих классов моделей:1.

контекстная модель частичного совпадения;2. экспертная модель;3. композиция моделей.Контекстные модели частичного совпадения или, иначе Марковские моделизаданного порядка (https://en.wikipedia.org/wiki/Prediction_by_partial_matching).Предполагается реализация необходимо реализовать контекстную модель заданногопорядка, например, PPM(2) или PPM(3). При этом стоит учитывать, что в распоряжениистудентов есть шаблон заготовка, в которой присутствует базовая реализация PPM(0) иPPM(1).При реализации экспертной модели студент выступает в роли эксперта, которыйобладает специальным знанием о структуре входной последовательности. Например, есливходная последовательность представляет текст на русском языке, то это может бытьинформация о структуре слов (например, какие сочетания букв могут встретиться в языке,а какие нет) или часто встречающихся фрагментов (например, приставки и суффиксы).При этом единственное ограничение, которое накладывается на формулировку модели,заключается в том, что модель должна выдавать распределение вероятностей символовили условной вероятности символа, при реализации заданного контекста.В качестве композиции моделей требуется реализовать один из следующих двухтипов композиции:1.

алгебраическая;2. логическая.Алгебраическая композиция представляет такую композицию моделей, при которойвсе базовые модели выдают свое распределение вероятностей, а потом в рамкахкорректирующей операции производится свертка указанных распределений в одно.Логическая композиция может быть реализована при помощи техники уходов (escapes).Реализация на С++ с использованием заготовкиТребуется реализовать алгоритмы на языке C++. При этом реализация на языке C++должна быть сделана с использованием шаблона, размещенного в Вашей папке.Указанный шаблон содержит реализацию алгоритма арифметического кодирования ибазовых PPM моделей ранга -1, 0 и 1.Заготовка является Вашей отправной точкой в выполнении задания.

Представьте,что Вам был передан частично завершенный проект, который Вам требуется закончить.Поэтому код, написанный Вами, должен быть согласован с изначальной заготовкой.Изменения, вносимые в саму заготовку, должны иметь разумные причины исоответствующим образом задокументированы.Реализация других алгоритмов сжатия (бонус)Дополнительно, можно реализовать другие алгоритмы сжатия данных илиадаптивные модели источников для алгоритма арифметического кодирования.Соответствующий алгоритм или модель должны быть подробно описаны в тексте отчета,и должно быть проведено тестирование качества сжатия полученной при этом реализации.Замеры скорости работы и анализ качества сжатия реализованныхалгоритмов сжатияТестирование полученных реализаций алгоритмов сжатия данных требуетсяпротестировать на следующих типах файлов:1 текст на русском языке в кодировке cp1251;2 текст на русском языке в кодировке UTF-8;3 текст на английском языке (в кодировке cp1251 или UTF-8, в данном случае онинеразличимы);4 данные в формате XML.Студентам предлагается самостоятельно подобрать файлы для тестирования(например, это могут быть фрагменты текстов ваших любимых книг).

При этом тестоваявыборка формируется по следующим правилам. Сначала генерируется по одному файлукаждого из четырех представленных типов размером 1Мб. Далее, каждый файлразбивается на два файла по 512Кб (пополам). При этом каждый фрагмент дополнительноинвертируется. В итоге получается 16 файлов размером 512Кб (половина файловсодержит фрагменты исходных текстов, другая половина содержит указанные фрагментыв инвертированным виде). Тестовая выборка состоит из файлов размером 1Мб,полученной из указанных 16 файлов объединением(конкатенацией) произвольной парыфайлов.Независимо от тестирования, проводимого студентами, реализации алгоритмовбудут тестироваться на скрытой выборке преподавателями. На основе результатовскрытого тестирования будет проведен конкурс.

Стоит отметить, что результаты конкурсане влияют на оценку задания.Требования к отчетуОтчет по заданию должен содержать следующие основные разделы:1 Введение.2 Постановка задачи.3 Описание алгоритма сжатия данных и адаптивных моделей источника.4 Результаты тестирования алгоритмов и анализ качества сжатия данных.5 Использование системы контроля версий.6 Заключение.7 Список литературы.Раздел «Введение» кратко описывает суть практического задания и его мотивацию.Раздел «Постановка задачи» описывает формальную постановку задачи с учетомвыбранных подходов к построению алгоритма сжатия данных и адаптивных моделейисточника.Раздел «Описание алгоритма сжатия данных и адаптивных моделей источника»содержит подробное описание выбранного алгоритма (или алгоритмов) сжатия данных иформальное описание используемых адаптивных моделей источника с указаниемосновных параметров и стратегии обновления модели.Раздел «Результаты тестирования алгоритмов и анализ качества сжатия данных»содержит описание того, как тестировалась программа.

Должна быть представленаинформация об используемой тестовой выборке. Должен быть проведен анализ качествасжатия на тестовой выборке с построением соответствующих графиков, иллюстрирующихкачество сжатия данных (замеры производить каждые 256 символов входного файла).Раздел «Использование системы контроля версий» содержит описание того, каксистема контроля версий использовалась при выполнении задания. Кроме того, должнабыть приведена статистика по числу коммитов, ветвей и других показателей, которыеможно рассчитать при использовании системы контроля версий.Раздел «Заключение» кратко описывает результаты практической работы, а такжевыводы, которые можно сделать из результатов тестирования.Раздел «Список литературы» содержит ссылки на статьи и электронные ресурсы,если таковые были упомянуты в тексте отчета.Критерии оценкиРезультаты выполнения домашнего задания оцениваются по следующим основнымкритериям:1 корректность и качество реализации моделей источников для сжатия данных;2 использование системы контроля версий;3 качество оформления кода (styleguide);4 тестирование программы и анализ производительности;5 документирование кода;6 структура и содержание отчета..

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов учебной работы