Сжатие данных. Алгоритмы сжатия данных

Цель лекции : изучить основные виды и алгоритмы сжатия данных и научиться решать задачи сжатия данных по методу Хаффмана и с помощью кодовых деревьев.

Основоположником науки о сжатии информации принято считать Клода Шеннона. Его теорема об оптимальном кодировании показывает, к чему нужно стремиться при кодировании информации и насколько та или иная информация при этом сожмется. Кроме того, им были проведены опыты по эмпирической оценке избыточности английского текста. Шенон предлагал людям угадывать следующую букву и оценивал вероятность правильного угадывания. На основе ряда опытов он пришел к выводу, что количество информации в английском тексте колеблется в пределах 0,6 – 1,3 бита на символ. Несмотря на то, что результаты исследований Шеннона были по-настоящему востребованы лишь десятилетия спустя, трудно переоценить их значение .

Сжатие данных – это процесс, обеспечивающий уменьшение объема данных путем сокращения их избыточности. Сжатие данных связано с компактным расположением порций данных стандартного размера. Сжатие данных можно разделить на два основных типа:

• Сжатие без потерь (полностью обратимое) – это метод сжатия данных, при котором ранее закодированная порция данных восстанавливается после их распаковки полностью без внесения изменений. Для каждого типа данных, как правило, существуют свои оптимальные алгоритмы сжатия без потерь.
• Сжатие с потерями – это метод сжатия данных, при котором для обеспечения максимальной степени сжатия исходного массива данных часть содержащихся в нем данных отбрасывается. Для текстовых, числовых и табличных данных использование программ, реализующих подобные методы сжатия, является неприемлемыми. В основном такие алгоритмы применяются для сжатия аудио- и видеоданных, статических изображений.

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

Введем ряд определений, которые будут использоваться далее в изложении материала.

Алфавит кода – множество всех символов входного потока. При сжатии англоязычных текстов обычно используют множество из 128 ASCII кодов. При сжатии изображений множество значений пиксела может содержать 2, 16, 256 или другое количество элементов.

Кодовый символ – наименьшая единица данных, подлежащая сжатию. Обычно символ – это 1 байт , но он может быть битом, тритом {0,1,2}, или чем-либо еще.

Кодовое слово – это последовательность кодовых символов из алфавита кода. Если все слова имеют одинаковую длину (число символов), то такой код называется равномерным (фиксированной длины) , а если же допускаются слова разной длины, то – неравномерным (переменной длины) .

Код – полное множество слов.

Токен – единица данных, записываемая в сжатый поток некоторым алгоритмом сжатия. Токен состоит из нескольких полей фиксированной или переменной длины.

Фраза – фрагмент данных, помещаемый в словарь для дальнейшего использования в сжатии.

Кодирование – процесс сжатия данных.

Декодирование – обратный кодированию процесс, при котором осуществляется восстановление данных.

Отношение сжатия – одна из наиболее часто используемых величин для обозначения эффективности метода сжатия.

Значение 0,6 означает, что данные занимают 60% от первоначального объема. Значения больше 1 означают, что выходной поток больше входного (отрицательное сжатие, или расширение).

Коэффициент сжатия – величина, обратная отношению сжатия.

Значения больше 1 обозначают сжатие, а значения меньше 1 – расширение.

Средняя длина кодового слова – это величина, которая вычисляется как взвешенная вероятностями сумма длин всех кодовых слов.

L cp =p 1 L 1 +p 2 L 2 +...+p n L n ,

где – вероятности кодовых слов;

L 1 ,L 2 ,...,L n – длины кодовых слов.

Существуют два основных способа проведения сжатия.

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

Словарное сжатие – это методы сжатия, хранящие фрагменты данных в "словаре" (некоторая структура данных ). Если строка новых данных, поступающих на вход, идентична какому-либо фрагменту, уже находящемуся в словаре, в выходной поток помещается указатель на этот фрагмент. Лучшие словарные методы применяют метод Зива-Лемпела.

Рассмотрим несколько известных алгоритмов сжатия данных более подробно.

Метод Хаффмана

Этот алгоритм кодирования информации был предложен Д.А. Хаффманом в 1952 году. Хаффмановское кодирование (сжатие) – это широко используемый метод сжатия, присваивающий символам алфавита коды переменной длины, основываясь на вероятностях появления этих символов.

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

Префиксный код – это код, в котором никакое кодовое слово не является префиксом любого другого кодового слова. Эти коды имеют переменную длину.

Оптимальный префиксный код – это префиксный код , имеющий минимальную среднюю длину.

Алгоритм Хаффмана можно разделить на два этапа.

1. Определение вероятности появления символов в исходном тексте.

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

2. Нахождение оптимального префиксного кода.

   Далее находятся два символа a и b с наименьшими вероятностями появления и заменяются одним фиктивным символом x , который имеет вероятность появления, равную сумме вероятностей появления символов a и b . Затем, используя эту процедуру рекурсивно, находится оптимальный префиксный код для меньшего множества символов (где символы a и b заменены одним символом x ). Код для исходного множества символов получается из кодов замещающих символов путем добавления 0 или 1 перед кодом замещающего символа, и эти два новых кода принимаются как коды заменяемых символов. Например, код символа a будет соответствовать коду x с добавленным нулем перед этим кодом, а для символа b перед кодом символа x будет добавлена единица.

Коды Хаффмана имеют уникальный префикс , что и позволяет однозначно их декодировать, несмотря на их переменную длину.

Пример 1 . Программная реализация метода Хаффмана.

