Osnova_teorii_informatsii_prodolzhenie_2


Основа теории информации
По формуле можно найти среднюю длину кода. Для русского языка средняя длина кода равняется 4, 964 бита. Из этого следует, что избыточность Qr=1-4,356/4,964≈0,122. Это означает, что при данном способе кодировании (код Хаффмана) будет передаваться приблизительно на 12% больше информации, чем содержится в исходном сообщении. Аналогичные вычисления для английского языка дают значения избыточности Qr= 0, 141(14%). Перед наукой стоят следующие вопросы: возможно ли такое кодирование, в котором не будет использоваться разделители знаков и существуют ли наиболее оптимальный способ неравномерного двоичного кодирования? Суть первой проблемы состоит в нахождении такого варианта кодирования в сообщении, при котором последующее выделение из его каждого отдельного знака, то есть декодирования оказываются однозначным без специальных указателей выделения знака.
Построение кодов Хаффмана следует рассматривать на следующем примере:
Пусть имеется первичный алфавит А, состоящей из шести знаков (a(1) … a(6)) с вероятностями появления с вероятностями появления в сообщение, соответственно 0,3; 0,25; 0,2; 0,15; 0,1; 0,05. Создадим новый вспомогательный алфавит a(1), объединив два знака с наименьшими вероятностями a(5) и a(6) , и объединим их одним знаком a(1). Вероятность нового знака будет равна сумме вероятности тех, что в него вошли, то есть 0,15; остальные знаки исходного алфавита включим в новый алфавит без изменений, при этом общее число знаков в новом алфавите будет на один меньше, чем исходный . Аналогичным образом продолжим создавать новые алфавиты, пока в последнем не останется два знака. Число таких шагов будет равно N-2, где N – число знаков исходного алфавита. В нашем случае N=6, следовательно, необходимо построить четыре вспомогательных алфавита. В промежуточных алфавитах каждый раз будем переупорядочивать знаки по убыванию вероятностей. Представим процедуру построения в виде таблицы:
№ знака Вероятности
Исходный алфавит Промежуточные алфавиты
A(1)A(2)A(3)A(4)1 0,3 0,3 0,3 0,4 0,6
2 0,2 0,2 0,3 0,3 0,4
3 0,2 0,2 0,2 0,3 4 0,15 0,15 0,2 5 0,1 0,15 6 0,05 Далее в обратном направлении проведем процедуру кодирования, двум знакам последнего алфавита присвоим коды 0 и 1. В нашем примере знак a1(4) алфавита A(4)получит код 0, а a2(4) код 1; в алфавите A(3) знак a1(3) с вероятностью 0,4 сохранит свой код (1); коды знаков a2(3) и a3(3), объединенных знаком a1(4) с вероятностью 0,6, будут уже двузначным: их первой цифрой станет код, связанного с ними знака (т.е.0), а вторая цифра - как условились – у верхнего 0, у нижнего – 1; таким образам, a2(3) будет иметь код 00, а a3(3) -код 01. Полностью процедуру кодирования можно представить в следующей таблице:
№ знака Вероятности
Исходный алфавит Промежуточные алфавиты
A(1)A(2)A(3)A(4)1 0,3 00 0,3 00 0,3 00 0,4 1 0,6 0
2 0,2 10 0,2 10 0,3 01 0,3 00 0,4 1
3 0,2 11 0,2 11 0,2 10 0,3 01 4 0,15 010 0,15 010 0,2 11 5 0,1 0110 0,15 011 6 0,05 0111 Из самой процедуры построения кодов видно, что они удовлетворяют условию Фана и, следовательно, не требует разделителя, средняя длина кода при этом оказывается равной:
K(2)=0,3*2+0,2*2+0,2*2+0,15*3+0,1*4+0,05*4=2,45 , при этом если посчитать избыточность кода Q=0,0169, то есть менее 2%.
Код Хаффмана важен в теоретическом отношении, поскольку модно доказать, что он является самым экономичным из всех возможных, то есть ни для какого метода алфавитного кодирования длина кода не может оказаться меньше, чем код Хаффмана. Применение описанного метода для букв русского алфавита дает следующие коды:
Буква Код Pi
103kiБуква Код Pi
103kjпробел 000 174 3 я 011001 18 6
о 111 90 3 ы010110 16 6
е 0100 72 4 з010111 16 6
а 0100 62 4 ь.ъ100001 14 6
и 0111 62 4 б 101100 14 6
т 1001 53 4 г 101101 13 6
н1010 53 5 ч 110011 12 6
с 1101 45 4 й0011001 10 7
р00101 40 5 х1000000 9 7
в 00111 38 5 ж 1000001 7 7
л 01010 35 5 ю1100101 6 7
к 10001 28 5 ш00110000 6 8
м 10111 26 5 ц11001000 4 8
д11000 25 5 щ11001001 3 8
п001000 23 6 э 001100010 3 9
у 001001 21 6 ф001100011 2 9

Приложенные файлы

  • docx 18395089
    Размер файла: 24 kB Загрузок: 0

Добавить комментарий