ЛекцииММ1 (Курс электронных лекций), страница 8

Алгоритмы сжатия без потерь.

Групповое кодирование - Run Length Encoding (RLE) - один из самых старых и самых простых алгоритмов архивации графики. Изображение в нем (как и в нескольких алгоритмах, описанных далее) вытягивается в цепочку байт по строкам растра. Само сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Замена их на пары "счетчик, значение" уменьшает избыточность данных. Лучший, средний и худший коэффициенты сжатия - 1/32, 1/2, 2/1. Ситуация, когда файл увеличивается в два раза, для этого простого алгоритма не так уж редка. Ее можно легко получить, применяя групповое кодирование к обработанным цветным фотографиям. Последовательность действий при групповом кодировании следующая:

Начиная с первой строки, программа группового кодирования просматривает значения пикселей слева направо и ищет отрезки повторяющихся пикселей. Всякий раз, когда встречаются три или более идущих подряд пикселей с одинаковым значением, программа заменяет их парой чисел: первое число указывает длину отрезка, второе - значение пикселей. Число, определяющее длину отрезка, будем называть меткой отрезка.

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

К положительным сторонам алгоритма, пожалуй, можно отнести только то, что он не требует дополнительной памяти при работе, и быстро выполняется. Ориентирован алгоритм на изображения с небольшим количеством цветов: деловую и научную графику. Применяется в форматах РСХ, TIFF, ВМР.

LZW

Собственно исходный Lempel/Ziv подход к сжатию данных был впервые обнародован в 1977г., а усовершенствованный (Terry Welch) вариант был опубликован в 1984г. LZW - код (Lempel-Ziv & Welch) является на сегодняшний день одним из самых распространенных кодов сжатия без потерь. Именно с помощью LZW-кода осуществляется сжатие в таких графических форматах, как TIFF и GIF, с помощью модификаций LZW осуществляют свои функции очень многие универсальные архиваторы. Существует довольно большое семейство LZ-подобных алгоритмов, различающихся, например, методом поиска повторяющихся цепочек.

Работа алгоритма основана на поиске во входном файле повторяющихся последовательностей символов, которые кодируются комбинациями длиной от 8 до 12 бит. Таким образом, наибольшую эффективность данный алгоритм имеет на текстовых файлах и на графических файлах, в которых имеются большие одноцветные участки или повторяющиеся последовательности пикселей. Реализация алгоритма LZW жестко зафиксирована международным стандартом и Американским Национальным институтом стандартов (ANSI), однако существуют достаточно интересные его модификации, которые дают больший коэффициент сжатия некоторых специфичных типах файлов - например, на исходных текстах программ.

Коэффициенты сжатия: 1/1000, 1/4, 7/5. Коэффициент 1/1000 достигается только на одноцветных изображениях размером больше 4 Мб. Ориентирован LZW на 8 - битные изображения, построенные на компьютере. Ситуация, когда алгоритм увеличивает изображение, встречается крайне редко.

Отсутствие потерь информации при LZW-кодировании обусловило широкое распространение основанного на нем формата TIFF. Этот формат не накладывает каких-либо ограничений на размер и глубину цвета изображения и широко распространен, например, в полиграфии. Другой основанный на LZW формат - GIF - более примитивен - он позволяет хранить изображения с глубиной цвета не более 8 бит/пиксель. В начале GIF - файла находится палитра. Это таблица, устанавливающая соответствие между индексом цвета - числом в диапазоне от 0 до 255 и истинным, 24 - битным значением цвета.

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

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

Алгоритм компрессии с кодом переменной длины LZW является разновидностью алгоритма компрессии Lempel - Ziv, в котором коды переменной длиной используются для замены сочетаний, обнаруженных в исходных данных. В данном алгоритме используется код, либо переводная таблица, составленная из комбинаций, встретившихся в исходных данных. Каждая новая комбинация заносится в эту таблицу, и затем в потоке данных, подлежащем компрессии, замещается определенным индексом.

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

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

Кодирование Хаффмана, вероятно, самый известный и классический метод сжатия данных. Простота и элегантность способа сделали его на долгое время академическим фаворитом. Но коды Хаффмана имеют и практическое применение; например, статические коды Хаффмана используются на последнем этапе сжатия JPEG. Кодирование Шеннона - Фано (Shannon - Fano), довольно близкое к кодированию Хаффмана, используется как один из этапов в мощном "imploding" - алгоритме программы PKZIP.

Кодирование Хаффмана работает на предпосылке, что некоторые символы используются в представлении данных чаще, чем другие. Наиболее общее представление - алфавит ASCII - использует 8 бит для каждого символа. В английском языке буква e явно будет чаще встречаться, чем буква q, хотя мы используем для их представления одинаковое количество бит. Если мы используем только 4 бита для e и 12 бит для q, мы могли бы выиграть несколько бит, сохраняя английский текст.

Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины, и напротив - встречающимся редко - цепочку большей длины. Для сбора статистики требует двух проходов по изображению. Коэффициенты сжатия: 1/8, 2/3, 1. Требует записи в файл таблицы соответствия кодируемых символов и кодирующих цепочек.

На практике используются его разновидности. Так, в некоторых случаях резонно либо использовать постоянную таблицу, либо строить ее "адаптивно", т.е. в процессе архивации/разархивации. Эти приемы избавляют от двух проходов по изображению и необходимости хранения таблицы вместе с файлом. Кодирование с фиксированной таблицей применяется в качестве последнего этапа архивации в JPEG.

