Файл: Методы кодирования данных (Краткая история кодирования ).pdf

Методы сжатия данных можно разделить на 2 группы: статические методы и адаптивные методы. Статические методы сжатия данных предназначены для кодирования конкретных источников информации с известной статистической структурой, которые порождают определенное множество сообщений. Эти методы основаны на знании статистической структуры исходных данных. К наиболее известным статическим методам сжатия относятся коды Хаффмана, Шеннона, Фано, Гилберта-Мура, арифметический код и другие методы, использующие известные сведения о вероятностях порождения источником различных символов или их сочетаний.

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

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

Рассмотрим несколько методов кодирования более подробно.

Оптимальный код Хаффмана

Метод оптимального побуквенного кодирования был создан в 1952 г. Д. Хаффманом. Оптимальный код Хаффмана обладает минимальной средней длиной кодового слова среди всех побуквенных кодов для данного источника с алфавитом А={a₁,…,a_n} и вероятностями p_i=P(a_i).

Рассмотрим алгоритм построения оптимального кода Хаффмана:

1. Привести в порядок символы исходного алфавита А={a₁,…,a_n} - по убыванию их вероятностей p₁≥p₂≥…≥p_n.
2. Если А={a₁,a₂}, то a₁→0, a₂→1.
3. Если А={a₁,…,a_j,…,a_n} и известны коды <a_j→b_j >,j= 1,…,n, то для алфавита {a₁,…a_j^/, a_j^//…,a_n} с новыми символами a_j^/ и a_j^/ вместо a_j, и вероятностями p(a_j)=p(a_j^/)+ p(a_j^//), код символа a_j заменяется на коды a_j^/→ b_j0, a_j^//→b_j1.

Пример. Пусть дан алфавит A={a₁,a₂,a₃,a₄,a₅,a₆} с вероятностями:

p₁=0.36, p₂=0.18, p₃=0.18, p₄=0.12, p₅=0.09, p₆=0.07

Здесь символы источника уже упорядочены в соответствии с их вероятностями. Будем складывать 2 наименьшие вероятности и включать суммарную вероятность на соответствующее место в упорядоченном списке вероятностей до тех пор, пока в списке не останется два символа. Тогда закодируем эти два символа 0 и 1. Далее кодовые слова достраиваются, как показано на рисунке 4.

Рисунок 4. Процесс построения кода Хаффмана

Таблица 1. Код Хаффмана

Посчитаем среднюю длину, построенного кода Хаффмана:

L_ср(P)=1.0.36 + 3.0.18 + 3.0.18 + 3.0.12 + 4.0.09 + 4.0.07 =2.44,

при этом энтропия данного источника

H(p₁,…,p₆)= − 0.36.log0.36 − 2.0.18.log0.18 − 0.12.log0.12 − 0.09.log0.09 − 0.07log0.07=2.37

Код Хаффмана обычно строится и хранится в виде двоичного дерева, в листьях которого находятся символы алфавита, а на «ветвях» – 0 или 1. Тогда уникальным кодом символа является путь от корня дерева к этому символу, по которому все 0 и 1 собираются в одну уникальную последовательность (рисунок 5).

Рисунок 5. Кодовое дерево для кода Хаффмана

Код Фано

Метод Фано построения префиксного почти оптимального кода, для которого , заключается в следующем. Упорядоченный по убыванию вероятностей список букв алфавита источника делится на 2 части так, чтобы суммы вероятностей букв, которые входят в эти части, как можно меньше отличались друг от друга. Буквам первой части приписывается 0, а буквам из второй части – 1. Далее также поступают с каждой из полученных частей. Процесс продолжается до тех пор, пока весь список не разобьется на части, содержащие по 1 букве.

Пример. Пусть дан алфавит A={a₁,a₂,a₃,a₄,a₅,a₆} с вероятностями p₁=0.36, p₂=0.18, p₃=0.18, p₄=0.12, p₅=0.09, p₆=0.07. Построенный код приведен в таблице 2 и на рисунке 6.

Таблица 2. Код Фано

Полученный код является префиксным и почти оптимальным со средней длиной кодового слова

L_ср=0.36.2+0.18.2+0.18.2+0.12.3+0.09.4+0.07.4=2.44

Рисунок 6. Кодовое дерево для кода Фано

Код Шеннона

Код Шеннона позволяет построить почти оптимальный код с длинами кодовых слов . Тогда по теореме Шеннона:

.

Код Шеннона, удовлетворяющий этому соотношению, строится следующим образом:

1. Приведем в порядок символы исходного алфавита А={a1,a2,…,an} по убыванию их вероятностей: p1≥p2≥p3≥…≥pn.
2. Вычислим величины Q_i, называющиеся кумулятивными вероятностями

Q₀=0, Q₁=p₁, Q₂=p₁+p₂, Q₃=p₁+p₂+p₃, … , Q_n=1

1. Представим Q_i в двоичной системе счисления и возьмем в качестве кодового слова первые знаков после запятой.

Для вероятностей, представленных в виде десятичных дробей, удобно определить длину кодового слова L_i из соотношения

, .

Пример. Пусть дан алфавит A={a₁,a₂,a₃,a₄,a₅,a₆} с вероятностями p₁=0.36,p₂=0.18,p₃=0.18,p₄=0.12,p₅=0.09,p₆=0.07. Построенный код приведен в таблице 3.

Таблица 3.Код Шеннона

Построенный код является префиксным. Вычислим среднюю длину кодового слова и сравним ее с энтропией. Значение энтропии вычислено при построении кода Хаффмана (H= 2.37), сравним его со значением средней длины кодового слова кода Шеннона

L_ср= 0.36.2+(0.18+0.18).3+(0.12+0.09+0.07).4=2.92< 2.37+1,

что полностью соответствует утверждению теоремы Шеннона.

Алфавитный код Гилберта-Мура

Е.Н.Гилбертом и Э.Ф.Муром был предложен метод построения алфавитного кода, для которого .

Пусть символы алфавита некоторым образом упорядочены, например, a₁≤a₂≤…≤a_n. Кодназывается алфавитным, если кодовые слова лексикографически упорядочены, т.е. .

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

1. Вычислим величины Q_i, i=1,n:

Q₁=p₁/2,

Q₂=p₁+p₂/2,

Q₃=p₁+p₂+p₃/2,

…

Q_n=p₁+p₂+…+p_n-1+p_n/2.

1. Представим суммы Q_i в двоичном виде.
2. В качестве кодовых слов возьмем младших бит в двоичном представлении Q_i, .

Пример. Пусть дан алфавит A={a₁,a₂,a₃,a₄,a₅,a₆} с вероятностями p₁=0.36, p₂=0.18, p₃=0.18, p₄=0.12, p₅=0.09, p₆=0.07. Построенный код приведен в таблице 4.

Таблица 4. Код Гилберта-Мура

Средняя длина кодового слова не превышает значения энтропии плюс 2. Действительно,

L_ср=4.0.18+4.0.18+3.0.36+5.0.07+5.0.09+5.0.12=3.92<2.37+2

Код «Стопка книг»

Этот метод был предложен Б.Я. Рябко в 1980 году. Название метод получил по подобию со стопкой книг, которая лежит на столе. Обычно сверху стопки лежат недавно использованные книги, а внизу стопки – книги, которые использовались давно, и после каждого обращения к стопке использованная книга кладется сверху стопки.

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

Пример. Приведем описание кода на примере алфавита A={a₁,a₂,a₃,a₄}. Пусть кодируется сообщение а₃а₃а₄а₄а₃…

• символ а₃ находится в 3 позиции стопки, кодируется кодовым словом 110 и перемещается на 1 позицию в стопке, при этом символы а₁ и а₂ смещаются на 1 позицию вниз;
• следующий символ а₃ уже находится в 1 позиции стопки, кодируется кодовым словом 0 и стопка не изменяется;
• символ а₄ находится в последней позиции стопки, кодируется кодовым словом 111 и перемещается на 1 позицию в стопке, при этом символы а₁,а₂,а₃ смещаются на 1 позицию вниз;
• следующий символ а₄ уже находится в 1 позиции стопки, кодируется кодовым словом 0 и стопка не изменяется;
• символ а₃находится во 2 позиции стопки, кодируется кодовым словом 10 и перемещается на 1 позицию в стопке, при этом символ а₄ смещается на одну позицию вниз.

Рисунок 7. Кодирование методом «стопка книг»

Таким образом, закодированное сообщение имеет следующий вид:

Рисунок 8. Результат кодирования методом «стопка книг»

Рассмотренный метод сжимает сообщение за счет того, что часто встречающиеся символы будут находиться в верхних позициях «стопки книг» и кодироваться более короткими кодовыми словами. Эффективность метода особо заметна при кодировании серий одинаковых символов. В этом случае все символы серии, начиная со второго, будут кодироваться самым коротким кодовым словом, соответствующим 1 позиции «стопки книг».

При декодировании используется такая же «стопка книг», находящаяся первоначально в том же состоянии. Над «стопкой» проводятся такие же преобразования, что и при кодировании. Это гарантирует однозначное восстановление исходной последовательности.

Заключение

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