«Основные алгоритмы сжатия данных»

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

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

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

Пусть алфавит, все возможные одноэлементные цепочки; - вероятности появления элементов. Разобьем полуинтервал на 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*/