pri_cod2

1. Алфавитное кодирование

Пусть B некоторый алфавит. Напомним, что словом над алфавитом B называется любая (конечная) упорядоченная последовательность символов этого алфавита. При необходимости слова заключают в кавычки. Если X слово над алфавитом B, то через l(X) обозначается длина этого слова, то есть число символов последовательности, изображающей это слово. Пустое слово это последовательность символов, не содержащая ни одного символа; обозначается пустое слово символом ^. Длина пустого слова равна 0.

Слова X = x1x2 : : : xn и Y = y1y2 : : : ym считаются равными тогда и только тогда, когда m = n и xi = yi при i = 1; 2; : : : ; n. Запись: X = Y .

Конкатенацией слов X = x1x2 : : : xn и Y = y1y2 : : : ym называется слово x1x2 : : : xny1y2 : : : ym; это слово обозначают XY . Так, если X = \автомобиль\ и Y =“ный“, то XY =“автомобильный“.

Если X = Y1Y2 : : : Yk, где Y1, Y2, : : :, Yk слова над алфавитом B и k ¸ 2, то говорят, что слово X разбито на слова Y1, Y2, : : :, Yk. Так, слово “математика“ можно разбить на слова “мате“ и “матика“, на слова “математи“ и “ка“, а также на слова “ма“ и “тематика“ (возможны и другие разбиения). Если X = Y Z, где Y и Z непустые слова, то Y называется началом (префиксом), а Z концом (постфиксом) слова X.

При алфавитном кодировании задается входной алфавит A и выходной алфавит B, состоящие из r и q символов соответственно: A = fa1; a2; : : : ; arg,

>

>

:

где xij 2 B при всех i, j. При i = 1; 2; : : : ; r слово xi1xi2 : : : xili называют кодовым и обозначают Bi. Слово Bi называют также кодом символа ai. Ясно,

что длина l(Bi) слова Bi равна li. Более коротко схема кодирования может

1

Используется и еще более компактная запись:

a1 ¡ B1; a2 ¡ B2; : : : ; ar ¡ Br:

Множество кодовых слов образует код, который называют кодом со схемой кодирования (§). Схемы кодирования обозначаются так: (§), (§0), (§1) и т. д. .

При кодировании очередному символу ai кодируемого сообщения сопоставляется кодовое слово Bi. Поэтому результат кодирования последовательности символов ai1ai2ai3 : : : входного алфавита это слово Bi1Bi2Bi3 : : :.

При декодировании закодированное сообщение разбивают на кодовые слова и считают, что кодовое слово Bj получено в результате кодирования символа aj при любом j. Если описанное разбиение не удается получить, то считают, что при передаче по каналу связи произошла по крайней мере одна ошибка.

Пример 1. Пусть схема кодирования имеет вид

a ¡ 01; b ¡ 10; c ¡ 210; d ¡ 221:

Тогда слово “bad“ будет закодировано словом \1001221\, а слово “abacad“ словом \01100121001221\. Слово \1001\ является результатом кодирования слова \ba\. Слово же \100\ не является результатом кодирования никакого слова, поскольку оно не может быть разбито на кодовые слова.

Отметим, что некоторые ранее рассмотренные методы кодирования по существу реализуют алфавитное кодирование (азбука Морзе, код “2 из 5“, кодирование с помощью таблицы Ascii см.[Pp, глава ..., стр. ]

2

1.1Проблема однозначности декодирования

Если для данного кода любое закодированное сообщение можно разбить на кодовые слова только одним способом, то говорят, что код удовлетворяет свойству однозначности декодирования (далее для краткости пишем (ОД)).

Пример 2. Закодированное азбукой Морзе сообщение

“¢ ¡ ¡ ¡ ¡ ¡ ¡ ¡ “

допускает расшифровки “ТЕЕЕЕЕЕЕ“, “АТОМ“, “АММТ“, “ВТО“, “ВОТ“, “АЕЕЕЕЕЕ“ и многие другие. Поэтому свойство (ОД) не выполнено.

Слово \121321223\ допускает две расшифровки a4a5 и a1a2a1a3, поэтому код не удовлетворяет свойству однозначности декодирования.

Отметим, что свойству (ОД) удовлетворяют два важных класса кодов:

1)Равномерные коды.