#include "stdafx.h" #include using namespace std; void Expectancy(); long MinK(); void SumUp(); void BuildBits(); void OutputResult(char **Result); void Clear(); const int MaxK = 1000; long k, a, b; char bits; char sk; bool Free; char *res; long i, j, n, m, kj, kk1, kk2; char str; int _tmain(int argc, _TCHAR* argv){ char *BinaryCode; Clear(); cout << "Введите строку для кодирования: "; cin >> str; Expectancy(); SumUp(); BuildBits(); OutputResult(&BinaryCode); cout << "Закодированная строка: " << endl; cout << BinaryCode << endl; system("pause"); return 0; } //описание функции обнуления данных в массивах void Clear(){ for (i = 0; i < MaxK + 1; i++){ k[i] = a[i] = b[i] = 0; sk[i] = 0; Free[i] = true; for (j = 0; j < 40; j++) bits[i][j] = 0; } } /*описание функции вычисления вероятности вхождения каждого символа в тексте*/ void Expectancy(){ long *s = new long; for (i = 0; i < 256; i++) s[i] = 0; for (n = 0; n < strlen(str); n++) s]++; j = 0; for (i = 0; i < 256; i++) if (s[i] != 0){ j++; k[j] = s[i]; sk[j] = i; } kj = j; } /*описание функции нахождения минимальной частоты символа в исходном тексте*/ long MinK(){ long min; i = 1; while (!Free[i] && i < MaxK) i++; min = k[i]; m = i; for (i = m + 1; i <= kk2; i++) if (Free[i] && k[i] < min){ min = k[i]; m = i; } Free[m] = false; return min; } //описание функции подсчета суммарной частоты символов void SumUp(){ long s1, s2, m1, m2; for (i = 1; i <= kj; i++){ Free[i] = true; a[i] = 0; b[i] = 0; } kk1 = kk2 = kj; while (kk1 > 2){ s1 = MinK(); m1 = m; s2 = MinK(); m2 = m; kk2++; k = s1 + s2; a = m1; b = m2; Free = true; kk1--; } } //описание функции формирования префиксных кодов void BuildBits(){ strcpy(bits,"1"); Free = false; strcpy(bits],bits); strcat(bits] , "0"); strcpy(bits],bits); strcat(bits] , "1"); i = MinK(); strcpy(bits[m],"0"); Free[m] = true; strcpy(bits],bits[m]); strcat(bits] , "0"); strcpy(bits],bits[m]); strcat(bits] , "1"); for (i = kk2 - 1; i > 0; i--) if (!Free[i]) { strcpy(bits],bits[i]); strcat(bits] , "0"); strcpy(bits],bits[i]); strcat(bits] , "1"); } } //описание функции вывода данных void OutputResult(char **Result){ (*Result) = new char; for (int t = 0; i < 1000 ;i++) (*Result)[t] = 0; for (i = 1; i <= kj; i++) res] = bits[i]; for (i = 0; i < strlen(str); i++) strcat((*Result) , res]); } Листинг.

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

Сжатие данных

Михаил Сваричевский

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

Все алгоритмы сжатия делятся на два типа: с потерями и без.

Сжатие с потерями позволяет достичь гораздо бóльшей степени сжатия (до 1/30 и менее от исходного объема).
Например, видеофильм, занимающий в неупакованном виде гигабайт 30, удается записать на 1 CD.
Однако, алгоритмы сжатия с потерями приводят к некоторым изменениям самих данных; поэтому применять такие алгоритмы можно только к тем данным, для которых небольшие искажения несущественны: видео, фото-изображения (алгоритмы JPEG), звук (алгоритм MP3).

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

Большинство алгоритмов сжатия без потерь делятся на две группы: первыесоставляют текст из кусочков исходного файла в той или иной форме (словарные методы); вторые (статистические методы) используют тот факт, что разные символы или символьные группы появляются в файле с разными вероятностями (например, буква "а" в текстовых файлах встречается гораздо чаще, чем "б").

Словарные методы

Словарные методы отличаются высокой скоростью сжатия/распаковки, но несколько худшим сжатием. Словом называется некоторая последовательность символов. В общем - речь, конечно, идет не о символах, а о байтах; но для простоты в примерах будут использоваться ASCII-символы.

Словарь содержит некоторое количество слов (обычно 2x; например, 4096).
Сжатие достигается за счет того, что номер слова в словаре обычно гораздо короче самого слова.
Алгоритмы словарного сжатия делятся на две группы:
1) использующие словарь в явной форме(алгоритмы LZ78, LZW, LZC, LZT, LZMV, LZJ, LZFG)
Например, по словарю
1. "Большинство"
2. "сжатия"
3. "без"
4. "потерь"
5. "алгоритмов"
текст "Большинство алгоритмов сжатия без потерь" сжимается в "15234".

2) указывающие вместо номера слова - позицию относительно текущей позиции и длину повторяющегося участка (алгоритмы LZ77, LZR, LZSS, LZB, LZH)
Например, текст "абаббабаббабвгббабв"
сжимается в "05абабб5504абвг65", где:
"05абабб" – позиция 0 означает, что далее 5 символов идут без сжатия.
"55" – 5 букв с позиции, отстоящей от текущей на 5 символов назад.
"04абвг" – еще 4 символа не сжимается.
"65" –5 букв с позиции, отстоящей от текущей на 6 символов назад.

Модификации LZ-алгоритмов отличаются только способами представления словаря, поиска и добавления слов. Одни сжимают быстрее, но хуже; другие требуют больше памяти.

Рассмотрим подробнее модифицированный алгоритм LZ77.
Архив будет состоять из записей следующего вида:
(n,m) – означает, что с позиции n начинается такая же строка длиной m, что и с текущей позиции.
(0,m,"m символов") – означает, что далее следует m символов, которые не удалось сжать.

Алгоритм сжатия будет заключаться в следующем: ищем в файле место, начиная с которого идет самая длинная последовательность, совпадающая с последовательностью, начинающейся на текущем байте. Если ее длина больше 3, то в архив записываем начало и длину последовательности; иначе - записываем 0, длину последовательности и сами несжатые символы. Распаковка еще проще: пока файл архива не кончился, читаем по 2 числа(n,m). Если n=0, то m символов из архива сразу помещаем в буфер (эти символы нам еще понадобятся) и записываем в выходной файл. Если n<>0 то из буфера с позиции n копируем m элементов в буфер и выходной файл.

Однако есть две проблемы:
1) Ограниченный размер буфера: если нам нужно будет сжать файл размеров в 100МБ, мы его в буфер никак не поместим. Поэтому, когда он будет заполнен (скажем, на 75%), придется сдвинуть данные в нем к началу (напр., на 25%;конечно, самые старые символы при этом потеряются). Это ухудшит сжатие, но сделает алгоритм нетребовательным к памяти.
2) Скорость работы программы сжатия очень мала. В самом деле, если нужно будет сжать файл размеров 10КБ, то это потребует от нас проведения как минимум около 10000*10000/2 операций (10000 раз нам нужно будет искать совпадающую подпоследовательность, а каждый такой поиск займет в среднем 10000/2 операций). Для того, чтобы ускорить операцию поиска, можно хранить в отдельном массиве номера позиций последовательностей, начинающихся на символ chr(0), chr(2) … chr(255). Тогда при поиске нам нужно будет проверить только те комбинации, первая буква которых совпадает с первой буквой искомой последовательности.

Статистические методы

Статистические методы гораздо медленнее словарных, но достигают более сильного сжатия. В них каждая буква заменяется некоторым кодом. Код – это несколько бит, однозначно идентифицирующие некоторый символ. Статистические методы используют различные приемы для того, чтобы наиболее часто встречающимся символам соответствовали более короткие коды. Существуют два основных алгоритма кодирования букв в соответствии с их частотой встречаемости:

