Каким свойством должны обладать данные чтобы их можно было сжать
Мы каждый день пользуемся различными архиваторами: zip, rar, ace окружают нас повсюду.
Графические и звуковые файлы тоже содержат сжатые данные. Если же нам нужно использовать
сжатие в своей проге, то мы используем различные dll’ки, многие из которых платные.
Шареварность – это не единственное свойство программных компонентов, мешающих их нормальному
использованию. Если, например, сжимать waw или bmp-файл архиватором, то
он будет значительно уступать специальному методу для конкретного типа данных, т.е.
метод должен учитывать особенности конкретного типа данных. Поэтому полезно уметь реализовывать сжатие самостоятельно.
В этой статье я расскажу, как вообще сжимать информацию и рассмотрю один из методов сжатия.
Классификация методов сжатия
Прежде всего, все методы сжатия делятся на
сжатие с потерями и сжатие без потерь. Задачу сжатия с потерями можно сформулировать так: требуется отобразить множество возможных
сообщений на множество, содержащее меньшее количество элементов, так, чтобы исходные сообщения
и их отображения были в определенном смысле близки (например, неразличимы на глаз), т.е.
малозначительная информация просто отбрасывается. После этого дополнительно применяется сжатие
без потерь. Сжатие без потерь – это однозначное кодирование, такое что закодированные сообщения
в среднем занимают меньше места. Именно такому сжатию посвящена эта статья.
Далее под словом “сжатие” мы будем подразумевать сжатие без потерь.
Теория
Прежде всего, ни один метод сжатия не может сжать любые данные, поскольку кодирование
должно быть однозначным. Задача состоит в том, чтобы построить правило кодирования, по которому
наиболее часто встречающимся сообщениям соответствовали бы сообщения меньшей длины. Поэтому любой метод сжатия должен быть основан на каких-либо предположениях о
вероятностной структуре сжимаемых данных. Например, для текста на определенном языке известны
частоты букв. Наиболее часто используемое предположение заключается в том, что с большей
вероятностью в сообщении будут встречаться одинаковые цепочки символов. Например, в тексте этой
статьи чаще всего встречается слово “сжатие”. Если же ничего не знать о вероятностной структуре
сжимаемых данных и считать все сообщения одной длины равновероятными, то мы вообще ничего не
сожмем.
Методы сжатия делятся на статистические и словарные. Словарные методы заключаются в том,
чтобы в случае встречи подстроки, которая уже была найдена раньше, кодировать ссылку, которая
занимает меньше места, чем сама подстрока. Классическим словарным методом является метод
Лемпела-Зива (LZ). Все используемые на сегодняшний день словарные методы являются лишь
модификациями LZ.
Статистическое кодирование заключается в том, чтобы кодировать каждый символ, но
использовать коды переменной длины. Примером таких методов служит метод Хаффмана
(Huffman). Обычно словарные и статистические методы комбинируются, поскольку у каждого свои
преимущества.
Отметим один момент, который почему-то неочевиден для некоторых “теоретиков”.
Правило кодирования определяется вероятностной структурой данных, а значит, декомпрессор
должен до начала раскодирования уже знать её. Если же мы получаем её из статистики конкретного
сообщения (так оно сжимается лучше), то её придется передать явно или неявно вместе со сжатым
сообщением, и еще неизвестно, будет ли общий размер меньше.
Доказано, что наименьший возможный средний размер сжатого сообщения равен энтропии
ансамбля возможных сообщений, округленной с избытком. Энтропия вычисляется по формуле:
H = -Sum(p[i] * log(p[i]))
где Sum – сумма по i, p[i] – вероятность i-го сообщения, log – логарифм по основанию 2.
Энтропия сложного сообщения равна сумме энтропий входящих в него простых сообщений.
Если кодировать каждый символ отдельно, то длина кода каждого сообщения должна быть
равна -log(p). Т.е., например, если вероятность символа 0.3, то его код должен иметь длину
1.73 бита, в то время, как реальные длины целые. Можно улучшить результаты, если не сводить
задачу к кодированию отдельных символов.
Арифметическое кодирование
Этот метод в корне отличается от всех рассмотренных ранее методов. Его главное
преимущество в том, что достигается теоретический предел сжатия. Рассмотрим этот метод подробно. Всё сообщение целиком представляется одним числом по следующему правилу. Число должно
находиться в интервале от 0 до 1. Этот интервал делится на части, пропорциональные вероятностям
значений первого символа. Выбирается часть, соответствующая символу и делится на части по
вероятностям значений второго символа и т.д.
новая_нижняя_граница = нижняя_граница + ширина * S[i]
новая_ширина = ширина * p[i]
где p[i] – вероятность i-го символа, S[i] – сумма вероятностей символов с номерами
меньше i.
После обработки всего сообщения по этому алгоритму остается только записать любое
число из получившегося интервала. Количество битов, необходимое для записи этого числа,
примерно равно минус логарифму ширины интервала. Ширина интервала равна произведению
вероятностей символов, т.е. вероятности всего сообщения. Т.о., длина кода равна
-log(p), т.е. теоретическому пределу. На практике мы будем работать с переменными ограниченной длины,
и точность вычислений будет ограничена, а значит, сжатие будет все-таки немного хуже.
Реализация
Проект, прикрепленный к этой статье, компилируется на Visual Studio .NET.
Это реализация арифметического кодирования, сжимающая файлы, рассматривая байты как символы.
Содержимое файла рассматривается как марковский процесс 1-го порядка, т. е. распределение
вероятностей символов зависит от предыдущего символа. Класс CMarkovProcessDef обрабатывает
данные, сохраненные в ресурсе в специальном формате. Эти данные сгенерированы по результатам
обработки большого количества текстов, т. е. текстовые файлы, скорее всего, будут сжиматься
хорошо, а если попытаться сжать какой-нибудь бинарник, то размер “сжатого” файла будет больше
исходного. Для того, чтобы получить метод сжатия для своего типа данных, нужно заменить данные о
вероятностях символов. Кроме того, символ – это не обязательно байт несжатых данных. Например,
если есть столбец таблицы, где значения должны быть уникальными, то каждое значение – это
символ, а после того, как символ встречается, сбрасываем его вероятность в ноль. Нижняя граница и ширина интервала хранятся в целочисленных переменных dwBuf1 и dwBuf2.
Если после обработки очередного символа старшие байты границ окажутся равными
(заметим, что это не то же самое, что если старший байт ширины равен нулю), то
соответствующий байт окончательного результата будет равен этому значению, и его можно
записать в файл. Запишем его и сдвинем буферы на 1 байт. При распаковке кроме переменных, обрабатываемых так же, как при упаковке, нам
понадобится еще одна, где будет информация из файла. Для того, чтобы определить очередной символ, нужно
найти символ с наименьшим номером, такой, что S[n] * dwBuf2 >= dwBuf3, т.е. P[n] >= dwBuf3 / dwBuf2. При работе с целыми числами возникает проблема: мы представляем вероятности (дробные
числа от 0 до 1) целочисленными переменными (0x100000000 * p). Для умножения и деления на них нужны
особые процедуры: при умножении берем старшее 32-битное слово 64-битного результата, а при делении
делим число, умноженное на 2^32. Компилятор не может, умножитв DWORD на DWORD, поместить результат
в 64-битную переменную – это недостаток языка С++. Поэтому пришлось написать специальные процедуры
на ассемблере.
void CArithmCompressorDlg::OnBnClickedCompress()
{
CFileDialog dlg1(TRUE);
if (dlg1.DoModal() != IDOK) return;
CFileDialog dlg2(FALSE, “compressed”, 0, OFN_HIDEREADONLY | OFN_OVERWRITEPROMPT, “*.compressed|*.compressed|All files|*.*||”);
if (dlg2.DoModal() != IDOK) return;
CFile file1(dlg1.GetPathName(), CFile::modeRead);
CFile file2(dlg2.GetPathName(), CFile::modeCreate | CFile::modeWrite);
BYTE b;
ULONGLONG fs = file1.GetLength();
file2.Write(&fs, 8); // Запишем размер исходного файла
// m_mpd – это объект класса CMarkovProcessDef
m_mpd.ResetProcess(); // Сбросим данные о предшествующих символах
// Здесь начинается сжатие
// Начальный интервал – от 0x00000000 до 0xFFFFFFFF
DWORD dwBuf1 = 0; // Нижняя граница
DWORD dwBuf2 = 0xFFFFFFFF; // Ширина
DWORD dww; // Временная переменная
while (file1.Read(&b, 1))
{
// Вычисляем новый интервал
if (b > 0) dww = MulHigh(m_mpd.GetDistribution(b-1), dwBuf2); else dww = 0;
/*
m_mpd.GetDistribution(b-1) – Это S[b], т. о.
p[b] – это m_mpd.GetDistribution(b) – m_mpd.GetDistribution(b-1)
Замените эту функцию на свою реализацию и получите метод сжатия для вашего типа данных.
*/
dwBuf1 += dww;
if (b Если старший байт буфера определен
{
file2.Write(((LPBYTE)&dwBuf1)+3, 1); // Записываем его
dwBuf1 = dwBuf1 И сдвигаем буфер
dwBuf2 = dwBuf2
}
/*
PushSymbol(b, 0) перемещает внутренний указатель на распределение для следующего символа
*/
m_mpd.PushSymbol(b, 0);
}
file2.Write(((LPBYTE)&dwBuf1)+3, 1); // Записываем последний байт
// Вот и всё
// Закрываем файлы
file1.Close();
file2.Close();
}
void CArithmCompressorDlg::OnBnClickedDecompress()
{
CFileDialog dlg1(TRUE, “compressed”, 0, 0, “*.compressed|*.compressed|All files|*.*||”);
if (dlg1.DoModal() != IDOK) return;
CFileDialog dlg2(FALSE);
if (dlg2.DoModal() != IDOK) return;
CFile file1(dlg1.GetPathName(), CFile::modeRead);
CFile file2(dlg2.GetPathName(), CFile::modeCreate | CFile::modeWrite);
ULONGLONG fs, i;
if (file1.Read(&fs, 8) != 8) return; // Читаем длину извлекаемого файла
m_mpd.ResetProcess();
DWORD dwBuf1 = 0, dwBuf2 = 0xFFFFFFFF, dwBuf3, dww;
// Читаем первые 4 байта
// Нужно поместить байты в переменную не в том порядке, в каком они в файле,
// поэтому читаем их по отдельности
for (int j = 3; j >= 0; j–) if (file1.Read(((LPBYTE)&dwBuf3)+j, 1) == 0) ((LPBYTE)&dwBuf3)[j] = 0xFF;
for (i = 0; i
{
DWORD l, h, m, v;
l = 0;
h = 255;
v = DivLarge(dwBuf3, 0xFFFFFFFF, dwBuf2); // Это число >= S[m]
// Поиск методом половинного деления
do
{
m = (l+h)/2;
if (h
if (m_mpd.GetDistribution(m)
} while (true);
// Вычисляем новый интервал
if (m > 0) dww = MulHigh(m_mpd.GetDistribution(m-1), dwBuf2); else dww = 0;
dwBuf1 += dww;
dwBuf3 -= dww;
if (m Пишем символ
m_mpd.PushSymbol(m, 0);
while (((dwBuf1 ^ (dwBuf1 + dwBuf2)) & 0xFF000000) == 0) // Если старший байт буфера определен
{
dwBuf1 = dwBuf1 сдвигаем буфер
dwBuf2 = dwBuf2
dwBuf3 = dwBuf3
if (file1.Read(&dwBuf3, 1) == 0) dwBuf3 |= 0xFF;
// Читаем следующий байт, если есть, иначе ставим 0xFF
}
}
// Закрываем файлы
file1.Close();
file2.Close();
}
DWORD CArithmCompressorDlg::MulHigh(DWORD dw1, DWORD dw2)
{
/*
Эта функция возвращает старшее двойное слово
произведения данных двойных слов
*/
DWORD r;
_asm
{
mov eax, dw1;
mul dw2;
mov r, edx;
}
return r;
}
DWORD CArithmCompressorDlg::DivLarge(DWORD hi, DWORD lo, DWORD dw)
{
/*
Эта функция делит 64-битное беззнаковое целое (hi;lo)
на 32-битное
*/
DWORD r;
_asm
{
mov eax, lo;
mov edx, hi;
div dw;
mov r, eax;
}
return r;
}
Исходники
Источник
Часть первая – историческая.
Введение
Существующие алгоритмы сжатия данных можно разделить на два больших класса – с потерями, и без. Алгоритмы с потерями обычно применяются для сжатия изображений и аудио. Эти алгоритмы позволяют достичь больших степеней сжатия благодаря избирательной потере качества. Однако, по определению, восстановить первоначальные данные из сжатого результата невозможно.
Алгоритмы сжатия без потерь применяются для уменьшения размера данных, и работают таким образом, что возможно восстановить данные в точности такими, какие они были до сжатия. Они применяются в коммуникациях, архиваторах и некоторых алгоритмах сжатии аудио и графической информации. Далее мы рассмотрим только алгоритмы сжатия без потерь.
Основной принцип алгоритмов сжатия базируется на том, что в любом файле, содержащем неслучайные данные, информация частично повторяется. Используя статистические математические модели можно определить вероятность повторения определённой комбинации символов. После этого можно создать коды, обозначающие выбранные фразы, и назначить самым часто повторяющимся фразам самые короткие коды. Для этого используются разные техники, например: энтропийное кодирование, кодирование повторов, и сжатие при помощи словаря. С их помощью 8-битный символ, или целая строка, могут быть заменены всего лишь несколькими битами, устраняя таким образом излишнюю информацию.
История
Иерархия алгоритмов:
Хотя сжатие данных получило широкое распространение вместе с интернетом и после изобретения алгоритмов Лемпелем и Зивом (алгоритмы LZ), можно привести несколько более ранних примеров сжатия. Морзе, изобретая свой код в 1838 году, разумно назначил самым часто используемым буквам в английском языке, “e” и “t”, самые короткие последовательности (точка и тире соотв.). Вскоре после появления мейнфреймов в 1949 году был придуман алгоритм Шеннона — Фано, который назначал символам в блоке данных коды, основываясь на вероятности их появления в блоке. Вероятность появления символа в блоке была обратно пропорциональна длине кода, что позволяло сжать представление данных.
Дэвид Хаффман был студентом в классе у Роберта Фано и в качестве учебной работы выбрал поиск улучшенного метода бинарного кодирования данных. В результате ему удалось улучшить алгоритм Шеннона-Фано.
Ранние версии алгоритмов Шеннона-Фано и Хаффмана использовали заранее определённые коды. Позже для этого стали использовать коды, созданные динамически на основе данных, предназначаемых для сжатия. В 1977 году Лемпель и Зив опубликовали свой алгоритм LZ77, основанный на использования динамически создаваемого словаря (его ещё называют «скользящим окном»). В 78 году они опубликовали алгоритм LZ78, который сначала парсит данные и создаёт словарь, вместо того, чтобы создавать его динамически.
Проблемы с правами
Алгоритмы LZ77 и LZ78 получили большую популярность и вызвали волну улучшателей, из которых до наших дней дожили DEFLATE, LZMA и LZX. Большинство популярных алгоритмов основаны на LZ77, потому что производный от LZ78 алгоритм LZW был запатентован компанией Unisys в 1984 году, после чего они начали троллить всех и каждого, включая даже случаи использования изображений в формате GIF. В это время на UNIX использовали вариацию алгоритма LZW под названием LZC, и из-за проблем с правами их использование пришлось сворачивать. Предпочтение отдали алгоритму DEFLATE (gzip) и преобразованию Барроуза — Уилера, BWT (bzip2). Что было и к лучшему, так как эти алгоритмы почти всегда превосходят по сжатию LZW.
К 2003 году срок патента истёк, но поезд уже ушёл и алгоритм LZW сохранился, пожалуй, только в файлах GIF. Доминирующими являются алгоритмы на основе LZ77.
В 1993 году была ещё одна битва патентов – когда компания Stac Electronics обнаружила, что разработанный ею алгоритм LZS используется компанией Microsoft в программе для сжатия дисков, поставлявшейся с MS-DOS 6.0. Stac Electronics подала в суд и им удалось выиграть дело, в результате чего они получили более $100 миллионов.
Рост популярности Deflate
Большие корпорации использовали алгоритмы сжатия для хранения всё увеличивавшихся массивов данных, но истинное распространение алгоритмов произошло с рождением интернета в конце 80-х. Пропускная способность каналов была чрезвычайно узкой. Для сжатия данных, передаваемых по сети, были придуманы форматы ZIP, GIF и PNG.
Том Хендерсон придумал и выпустил первый коммерчески успешный архиватор ARC в 1985 году (компания System Enhancement Associates). ARC была популярной среди пользователей BBS, т.к. она одна из первых могла сжимать несколько файлов в архив, к тому же исходники её были открыты. ARC использовала модифицированный алгоритм LZW.
Фил Катц, вдохновлённый популярностью ARC, выпустил программу PKARC в формате shareware, в которой улучшил алгоритмы сжатия, переписав их на Ассемблере. Однако, был засужен Хендерсоном и был признан виновным. PKARC настолько открыто копировала ARC, что иногда даже повторялись опечатки в комментариях к исходному коду.
Но Фил Катц не растерялся, и в 1989 году сильно изменил архиватор и выпустил PKZIP. После того, как его атаковали уже в связи с патентом на алгоритм LZW, он изменил и базовый алгоритм на новый, под названием IMPLODE. Вновь формат был заменён в 1993 году с выходом PKZIP 2.0, и заменой стал DEFLATE. Среди новых возможностей была функция разбиения архива на тома. Эта версия до сих пор повсеместно используется, несмотря на почтенный возраст.
Формат изображений GIF (Graphics Interchange Format) был создан компанией CompuServe в 1987. Как известно, формат поддерживает сжатие изображения без потерь, и ограничен палитрой в 256 цветов. Несмотря на все потуги Unisys, ей не удалось остановить распространение этого формата. Он до сих пор популярен, особенно в связи с поддержкой анимации.
Слегка взволнованная патентными проблемами, компания CompuServe в 1994 году выпустила формат Portable Network Graphics (PNG). Как и ZIP, она использовала новый модный алгоритм DEFLATE. Хотя DEFLATE был запатентован Катцем, он не стал предъявлять никаких претензий.
Сейчас это самый популярный алгоритм сжатия. Кроме PNG и ZIP он используется в gzip, HTTP, SSL и других технологиях передачи данных.
К сожалению Фил Катц не дожил до триумфа DEFLATE, он умер от алкоголизма в 2000 году в возрасте 37 лет. Граждане – чрезмерное употребление алкоголя опасно для вашего здоровья! Вы можете не дожить до своего триумфа!
Современные архиваторы
ZIP царствовал безраздельно до середины 90-х, однако в 1993 году простой русский гений Евгений Рошал придумал свой формат и алгоритм RAR. Последние его версии основаны на алгоритмах PPM и LZSS. Сейчас ZIP, пожалуй, самый распространённый из форматов, RAR – до недавнего времени был стандартом для распространения различного малолегального контента через интернет (благодаря увеличению пропускной способности всё чаще файлы распространяются без архивации), а 7zip используется как формат с наилучшим сжатием при приемлемом времени работы. В мире UNIX используется связка tar + gzip (gzip — архиватор, а tar объединяет несколько файлов в один, т.к. gzip этого не умеет).
Прим. перев. Лично я, кроме перечисленных, сталкивался ещё с архиватором ARJ (Archived by Robert Jung), который был популярен в 90-х в эру BBS. Он поддерживал многотомные архивы, и так же, как после него RAR, использовался для распространения игр и прочего вареза. Ещё был архиватор HA от Harri Hirvola, который использовал сжатие HSC (не нашёл внятных объяснений — только «модель ограниченного контекста и арифметическое кодирование»), который хорошо справлялся со сжатием длинных текстовых файлов.
В 1996 году появился вариант алгоритма BWT с открытыми исходниками bzip2, и быстро приобрёл популярность. В 1999 году появилась программа 7-zip с форматом 7z. По сжатию она соперничает с RAR, её преимуществом является открытость, а также возможность выбора между алгоритмами bzip2, LZMA, LZMA2 и PPMd.
В 2002 году появился ещё один архиватор, PAQ. Автор Мэтт Махоуни использовал улучшенную версию алгоритма PPM с использованием техники под названием «контекстное смешивание». Она позволяет использовать больше одной статистической модели, чтобы улучшить предсказание по частоте появления символов.
Будущее алгоритмов сжатия
Конечно, бог его знает, но судя по всему, алгоритм PAQ набирает популярность благодаря очень хорошей степени сжатия (хотя и работает он очень медленно). Но благодаря увеличению быстродействия компьютеров скорость работы становится менее критичной.
С другой стороны, алгоритм Лемпеля-Зива –Маркова LZMA представляет собой компромисс между скоростью и степенью сжатия и может породить много интересных ответвлений.
Ещё одна интересная технология «substring enumeration» или CSE, которая пока мало используется в программах.
В следующей части мы рассмотрим техническую сторону упомянутых алгоритмов и принципы их работы.
Источник
Принципы сжатия данных
Как было сказано выше, одной из важных задач предварительной подготовки данных к шифрованию является уменьшение их избыточности и выравнивание статистических закономерностей применяемого языка. Частичное устранение избыточности достигается путём сжатия данных.
Сжатие информации представляет собой процесс преобразования исходного сообщения из одной кодовой системы в другую, в результате которого уменьшается размер сообщения. Алгоритмы, предназначенные для сжатия информации, можно разделить на две большие группы: реализующие сжатие без потерь (обратимое сжатие) и реализующие сжатие с потерями (необратимое сжатие).
Обратимое сжатие подразумевает абсолютно точное восстановление данных после декодирования и может применяться для сжатия любой информации. Оно всегда приводит к снижению объема выходного потока информации без изменения его информативности, то есть без потери информационной структуры. Более того, из выходного потока, при помощи восстанавливающего или декомпрессирующего алгоритма, можно получить входной, а процесс восстановления называется декомпрессией или распаковкой и только после процесса распаковки данные пригодны для обработки в соответствии с их внутренним форматом. Сжатие без потерь применяется для текстов, исполняемых файлов, высококачественного звука и графики.
Необратимое сжатие имеет обычно гораздо более высокую степень сжатия, чем кодирование без потерь, но допускает некоторые отклонения декодированных данных от исходных. На практике существует широкий круг практических задач, в которых соблюдение требования точного восстановления исходной информации после декомпрессии не является обязательным. Это, в частности, относится к сжатию мультимедийной информации: звука, фото- или видеоизображений. Так, например, широко применяются форматы мультимедийной информации JPEG и MPEG, в которых используется необратимое сжатие. Необратимое сжатие обычно не используется совместно с криптографическим шифрованием, так как основным требованием к криптосистеме является идентичность расшифрованных данных исходным. Однако при использовании мультимедиа-технологий данные, представленные в цифровом виде, часто подвергаются необратимой компрессии перед подачей в криптографическую систему для шифрования. После передачи информации потребителю и расшифрования мультимедиа-файлы используются в сжатом виде (то есть не восстанавливаются).
Рассмотрим подробнее некоторые из наиболее распространённых способов обратимого сжатия данных.
Наиболее известный простой подход и алгоритм сжатия информации обратимым путем – это кодирование серий последовательностей (Run Length Encoding – RLE). Суть методов данного подхода состоит в замене цепочек или серий повторяющихся байтов на один кодирующий байт-заполнитель и счетчик числа их повторений. Проблема всех аналогичных методов заключается лишь в определении способа, при помощи которого распаковывающий алгоритм мог бы отличить в результирующем потоке байтов кодированную серию от других, – не кодированных последовательностей байтов. Решение проблемы достигается обычно простановкой меток вначале кодированных цепочек. Такими метками могут быть характерные значения битов в первом байте кодированной серии, значения первого байта кодированной серии. Недостатком метода RLE является достаточно низкая степень сжатия или стоимость кодирования файлов с малым числом серий и, что еще хуже – с малым числом повторяющихся байтов в сериях.
При равномерном кодировании информации на сообщение отводится одно и то же число бит, независимо от вероятности его появления. Вместе с тем логично предположить, что общая длина передаваемых сообщений уменьшится, если часто встречающиеся сообщения кодировать короткими кодовыми словами, а редко встречающиеся – более длинными. Возникающие при этом проблемы связаны с необходимостью использования кодов с переменной длиной кодового слова. Существует множество подходов к построению подобных кодов.
Одними из широко используемых на практике являются словарные методы, к основным представителям которых относятся алгоритмы семейства Зива и Лемпела. Их основная идея заключается в том, что фрагменты входного потока (“фразы”) заменяются указателем на то место, где они в тексте уже ранее появлялись. В литературе подобные алгоритмы обозначаются как алгоритмы LZ сжатия.
Подобный метод быстро приспосабливается к структуре текста и может кодировать короткие функциональные слова, так как они очень часто в нем появляются. Новые слова и фразы могут также формироваться из частей ранее встреченных слов. Декодирование сжатого текста осуществляется напрямую, – происходит простая замена указателя готовой фразой из словаря, на которую тот указывает. На практике LZ-метод добивается хорошего сжатия, его важным свойством является очень быстрая работа декодера.
Другим подходом к сжатию информации является код Хаффмана, кодер и декодер которого имеют достаточно простую аппаратную реализацию. Идея алгоритма состоит в следующем: зная вероятности вхождения символов в сообщение, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью присваиваются более короткие коды, тогда как реже встречающимся символам – более длинные. За счет этого достигается сокращение средней длины кодового слова и большая эффективность сжатия. Коды Хаффмана имеют уникальный префикс (начало кодового слова), что и позволяет однозначно их декодировать, несмотря на их переменную длину.
Процедура синтеза классического кода Хаффмана предполагает наличие априорной информации о статистических характеристиках источника сообщений. Иначе говоря, разработчику должны быть известны вероятности возникновения тех или иных символов, из которых образуются сообщения. Рассмотрим синтез кода Хаффмана на простом примере.
Пусть источник информации способен генерировать четыре различных символа S1…S4 с вероятностями возникновения p(S1)=0,2, p(S2)=0,15, p(S3)=0,55, p(S4)=0,1. Отсортируем символы по убыванию вероятности появления и представим в виде таблицы (
рис.
14.3, а).
Процедура синтеза кода состоит из трех основных этапов. На первом происходит свертка строк таблицы: две строки, соответствующие символам с наименьшими вероятностями возникновения заменяются одной с суммарной вероятностью, после чего таблица вновь переупорядочивается. Свертка продолжается до тех пор, пока в таблице не останется лишь одна строка с суммарной вероятностью, равной единице (
рис.
14.3, б).
Рис.
14.3.
Первый этап кодирования Хаффмана
На втором этапе осуществляется построение кодового дерева по свернутой таблице (
рис.
14.4, а). Дерево строится, начиная с последнего столбца таблицы.
Рис.
14.4.
Второй этап кодирования Хаффмана
Корень дерева образует единица, расположенная в последнем столбце. В рассматриваемом примере эта единица образуется из вероятностей 0,55 и 0,45, изображаемых в виде двух узлов дерева, связанных с корнем. Первый из них соответствует символу S3 и, таким образом, дальнейшее ветвление этого узла не происходит.
Второй узел, маркированный вероятностью 0,45, соединяется с двумя узлами третьего уровня, с вероятностями 0,25 и 0,2. Вероятность 0,2 соответствует символу S1, а вероятность 0,25, в свою очередь, образуется из вероятностей 0,15 появления символа S2 и 0,1 появления символа S4.
Ребра, соединяющие отдельные узлы кодового дерева, нумеруются цифрами 0 и 1 (например, левые ребра – 0, а правые – 1 ). На третьем, заключительном этапе, строится таблица, в которой сопоставляются символы источника и соответствующие им кодовые слова кода Хаффмана. Эти кодовые слова образуются в результате считывания цифр, которыми помечены ребра, образующие путь от корня дерева к соответствующему символу. Для рассматриваемого примера код Хаффмана примет вид, показанный в таблице справа (
рис.
14.4, б).
Однако классический алгоритм Хаффмана имеет один существенный недостаток. Для восстановления содержимого сжатого сообщения декодер должен знать таблицу частот, которой пользовался кодер. Следовательно, длина сжатого сообщения увеличивается на длину таблицы частот, которая должна посылаться впереди данных, что может свести на нет все усилия по сжатию сообщения.
Другой вариант статического кодирования Хаффмана заключается в просмотре входного потока и построении кодирования на основании собранной статистики. При этом требуется два прохода по файлу – один для просмотра и сбора статистической информации, второй – для кодирования. В статическом кодировании Хаффмана входным символам (цепочкам битов различной длины) ставятся в соответствие цепочки битов также переменной длины – их коды. Длина кода каждого символа берется пропорциональной двоичному логарифму его частоты, взятому с обратным знаком. А общий набор всех встретившихся различных символов составляет алфавит потока.
Существует другой метод – адаптивного или динамического кодирования Хаффмана. Его общий принцип состоит в том, чтобы менять схему кодирования в зависимости от характера изменений входного потока. Такой подход имеет однопроходный алгоритм и не требует сохранения информации об использованном кодировании в явном виде. Адаптивное кодирование может дать большую степень сжатия, по сравнению со статическим, поскольку более полно учитываются изменения частот входного потока. При использовании адаптивного кодирования Хаффмана усложнение алгоритма состоит в необходимости постоянной корректировки дерева и кодов символов основного алфавита в соответствии с изменяющейся статистикой входного потока.
Методы Хаффмана дают достаточно высокую скорость и умеренно хорошее качество сжатия. Однако кодирование Хаффмана имеет минимальную избыточность при условии, что каждый символ кодируется в алфавите кода символа отдельной цепочкой из двух бит – {0, 1}. Основным же недостатком данного метода является зависимость степени сжатия от близости вероятностей символов к 2 в некоторой отрицательной степени, что связано с тем, что каждый символ кодируется целым числом бит.
Совершенно иное решение предлагает арифметическое кодирование. Этот метод основан на идее преобразования входного потока в одно число с плавающей запятой. Арифметическое кодирование является методом, позволяющим упаковывать символы входного алфавита без потерь при условии, что известно распределение частот этих символов.
Предполагаемая требуемая последовательность символов при сжатии методом арифметического кодирования рассматривается как некоторая двоичная дробь из интервала [0, 1). Результат сжатия представляется как последовательность двоичных цифр из записи этой дроби. Идея метода состоит в следующем: исходный текст рассматривается как запись этой дроби, где каждый входной символ является “цифрой” с весом, пропорциональным вероятности его появления. Этим объясняется интервал, соответствующий минимальной и максимальной вероятностям появления символа в потоке.
Рассмотренные методы обеспечивают обратимое сжатие данных. На практике применяются как программные, так и аппаратные их реализации, позволяющие добиваться коэффициентов сжатия порядка 20-40% в зависимости от типа сжимаемой информации.
Таким образом, криптографическое шифрование, помехоустойчивое кодирование и сжатие отчасти дополняют друг друга и их комплексное использование помогает эффективно использовать каналы связи для надежной защиты передаваемой информации.
Ключевые термины
Избыточность – характеристика помехоустойчивого кода, показывающая, насколько увеличена длина кодового слова по сравнению с обычным непомехоустойчивым кодом. Для многих помехоустойчивых кодов избыточность можно определить как отношение числа контрольных разрядов к общему числу разрядов кодового слова.
Код – совокупность знаков, а также система правил, позволяющая представлять информацию в виде набора таких знаков.
Кодовое слово – любой ряд допустимых знаков в соответствии с используемой системой правил.
Минимальное кодовое расстояние – наименьшее из всех расстояний по Хэммингу для любых пар различных кодовых слов, образующих код.
Помехоустойчивый код – код, позволяющий обнаруживать и корректировать ошибки при хранении и передаче сообщений.
Расстояние по Хэммингу – число разрядов кодовых слов, в которых они различны.
Сжатие информации – процесс преобразования исходного сообщения из одной кодовой системы в другую, в результате которого уменьшается размер сообщения.
Соседние кодовые слова – кодовые слова, отличающиеся значением только одного разряда.
Краткие итоги
В теории информации выделяют три вида преобразования информации: криптографическое шифрование, помехоустойчивое кодирование и сжатие (или эффективное кодирование). Общим для всех трех видов преобразования является то, что информация каким-либо образом меняет форму представления, но не смысл. Отличия разных видов кодирования связаны с целью проводимых преобразований.
Так, целью криптографического преобразования является, как известно, защита от несанкционированного доступа, аутентификация и защита от преднамеренных изменений. Помехоустойчивое кодирование выполняется с целью защиты информации от случайных помех при передаче и хранении. Для этого при записи и передаче в полезные данные добавляют специальным образом структурированную избыточную информацию, а при чтении (приёме) её используют для того, чтобы обнаружить или исправить ошибки. Естественно, что число ошибок, которое можно исправить, ограничено и зависит от конкретного применяемого кода.
Эффективное кодирование (или сжатие информации) представляет собой процесс преобразования исходного сообщения из одной кодовой системы в другую, в результате которого уменьшается размер сообщения. Алгоритмы сжатия информации делятся на две группы: алгоритмы сжатия без потерь (обратимого сжатия) и алгоритмы сжатия с потерями (необратимого сжатия). За счет эффективного кодирования уменьшается избыточность сообщений, что позволяет производить более надежное криптографическое шифрование информации.
Таким образом, криптографическое шифрование, помехоустойчивое кодирование и сжатие отчасти дополняют друг друга и их комплексное использование помогает эффективно использовать каналы связи для надежной защиты передаваемой информации.
Набор для практики
Вопросы для самопроверки
- Какие виды преобразований информации используются для комплексной защиты информации?
- Каковы основные принципы помехоустойчивого кодирования сообщений?
- Каким образом используется синдром ошибки при кодировании сообщений кодом Хэмминга?
- Приведите примеры кодов, обеспечивающих сжатие сообщений.
- За счет чего достигается сжатие сообщений при кодировании методом Хаффмана?
- Как формируется кодовое слова Хаффмана?
- Для каких типов данных целесообраз?