2)Префиксные коды, то есть такие коды, ни одно кодовое слово которых не является началом другого кодового слова.

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

В литературе описаны методы, позволяющие выяснить удовлетворяет

ли заданный код свойству (ОД) (см., например, [Ябл, Часть IV, §2, стр. ....]). Эти методы мы не будем рассматривать, поскольку в реально действующих N

системах кодирования обычно используют коды со свойством (ОД). Более того, для всякого кода C с таким свойством существует префиксный код C0, основные характеристики которого не хуже, чем у кода C (см. теорему Макмиллана и следствия из нее в [Ябл, Часть IV, §2, стр. ....]). Поэтому в дальнейшем будем рассматривать только префиксные коды.

3

1.2Избыточность схемы кодирования

Пусть задана схема кодирования (§) и символы a1 , a2 , : : : , ar встречаются в кодируемом сообщении с вероятностями p1 , p2 , : : : , pr соответственно. Тогда сумма

называется избыточностью схемы кодирования (§) или избыточностью кода

(соответствующего этой схеме). Отметим, что вероятности p1, p2 , : : : , pr удовлетворяют следующим условиям:

r

X pi = 1 и pi ¸ 0 для всех i:

i=1

Напомним, что li = l(Bi) это длина кодового слова Bi, то есть число символов в этом слове.

Для любого сообщения вероятности pi можно найти следующим образом: если N длина сообщения, а символ ai встречается в этом сообщении ki раз, то pi = kpii . Например, сообщение “площадь квадрата“ состоит из 16 символов (включая пробел), символ “а“ встречается 4 раза, а пробел - 1 раз. Поэтому соответствующие вероятности равны 164 и 161 . Те же символы появляются в сообщении “параллелограмм“ с вероятностями 143 и 140 . Если строится код для кодирования одного сообщения (так поступают при сжатии файлов), то находят точное значение вероятностей pi. Если же кодировать предполагается различные сообщение, то берут приближенные (усредненные по соощениям) значения вероятностей. При этом полезно использовать таблицы частот символов того или иного языка.

Замечание 1. Величина l(§) показывает во сколько раз (в среднем) длина закодированного текста больше длины исходного текста. В самом деле, пусть кодируемый текст состоит из N символов. Тогда при любом i, 1 · i · r, символ ai в этом тексте встретится приблизительно N ¢ pi раз. При кодировании каждый символ ai будет закодирован кодовым словом Bi, состоящим из li символов. Поэтому закодированный текст будет иметь длину, приблизительно равную Pri=1(N ¢ pi)li. Последняя же сумма равна N ¢ l(§).

4

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

Пример 4. Пусть входной алфавит A = fa1; a2; : : : ; a6g состоит из r = 6 символов и эти символы встречаются в кодируемом сообщении с вероятностями p1 = 0:4, p2 = 0:3, p3 = 0:2, p4 = 0:05, p5 = 0:03, p6 = 0:02 соответственно. Найдем избыточность следующих схем кодирования:

8

(§1) < a1 ¡ 12; a2 ¡ 13; a3 ¡ 23; ; (§1) : a4 ¡ 213; a5 ¡ 222; a6 ¡ 2131

8

(§2) < a1 ¡ 0; a2 ¡ 10; a3 ¡ 1101; : (§2) : a4 ¡ 1110; a5 ¡ 11110; a6 ¡ 11111

Имеем:

l(§1) = 2 ¢ 0:4 + 2 ¢ 0:3 + 2 ¢ 0:2 + 3 ¢ 0:05 + 3 ¢ 0:03 + 4 ¢ 0:02 = 2:12;

l(§2) = 1 ¢ 0:4 + 2 ¢ 0:3 + 4 ¢ 0:2 + 4 ¢ 0:05 + 5 ¢ 0:03 + 5 ¢ 0:02 = 2:25:

Поскольку l(§1) < l(§2), заключаем, что первая схема более экономна.

Упражнение 1 Найти избыточность следующей схемы кодирования:

5

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

l(§) = L ¢ P;

где L = (l1; l2; : : : ; lr) вектор длин кодовых слов, а P = (p1; p2; : : : ; pr) вектор вероятностей появления символов в кодируемом сообщении. В дальнейшем будем для краткости называть P вектором вероятностей.

1.3Коды с минимальной избыточностью