1) Коды Хаффмана: все символы кодируются целым количеством бит; причем так, что раскодирование всегда однозначно (например, если букве "а" соответствует последовательность бит "1001", а "b" – "10010", то раскодирование неоднозначно). Достоинство - высокая скорость сжатия. Недостатки - неоптимальное сжатие, сложности при реализации адаптивного варианта. Так как в последнее время скорость собственно алгоритма кодирования играет все меньшую роль (алгоритмы накопления статистической информации работают все медленнее и медленнее, и даже 2-х кратное увеличение времени работы кодировщика практически не влияет на скорость), этот алгоритм не имеет существенных преимуществ перед арифметическим кодированием.

2) Арифметическое кодирование: для каждого символа определяется промежуток на отрезке и в зависимости от ширины этого отрезка может выделяться разное количество бит, условно говоря, даже дробное (например: пусть строке "a" соответствует0 , а строке "ab" - 1, тогда строка "aba" закодируется в 2 бита, т.е в среднем 2/3 бита на символ). Этот метод точнее использует статистическую информацию, и всегда сжимает не хуже алгоритма Хаффмана, но медленнее. Достоинства - максимальная теоретически достижимая степень сжатия, простая реализация адаптивного варианта. Недостатки - несколько меньшая скорость.

Принцип работы арифметического кодирования:

Например, мы присвоили символу "a" промежуток , "b" – и "c" – . Тогда, если у нас будет число 0.4, то мы можем сказать, что закодирована буква "b"(0.3<=0.4<=0.6), а если 0.9 – то c(0.6<=0.9<=1). Итак, у нас получилось закодировать 1 букву в число. Как же закодировать 2 буквы? Очень просто: например, если первая буква – "b", то интервал равен . Разделим этот интервал на части, в отношении наших первоначальных отрезков. Тогда 2-м буквам "ba" будет соответствовать интервал , "bb" – и "bc" – . Для раскодирования нам достаточно знать любое число из этого интервала.

Попробуем раскодировать: пусть дано число 0.15. Это число попадает в интервал буквы "a", значит первая закодированная буква – "a". Для того, чтобы узнать вторую букву, нужно преобразовать число, чтобы оно указывало букву в интервале не , а . Для этого от числа отнимем нижнюю границу исходного интервала (0) и разделим на ширину интервала (0.3-0=0.3). Получим новое число(0.15-0)/0.3 = 0.5. Повторив те же действия, мы узнаем, что вторая буква – "b". Если бы было закодировано 3 и более букв, то, многократно повторяя этот процесс, мы нашли бы все буквы.

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

Алгоритм сжатия:
Для каждого символа мы должны присвоить соответствующий промежуток в соответствии с частотой (вероятностью встречи) в данных: пусть символ "а"имеет вероятность 0.4, "b" – 0,3 и "c" – тоже 0.3; тогда символу "а" будет соответствовать промежуток , "b" – , "c" – . Т.е мы делим имеющийся у нас промежуток между всеми необходимыми буквами в соответствии с вероятностью их встречи (более вероятному символу соответствует больший промежуток).

В процессе сжатия у нас есть 2 границы: верхняя и нижняя, назовем их соответственно hiи lo. Пусть нам нужно закодировать символ, которому мы отвели промежуток . Тогда в наш промежуток "вставляется" промежуток символа, и lo будет равен нижней границе вставляемого промежутка, hi – верхней. В итоге по мере кодирования промежуток между loи hi становится все уже и уже. Наконец, когда мы закодировали все данные, выбираем любое число из получившегося промежутка и выводим. Оно и будет сжатыми данными.

Распаковка:
Построим промежутки для символов, как и для сжатия. Символ, в промежуток которого попадает число-архив, и есть первый символ данных. "Растягиваем" промежуток символа вместе с числом-архивом до промежутка (т.е отнимаем нижнюю границу интервала только что раскодированного символа, и делим на ширину этого интервала), затем повторяем операцию, пока все не раскодируем.

Проблемы:
Если бы все было так просто… На самом деле, для хранения числа-архива нужна будет очень большая точность (десятки и сотни тысяч знаков), поэтому на практике приходится пользоваться обычными типами данных. Чтобы этого добиться, будем смотреть на старшие биты/цифры числа-архива. Как только у hi и lo они совпадут, мы можем сразу записать их в архив и "отсечь". При распаковке наоборот, когда увидим, что мы довольно много раз расширяли промежуток до , считаем из файла-архива несколько цифр и допишем их в конец нашего числа-архива.
Часто используется модификация арифметического кодирования - range coder. Основное отличие - начальный интервал - . Это позволяет выводить данные сразу по байту, а не наскребать по биту, что отражается на скорости работы. В конце статьи приведена реализация именно этого варианта.

Определение вероятностей символов

Основной процесс, влияющий на скорость и степень сжатия – определение вероятностей символов. В простейшем случае будем считать вероятностью символа - количество его встреч в уже закодированной части данных, делённое на общее количество символов в данных. Для текстов это дает приблизительно 2-кратное сжатие. Чтобы его увеличить, можно учитывать такие факты, как, например, то, что вероятность встречи символа "я" после "ю" практически равна 0, а "o" после "с" – около 0.25. Поэтому для каждого предыдущего символа будем отдельно считать вероятности.

Предположения, которые мы делаем относительно сжимаемых данных (например, зависимость вероятности от предыдущих символов) называются вероятностной моделью. Модель, вероятности в которой не зависят от предыдущих символов, называется моделью 0-го порядка. Если вероятности зависят от 1 предыдущего символа, то это модель 1-го порядка, если от 2-х последних – то 2-го и т.д. Для эффективного вычисления вероятностей символов в моделях высокого порядка существуют специальная группа алгоритмов – PPM и его модификации.
Модели могут быть неадаптивными, полуадаптивными и адаптивными. В неадаптивных методах вероятности всех символов жестко зашиты в программу. В полуадаптивных по входным данным делается 2 прохода: 1-й - для определения вероятностей, 2-й – собственно для сжатия. Адаптивный – вероятности символов изменяются в процессе сжатия. Адаптивные модели самые медленные, но они обычно сжимают данные сильнее неадаптивных и полуадаптивных моделей. В общем, среди всех моделей лучше сжимают использующие наибольшее кол-во информации о сжимаемых данных - зависимость от предыдущих символов, некоторые факты, например: в текстах после точки обычно следует большая буква и т.д.

Алгоритмы, используемые в популярных архиваторах:

