Методическое пособие 276

Общее правило составления уравнений Колмогорова для предельных вероятностей pi(t) можно сформулировать следующим образом:

•в левой части уравнения стоит сумма произведений вероятностей всех состояний, из которых идут стрелки в i-ое состояние, на интенсивности соответствующих потоков минус сумма интенсивностей всех потоков, выводящих систему из данного (j-го) состояния, умноженная на вероятность данного (j-го) состояния;

•в правой части уравнения стоит 0.

19

2. МЕТОДЫ ЭФФЕКТИВНОГО КОДИРОВАНИЯ

Под кодированием понимают отображение состояний некоторой системы (источника сообщений) с помощью состояний сложного сигнала, который представляет собой последовательность из nэлементарных сигналов [11, 15].

Состояние сложного сигнала описывается последовательностью из нулей и единиц, которая называется кодовым словом. Если кодовые слова имеют разную длину, то код называется неравномерным, а если одинаковую, то код называется равномерным.

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

Методы сжатия данных были разработаны как математическая теория, которая до первой половины 80-х годов 20 века мало использовалась в компьютерной технике.

Методы или алгоритмы сжатия данных без потерь можно разделить на:

1.Статистические методы или алгоритмы. Например, методы Шеннона-Фано, Хаффмана и др.

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

2.Адаптивные методы или алгоритмы. Например, модифицированные коды Хаффмана, арифметическое кодирование и др.

20

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

3. Динамические методы или алгоритмы. Они являются универсальными и не нуждаются в априорной статистике. Например, метод Лемпела-Зива.

Основные информационные характеристики при кодировании:

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

где dimA - размер алфавита данных A.

Таким образом, коэффициент сжатия r= 2 означает, что объем сжатых данных составляет половину от объема данных источника. Чем больше коэффициент сжатия r, тем лучше работает система сжатия данных.

21

Наряду с коэффициентом сжатия r эффективность системы сжатия может быть охарактеризована скоростью сжатия R, определяемой как отношение

R = k/n

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

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

Такое кодирование называется статистическим. Неравномерный код при статистическом кодирова-

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

2.1.Метод кодирования Шеннона - Фано

Другим простейшим способом статистического кодирования является кодирование по методу ШеннонаФано [19]. Кодирование в соответствии с этим алгоритмом производится так:

- сначала все буквы из алфавита сообщения записывают в порядке убывания их вероятностей;

22

-затем всю совокупность букв разбивают на две примерно равные по сумме вероятностей группы; одной из них (в группе может быть любое число символов, в том числе – один) присваивают символ «1», другой - «0»;

-каждую из этих групп снова разбивают (если это возможно) на две части и каждой из частей присваивают

«1» и «0» и т.д.

Процедура кодирования по методу Шеннона-Фано иллюстрируется табл.1.

Таблица 1 Процедура кодирования по методу Шеннона-Фано

̅ = ∑8=1 = =(0,25*2+0,25*2+0,15*3+0,15*3+0,05*4+0,05*4+0,05*4+

+0,15*4)=2,7 бит

23

8

( ) = − ∑ log2 =

=1

= −(2 0,25 log2 0,25 + 2 0,15

log2 0,15 + 4 0,05 log2 0,05) = 2,7 бит

= (̅) = ,, = .

Метод Шеннона-Фано не всегда приводит к однозначному построению кода, так как при разбиении на подмножества можно сделать большей по вероятности как верхнюю, так и нижнюю часть, следовательно, такое кодирование хотя и является эффективным, но не всегда будет оптимальным.

2.2. Метод кодирования Хаффмана

Алгоритм Хаффмана изящно реализует общую идею статистического кодирования с использованием префиксных множеств и работает следующим образом [2]:

1. Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте.

2.Последовательно объединяем два символа с наименьшими вероятностями появления в новый составной символ, вероятность появления которого полагаем равной сумме вероятностей составляющих его символов. В конце концов построим дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него.

3. Прослеживаем путь к каждому листу дерева, помечая направление к каждому узлу (например, направо - 1, налево – 0) . Полученная последовательность дает кодовое слово, соответствующее каждому символу.

24

Этот метод всегда дает оптимальное кодирование в отличие от предыдущего, так как получаемая средняя длина кодового слова является минимальной.

Буквы алфавита сообщения располагают в порядке убывания вероятностей(для букв русского алфавита - см. приложение 1). Две последние буквы объединяют в один составной символ, которому приписывают суммарную вероятность. Далее заново переупорядочивают символы и снова объединяют пару с наименьшими вероятностями. Продолжают эту процедуру до тех пор, пока все значения не будут объединены. Это называется редукцией. Затем строится кодовое дерево из точки, соответствующей вероятности 1 (это корень дерева), причем ребрам с большей вероятностью присваивают 1,а с меньшей – 0. Двигаясь по кодовому дереву от корня к оконечному узлу, можно записать кодовое слово для каждой буквы исходного алфавита.

Пример 3.

Расположим буквы алфавита А1 в порядке убывания их вероятностей и подвергнем сжатию алфавит А1; при этом мы придём к алфавиту А2, который получается из первоначального алфавитаА с помощью двукратного сжатия (а из алфавита А1 ─ с помощью простого или однократного сжатия). Ясно, что алфавит А2 будет содержать уже всего n-2 буквы. Продолжая эту процедуру, мы будем приходить к всё более коротким алфавитам; после (n-2)- кратного сжатия мы придём к алфавиту Аn-2, содержащему уже всего две буквы.

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

x1 = 0,4;x2 = 0,2;x3 = 0,2;x4 = 0,1;x5 = 0,05 и x6 = 0,05(табл. 2).

25

Таблица 2

Преобразование алфавита с помощью последовательных сжатий

Условимся теперь приписывать двум буквам последнего алфавита Аn-2 кодовые обозначения 1 и 0. Далее, если кодовые обозначения уже приписаны всем буквам алфавита Аj, то буквам «предыдущего» алфавита Аj-1 (где, разумеется, А1-1 = А0 ─это исходный алфавит А), сохранившимся и в алфавите Аj, мы пишем те же кодовые обозначения, которые они имели в алфавите Аj-1; двум же буквам а’ и а’’ алфавита Аj, «слившимся» в одну букву b алфавита Аj-1, мы припишем обозначения, получившиеся из кодового обозначения буквы b добавлением цифр 1 и 0 в конце (Табл. 3).

26

Таблица 3

Алгоритм приписывания «0» и «1»

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

Заметим ещё, что кодирование некоторого алфавита по методу Хаффмана (так же, впрочем, как и по методу Шеннона − Фано) не является однозначной процедурой.

Так, например, на любом этапе построения кода можно, разумеется, заменить цифру 1 на цифру 0 и наоборот; при этом мы получим два разных кода (отличающихся весьма несущественно друг от друга). Но помимо того в некоторых случаях можно построить и несколько существенно различающихся кодов Хаффмана; так, например, в разобранном выше примере можно строить код и в соответствии со следующей таблицей (табл. 4):

27

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

1 · 0,4 + 2 · 0,2 + 3 · 0,2 + 4 · 0,1 + 5 · (0,05 + 0,05) = 2,3, а во втором ─ равно 1 · (0,4 + 0,2 + 0,2) + 3 · 0,1 + 4 · (0,05 + 0,05) = 2,3.

28