Близкая модификация алгоритма используется при сжатии черно-белых изображений. Последовательности подряд идущих черных и белых точек заменяются числом, равным их количеству с признаком цвета, а этот ряд уже, в свою очередь, сжимается по Хаффману с фиксированной таблицей. Этот алгоритм реализован также и в формате TIFF.

Кодирование Хаффмана формализует идею связи длины символа с вероятностью появления символов. Статическое кодирование Хаффмана требует, чтобы у вас была таблица вероятностей, прежде чем вы начнете сжимать данные. Эта таблица может быть взята из результатов статистических исследований (такие таблицы были опубликованы для некоторых данных, например, для английского языка), или же система сжатия может просканировать входные данные для определения вероятностей символов, прежде чем начать сжимать данные.

С помощью этой информации о вероятностях компрессор и декомпрессор могут сконструировать кодирующее дерево.

Лист дерева - это узел, из которого не выходит ни одной дуги. Два листа, имеющие общий узел, называются родственными.

Двоичное дерево - дерево, у которого из каждого угла выходит только две дуги.

H - дерево - двоичное дерево кодирования, у которого каждый узел имеет вес, причем вес родителя равен сумме весов детей.

Входной алфавит - совокупность всех символов.

Алгоритм Хаффмана: Кодирующее дерево является двоичным деревом с одним листом для каждого символа. Чтобы построить дерево, компрессор начинает с двух символов наименьшей вероятности. Затем он объединяет их как два листа двумя ветвями в узел; этому узлу, в свою очередь, назначается сумма двух вероятностей. Компрессор затем рассматривает этот узел вместе с оставшимися символами в списке вероятностей, и снова выбирает два наименее вероятных элемента. Он продолжает строить и объединять узлы, пока не построит единое дерево с вероятностью корня, равной 1.

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

Для кодировки символа компрессор находит путь от корня дерева к листу символа. Предположим, что компрессор хочет закодировать букву s. Он начинает с листа, соответствующего букве s, и переходит в родительский узел, отмечая при этом, по какой ветви он про шел (по 0 или по 1). Он продолжает идти вверх по дереву, пока не достигнет корня. Список ветвей в обратном порядке описывает путь от корня до s: это и есть код Хаффмана для этого символа.

Символы с большой вероятностью находятся ближе к корню, так что их коды короткие. Символы с малой вероятностью дальше от корня, и их коды длиннее.

Чтобы декодировать, декомпрессор берет код и обрабатывает его в обратном порядке. Это значит, что он начинает с корня дерева. Если первый бит кода равен 1, то декомпрессор идет от корня в узел по ветви 1. Он продолжает чтение битов и проход по ветвям, пока не достигнет листа; символ в листе и есть декодированный символ.

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

Динамическое кодирование Хаффмана.

Самой большой сложностью с кодами Хаффмана является необходимость иметь таблицы вероятностей для каждого типа сжимаемых данных. Это не представляет проблемы, если вы знаете, что всегда будете сжимать   английский текст; вы просто предоставляете компрессору и декомпрессору подходящее для английского текста дерево. Протокол JPEG определяет дерево Хаффмана, используемое по умолчанию для сжатия данных JPEG. В общем же случае, когда не известны вероятности символов для ваших входных данных, статические коды Хаффмана не могут использоваться эффективно.

Динамическая версия сжатия Хаффмана может строить дерево Хаффмана "на лету" во время чтения и активного сжатия. Дерево постоянно обновляется, чтобы отражать изменения вероятностей входных данных.

Ключом к началу неинициализированного дерева является введение пустого листа. Пустой лист - это просто лист без присоединенного к нему символа; этот лист имеет нулевую вероятность. Начальное дерево как в компрессоре, так и в декомпрессоре, имеет только корень и единственный пустой лист.

Компрессор присоединяет символ к ветви 1 корня, оставляя пустой лист на ветви 0. Затем он посылает этот символ в декомпрессор как буквальный код ASCII, и декомпрессор выполняет точно такое же действие над своим деревом.

Для каждого символа, прочитанного после этого, компрессор выполняет следующие шаги. Вначале он проверяет, находится ли код в кодовом дереве. Если код есть, компрессор выдает его так же, как и в случае статического сжатия. Если же нет, он посылает код для пустого листа. Затем он посылает новый символ как буквальный код ASCII. Наконец, компрессор добавляет два кода, один для нового пустого листа на ветви 0, и один - для нового кода ветви 1. Когда дерево заполнится, т.е. когда в нем будут все символы, компрессор просто изменяет последний пустой лист на последний символ.  Программа декомпрессии может делать уточнения в своем дереве, потому что у нее имеется в точности то же самое дерево, что и у компрессора. Когда она принимает код пустого листа, она читает следующий код из сжатых данных как литерал ASCII. Затем декомпрессор применяет для изменения дерева ту же программу, какую использовал и компрессор.

Однако пустой лист и неинициализированное дерево не решают проблему отслеживания изменения вероятностей. Чтобы делать это, вам необходимо добавить веса к каждому узлу дерева и изменять эти веса во время обработки данных. Вы должны также поддерживать список обозначений узлов (и весов), сортированный по весу.