ZIP,ARJ,RAR - LZ+Хаффман
HA - PPM+Арифметическое кодирование
BOA - BWT+Арифметическое кодирование
UHARC - LZ+PPM+Арифметическое кодирование
(Здесь "+" означает, что результат работы алгоритма, написанного слева от знака, далее сжимается алгоритмом, записанным справа).
Как видно, в архиваторах ZIP,ARJ,RAR ,разрабатывавшихся в конце 80-х - начале 90-х, используются уже довольно устаревшие алгоритмы; поэтому они по тестам проигрывают более современным.

Пример программы адаптивного сжатия/распаковки 0-го порядка:

Данные: compr – тут хранятся сжатые данные
Data- тут хранятся исходные данные
Freq – частоты символов

Procedure compress_range; {Процедура сжатия}
Var
cum_freq: Extended;
Begin
{- Инициализация модели и кодера -}
For q:= 0 To 255 Do
freq [q] := 1; {Все символы в начале имеют одинаковую вероятность}
freq := freq - 0.20000;
total:= 256; {Сумма частот всех символов.}
{ В freq - небольшой остступ от 0 и макс.значения}
PC:= 0;{Кол-во уже закодированых байт }
Lo:= 0; range:= 256;
{- Кодирование -}
For q:= 1 To Size Do
Begin
{Нахождение интервала, соответствующего кодируемому символу}
cum_freq:= 0.1; {Начинаем накапливать вероятность}
For w:= 0 To data [q] - 1 Do
cum_freq:= cum_freq + freq [w];
{Изменяем range&lo}
range:= range / total;
Lo:= Lo + range * (cum_freq);
range:= range * freq ];
{Нормализация т.е вывод байтов, одинаковых у Lo и Hi(Hi=Lo+Range)}

Begin
Inc (PC);
compr := Trunc (Lo);
Lo:= Frac (Lo) * 256;
range:= range * 256;
End;
{Обновления модели}
freq ] := freq ] + 1;
{Присваеваем кодируемому символу на 1 большую вероятность}
total:= total + 1;
End;
{Сжатие закончено, выводим остаток}
Lo:= Lo + range / 2;
Inc (PC);
compr := Trunc (Lo);
Lo:= Frac (Lo) * 256;
range:= range * 256;
End;

Procedure decompress_range;{Процедура распаковки}
Var
temp: Extended;
ee: Extended;
Begin
{Инициализация модели и кодера}
For q:= 0 To 255 Do
freq [q] := 1;
freq := freq - 0.20000; { В freq - небольшой остступ от 0 и макс.значения}
total:= 256;
PC:= 4; {PC - номер байта, которые мы считываем}
code:= 0;
Lo:= 0; range:= 256;
{Считываем начальное, приближенное значение code.}
For q:= 1 To 4 Do
Begin
code:= code * 256 + compr [q] / 65536 / 256;
End;
w:= 0; {W- кол-во верно распакованных байт}
{Собственно расжатие}
While True Do
Begin
{Нахождения вероятности следующего символа}
temp:= (code- Lo) * total / range;
{Поиск символа, в интервал которого попадает temp}
sum:= 0.1; ssum:= 0.1;
For e:= 0 To 255 Do
Begin
sum:= sum + freq [e];
If sum > temp Then Break;
ssum:= sum;
End;
Inc (w);
{Проверка правильности распаковки}
{Сейчас в e – распакованный байт, и его можно выводить в файл}
If data [w] <> e Then Break; {Если неправильно распаковали - выходим}
If w = Size Then Begin Inc (w); Break End; {Если все распаковали выходим,}
{и модель не обновляем:-)}
{Обновления Lo&Hi(Растягивание)}
range:= range / total;
Lo:= Lo + range * (ssum);
range:= range * (freq [e]);
{Обновление модели(Делаем символ e более вероятным)}
freq [e] := freq [e] + 1;
total:= total + 1;
{Нормализация, уточнение числа}
While Trunc (Lo) = Trunc (Lo + range) Do
Begin
Inc (PC);
temp:=compr;
code:= (code - trunc(code)) * 256 + temp / 16777216;
Lo:= Frac (Lo) * 256;
range:= range * 256;
End;
End;
Dec (w);
{DONE_DECOMPRESS}
End;

Введение.

Сжатие сокращает объем пространства, тpебуемого для хранения файлов в ЭВМ, и

количество времени, необходимого для передачи информации по каналу установленной

ширины пропускания. Это есть форма кодирования. Другими целями кодирования

являются поиск и исправление ошибок, а также шифрование. Процесс поиска и

исправления ошибок противоположен сжатию - он увеличивает избыточность данных,

когда их не нужно представлять в удобной для восприятия человеком форме. Удаляя

из текста избыточность, сжатие способствует шифpованию, что затpудняет поиск

шифpа доступным для взломщика статистическим методом.

Рассмотpим обратимое сжатие или сжатие без наличия помех, где первоначальный

текст может быть в точности восстановлен из сжатого состояния. Необратимое или

ущербное сжатие используется для цифровой записи аналоговых сигналов, таких как

человеческая речь или рисунки. Обратимое сжатие особенно важно для текстов,

записанных на естественных и на искусственных языках, поскольку в этом случае

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

рассматриваемых методов есть сжатие текстов, что отpажает и наша терминология,

однако, эта техника может найти применение и в других случаях, включая обратимое

кодирование последовательностей дискретных данных.

Существует много веских причин выделять ресурсы ЭВМ в pасчете на сжатое

представление, т.к. более быстрая передача данных и сокpащение пpостpанства для

их хpанения позволяют сберечь значительные средства и зачастую улучшить

показатели ЭВМ. Сжатие вероятно будет оставаться в сфере внимания из-за все

возрастающих объемов хранимых и передаваемых в ЭВМ данных, кроме того его можно

использовать для преодоления некотоpых физических ограничений, таких как,

напpимеp, сравнительно низкая шиpину пpопускания телефонных каналов.

ПРИМЕНЕНИЕ РАСШИРЯЮЩИХСЯ ДЕРЕВЬЕВ ДЛЯ СЖАТИЯ ДАННЫХ.

Алгоритмы сжатия могут повышать эффективность хранения и передачи данных

посредством сокращения количества их избыточности. Алгоритм сжатия берет в

качестве входа текст источника и производит соответствующий ему сжатый текст,

когда как разворачивающий алгоритм имеет на входе сжатый текст и получает из

него на выходе первоначальный текст источника. Большинство алгоритмов сжатия

рассматривают исходный текст как набор строк, состоящих из букв алфавита

исходного текста.

Избыточность в представлении строки S есть L(S) - H(S), где L(S) есть длина

представления в битах, а H(S) - энтропия - мера содержания информации, также

