Основное использование вычислительной техники связано с хранением и передачей информации, вследствие чего возникает задача об экономном методе ее записи. <...> Основное использование вычислительной техники связано с хранением и организацией доступа к информации. <...> При этом возникает задача о сжатии данных. <...> Цель сжатия данных – обеспечить компактное представление данных, вырабатываемых источником, для их более экономного хранения и передачи по каналам связи. <...> Все способы сжатия можно разделить на две категории: обратимое и необратимое сжатие. <...> Обратимое сжатие, или сжатие без потерь, приводит к снижению объема выходного потока информации без изменения его информативности, т. е. без потери информационной структуры. <...> Из выходного потока, полученного после выполнения алгоритма обратимого сжатия, при помощи декодирования получается поток, в точности совпадающий с исходным. <...> Таким образом, сжатие с потерями состоит из двух этапов: а) выделение сохраняемой части информации с помощью модели, зависящей от цели сжатия; б) сжатие без потерь. <...> 3 Методы сжатия без потерь Рассмотрим методы сжатия без потерь на основе статистических алгоритмов (кодирование по Хаффману и арифметическое кодирование), а также на основе алгоритма RLE. <...> Тогда при кодировании очередного элемента i вероятностей F принимает одно из возможных значений k ответственно H H= числить по формуле H = −P H = − k k P – вероятность того, что F принимает k -е значение, которому соответствует набор вероятностей p s генерации всех возможных элементов .i где k k ( )i s Статистические алгоритмы нуждаются в знании вероятностей появления символов, оценкой, которой может являться частота появления символов во входных данных. <...> Среднюю длину кодов в битах можно выP pk s( )log ( ) , s распределение F и со С учетом этого статистические алгоритмы можно разделить на три класса: • Неадаптивные. <...> Таблица вероятностей символов не передается вместе с файлом, поскольку она известна <...>
Методы_сжатия_Методические_указания.pdf
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Ярославский государственный университет им. П. Г. Демидова
Кафедра компьютерных сетей
Методы сжатия
Методические указания
Рекомендовано
Научно-методическим советом университета
для студентов, обучающихся по специальности
Прикладная математика и информатика
Ярославль 2009
1
Стр.1
УДК 519.2
ББК В 182я73
М 54
Рекомендовано
Редакционно-издательским советом университета
в качестве учебного издания. План 2009 года
Рецензент
кафедра компьютерных сетей
Ярославского государственного университета им. П. Г. Демидова
Составитель М. В. Краснов
сжатия:
Методы
М 54
метод.
указания
/ сост.
М. В. Краснов; Яросл. гос. ун-т им. П. Г. Демидова. –
Ярославль : ЯрГУ, 2009. – 44 с.
Основное использование вычислительной техники связано
с хранением и передачей информации, вследствие
чего возникает задача об экономном методе ее записи.
Методические указания содержат описание некоторых
математических понятий и приемов, используемых при
решении этой задачи.
Предназначены для студентов, обучающихся по специальности
010501 Прикладная математика и информатика
(дисциплина «Теория информации и кодирования», блок
СД), очной формы обучения.
УДК 519.2
ББК В 182я73
© Ярославский государственный
университет им. П. Г. Демидова,
2009
2
Стр.2
Введение
В настоящее время электронная вычислительная техника
применяется во многих сферах человеческой деятельности. Основное
использование вычислительной техники связано с хранением
и организацией доступа к информации. При этом возникает
задача о сжатии данных. Цель сжатия данных – обеспечить компактное
представление данных, вырабатываемых источником,
для их более экономного хранения и передачи по каналам связи.
Все способы сжатия можно разделить на две категории: обратимое
и необратимое сжатие.
Обратимое сжатие, или сжатие без потерь, приводит к снижению
объема выходного потока информации без изменения его
информативности, т. е. без потери информационной структуры.
Из выходного потока, полученного после выполнения алгоритма
обратимого сжатия, при помощи декодирования получается поток,
в точности совпадающий с исходным.
Под необратимым сжатием, или сжатием с потерями, подразумевают
такое преобразование входного потока данных, при котором
выходной поток представляет из себя объект, с некоторой
точки зрения достаточно похожий по внешним характеристикам
на входной поток, однако отличается от него объемом.
Таким образом, сжатие с потерями состоит из двух этапов:
а) выделение сохраняемой части информации с помощью модели,
зависящей от цели сжатия;
б) сжатие без потерь.
Такие подходы и алгоритмы используются для сжатия, например
данных растровых графических файлов, где на выходе
нужно представить графическую картинку, очень похожую на
оригинал, но не обязательно являющуюся его точной копией.
Заметим, что сжатию могут подвергаться не только сами исходные
данные, но и какие-либо преобразования над ними.
3
Стр.3
Методы сжатия без потерь
Рассмотрим методы сжатия без потерь на основе статистических
алгоритмов (кодирование по Хаффману и арифметическое
кодирование), а также на основе алгоритма RLE.
В основе этих методов сжатия лежит идея: «Если представлять
часто используемые элементы короткими кодами, а редко
используемые – длинными кодами, то для хранения блока данных
требуется меньший объем памяти, чем если бы все элементы
представлять кодами одинаковой длины».
Однако хочется заметить, что ни один компрессор не может
сжать любой файл. После обработки любым компрессором размер
части файлов уменьшится, а оставшейся части – увеличится
или останется неизменным.
Утверждение. Элемент i
равняется p s , выгоднее всего представлять −log ( ) битами.
Если распределение вероятностей F неизменно и вероятно(
)i
s , вероятность появления которого
2 p si
сти появления элементов независимы, то среднюю длину кодов в
битах можно найти как
= −
H
p s( )log ( ) ,
i
2 p si
это значение также называют энтропией источника в заданный
момент времени.
Обычно вероятность появления элемента является условной.
Тогда при кодировании очередного элемента i
вероятностей F принимает одно из возможных значений k
ответственно H H=
числить по формуле
H = −P H = −
k
k
P – вероятность того, что F принимает k -е значение, которому
соответствует набор вероятностей p s генерации всех
возможных элементов .i
где k
k ( )i
s
Статистические алгоритмы нуждаются в знании вероятностей
появления символов, оценкой, которой может являться частота
появления символов во входных данных.
4
k
,
k i
k
i
pk si
k . Среднюю длину кодов в битах можно выP
pk s( )log ( ) ,
s распределение
F и со
Стр.4
С учетом этого статистические алгоритмы можно разделить
на три класса:
• Неадаптивные. Они используют фиксированные, заблаговременно
заданные вероятности символов. Таблица вероятностей
символов не передается вместе с файлом, поскольку она известна
заблаговременно.
• Полуадаптивные. Для каждого файла строится таблица частот
символов, и на её основе сжимают файл. Вместе со сжатым
файлом передается таблица символов. Кодирование происходит
за два этапа (на первом происходит подсчет частот, а на втором –
кодирование).
• Адаптивные. Они начинают работать с фиксированной начальной
таблицей частот символов (обычно все символы сначала
равновероятны), и в процессе работы эта таблица изменяется в
зависимости от символов, которые встречаются в файле. Кодирование
происходит за один проход.
Алгоритм Хаффмана
• p a – вероятность появления каждого символа алфавита в
Исходными данными алгоритма являются:
• алфавит {}n
( )i
A а ,...,1
=
a
рассматриваемом сообщении.
Алгоритм Хаффмана состоит из нескольких шагов.
Шаг 1. Выстраиваем все символы текущего алфавита в порядке
убывания вероятностей.
Шаг 2. Строим новый алфавит j
предыдущего заменой двух символов air− 1
роятностями) на псевдосимвол a′ , причем p a′ = p air−1
( )
(
A , который получается из
a (с наименьшими ве)
+ p ai ).
i r
(
r
Продолжая эту процедуру (шаг 1 – шаг 2), будем приходить
ко все более коротким алфавитам; после n − 2 – кратного сжатия
придем к алфавиту 2−n
A , содержавшему уже всего две буквы.
Шаг 3. Символам последнего алфавита поставим в соответствие
кодовые обозначения 0 и 1.
5
, состоящий из n символов;
Стр.5