Если для набора данных r, q, P = (p1; p2; : : : ; pr) схема кодирования (§) обладает тем свойством, что ее избыточность l(§) принимает наименьшее возможное значение среди всех схем, построенных по этому набору, то говорят, что (§) схема с минимальной избыточностью, а соответствущий этой схеме код является кодом Хаффмана. Используют также выражения “оптимальная схема кодирования“, “оптимальный код“.

Пусть (§1) и (§2) две схемы кодирования, построенные для одного и того же набора данных. Ясно, что справедливы следующие свойства:

(М1) Если схема (§1) оптимальна, то l(§1) · l(§2).

(М2) Если l(§1) > l(§2), то (§1) не является оптимальной схемой.

Лемма 1 Пусть § схема кодирования со входным алфавитом A и выходным алфавитом B, состоящим из q символов. Тогда существует схема кодирования (§0) со входным алфавитом A и выходным алфавитом Zq = f0; 1; 2; : : : ; q ¡ 1g, для которой l(§) = l(§0).

Доказательство. Пусть A = fa1; a2; : : : ; arg и B = fb1; b2; : : : ; bqg. Пусть i

целое число от 1 до r. Схема кодирования (§) ставит в соответствие символу ai некоторое кодовое слово Bi, которое можно записать в виде

Bi = bj1bj2 : : : bjl;

где l = li длина слова Bi. Пусть схема (§0) ставит в соответствие тому же символу ai кодовое слово Bi0, где

Bi0 = j1j2 : : : jl:

6

Легко проверить, что схема §0 искомая.

Доказанная лемма показывает, что при построении схем с минимальной избыточностью можно ограничиться рассмотрением кодов с выходным алфавитом Zq = f0; 1; 2; : : : ; q ¡ 1g, где q = 2; 3; : : :.

Пример 5. Пусть (§) схема кодирования из упражнения 1. Проверим, что она не оптимальна. Заменим код \132\ символа a1 на код \2\, а коды остальных символов сохраним. Тогда получится новая схема (§0). Она обладает свойством префикса, поскольку в исходной схеме ни одно кодовое слово не начинается с цифры 2. Пусть li и li0, i = 1; 2; : : : ; 8 длины кодовых слов в схемах (§) и (§0) соответственно. Тогда l1 = 3, l10 = 1 и li = li0 при остальных i. Поэтому

l(§) ¡ l(§0) = l1p1 ¡ l10 p1 = 3p1 ¡ p1 = 2p1 = 0:44 > 0;

откуда l(§) > l(§0). Следовательно, схема (§) не оптимальна.

Предложение 1 Пусть r · qn и (§¤) оптимальная схема кодирования. Тогда l(§¤) · n.

Доказательство. Рассмотрим множество P всех упорядоченных последовательностей длины n из символов выходного алфавита B. Число jPj таких последовательностей равно qn, поскольку jBj = q. Из соотношений jAj = r и r · qn получаем jAj · jPj, поэтому существует такое отображение A ! P, которое разным символам алфавита A ставит в соответствие различные последовательности. Это отображение задает схему кодирования (§), все кодовые слова которой имеют одну и ту же длину n. Для этой схемы верно

Таким образом, найдена схема кодирования (§) с избыточностью, не большей n. Для завершения доказательства осталось использовать свойство (М1) при

§2 = §.

7

1.4Методы построения кодов с минимальной избыточностью

Пусть задано число r символов входного алфавита A, набор вероятностей p1, p2, : : :, pr и число q символов выходного алфавита B. Требуется построить ко этим данным код с минимальной избыточностью. Для случая q = 2 имеется алгоритм Шеннона-Фано, который позволяет построить бинарный код, близкий к оптимальному. В общем случае задача может быть решена точно с помощью алгоритма Хаффмана. Рассмотрим упомянутые алгоритмы.

1.4.1Метод Шеннона-Фано

Этот метод разработан в 1948-50гг и позволяет строить бинарные коды, близкие к оптимальным. Предполагается, таким образом, что выходной алфавит B состоит из двух символов. Обычно считают, что B = f0; 1g (хотя в азбуке Морзе выходной алфавит состоит из точки и тире). Суть метода заключается в следующем. Входной алфавит A разбивают на две части так, чтобы суммы вероятностей pi по каждой части были примерно одинаковы. Затем каждую часть разбивают на две меньшие части по тому же принципу до тех пор, пока в каждой части не останется по одному символу. Более точное описание алгоритма таково:

1)Входной алфавит A разбивают на две части A0 и A1 так, чтобы суммы вероятностей pi по каждой части были примерно одинаковы.

2)Пусть построена некоторая часть Aj1j2:::jm алфавита A, где j1; j2; : : : ; jm 2 f0; 1g. Если эта часть состоит из единственного символа ai, то кодируем этот символ последовательностью

j1; j2; : : : ; jm из нулей и единиц. Если же часть Aj1j2:::jm содержит не менее двух символов, то разбиваем ее на две

части Aj1j2:::jm0 и Aj1j2:::jm1 так, чтобы суммы вероятностей pi по каждой части были примерно одинаковы. Этот пункт следут

повторять до тех пор, пока находятся части алфавита (вида Aj1j2:::jm), содержащие не менее двух символов.

Замечание 1. Обычно вероятности pi являются рациональными числами. Для упрощения записи вместо этих чисел можно рассматривать относительные частоты ki = ¸pi, i = 1; 2; : : : ; r появления символов ai в коди-

8

руемом тексте. Положительное число ¸ выбирают так, чтобы числа ki были целыми. Несложно убедиться, что в описании алгорита Шеннона-Фано вероятности pi можно заменить относительными частотами ki. Поэтому наряду с вектором вероятностей P будем рассматривать также вектор K = ¸P относительных частот. При построении оптимальных кодов удобнее использовать вектор K.

Замечание 2. Части Aj1j2:::jm алфавита удобно записывать не как множества, состоящие из символов, а как множества, состоящие из относительных частот ki соответствующих символов.

Пример 6. Построим код Шеннона-Фано для набора вероятностей p1 = 0:22, p2 = 0:20, : : :, p8 = 0:06 из упражнения 1. Выбрав ¸ = 100, запишем набор относительных частот символов (всего) входного алфавита в виде

A = f22; 20; 15; 11; 10; 9; 7; 6g:

На первом шаге можно положить

A0 = f22; 20; 7g и A1 = f15; 11; 10; 9; 6g;

поскольку суммы 22+20+7 = 49 и 15+11+10+9+6 = 51 мало отличаются друг от друга. Теперь полагаем

A00 = f22g; A01 = f20; 7g; A10 = f15; 11g и A11 = f10; 9; 6g:

Так как множество A00 состоит только из одного элемента, являющегося относительной частотой символа a1, этот символ получает код 00. Остальные части разбиения содержат по меньшей мере два символа и эти части разбиваем на более мелкие:

A010 = f20g; A011 = f7g; A100 = f15g;

A101 = f11g; A110 = f10g и A111 = f9; 6g:

Остается разбить на две части множество A111:

A1110 = f9g и A1111 = f6g:

9

Теперь можно выписать схему полученного кода:

Избыточноть построенного кода равна 2:93.

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

Если число r символов алфавита A достаточно велико, то при использовании алгоритма Шеннона-Фано приходится рассматривать много вариантов разбиений данного набора символов на две части. Например, существует более 30 000 000 способов разбиения английского алфавита (r = 26) на две непустые части. Поэтому есть упрощенный вариант алгоритма. В этом варианте сначала составляют такой (упорядоченный) список S всех символов алфавита A, для которого выполнено следующее условие:

Если pi > pj, то символ ai стоит в списке S раньше символа aj:

Иными словами, символы алфавита A записывают в порядке убывания (более точно невозрастания) соответствующих им вероятностей pi. Список S разбиваем на два списка S0 и S1 так, что любой символ из S0 стоит в списке S раньше любого символа из S1 (таким образом, S0 начало списка S, а S1 конец списка S). При этом суммы вероятностей pi по спискам S0 и S1 должны быть примерно равны. На следующих шагах алгоритма поступаем аналогичным образом. Отметим, что существует только 25 способов разбиения английского алфавита на две непустые части.

Пример 7. Построим код по упрощенному алгоритму Шеннона-Фано для набора вероятностей p1 = 0:22, : : :, p8 = 0:06 из упражнения 1. Выбрав ¸ = 100, выпишем список относительных частот символов входного алфавита

S = f22; 20; 15; 11; 10; 9; 7; 6g:

10