выраженная в битах. Алгоритмов, которые могли бы без потери информации сжать

строку к меньшему числу бит, чем составляет ее энтропия, не существует. Если из

исходного текста извлекать по одной букве некоторого случайного набоpа,

использующего алфавит А, то энтропия находится по формуле:

H(S) = C(S) p(c) log ---- ,

где C(S) есть количество букв в строке, p(c) есть статическая вероятность

появления некоторой буквы C. Если для оценки p(c) использована частота появления

каждой буквы c в строке S, то H(C) называется самоэнтропией строки S. В этой

статье H (S) будет использоваться для обозначения самоэнтропии строки, взятой из

статичного источника.

Расширяющиеся деревья обычно описывают формы лексикографической упорядоченности

деpевьев двоичного поиска, но деревья, используемые при сжатии данных могут не

иметь постоянной упорядоченности. Устранение упорядоченности приводит к

значительному упрощению основных операций расширения. Полученные в итоге

алгоритмы предельно быстры и компактны. В случае применения кодов Хаффмана,

pасширение приводит к локально адаптированному алгоритму сжатия, котоpый

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

Когда он применяется к арифметическим кодам, то результат сжатия близок к

оптимальному и приблизительно оптимален по времени.

КОДЫ ПРЕФИКСОВ.

Большинство широко изучаемых алгоритмов сжатия данных основаны на кодах

Хаффмана. В коде Хаффмана каждая буква исходного текста представляется в архиве

кодом переменной длины. Более частые буквы представляются короткими кодами,

менее частые - длинными. Коды, используемые в сжатом тексте должны подчиняться

свойствам префикса, а именно: код, использованный в сжатом тексте не может быть

префиксом любого другого кода.

Коды префикса могут быть найдены посредством дерева, в котором каждый лист

соответствует одной букве алфавита источника. Hа pисунке 1 показано дерево кода

префикса для алфавита из 4 букв. Код префикса для буквы может быть прочитан при

обходе деpева от корня к этой букве, где 0 соответствует выбору левой его ветви,

а 1 - правой. Дерево кода Хаффмана есть дерево с выравненным весом, где каждый

лист имеет вес, равный частоте встречаемости буквы в исходном тексте, а

внутренние узлы своего веса не имеют. Дерево в примере будет оптимальным, если

частоты букв A, B, C и D будут 0.125, 0.125, 0.25 и 0.5 соответственно.

Обычные коды Хаффмана требуют предварительной информации о частоте встречаемости

букв в исходном тексте, что ведет к необходимости его двойного просмотра - один

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

последующем, значения этих частот нужно объединять с самим сжатым текстом, чтобы

в дальнейшем сделать возможным его развертывание. Адаптивное сжатие выполняется

за один шаг, т.к. код, используемый для каждой буквы исходного текста, основан

на частотах всех остальных кpоме нее букв алфавита. Основы для эффективной

реализации адаптивного кода Хаффмана были заложены Галлагером, Кнут опубликовал

практическую версию такого алгоритма, а Уиттер его pазвил.

Оптимальный адаптированный код Уиттера всегда лежит в пределах одного бита на

букву источника по отношению к оптимальному статичному коду Хаффмана, что обычно

составляет несколько процентов от H . К тому же, статичные коды Хаффмана всегда

лежат в пределах одного бита на букву исходного текста от H (они достигают этот

предел только когда для всех букв p(C) = 2). Существуют алгоритмы сжатия

которые могут преодолевать эти ограничения. Алгоритм Зива-Лемпелла, например,

присваивает слова из аpхива фиксированной длины строкам исходного текста

пеpеменной длины, а арифметическое сжатие может использовать для кодирования

букв источника даже доли бита.

Применение расширения к кодам префикса.

Расширяющиеся деревья были впервые описаны в 1983 году и более подpобно

рассмотрены в 1985. Первоначально они понимались как вид самосбалансиpованных

деpевьев двоичного поиска, и было также показано, что они позволяют осуществить

самую быструю реализацию приоритетных очередей. Если узел расширяющегося дерева

доступен, то оно является расширенным. Это значит, что доступный узел становится

корнем, все узлы слева от него образуют новое левое поддерево, узлы справа -

новое правое поддерево. Расширение достигается при обходе дерева от старого

корня к целевому узлу и совершении пpи этом локальных изменений, поэтому цена

расширения пропорциональна длине пройденного пути.

Тарьян и Слейтон показали, что расширяющиеся деревья статично оптимальны.

Другими словами, если коды доступных узлов взяты согласно статичному

распределению вероятности, то скорости доступа к расширяющемуся дереву и

статично сбалансированному, оптимизированному этим распределением, будут

отличаться друг от друга на постоянный коэффициент, заметный при достаточно

длинных сериях доступов. Поскольку дерево Хаффмана представляет собой пример

статично сбалансированного дерева, то пpи использовании расширения для сжатия

данных, pазмер сжатого текста будет лежать в пределах некоторого коэффициента от

размера архива, полученного при использовании кода Хаффмана.

Как было первоначально описано, расширение применяется к деревьям, хранящим

данные во внутренних узлах, а не в листьях. Деревья же кодов префикса несут все

свои данные только в листьях. Существует, однако, вариант расширения, называемый

полурасширением, который применим для дерева кодов префикса. При нем целевой

узел не перемещается в корень и модификация его наследников не производится,

взамен путь от корня до цели просто уменьшается вдвое. Полурасширение достигает

тех же теоретических границ в пределах постоянного коэффициента, что и

расширение.

В случае зигзагообразного обхода лексикографического дерева, проведение как

расширения, так и полурасширения усложняется, в отличие от прямого маршрута по

левому или правому краю дерева к целевому узлу. Этот простой случай показан на

рисунке 2. Воздействие полурасширения на маршруте от корня (узел w) до листа

узла A заключается в перемене местами каждой пары внутренних следующих друг за

другом узлов, в результате чего длина пути от корня до узла-листа сокращается в

2 раза. В процессе полурасширения узлы каждой пары, более далекие от корня,

включаются в новый путь (узлы x и z), а более близкие из него

исключаются (узлы w и y).

Сохранение операцией полурасширения лексикографического порядка в деревьях кода

префикса не является обязательным. Единственно важным в операциях с кодом

префикса является точное соответствие дерева, используемого процедурой сжатия

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

между последовательно идущими буквами, производится только в том случае, если

обе процедуры осуществляют одинаковые изменения в одинаковом порядке.

Hенужность поддержки лексикографического порядка значительно упрощает проведение

операции полурасширения за счет исключения случая зигзага. Это может быть

