МЕТОДЫ СЖАТИЯ ИНФОРМАЦИИ. Методические указания Рекомендовано Научнометодическим советом университета для студентов, обучающихся по направлению Фундаментальная информатика и информационные технологии
 Скачать 0.87 Mb.
|
|
Министерство образования и науки Российской Федерации Ярославский государственный университет им. П. Г. Демидова Кафедра компьютерных сетей Методы сжатия информации: текст и изображение Методические указания Рекомендовано Научно-методическим советом университета для студентов, обучающихся по направлению Фундаментальная информатика и информационные технологии Ярославль ЯрГУ 2014 2 УДК 681.3(072) ББК В182я73 М54 Рекомендовано Редакционно-издательским советом университета в качестве учебного издания. План 2014 года Рецензент кафедра компьютерных сетей Ярославского государственного университета им. П. Г. Демидова Составитель М. В. Краснов М54 Методы сжатия информации : текст и изображение : метод. указания / сост. МВ. Краснов ; Яросл. гос. унт им. П. Г. Демидова. – Ярославль : ЯрГУ, 2014. – 56 с. Основное использование вычислительной техники связано с хранением и передачей информации, вследствие чего возникает задача об экономном методе ее записи. Описанию некоторых математических понятий и приемов, используемых при решении этой задачи посвящена данная работа. Методические указания предназначены для студентов, обучающихся по направлению Фундаментальная информатика и информационные технологии дисциплина Методы сжатия, цикл Б, очной формы обучения. УДК 681.3(072) ББК В182я73 © ЯрГУ, 2014 3 1. Введение В настоящее время электронная вычислительная техника применяется во многих сферах человеческой деятельности. Основное использование вычислительной техники связано с хранением информации и организацией доступа к ней. К сожалению, основная часть данных, с которыми работают пользователи, часто представлена некомпактно (обычно данные хранятся в форме, которая обеспечивает наиболее простое их использование, например текстовый документ хранится в кодировке одной из кодовых страниц Unicode, ASCII итак далее каждый символ кодируется кодом фиксированной длины, в ASCII это 8 бит. Цель сжатия данных – обеспечить компактное представление данных, вырабатываемых источником, для более экономного их хранения и передачи по каналам связи. Рис. 1. Процесс работы со сжатыми данными В этой схеме данные, вырабатываемые источником, определим как данные источника, а их компактное представление – как сжатые данные. Отметим, что под информацией понимаем значение или изменение некоторой физической величины, отражающее состояние объекта (системы или явления. Первичными сообщениями, которые генерируются источником, являются текст, речь, музыка, изображения и т. д. Студенты должны обратить внимание, что существуют разные модели источников данных, например источник данных без памяти и источник данных с памятью. При использовании модели источника данных без памяти события считаются независимыми, а вероятность наступления каждого события считается фиксированной величиной, те. Однако события могут оказаться коррелированными друг с другом, те и значит надо рассматривать источник данных с памятью. Можно говорить, что источник без памяти порождает элементы, а источник данных с памятью – слова, поскольку во втором случае учет значений соседних элементов (контекста) улучшает сжатие. Все способы сжатия можно разделить на две категории обратимое и необратимое сжатие. Обратимое сжатие, или сжатие без потерь, приводит к снижению объема выходного потока информации без изменения его информативности, те. без потери информационной структуры. Другими словами, после выполнения операции декодирования получается поток, в точности совпадающий с потоком данных источника. Обратимое сжатие обычно используется при кодировании текстовой информации. Под необратимым сжатием, или сжатием с потерями, подразумевают такое преобразование входного потока данных, в результате которого декодер не в состоянии восстановить данные источника в первоначальном виде. Студенты должны обратить особое внимание на тот факт, что полученные при декодировании данные с некоторой точки зрения могут быть похожи по внешним характеристикам на данные источника. Обычно сжатие с потерями состоит из двух этапов) выделение сохраняемой части информации с помощью модели, зависящей от цели сжатия) сжатие без потерь. Необратимое сжатие обычно используется при кодировании графической, звуковой и видеоинформации. Студентам следует обратить внимание, что сжатию могут подвергаться не только сами исходные данные, но и какие-либо преобразования над ними. При решении задачи сжатия естественным является вопрос, насколько эффективна таили иная система сжатия. Приведем несколько величин, которые используют для оценки системы) коэффициент сжатия ( ) ( ) ðàçì åð âû õî äí î ãî ô àéëà ñæ àò û å äàí í û å êî ýô ô èöèåí ò ñæ àò èÿ ðàçì åð âõî äí î ãî ô àéëà äàí í û å èñò î ÷í Сжатие считается успешным, если выполняется условие 0 < коэффициент сжатия < коэффициент сжатия размер выходного файла (сжатые данные) размер входного файла (данные источника 5 b) качество сжатия качество сжатия = 100 * (1 – коэффициент сжатия) скорость сжатия R, определяемая как отношение и измеряемая в количестве кодовых бит, приходящихся на отсчет данных источника d) в случае использования необратимого сжатия необходимы метрики для измерения расхождения декодированных данных с исходными. Например, при сжатии изображений можно использовать величину искажений D: ( ) , 1 2 1 ∑ = - = n i i i Q P m D P i – пикселы исходного изображения, Q i – пикселы восстановленного изображения (где 1 ≤ i ≤ Однако хочется заметить, что ни один компрессор не может сжать любой файл. После обработки любым компрессором размер части файлов уменьшится, а оставшейся части – увеличится или останется неизменным. Универсальное сжатие. Неравномерное кодирование дискретных источников Под дискретным источником будем понимать устройство, выдающее дискретную последовательность B, элементами которой являются a i , принадлежащие некоторому алфавиту A = {a 1 , …, a n }. Величина n называется объемом алфавита источника. Каждый элемент сообщения появляется на выходе источника с вероятностью p(a j ), причем ∑p(a i ) = 1. Заметим, что рассматриваемый источник удобно использовать при побуквенном кодировании В основе методов неравномерного кодирования лежит идея если представлять часто используемые элементы короткими кодами, а редко используемые – длинными кодами, то для хранения блока данных требуется меньший объем памяти, чем если бы все элементы представлять кодами одинаковой длины. Для однозначного декодирования неравномерного кода будем считать, что никакое кодовое обозначение не совпадает с началом какого- либо другого более длинного кодового обозначения (другими словами, код является префиксным). Утверждение. Элемент a i , вероятность появления которого равняется p(a i ), выгоднее всего представлять – log 2 p(a i ) битами.■ Если распределение вероятностей F неизменно и вероятности появления элементов независимы, то среднюю длину кодов в битах можно найти как это значение также называют энтропией источника в заданный момент времени. Обычно вероятность появления элемента является условной. Тогда при кодировании очередного элемента a i распределение вероятностей F принимает одно из возможных значений F k и соответственно. Среднюю длину кодов в битах можно вычислить по формуле ∑ ∑ - = - = i k i k i k k k k k a p a p P H P H , ) ( log ) ( , где P k – вероятность того, что F принимаете значение, которому соответствует набор вероятностей p k (s i ) генерации всех возможных элементов s i Студентам следует обратить внимание на тот факт, что статистические алгоритмы можно разделить натри класса Неадаптивные – используют фиксированные, заблаговременно заданные вероятности символов. Таблица вероятностей символов не передается вместе с файлом, поскольку она известна заблаговременно. › Полуадаптивные – для каждого файла строится таблица частот символов, и на её основе сжимают файл. Вместе со сжатым файлом передается таблица символов. Кодирование происходит в два этапа (на первом происходит подсчет частота на втором – кодирование Адаптивные – начинают работать с фиксированной начальной таблицей частот символов (обычно все символы сначала равновероятны, ив процессе работы эта таблица изменяется в зависимости от символов, которые встречаются в файле. Кодирование происходит за один проход. Определение. Пусть при кодировании элементов (s 1 , …, s m ) с вероятностями появления (p 1 , …, p m ) получается код (c 1 , …, c m с длинами кодовых слов (l 1 , …, l m ), тогда средней длиной кодовых слов называется величина Определение. Избыточностью неравномерного кода называется величина r = l – H. Она показывает, что на каждое сообщение будет тратиться набит больше, чем потратилось бы, если использовать теоретически наилучший метод кодирования 1 .■ Отметим, что неравномерные коды очень чувствительны к ошибкам в канале связи, т. к. полученные битовые последовательности упаковываются в байты без учета границ байтов, и при возникновении ошибок декодирование очередного символа может начаться с середины кода с выдачи бессмысленного результата. 2.1.1. Код Хаффмана Статический алгоритм Кодирование Хаффмана является простым алгоритмом для построения кодов переменной длины. Он весьма популярен и используется во многих методах сжатия текстовой и графической информации. Одним из удобных способов описания двоичных кодов является их представление в виде двоичного кодового дерева. Для того чтобы построить е кодовое дерево для данного кода, начиная с некоторой точки – корня кодового дерева – будем проводить ветви с весами (0,1 …, m – 1). Будем считать, что 1 Наилучшего метода кодирования программно может и несу- ществовать. на листьях кодового дерева находятся буквы алфавита источника, причем каждой букве будет соответствовать своя вершина и свой путь от корня к вершине. Кодом буквы будем считать запись, которая получается после применения операции конкатенации для весов ребер, входящих в путь от корня к листу. Описание алгоритма приведено по работам [1; 2]. Исходными данными алгоритма являются алфавит A = {a 1 ,…, a n }, состоящий из n символов p(a i ) – вероятность появления каждого символа алфавита в рассматриваемом сообщении. Алгоритм Хаффмана для х кодов состоит из нескольких шагов. Шаг 1. Инициализация) добиваемся, чтобы число n можно было представить в виде n = m + k(m – 1), где k – целое число. Этого можно добиться, добавив, если необходимо, к алфавиту A фиктивные буквы с нулевой вероятностью 2) выстраиваем все символы текущего алфавита в порядке убывания вероятностей) вводим вспомогательную переменную M – число необработанных узлов и список необработанных узлов S; 4) перед основным шагом алгоритма будем считать, что › M = n; › S = Шаг 2. Основной этап работы алгоритма while M > 1 { 1) в списке S выбираем m элементов с наименьшими вероятностями) исключаем эти узлы из списка S; 3) в список S вводим новый узел и приписываем ему суммарный вес исключенных узлов) новый узел связать с исключенными узлами) M = M – (m – Алгоритм окончен Пример. Дан алфавит A = без, "мл, "ь, для каждого символа из алфавита А задана вероятность его появления в тексте. символ е б з м л ь вероятность 10 4 10 1 10 2 10 1 10 1 10 Закодировать алфавит с помощью троичного кода Хаффмана. Решение. Легко заметить, что равенство 6 = 3 + 2k, где k – целое число, не выполняется. Присоединим в алфавит фиктивный символ d» с нулевой вероятностью, и тогда равенство 7 = 3 + 2k выполняется. Следовательно, мы получили новый алфавит символ е б з м л ь d вероятность 10 4 10 1 10 2 10 1 10 1 10 Выполняем алгоритм Хаффмана для го кода (рис. 2 ). Кодом буквы считаем запись, которая получается после применения операции конкатенации для весов ребер, входящих в путь от корня к листу. Pис. 2. Кодовое дерево Хаффмана символ коде окончен 10 10 10 10 10 10 10 10 10 10 10 Динамический (адаптивный) алгоритм Основная идея динамического кодирования заключается в том, что кодер и декодер начинают работу с пустого дерева Хаффмана, а потом модифицируют его при обработке очередного символа. Описание алгоритма приведено по работе [3]. Заметим, что двоичное дерево Хаффмана должно обладать следующими свойствами) внешние узлы (листья) кодового дерева имеют неотрицательный вес каждый внутренний (родительский) узел имеет подчиненные (дочерние) узлы, а его вес равен сумме весов дочерних узлов 2) на каждом уровне дерева (за исключением корневого) должно быть не менее одной пары узлов, имеющих общий родительский узел) узлы могут быть перечислены в порядке возрастания таким образом, что узлы с номерами (2j – 1) и (2j) являются узлами одного уровня, а их общий родительский узел имеет более высокий уровень. Нумерация узлов соответствует тому порядку, в котором узлы объединяются в соответствии со статическим алгоритмом Хаффмана. Приведем пример дерева, обладающего свойством соперничества (рис. Дерево Хаффмана можно представить в виде упорядоченного списка. Рис. 3. Дерево Хаффмана Структура представления Узел дерева Корень В узел 1 А ξ Вес узла 2 1 Номер узла 4 3 Исходными данными алгоритма являются алфавит A = {a 1 ,…, a n }, состоящий из n символов строка B = b 1 b 2 b 3 …b s , которую надо закодировать и элементы, которой принадлежат алфавиту A. Алгоритм Хаффмана состоит из нескольких шагов. Введем обозначения символ || обозначает операцию конкатенации код) – функция, которая возвращает неравномерный код символа r, построенный по текущему двоичному дереву Хафф- мана; › код) – функция, которая возвращает равномерный код символа r, построенный по исходному алфавиту, например битовый код ASCII; › // комментарии. Шаг 1. Инициализация) введем вспомогательный символ ξ с нулевой вероятностью, его кодовое значение в выходной строке будет сигнализировать, что следующим будет идти несжатый символ) введем вспомогательную переменную cod; 3) инициализируем пустое двоичное дерево Хаффмана; 4) для каждого элемента алфавита a i ∈ A введем счетчик n a i . Отметим, что каждый узел двоичного дерева Хаффмана будет иметь вес. Пусть n a i = 0, n ξ = Шаг 2. Работа алгоритма (шаг два выполняется до конца строки, которую надо закодировать) считываем очередной символ b j ; 2) If (n b j = = 0) { cod = код) || код1(n b j ) выполнить процедуру New(b j ) } else cod = код 3) выдать в сжатый файл cod; 4) с помощью процедуры Tree(b j ) модифицируем текущее дерево, одновременно добиваясь, чтобы оно являлось деревом Хаффмана 2 } Алгоритм окончен При кодировании символа b 1 можно считать, что cod = код Опишем процедуры New(X ) и Tree(X ) более подробно. Процедура New(X ) состоит из нескольких шагов) создаем новый узел η с нулевым весом) находим на текущем дереве лист символа ξ и заменяем его узлом η; 3) создаем новые листья с нулевыми весами ξ и X (родителем их является узел η). Пронумеруем узлы начиная с левого подчиненного узла левый, правый, родительский Процедура добавления нового символа состоит в том, что в хвост упорядоченного списка, коим является наше дерево кодов, добавляются два новых элемента. // Процедура завершена. Процедура Tree(X ) состоит из двух шагов. Шаг 1. Найдем на текущем дереве лист символа X (пусть мы нашли s – узел графа, n s – вес узла. Шаг 2. Работа алгоритма (s and ξ являются дочерними узлами одного родителя) { Поменять местами s илист, имеющий максимальный номер того же самого веса = n s + 1; s – родитель s // новым текущим узлом становится родитель s } while (true) { n s = n s + 1; If (s корень) exit; If (n s > n s + 1 ) { i = 1; while (n s > n s + i ) i = i + 1; // мы обнаружили группу, где может нарушаться упорядоченность. В этом случае следует поменять местами s и последний узел в этой группе (за исключением родителя данное действие можно выполнять, используя упорядоченный список // 13 Перестановка_поддеревьев (s, s + i) 3 ; } s – родитель s // новым текущим узлом становится родитель s Процедура завершена. Пример Дан алфавита, вор, т. Закодировать строку В = ворота с помощью динамического алгоритма Хаффмана. Решение Символы алфавита А могут быть закодированы равномерным кодом а-(000) в-(001) о-(010) р-(110) т-(111) Строим дерево Хаффмана (см. с. Студентам следует обратить внимание, что на рис. 4-ё (введение в дерево символа р) нарушается свойство хаффманско- го дерева и оно нуждается в модификации. После модификации получим дерево с рис. ж. Аналогично свойства хаффманского дерева нарушаются на рис.:4-з, к, 4-м. Учитывая биты, которые поступают на выход в процессе кодирования, получим, что слово ворота будет закодировано в последовательность Пример окончен Поддерево s – это дерево, корнем которого является узел s. 14 Симв ол Дерев о до пре образ ов ания Пре дст авл ение Де ре во после п ре об ра зо ва ни я Вых од инициа- лизация 0 0 ξ Узел ξ Ве с 0 но мер 0 0 ξ в Уз1 в ξ 1 1 0 3 2 ко д1(в) о Уз1 в Уз2 о ξ 2 1 1 1 0 5 4 3 2 к од1(о) р Уз1 Уз2 в о Уз3 3 2 1 1 1 7 6 5 р 0 2 к од1(р) Рис. 4-в Рис. 4-ж Рис. Рис. 4-е Рис. 4-д Рис. 4-г Рис. 4-б Рис. 4-а |