Основные алгоритмы сжатия данных - Курсовая работа

Содержание

Введение 3

Теоретическая часть 3

1. Основные понятия 3

2. Краткий обзор источников и ПО 4

3. Действия с файлами в процессе его сжатия. 8

4. Статистическая, полуадаптивная и адаптивная схемы сжатия 11

5. Идея и основные алгоритмы арифметического кодирования. 13

6. Принципы моделирования 16

Практическая часть 18

Заключение 22

Список литературы 23

Введение (выдержка)

Современному человеку очень часто приходится работать с различными типами данных. Со временем, количество данных увеличивается и появляется потребность в свободном пространстве на носителях информации. Для решения данной проблемы используют процесс сжатия, который сокращает объем пространства. Данный процесс основан на алгоритмах сжатия данных. О них и пойдет речь в данной работе.

Цель работы – рассказать о процессе сжатия данных, рассмотреть основные механизмы и алгоритмы, лежащие в основе сжатия данных.

Задачи, необходимые для достижения цели:

1. Дать трактовку основных понятий по данной теме;

2. Проанализировать литературу и ПО по данной тематике;

3. Объяснить, что значит «сжать файл» на конкретных примерах;

4. Рассмотреть схемы сжатия;

5. Разобрать алгоритм арифметического кодирования;

6. Выделить основные принципы моделирования;

7. Показать, как работает алгоритм арифметического кодирования на практике.

Основная часть (выдержка)

Пусть алфавит, все возможные одноэлементные цепочки; - вероятности появления элементов. Разобьем полуинтервал на n непересекающихся полуинтервалов соответствующих элементам , причем длина пропорциональна .

Далее строится кодирующая дробь: производится построение системы вложенных полуинтервалов так, что каждый последующий полуинтервал занимает в предыдущем место, соответствующее положению элемента в исходном разбиении полуинтервала . [5]

Кратко процесс выглядит так:

• считывание очередного элемента;

• выбор соответствующего полуинтервала из разбиения текущего полуинтервала (на первом шаге - [0, 1) ).

Заключение (выдержка)

В процессе выполнения курсовой работы были подробно изучены вопросы, связанные с моделированием и кодированием информации в процессе ее сжатия. Была изучена литература по данной тематике, рассмотрены особенности современных архиваторов и проведены тесты на определение скорости и объема сжатия. Изучены наиболее популярные схемы сжатия и изучен алгоритм арифметического кодирования. Рассмотренные теоретические положения были использованы в практической части работы, в которой представлен простейший архиватор, использующий алгоритм арифметического кодирования. «Архиватор» реализован в виде решения на языке С++ в среде Microsoft Visual Studio 2010.

Литература

1. Мозговой, М.В. Занимательное программирование: самоучитель/ М.В. Мозговой – СПб.: Питер, 2005. – 208 с.

2. Окулов, С.М. Программирование в алгоритмах./ С.М. Окулов – М.: БИНОМ. Лаборатория знаний, 2004. – 341 с.

3. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - М.: ДИАЛОГ-МИФИ, 2002. - 384 с.

4. Окулов, С.М. 100 задач по информатике./ С.М.Окулов, А.В.Лапунов. – Киров: Изд-во ВятГПУ, 2000. – 422 с.

5. Прата, С., Язык программирования C++. Лекции и упражнения/С.Прата – М.: Вильямс, 2012 г., 1248 с.

6. Национальный открытый университет [Электрон. ресурс] / 2003-2013. Режим доступа: h**t://w*w.intuit.r*/

7. Словари и энциклопедии на академике [Электрон. ресурс] / 2000-2010. Режим доступа: h**t://dic.academic.r*/