Современные методы хранения информации в сжатом виде(методы неискажающего сжатия и восстановления информации)

Алгоритм обновления дерева

ОбновитьМодельСимволом(Символ)

{

  ТекущийУзел = ЛистСоответствующий(Символ);

  Всегда

  УвеличитьВес(ТекущийУзел);

  Если ТекущийУзел = КореньДерева

    Выход;

  Если Вес(ТекущийУзел) > Вес(СледующийЗа(ТекущийУзел))

    Перестановка();

  ТекущийУзел = Родитель(ТекущийУзел);

  Конец Всегда;

}

5.16.6 Проблемы адаптивного кодирования

Хорошо было бы, чтобы кодер не тратил зря кодовое пространство на символы, которые не встречаются  в сообщении. Если речь идет о классическом алгоритме Хаффмана, то те символы, которые не встречаются в сообщении, уже известны до начала кодирования, так как известна таблица частот и символы, у которых частота встречаемости равна 0. В адаптивной версии алгоритма мы не можем знать заранее, какие символы появятся в сообщении. Можно проинициализировать дерево Хаффмана так, чтобы оно имело все 256 символов алфавита (для 8-и битовых кодов) с частотой, равной 1. В начале кодирования каждый код будет иметь длину 8 битов. По мере адаптации модели наиболее часто встречающиеся символы будут кодироваться все меньшим и меньшим количеством битов. Такой подход работоспособен, но он значительно снижает степень сжатия, особенно на коротких сообщениях.

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

Чтобы разрешить это противоречие, введем специальный ESCAPE код, который будет означать, что следующий символ закодирован вне контекста модели сообщения. Например, его можно передать в поток сжатой информации как есть, не кодируя вообще. Метод "ЗакодироватьСимвол" в алгоритме адаптивного кодирования Хаффмана можно записать следующим образом:

ЗакодироватьСимвол(Символ)

{

  Если СимволУжеЕстьВТаблице(Символ)

  ВыдатьКодХаффманаДля(Символ);

  Иначе

  {

    ВыдатьКодХаффманаДля(ESC);

    ВыдатьСимвол(Символ);

  }

}

Использование специального символа ESC подразумевает определенную инициализацию дерева до начала кодирования и декодирования: в него помещаются 2 специальных символа: ESC и EOF (конец файла), с весом, равным 1.

Поскольку процесс обновления не коснется их веса, то по ходу кодирования они будут перемещаться на самые удаленные ветви дерева и иметь самые длинные коды.

5.16.7 Фиксированный алгоритм Хаффмана

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

5.16.8 Алгоритм стопки книг

Cужествует еще одна разновидность адаптивного алгоритма Хаффмана, описанная Рябко, а затем Бентли и названная, соответственно, алгоритмом стопки книг или “двигай вверх” (“MTF – Move To Front”).

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

 

Заключение

С тех пор, как Д. А. Хаффман опубликовал  в 1952 году свою работу "Метод построения кодов с минимальной избыточностью", его алгоритм кодирования стал базой  для огромного количества дальнейших исследований в этой области. По сей  день в компьютерных журналах можно  найти большое количество публикаций, посвященных как различным реализациям  алгоритма Хаффмана, так и поискам  его лучшего применения. Кодирование  Хаффмана используется в коммерческих программах сжатия (например в PKZIP и LHA), встроено в некоторые телефаксы и даже используется в алгоритме JPEG сжатия графических изображений с потерями.

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

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

Текст, сжатый арифметическим кодером, рассматривается как некоторая  двоичная дробь из интервала [0, 1). Результат сжатия можно представить как последовательность двоичных цифр из записи этой дроби. Каждый символ исходного текста представляется отрезком на числовой оси с длиной, равной вероятности его появления и началом, совпадающим с концом отрезка символа, предшествующего ему в алфавите. Сумма всех отрезков, очевидно должна равняться единице. Если рассматривать на каждом шаге текущий интервал как целое, то каждый вновь поступивший входной символ “вырезает” из него подинтервал пропорционально своей длине и положению.

Поясним работу метода на примере:

Пусть алфавит состоит из двух символов: “a” и “b” с вероятностями  соответственно 3/4 и 1/4.

Рассмотрим (открытый справа) интервал [0, 1). Разобьем его на части, длина которых пропорциональна вероятностям символов. В нашем случае это [0, 3/4) и [3/4, 1). Суть алгоритма в следующем: каждому слову во входном алфавите соответствует некоторый подинтервал из [0, 1). Пустому слову соответствует весь интервал [0, 1). После получения каждого очередного символа арифметический кодер уменьшает интервал, выбирая ту его часть, которая соответствует вновь поступившему символу. Кодом сообщения является интервал, выделенный после обработки всех его символов, точнее, число минимальной длины, входящее в этот интервал. Длина полученного интервала пропорциональна вероятности появления кодируемого текста.

Выполним алгоритм для цепочки  “aaba”:

Шаг	Просмотренная цепочка	Интервал
0	“”	[0, 1) = [0, 1)
1	“a”	[0, 3/4) = [0, 0.11)
2	“aa”	[0, 9/16) = [0, 0.1001)
3	“aab”	[27/64, 36/64) = [0.011011, 0.100100)
4	“aaba”	[108/256, 135/256) = [0.01101100, 0.10000111)

На первом шаге мы берем первые 3/4 интервала, соответствующие символу "а", затем оставляем от него еще только 3/4. После третьего шага от предыдущего интервала останется  его правая четверть в соответствии с положением и вероятностью символа "b". И, наконец, на четвертом шаге мы оставляем лишь первые 3/4 от результата. Это и есть интервал, которому принадлежит  исходное сообщение.

В качестве кода можно взять любое  число из диапазона, полученного  на шаге 4. Возникает вопрос: "А  где же здесь сжатие? Исходный текст можно было закодировать четырьмя битами, а мы получили восьмибитный интервал". Дело в том, что в качестве кода мы можем выбрать, например, самый короткий код из интервала, равный 0.1 и получить четырехкратное сокращение объема текста. Для сравнения, код Хаффмана не смог бы сжать подобное сообщение, однако, на практике выигрыш обычно невелик и предпочтение отдается более простому и быстрому алгоритму из предыдущего раздела.

Арифметический декодер работает синхронно с кодером: начав с  интервала [0, 1), он последовательно  определяет символы входной цепочки. В частности, в нашем случае он вначале разделит (пропорционально частотам символов) интервал [0, 1) на [0, 0.11) и [0.11, 1). Поскольку число 0.1 (переданный кодером код цепочки "aaba") находится в первом из них, можно получить первый символ: "a". Затем делим первый подинтервал [0, 0.11) на [0, 0.1001) и [0.1001, 0.1100) (пропорционально частотам символов). Опять выбираем первый, так как 0 < 0.1 < 0.1001. Продолжая этот процесс, мы однозначно декодируем все четыре символа.

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

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

5.18 Вероятностное  сжатие

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

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

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

 

Заключение

 

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

 

 

Библиографический список

1 http://www.findpatent.ru

2 http://mf.grsu.by

3 www.wikipedia.ru

4 www.intuit.ru

5 www.landef.ru