Изучим методы эффективного кодирования на примере небольшого текста на русском языке. Вероятности знаков будем

Изучим методы эффективного кодирования на примере небольшого текста на русском языке. Вероятности знаков будем считать равными относительной частоте встречаемости знаков в тексте. В качестве текста возьмите свою фамилию, имя и отчество: Солоха Данил Денисович Постройте коды Хаффмена, Шеннона и Гилберта-Мура. Сравните полученные коды по средней длине кодового слова и по относительной избыточности. Для блока этого же текста длиной 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