Мы с моим научным руководителем готовим небольшую монографию по обработке изображений. Решил представить на суд хабрасообщества главу, посвящённую алгоритмам сжатия изображений. Так как в рамках одного поста целую главу уместить тяжело, решил разбить её на три поста:
1. Методы сжатия данных;
2. Сжатие изображений без потерь;
3. Сжатие изображений с потерями.
Ниже вы можете ознакомиться с первым постом серии.

На текущий момент существует большое количество алгоритмов сжатия без потерь, которые условно можно разделить на две большие группы:
1. Поточные и словарные алгоритмы. К этой группе относятся алгоритмы семейств RLE (run-length encoding), LZ* и др. Особенностью всех алгоритмов этой группы является то, что при кодировании используется не информация о частотах символов в сообщении, а информация о последовательностях, встречавшихся ранее.
2. Алгоритмы статистического (энтропийного) сжатия. Эта группа алгоритмов сжимает информацию, используя неравномерность частот, с которыми различные символы встречаются в сообщении. К алгоритмам этой группы относятся алгоритмы арифметического и префиксного кодирования (с использованием деревьев Шеннона-Фанно, Хаффмана, секущих).
В отдельную группу можно выделить алгоритмы преобразования информации. Алгоритмы этой группы не производят непосредственного сжатия информации, но их применение значительно упрощает дальнейшее сжатие с использованием поточных, словарных и энтропийных алгоритмов.

Поточные и словарные алгоритмы

Кодирование длин серий

Кодирование длин серий (RLE - Run-Length Encoding) - это один из самых простых и распространённых алгоритмов сжатия данных. В этом алгоритме последовательность повторяющихся символов заменяется символом и количеством его повторов.
Например, строку «ААААА», требующую для хранения 5 байт (при условии, что на хранение одного символа отводится байт), можно заменить на «5А», состоящую из двух байт. Очевидно, что этот алгоритм тем эффективнее, чем длиннее серия повторов.

Основным недостатком этого алгоритма является его крайне низкая эффективность на последовательностях неповторяющихся символов. Например, если рассмотреть последовательность «АБАБАБ» (6 байт), то после применения алгоритма RLE она превратится в «1А1Б1А1Б1А1Б» (12 байт). Для решения проблемы неповторяющихся символов существуют различные методы.

Самым простым методом является следующая модификация: байт, кодирующий количество повторов, должен хранить информацию не только о количестве повторов, но и об их наличии. Если первый бит равен 1, то следующие 7 бит указывают количество повторов соответствующего символа, а если первый бит равен 0, то следующие 7 бит показывают количество символов, которые надо взять без повтора. Если закодировать «АБАБАБ» с использованием данной модификации, то получим «-6АБАБАБ» (7 байт). Очевидно, что предложенная методика позволяет значительно повысить эффективность RLE алгоритма на неповторяющихся последовательностях символов. Реализация предложенного подхода приведена в Листинг 1:

