2.2. Равномерно двоичный код (рдк)
S=у моей мамы золотые руки; Ls=24.
А={у,_,м,о,е,й,а,ы,з,л,т,р,к,и}, LА=14.
Запишем сообщение в коде РДК и определить длину РДК (Lрдк);
|
i |
a(i) |
Vi |
p(ai) |
РБК |
|
1 |
у |
2 |
0,0833 |
0001 |
|
2 |
_ |
4 |
0,1666 |
0010 |
|
3 |
м |
3 |
0,125 |
0011 |
|
4 |
о |
3 |
0,125 |
0100 |
|
5 |
е |
2 |
0,0833 |
0101 |
|
6 |
й |
1 |
0,0416 |
0110 |
|
7 |
а |
1 |
0,0416 |
0111 |
|
8 |
ы |
2 |
0,0833 |
1000 |
|
9 |
з |
1 |
0,0416 |
1001 |
|
10 |
л |
1 |
0,0416 |
1010 |
|
11 |
т |
1 |
0,0416 |
1011 |
|
12 |
р |
1 |
0,0416 |
1100 |
|
13 |
к |
1 |
0,0416 |
1101 |
|
14 |
и |
1 |
0,0416 |
1110 |
Lрдк=4бита
Здесь: i–номер символа, v(ai)- количество встречающихся символов в сообщении, p(ai) –вероятность появления, и РБК – равномерный бинарный код.
Ls=24*4=96 бит – займет все сообщение
SРБК={00010010001101000101011000100011011100111000001010010100101 0010010111000010100101100000111011110}
Рис.
2. 1. КБД (РДК)
2.3. Онк Шенона-Фано
-
Предварительный шаг
Все вероятности символов ранжируется по убыванию или по возрастанию
-
Шаг1 (первый бит ОНК)
Все вероятности делятся на 2 равномерных секции. Символам верхней секции присваивается «1», нижней – «0» (или наоборот)
-
Шаг2 (второй бит ОНК)
Каждую секцию делим на 2 равновероятные подсекции. Символам верхней секции присваивается «1», нижней – «0» и т.д. Деление заканчивается, когда в подсекции остается 1 символ.
|
i |
a(i) |
p(ai) |
1 бит |
2 бит |
3 бит |
4 бит |
5 бит |
ОНК |
ИОНК |
Li |
pi*Li |
|
1 |
_ |
0,1666 |
|
1 |
1 |
) |
|
111 |
000 |
3 |
0,5 |
|
2 |
м |
0,125 |
1 |
0,2916 |
0 |
) |
|
110 |
001 |
3 |
0,375 |
|
3 |
о |
0,125 |
|
0 |
1 |
) |
|
101 |
010 |
3 |
0,375 |
|
4 |
у |
0,0833 |
0,4999 |
0,2083 |
0 |
) |
|
100 |
011 |
3 |
0,25 |
|
5 |
е |
0,0833 |
|
1 |
1 |
1 |
) |
0111 |
1000 |
4 |
0,333 |
|
6 |
ы |
0,0833 |
|
|
0,1666 |
0 |
) |
0110 |
1001 |
4 |
0,333 |
|
7 |
й |
0,0416 |
|
0,2498 |
|
1 |
) |
0101 |
1010 |
4 |
0,166 |
|
8 |
а |
0,0416 |
0 |
|
0,0832 |
0 |
) |
0100 |
1011 |
4 |
0,166 |
|
9 |
з |
0,0416 |
|
0 |
1 |
1 |
) |
0011 |
1100 |
4 |
0,166 |
|
10 |
л |
0,0416 |
0,4994 |
|
0,1248 |
0 |
1 |
) 00101 |
11010 |
5 |
0,208 |
|
11 |
т |
0,0416 |
|
0,2496 |
|
0,0832 |
0 |
) 00100 |
11011 |
5 |
0,208 |
|
12 |
р |
0,0416 |
|
|
0 |
1 |
1 |
) 00011 |
11100 |
5 |
0,208 |
|
13 |
к |
0,0416 |
|
|
0,1248 |
0,0832 |
0 |
) 00010 |
11101 |
5 |
0,208 |
|
14 |
и |
0,0416 |
|
|
0 |
) |
0000 |
1111 |
4 |
0,166 |
Критерий Фано декодирования сообщения в неравномерных кодах (префиксность ОНК): ни одно слово ОНК не является началом другого ОНК. Критерий Фано позволяет записать сообщение в сжатом виде, а также при этом однозначно его декодировать.
Сообщение в кодах Шеннона-Фано:
S={1001111011010111010111111001001100110111001110100101101001000110011111100011100000100000}
Рис.2.2. КБД (ОНК)
Информационные
характеристики ОНК
:
(Для удобства вычислений нам понадобятся эти данные)
|
i |
p(ai) |
Li |
pi*Li |
|
1 |
0,1666 |
3 |
0,5 |
|
2 |
0,125 |
3 |
0,375 |
|
3 |
0,125 |
3 |
0,375 |
|
4 |
0,0833 |
3 |
0,25 |
|
5 |
0,0833 |
4 |
0,333 |
|
6 |
0,0833 |
4 |
0,333 |
|
7 |
0,0416 |
4 |
0,166 |
|
8 |
0,0416 |
4 |
0,166 |
|
9 |
0,0416 |
4 |
0,166 |
|
10 |
0,0416 |
5 |
0,208 |
|
11 |
0,0416 |
5 |
0,208 |
|
12 |
0,0416 |
5 |
0,208 |
|
13 |
0,0416 |
5 |
0,208 |
|
14 |
0,0416 |
4 |
0,166 |
-
Средняя длина ОНК
=
= 3,66 [бит]
-
Энтропия ОНК
3,6
[бит/символ]
-
Максимальная энтропия
Hmax(X) = log ls ls = 24
Hmax(X) = log (24) = 4,584963 [бит/симв]
-
Относительная энтропия
0,78
[бит/символ]
-
Информационная избыточность
D=1-
0,22
-
Абсолютная недогруженность
0,98[бит/символ]
-
Коэффициент сжатия
Kc=1
-
1-0,915=0,085=8,5
%
-
Коэффициент эффективности
2.4. ОНК Хаффмeна
-
Шаг1
Суммируются 2 самые маленькие вероятности символов алфавита. Получается усеченный алфавит, уменьшенный на 1 символ.
-
Шаг2
В усеченном алфавите суммируем 2 самые маленькие вероятности. Получаем усеченный алфавит, уменьшенный на 1 символ.
И так до тех пор, пока в усеченном коде не останется один символ с вероятностью 1.В результате получится корневое дерево Хаффмана.
Сообщение в ОНК Хаффмена: SОНК = {0011001010000101100010010111001101011100110100001101100011100011010100111010011111011111}
Критерий Фано декодирование сообщения в неравномерных кодах: ОНК Хаффмена обладает свойством префиксности. Это позволяет однозначно декодировать сжатое сообщение.
Рис.2.3. КБД ОНК Хаффмен
Информационные характеристики ОНК:
-
Средняя длина ОНК
=3,66
[бит]
-
Коэффициент эффективности
В нашем случае информационные характеристики ОНК Шеннона – Фано и ОНК Хаффмена совпадают.
Вывод об эффективности ОНК:
Эффективность ОНК определяет отношение энтропии к средней длине ОНК, при этом ОНК тем выше, чем ближе средняя длина ОНК приближается к энтропии H:
В моем случае, эти значения почти одинаковы, следовательно, ОНК обладает достаточно высокой эффективностью.