Алгоритм Лемпеля–Зива

Классический алгоритм Лемпеля–Зива - LZ77, названный так по году опубликования, предельно прост. Он формулируется следующим образом: “если в прошедшем ранее выходном потоке уже встречалась подобная последовательность байт, причем запись о ее длине и смещении от текущей позиции короче, чем сама эта последовательность, то в выходной файл записывается ссылка (смещение, длина), а не сама последовательность”.

Пример

Фраза КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ

закодируется как

КОЛО(-4, 3)_(-5, 4)0_(-14, 7)ЬНИ

Строка из одинаковых символов

ААААААА

закодируется как

А(-1, 6)

Алгоритмы сжатия изображений

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

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

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

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

Фрактальный алгоритм. Фрактальная архивация основывается на том, что мы представляем изображение в более компактной форме – с помощью коэффициентов системы итерируемых функций (IFS). Строго говоря, IFS представляет собой набор трехмерных аффинных преобразований, переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (x координата, y координата, яркость). Фактически, фрактальная компрессия – это поиск самоподобных областей в изображении и определение для них аффинных преобразований. При этом каждое преобразование кодируется считанными байтами, в то время, как изображение, построенное с их помощью может занимать несколько мегабайт.

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

Так два числа a2_i a2_i+1 всегда можно представить в виде b^l_i = (a2_i + a2_i+1)/2 b²_i = (a2_i – a2_i+1)/2.

Рассмотрим конкретный пример: пусть мы сжимаем строку из 8 значений яркости пикселов (a_i): (220, 211, 212, 218, 217, 214, 210, 202). Мы получим следующие последовательности b¹_i и b²_i: (215.5, 215, 215.5, 206) и (4.5, -3, 1.5, 4). Повторим операцию, рассматривая b¹_i как a_i. Мы получим из (215.5, 215, 215.5, 206): (215.25, 210.75) (0.25, 4.75). Полученные коэффициенты, округлив до целых и сжав, например, с помощью алгоритма Хоффмана, мы можем помесить в файл. Дополнительное сжатие можно получить, повторяя преобразование 4-6 раз.