Изучим методы эффективного кодирования на примере небольшого текста на русском языке. Вероятности знаков будем считать равными относительной частоте встречаемости знаков в тексте.
В качестве текста возьмите свою фамилию, имя и отчество:
Солоха Данил Денисович
Постройте коды Хаффмена, Шеннона и Гилберта-Мура. Сравните полученные коды по средней длине кодового слова и по относительной избыточности. Для блока этого же текста длиной 4 или 5 букв постройте блочный арифметический код.
Решение
Определяем количество символов в ФИО: Солоха Данил Денисович. Рассчитываем вероятность их появления в сообщении.
№ Символ Количество символов Вероятность
1 z1 А 2 1/11
2 z2 В 1 1/22
3 z3 Д 2 1/11
4 z4 Е 1 1/22
5 z5 И 3 3/22
6 z6 Л 2 1/11
7 z7 Н 2 1/11
8 z8 О 3 3/22
9 z9 С 2 1/11
10 z10 Х 1 1/22
11 z11 Ч 1 1/22
12 z12 Пробел 2 1/11
Итого 22
Код Хаффмена:
zi p(zi) ni
код
z5 3/22 3 100
z8 3/22 3 101
z1 1/11 3 000
z3 1/11 3 001
z6 1/11 3 010
z7 1/11 3 011
z9 1/11 4 1100
z12 1/11 4 1101
z2 1/22 5 11100
z4 1/22 5 11101
z10 1/22 5 11110
z11 1/22 5 11111
Средняя длина кодового слова:
бит.
Энтропия:
Избыточность источника X определяется как:
.
Избыточность кода Хаффмена равна:
.
Код Шеннона:
zi p(zi) q(zi) -log p(zi) ri
Двоичная запись q(zi) код
z5 3/22 0,0000 2,8745 3 0,00000000 000
z8 3/22 0,1364 2,8745 3 0,00100011 001
z1 1/11 0,2727 3,4594 4 0,01000110 0100
z3 1/11 0,3636 3,4594 4 0,01011101 0101
z6 1/11 0,4545 3,4594 4 0,01110100 0111
z7 1/11 0,5455 3,4594 4 0,10001100 1000
z9 1/11 0,6364 3,4594 4 0,10100011 1010
z12 1/11 0,7273 3,4594 4 0,10111010 1011
z2 1/22 0,8182 4,4594 5 0,11010001 11010
z4 1/22 0,8636 4,4594 5 0,11011101 11011
z10 1/22 0,9091 4,4594 5 0,11101001 11101
z11 1/22 0,9545 4,4594 5 0,11110100 11110
Средняя длина кодового слова:
бит.
Избыточность кода Шеннона равна:
.
Код Гилберта-Мура:
zi p(zi) q(zi) σ(zi) = q(zi) + p(zi)/2 -log p(zi) ri
Двоичная запись q(zi) код
z1 1/11 0,0000 0,0455 3,4594 4 0,01110100 0111
z2 1/22 0,0909 0,1136 4,4594 5 0,00011101 00011
z3 1/11 0,1364 0,1818 3,4594 4 0,00101111 0010
z4 1/22 0,2273 0,2500 4,4594 5 0,01000000 01000
z5 3/22 0,2727 0,3409 2,8745 3 0,01010111 010
z6 1/11 0,4091 0,4545 3,4594 4 0,01110100 0111
z7 1/11 0,5000 0,5455 3,4594 4 0,10001100 1000
z8 3/22 0,5909 0,6591 2,8745 3 0,10101001 101
z9 1/11 0,7273 0,7727 3,4594 4 0,11000110 1100
z10 1/22 0,8182 0,8409 4,4594 5 0,11010111 11010
z11 1/22 0,8636 0,8864 4,4594 5 0,11100011 11100
z12 1/11 0,0000 0,0455 3,4594 4 0,01110100 0111
Средняя длина кодового слова:
бит.
Избыточность кода Гилберта-Мура равна:
.
Блочный арифметический код для блока этого же текста длиной 4:
i zi p(zi) q(zi) F G
0 0 1
1 А 1/11 0 0,0000 0,0909
2 Л 1/11 0 0,0000 0,0083
3 И 3/22 1/11 0,0008 0,0011
4 Н 1/11 0 0,0008 0,0001
5 А 1/11 0 0,0008 0,00001
Длина кодового слова:
Кодовое слово – это первые 18 знаков двоичной записи числа:
, то есть 000000000011000110
Задать вопрос
на новый заказ в Автор24.
