Министерство науки и образования Российской Федерации

Южно-Уральский государственный университет

Приборостроительный факультет

Кафедра Автоматики и Управления

Реферат

По дисциплине «Дискретная математика»

На тему: «Сжатие данных»

Выполнил: Коченгин А.Е

Группы ПС-217

Проверил: Барбасова Т. А.

Г. Челябинск 2011

АННОТАЦИЯ

Коченгин А.Е.Сжатие данных.

Челябинск:ЮУрГУ,ПС-217, 20 с ,

библиограф. список - 4 наим.

Данный реферат является работой по обобщению понятия сжатия данных. В работе были рассмотрены основные понятия сжатия данных и их принципы, алгоритмы RLE, KWE и алгоритм Хаффмана.

Содержание

Введение ………………………………………………………………………4

Понятие сжатия данных…………………………………………………….…5

Принципы сжатия данных…………………………....……………………….7

Алгоритм RLE...……………………………………………………………….11

Алгоритмы KWE……………………………………………………………...12

Алгоритм Хаффмана…………………………………………………….….…13

Алгоритмы сжатия данных неизвестного формата……………………….…17

Системные требования алгоритмов…..…………………………………........18

Библиографический список...…………………………………….……….…..20

Введение

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

Представление информации, которым люди привыкли пользоваться, почти всегда избыточно. Избыточность присутствует в текстах, так как в них обязательно есть повторяющиеся слова, фразы, а то и целые абзацы. Избыточность информации присуща звуковой речи, так как в ней обязательно есть частоты, не слышимые человеком, или не существенные для восприятия. Аналогично, избыточно представление информации в электронном виде, обязательно есть некоторые повторяющиеся символы, цепочки символов. Удалив избыточность, мы можем уменьшить потребности в информационных емкостях, необходимых для хранения информации, и при этом не уменьшив содержательную сторону информации, то есть сохранив возможность восстановления ее к исходному виду. Таким образом, удаляя избыточность информации, можно уменьшить ресурсы, необходимые для хранения и передачи данных.

Любой способ, подход и алгоритм, реализующий сжатие данных, предназначен для снижения объема выходного потока данных при помощи ее обратимого или необратимого преобразования.

Понятие сжатия данных

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

Обратная процедура называется восстановлением данных (распаковкой, декомпрессией).

Сжатие основано на устранении избыточности, содержащейся в исходных данных.

Избыточность — термин из теории информации, означающий превышение количества информации, используемой для передачи или хранения сообщения, над его информационной энтропией

Информацио́нная энтропи́я — мера неопределённости или непредсказуемости информации, неопределённость появления какого-либо символа первичного алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.

Простейшим примером избыточности является повторение в тексте фрагментов (например, слов естественного или машинного языка). Подобная избыточность обычно устраняется заменой повторяющейся последовательности ссылкой на уже закодированный фрагмент с указанием его длины. Другой вид избыточности связан с тем, что некоторые значения в сжимаемых данных встречаются чаще других. Сокращение объёма данных достигается за счёт замены часто встречающихся данных короткими кодовыми словами, а редких — длинными (энтропийное кодирование). Сжатие данных, не обладающих свойством избыточности (например, случайный сигнал или шум, зашифрованные сообщения), принципиально невозможно без потерь. Характерной особенностью большинства типов данных является их избыточность. Степень избыточности данных зависит от типа данных. Например, для видеоданных степень избыточности в несколько раз больше чем для графических данных, а степень избыточности графических данных, в свою очередь, больше чем степень избыточности текстовых данных. Другим фактором, влияющим на степень избыточности является принятая система кодирования. Примером систем кодирования могут быть обычные языки общения, которые являются ни чем другим, как системами кодирования понятий и идей для высказывания мыслей. Так, установлено, что кодирование текстовых данных с помощью средств русского языка дает в среднем избыточность на 20-25% большую, чем кодирование аналогичных данных средствами английского языка.

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

В зависимости от того, в каком объекте размещены данные, подлежащие сжатию различают:

Сжатие (архивация) файлов: используется для уменьшения размеров файлов при подготовке их к передаче каналами связи или к транспортированию на внешних носителях маленькой емкости;

Сжатие (архивация) папок: используется как средство уменьшения объема папок перед долгим хранением, например, при резервном копировании;

Сжатие (уплотнение) дисков: используется для повышения эффективности использования дискового пространства путем сжатия данных при записи их на носителе информации (как правило, средствами операционной системы).

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