1. type
2. function RLEEncode(InMsg: ShortString) : TRLEEncodedString;
3. MatchFl: boolean ;
4. MatchCount: shortint ;
5. EncodedString: TRLEEncodedString;
6. N, i: byte ;
7. begin
8. N : = 0 ;
9. SetLength(EncodedString, 2 * length(InMsg) ) ;
10. while length(InMsg) >= 1 do
11. begin
12. MatchFl : = (length(InMsg) > 1 ) and (InMsg[ 1 ] = InMsg[ 2 ] ) ;
13. MatchCount : = 1 ;
14. while (MatchCount <= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do
15. MatchCount : = MatchCount + 1 ;
16. if MatchFl then
17. begin
18. N : = N + 2 ;
19. EncodedString[ N - 2 ] : = MatchCount + 128 ;
20. EncodedString[ N - 1 ] : = ord (InMsg[ 1 ] ) ;
21. else
22. begin
23. if MatchCount <> length(InMsg) then
24. MatchCount : = MatchCount - 1 ;
25. N : = N + 1 + MatchCount;
26. EncodedString[ N - 1 - MatchCount] : = - MatchCount + 128 ;
27. for i : = 1 to MatchCount do
28. EncodedString[ N - 1 - MatchCount + i] : = ord (InMsg[ i] ) ;
29. end ;
30. delete(InMsg, 1 , MatchCount) ;
31. end ;
32. SetLength(EncodedString, N) ;
33. RLEEncode : = EncodedString;
34. end ;

Декодирование сжатого сообщения выполняется очень просто и сводится к однократному проходу по сжатому сообщению см. Листинг 2:

1. type
2. TRLEEncodedString = array of byte ;
3. function RLEDecode(InMsg: TRLEEncodedString) : ShortString;
4. RepeatCount: shortint ;
5. i, j: word ;
6. OutMsg: ShortString;
7. begin
8. OutMsg : = "" ;
9. i : = 0 ;
10. while i < length(InMsg) do
11. begin
12. RepeatCount : = InMsg[ i] - 128 ;
13. i : = i + 1 ;
14. if RepeatCount < 0 then
15. begin
16. RepeatCount : = abs (RepeatCount) ;
17. for j : = i to i + RepeatCount - 1 do
18. OutMsg : = OutMsg + chr (InMsg[ j] ) ;
19. i : = i + RepeatCount;
20. else
21. begin
22. for j : = 1 to RepeatCount do
23. OutMsg : = OutMsg + chr (InMsg[ i] ) ;
24. i : = i + 1 ;
25. end ;
26. end ;
27. RLEDecode : = OutMsg;
28. end ;

Вторым методом повышения эффективности алгоритма RLE является использование алгоритмов преобразования информации, которые непосредственно не сжимают данные, но приводят их к виду, более удобному для сжатия. В качестве примера такого алгоритма мы рассмотрим BWT-перестановку, названную по фамилиям изобретателей Burrows-Wheeler transform. Эта перестановка не изменяет сами символы, а изменяет только их порядок в строке, при этом повторяющиеся подстроки после применения перестановки собираются в плотные группы, которые гораздо лучше сжимаются с помощью алгоритма RLE. Прямое BWT преобразование сводится к последовательности следующих шагов:
1. Добавление к исходной строке специального символа конца строки, который нигде более не встречается;
2. Получение всех циклических перестановок исходной строки;
3. Сортировка полученных строк в лексикографическом порядке;
4. Возвращение последнего столбца полученной матрицы.
Реализация данного алгоритма приведена в Листинг 3.

1. const
2. EOMsg = "|" ;
3. function BWTEncode(InMsg: ShortString) : ShortString;
4. OutMsg: ShortString;
5. LastChar: ANSIChar;
6. N, i: word ;
7. begin
8. InMsg : = InMsg + EOMsg;
9. N : = length(InMsg) ;
10. ShiftTable[ 1 ] : = InMsg;
11. for i : = 2 to N do
12. begin
13. LastChar : = InMsg[ N] ;
14. InMsg : = LastChar + copy(InMsg, 1 , N - 1 ) ;
15. ShiftTable[ i] : = InMsg;
16. end ;
17. Sort(ShiftTable) ;
18. OutMsg : = "" ;
19. for i : = 1 to N do
20. OutMsg : = OutMsg + ShiftTable[ i] [ N] ;
21. BWTEncode : = OutMsg;
22. end ;

Проще всего пояснить это преобразование на конкретном примере. Возьмём строку «АНАНАС» и договоримся, что символом конца строки будет символ «|». Все циклические перестановки этой строки и результат их лексикографической сортировки приведены в Табл. 1.

Т.е. результатом прямого преобразования будет строка «|ННАААС». Легко заметить, что это строка гораздо лучше, чем исходная, сжимается алгоритмом RLE, т.к. в ней существуют длинные подпоследовательности повторяющихся букв.
Подобного эффекта можно добиться и с помощью других преобразований, но преимущество BWT-преобразования в том, что оно обратимо, правда, обратное преобразование сложнее прямого. Для того, чтобы восстановить исходную строку, необходимо выполнить следующие действия:
Создать пустую матрицу размером n*n, где n-количество символов в закодированном сообщении;
Заполнить самый правый пустой столбец закодированным сообщением;
Отсортировать строки таблицы в лексикографическом порядке;
Повторять шаги 2-3, пока есть пустые столбцы;
Вернуть ту строку, которая заканчивается символом конца строки.

Реализация обратного преобразования на первый взгляд не представляет сложности, и один из вариантов реализации приведён в Листинг 4.

1. const
2. EOMsg = "|" ;
3. function BWTDecode(InMsg: ShortString) : ShortString;
4. OutMsg: ShortString;
5. ShiftTable: array of ShortString;
6. N, i, j: word ;
7. begin
8. OutMsg : = "" ;
9. N : = length(InMsg) ;
10. SetLength(ShiftTable, N + 1 ) ;
11. for i : = 0 to N do
12. ShiftTable[ i] : = "" ;
13. for i : = 1 to N do
14. begin
15. for j : = 1 to N do
16. ShiftTable[ j] : = InMsg[ j] + ShiftTable[ j] ;
17. Sort(ShiftTable) ;
18. end ;
19. for i : = 1 to N do
20. if ShiftTable[ i] [ N] = EOMsg then
21. OutMsg : = ShiftTable[ i] ;
22. delete(OutMsg, N, 1 ) ;
23. BWTDecode : = OutMsg;
24. end ;

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

После сортировки таблицы, полученной на седьмом шаге, необходимо выбрать из таблицы строку, заканчивающуюся символом «|». Легко заметить, что это строка единственная. Т.о. мы на конкретном примере рассмотрели преобразование BWT.

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

Словарное сжатие (алгоритмы LZ)

Группа словарных алгоритмов, в отличие от алгоритмов группы RLE, кодирует не количество повторов символов, а встречавшиеся ранее последовательности символов. Во время работы рассматриваемых алгоритмов динамически создаётся таблица со списком уже встречавшихся последовательностей и соответствующих им кодов. Эту таблицу часто называют словарём, а соответствующую группу алгоритмов называют словарными.

Ниже описан простейший вариант словарного алгоритма:
Инициализировать словарь всеми символами, встречающимися во входной строке;
Найти в словаре самую длинную последовательность (S), совпадающую с началом кодируемого сообщения;
Выдать код найденной последовательности и удалить её из начала кодируемого сообщения;
Если не достигнут конец сообщения, считать очередной символ и добавить Sc в словарь, перейти к шагу 2. Иначе, выход.

Например, только что инициализированный словарь для фразы «КУКУШКАКУКУШОНКУКУПИЛАКАПЮШОН» приведён в Табл. 3:

В процессе сжатия словарь будет дополняться встречающимися в сообщении последовательностями. Процесс пополнения словаря приведён в Табл. 4.

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

Для начала определим словарь как запись, хранящую не только встречавшиеся подстроки, но и количество хранящихся в словаре подстрок:

Встречавшиеся ранее подпоследовательности хранятся в массиве Words, а их кодом являются номера подпоследовательностей в этом массиве.
Также определим функции поиска в словаре и добавления в словарь:

1. const
2. MAX_DICT_LENGTH = 256 ;
3. function FindInDict(D: TDictionary; str: ShortString) : integer ;
4. r: integer ;
5. i: integer ;
6. fl: boolean ;
7. begin
8. r : = - 1 ;
9. if D. WordCount > 0 then
10. begin
11. i : = D. WordCount ;
12. fl : = false ;
13. while (not fl) and (i >= 0 ) do
14. begin
15. i : = i - 1 ;
16. fl : = D. Words [ i] = str;
17. end ;
18. end ;
19. if fl then
20. r : = i;
21. FindInDict : = r;
22. end ;
23. procedure AddToDict(var D: TDictionary; str: ShortString) ;
24. begin
25. if D. WordCount < MAX_DICT_LENGTH then
26. begin
27. D. WordCount : = D. WordCount + 1 ;
28. SetLength(D. Words , D. WordCount ) ;
29. D. Words [ D. WordCount - 1 ] : = str;
30. end ;
31. end ;

Используя эти функции, процесс кодирования по описанному алгоритму можно реализовать следующим образом:

1. function LZWEncode(InMsg: ShortString) : TEncodedString;
2. OutMsg: TEncodedString;
3. tmpstr: ShortString;
4. D: TDictionary;
5. i, N: byte ;
6. begin
7. SetLength(OutMsg, length(InMsg) ) ;
8. N : = 0 ;
9. InitDict(D) ;
10. while length(InMsg) > 0 do
11. begin
12. tmpstr : = InMsg[ 1 ] ;
13. while (FindInDict(D, tmpstr) >= 0 ) and (length(InMsg) > length(tmpstr) ) do
14. tmpstr : = tmpstr + InMsg[ length(tmpstr) + 1 ] ;
15. if FindInDict(D, tmpstr) < 0 then
16. delete(tmpstr, length(tmpstr) , 1 ) ;
17. OutMsg[ N] : = FindInDict(D, tmpstr) ;
18. N : = N + 1 ;
19. delete(InMsg, 1 , length(tmpstr) ) ;
20. if length(InMsg) > 0 then
21. AddToDict(D, tmpstr + InMsg[ 1 ] ) ;
22. end ;
23. SetLength(OutMsg, N) ;
24. LZWEncode : = OutMsg;
25. end ;

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

Единственная проблема возможна в следующей ситуации: когда необходимо декодировать подпоследовательность, которой ещё нет в словаре. Легко убедиться, что это возможно только в случае, когда необходимо извлечь подстроку, которая должна быть добавлена на текущем шаге. А это значит, что подстрока удовлетворяет шаблону cSc, т.е. начинается и заканчивается одним и тем же символом. При этом cS – это подстрока, добавленная на предыдущем шаге. Рассмотренная ситуация – единственная, когда необходимо декодировать ещё не добавленную строку. Учитывая вышесказанное, можно предложить следующий вариант декодирования сжатой строки:

1. function LZWDecode(InMsg: TEncodedString) : ShortString;
2. D: TDictionary;
3. OutMsg, tmpstr: ShortString;
4. i: byte ;
5. begin
6. OutMsg : = "" ;
7. tmpstr : = "" ;
8. InitDict(D) ;
9. for i : = 0 to length(InMsg) - 1 do
10. begin
11. if InMsg[ i] >= D. WordCount then
12. tmpstr : = D. Words [ InMsg[ i - 1 ] ] + D. Words [ InMsg[ i - 1 ] ] [ 1 ]
13. else
14. tmpstr : = D. Words [ InMsg[ i] ] ;
15. OutMsg : = OutMsg + tmpstr;
16. if i > 0 then
17. AddToDict(D, D. Words [ InMsg[ i - 1 ] ] + tmpstr[ 1 ] ) ;
18. end ;
19. LZWDecode : = OutMsg;
20. end ;

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

Энтропийное кодирование

Кодирование с помощью деревьев Шеннона-Фано

Алгоритм Шеннона-Фано - один из первых разработанных алгоритмов сжатия. В основе алгоритма лежит идея представления более частых символов с помощью более коротких кодов. При этом коды, полученные с помощью алгоритма Шеннона-Фано, обладают свойством префиксности: т.е. ни один код не является началом никакого другого кода. Свойство префиксности гарантирует, что кодирование будет взаимно-однозначным. Алгоритм построения кодов Шеннона-Фано представлен ниже:
1. Разбить алфавит на две части, суммарные вероятности символов в которых максимально близки друг к другу.
2. В префиксный код первой части символов добавить 0, в префиксный код второй части символов добавить 1.
3. Для каждой части (в которой не менее двух символов) рекурсивно выполнить шаги 1-3.
Несмотря на сравнительную простоту, алгоритм Шеннона-Фано не лишён недостатков, самым существенным из которых является неоптимальность кодирования. Хоть разбиение на каждом шаге и является оптимальным, алгоритм не гарантирует оптимального результата в целом. Рассмотрим, например, следующую строку: «ААААБВГДЕЖ». Соответствующее дерево Шеннона-Фано и коды, полученные на его основе, представлены на Рис. 1:

Без использования кодирования сообщение будет занимать 40 бит (при условии, что каждый символ кодируется 4 битами), а с использованием алгоритма Шеннона-Фано 4*2+2+4+4+3+3+3=27 бит. Объём сообщения уменьшился на 32.5%, но ниже будет показано, что этот результат можно значительно улучшить.

Кодирование с помощью деревьев Хаффмана

Алгоритм кодирования Хаффмана, разработанный через несколько лет после алгоритма Шеннона-Фано, тоже обладает свойством префиксности, а, кроме того, доказанной минимальной избыточностью, именно этим обусловлено его крайне широкое распространение. Для получения кодов Хаффмана используют следующий алгоритм:
1. Все символы алфавита представляются в виде свободных узлов, при этом вес узла пропорционален частоте символа в сообщении;
2. Из множества свободных узлов выбираются два узла с минимальным весом и создаётся новый (родительский) узел с весом, равным сумме весов выбранных узлов;
3. Выбранные узлы удаляются из списка свободных, а созданный на их основе родительский узел добавляется в этот список;
4. Шаги 2-3 повторяются до тех пор, пока в списке свободных больше одного узла;
5. На основе построенного дерева каждому символу алфавита присваивается префиксный код;
6. Сообщение кодируется полученными кодами.

Рассмотрим тот же пример, что и в случае с алгоритмом Шеннона-Фано. Дерево Хаффмана и коды, полученные для сообщения «ААААБВГДЕЖ», представлены на Рис. 2:

Легко подсчитать, что объём закодированного сообщения составит 26 бит, что меньше, чем в алгоритме Шеннона-Фано. Отдельно стоит отметить, что ввиду популярности алгоритма Хаффмана на данный момент существует множество вариантов кодирования Хаффмана, в том числе и адаптивное кодирование, которое не требует передачи частот символов.
Среди недостатков алгоритма Хаффмана значительную часть составляют проблемы, связанные со сложностью реализации. Использование для хранения частот символов вещественных переменных сопряжено с потерей точности, поэтому на практике часто используют целочисленные переменные, но, т.к. вес родительских узлов постоянно растёт, рано или поздно возникает переполнение. Т.о., несмотря на простоту алгоритма, его корректная реализация до сих пор может вызывать некоторые затруднения, особенно для больших алфавитов.

Кодирование с помощью деревьев секущих функций

Кодирование с помощью секущих функций – разработанный авторами алгоритм, позволяющий получать префиксные коды. В основе алгоритма лежит идея построения дерева, каждый узел которого содержит секущую функцию. Чтобы подробнее описать алгоритм, необходимо ввести несколько определений.
Слово – упорядоченная последовательность из m бит (число m называют разрядностью слова).
Литерал секущей – пара вида разряд-значение разряда. Например, литерал (4,1) означает, что 4 бит слова должен быть равен 1. Если условие литерала выполняется, то литерал считается истинным, в противном случае - ложным.
k-разрядной секущей называют множество из k литералов. Если все литералы истинны, то и сама секущая функция истинная, в противном случае она ложная.

Дерево строится так, чтобы каждый узел делил алфавит на максимально близкие части. На Рис. 3 показан пример дерева секущих:

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

Арифметическое кодирование

Арифметическое кодирование – один из наиболее эффективных способов сжатия информации. В отличие от алгоритма Хаффмана арифметическое кодирование позволяет кодировать сообщения с энтропией меньше 1 бита на символ. Т.к. большинство алгоритмов арифметического кодирования защищены патентами, далее будут описаны только основные идеи.
Предположим, что в используемом алфавите N символов a_1,…,a_N, с частотами p_1,…,p_N, соответственно. Тогда алгоритм арифметического кодирования будет выглядеть следующим образом:
В качестве рабочего полуинтервала взять }