В.Д. Валединский - Избранные главы лекций по программированию (1114957), страница 7
Текст из файла (страница 7)
длина сжатого набора данных увеличивается на 1/127 (это меньше 1%).Наиболее часто (и наиболее эффективно) алгоритм RLE применяется для сжатия не имеющих полутоноврастровых графических изображений. Например, если цвет отдельного пиксела кодируется одним байтом и визображении присутствуют обширные участки, заполненные одним цветом, то этот алгоритм позволяет существенно сократить объем входной информации. С другой стороны, изображения фотографического качестваимеют шум и частые переходы к другому цвету или оттенку, что исключает наличие повторяющихся участков.
В таких случаях алгоритм RLE неприменим, и здесь обычно используются алгоритмы сжатия с потерями(JPEG).Существует также несколько вариантов алгоритма RLE, ориентированные на работу с последовательностьюбитов. Эти алгоритмы особенно успешно работают для двуцветных (черно-белых изображений). Итак, пустьвходной набор данных представляет собой последовательность битов с достаточно длинными участками повторяющихся значений (0 или 1).
Опишем две битовых модификации алгоритма.Первый способ в точности копирует байтовый вариант алгоритма. Выходным кодом является байт, в которомстаршие два бита являются признаком для интерпретации оставшихся 6 бит по следующим правилам:биты 7001601I5LLM4EEG3NND2GGA1TTT0HHALENGTH - длина строки из нулевых битLENGTH - длина строки из единичных битIMGDATA (Image Data)- фрагмент 7 бит изображения без преобразованияКак видно из этого представления, длина цепочки здесь ограничена значением 64.
Это ограничение позволяетполучить сжатие до 8 раз. В ряде случаев более хорошую степень сжатия дает более простой вариант, неучитывающий кодирование неповторяющихся групп.биты 7 6 5 4 3 2 1 00 Z L E N G T H1 U L E N G T HZLENGTH (Zeros Length) - длина строки из нулевых битULENGTH (Unit Length) - длина строки из единичных битЗдесь можно кодировать длины до 128 пикселов, что позволяет в принципе получить сжатие в 16 раз.Непостоянные участки дадут увеличение кода в 8 раз.
Какой из этих двух вариантов предпочтительней, обычнорешается путем проб и сравнений в каждом конкретном случае3 .3 Строго говоря, необходимо применять адаптивный алгоритм, который сам подбирает необходимое количество бит на длинуодинаковых участков. Реализация такого алгоритма не сильно сложнее, но сжатие сильно улучшается — Прим. ред.184.2. Алгоритм Хаффмана (Huffman Encoding)Алгоритм Хаффмана (иногда его называют CCITT кодирование) состоит в сопоставлении каждому символувходного потока некоторого кода переменной длины так, что наиболее часто встречающиеся символы кодируются наиболее короткими кодами. Для этого строится бинарное дерево (дерево Хаффмана), в концевых вершинахкоторого располагаются все возможные символы, а ветви, ведущие к этим вершинам, соответствуют кодам символов.
Для построения дерева нужно иметь таблицу количеств появления каждого символа в исходном файле.Каждая вершина дерева имеет свой вес, который для концевых вершин равен количеству появлений символа,записанного в этой вершине.Процесс построения дерева описывается следующей схемой.1. Создаём концевые вершины, содержащие все символы входного алфавита, задаём каждой вершине вес всоответствии с таблицей количеств, объявляем все эти вершины свободными.2.
В множестве свободных вершин находим две вершины (обозначим их A и B), имеющие наименьшие веса,создаем новую родительскую вершину C, присоединяем A и B к C справа и слева, устанавливаем вес Cравным сумме весов A и B, исключаем A и B из множества свободных вершин, добавляем C к множествусвободных вершин.3. Если в множестве свободных вершин более одного элемента, то перейти к пункту 2, иначе единственныйоставшийся элемент есть корень дерева.Далее, левым ребрам построенного дерева сопоставляется число 0, а правым ребрам — 1. Теперь, спускаясь от корня к конкретной концевой вершине и последовательно выписывая нули и единицы, сопоставленныепроходимым ребрам, мы получаем код символа в этой вершине.Заметим, что каждому способу кодирования можно сопоставить подобное дерево.Кодирование и декодирование осуществляется заменой каждого символа его кодом и наоборот.
При практической реализации биты кодов символов выписываются подряд, а затем делятся на группы по 8 бит (байты),которые и выдаются в выходной поток. При декодировании входной поток рассматривается как последовательность битов, определяющих направления спуска по ветвям дерева Хаффмана. При достижении концевойвершины соответствующий символ выдается в выходной поток и спуск опять начинается от корня.Алгоритм Хаффмана строит оптимальный код для данного частотного распределения символов. Оптимальность означает, что любой другой способ кодирования, сопоставляющий каждому входному символу некоторыйнабор битов, даст выходную кодовую последовательность не меньшей длины. Оценим длину кодирующей последовательности Хаффмана и докажем ее оптимальность.Пусть нам дана некоторая входная последовательность символов (байт) длины n и каждый символ со значением k имеет вес (количество появлений) wk .
Построим дерево Хаффмана. Все символы будут концевымивершинами, и длины их кодов есть длины соответствующих ветвей от корня к этим вершинам. Обозначимчерез lk длину ветви от корня до вершины символа k, тогда длина кода для исходного набора данных естьLH =Xkwk · lk .Теорема 4.1. Не существует кода, сопоставляющего каждому входному символу некоторый набор битов, который для фиксированного входного набора данных даёт выходную кодовую последовательность короче,чем LH . Разобьём доказательство на несколько этапов.Лемма 4.2.
Пусть некоторый способ кодирования на указанном наборе даёт выходную кодовую последовательность наименьшей длины. Тогда можно построить способ кодирования, дающий ту же самую длинукодовой последовательности, и такой, что две минимальные по весу вершины лежат в самых длинных ветвяхи имеют одного родителя. Рассмотрим кодовое дерево исходного метода.
Пусть a и b — два минимальных по весу символа с весамиwa и wb , лежащих в ветвях с длинами la и lb соответственно. Пусть также x и y — два символа, имеющие одногородителя и лежащие в самых длинных ветвях. Имеют место неравенстваwa 6 wx ,wb 6 wy ,la 6 lx ,lb 6 ly .Переставим местами символы a и x, а также b и y. Посмотрим, какое влияние окажет эта перестановка надлину выходной кодовой последовательности. До перестановки вклад символов a, b, x, y в выходную кодовуюпоследовательность был равен L1 = wa · la + wb · lb + wx · lx + wy · ly , а после перестановки стал равен L2 =wa · lx + wb · ly + wx · la + wy · lb .
Рассмотрим разностьL2 − L1 = wa · lx + wb · ly + wx · la + wy · lb − wa · la − wb · lb − wx · lx − wy · ly =19= (wa − wx )(lx − la ) + (wb − wy )(ly − lb ) 6 0.Последнее неравенство означает, что L2 6 L1 , но в силу минимальности дерева получаем L2 = L1 . Вкладвсех остальных символов остался без изменения. Таким образом, перестроенное дерево удовлетворяет условиямутверждения и определяет искомый метод кодирования.
Приступим к доказательству теоремы. Пусть Th — кодирующее дерево Хаффмана, а To — кодирующее дерево некоторого другого оптимального метода. Докажем, что кодовая последовательность, получаемая с помощьюдерева To , не короче кодовой последовательности Хаффмана. В силу только что доказанного утверждения можно считать, что в дереве To две вершины, отвечающие символам a и b с минимальными весами wa и wb , имеютобщего родителя и расположены в самых длинных ветвях.
Напомним, что точно таким же свойством обладаетпо построению и дерево Th . Отождествим символы a и b и удалим соответствующие им вершины из деревьевTh и To , оставив только родительскую вершину с весом wa + wb . Рассмотрим теперь новые полученные деревьяTh и To как кодирующие деревья для множества символов, содержащего на один символ меньше (посколькусимволы a и b отождествились в один новый «суммарный» символ). Длины кодирующих последовательностей,получаемых по обоим этим деревьям, уменьшились на wa + wb бит по сравнению длиной исходных кодовыхпоследовательностей. При этом дерево Th остается деревом Хаффмана для нового множества символов, а дерево To остается деревом оптимального кодирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
