букв ФИО адаптивным кодом Хаффмана (размер окна 6) Подсчитаем частоту вхождения символов в ФИО и расположим их по убыванию

букв ФИО адаптивным кодом Хаффмана (размер окна 6).

Подсчитаем частоту вхождения символов в ФИО и расположим их по убыванию. Общее количество символов – 23:

Таблица 1. Частота вхождения символов

Символ Кол-во символов Частота вхождения
А 4 0,17391
И 4 0,17391
Н 4 0,17391
Р 2 0,08695
Б 1 0,04348
В 1 0,04348
Е 1 0,04348
Й 1 0,04348
Л 1 0,04348
М 1 0,04348
О 1 0,04348
У 1 0,04348
Х 1 0,04348

Код Хаффмана.

Будем складывать две наименьшие вероятности и включать суммарную вероятность на соответствующее место в упорядоченном списке вероятностей до тех пор, пока в списке не останется два символа.

Рисунок 1. Процесс построения кода Хаффмана

Таблица 2. Код Хаффмана

Символ Частота вхождения, p Длина кода, L Кодовое слово
А 0,17391 3 000
И 0,17391 3 001
Н 0,17391 3 010
Р 0,08695 4 0110
Б 0,04348 4 0111
В 0,04348 4 1000
Е 0,04348 4 1001
Й 0,04348 4 1010
Л 0,04348 4 1011
М 0,04348 4 1100
О 0,04348 4 1101
У 0,04348 4 1110
Х 0,04348 4 1111

Средняя длина построенного кода Хаффмана:

Lср=0,17391 * 3 + 0,17391 * 3 + 0,17391 * 3 + 0,08695 * 4 + 0,04348 * 4 + 0,04348 * 4 +

+ 0,04348 * 4 + 0,04348 * 4 + 0,04348 * 4 + 0,04348 * 4 + 0,04348 * 4 + 0,04348 * 4 +

+ 0,04348 * 4 =3,3044

При этом энтропия равна:

H=-3*0,17391*log 0,17391- 0,08695*log 0,08695 – 9*0,04348*log 0,04348 = 2,9543

Построим кодовое дерево для кода Хаффмана:

1
0

0
1
00,30434

1

0,6522
0,3478
1
0
1
0

0

1
0
1

0,34782
И

0,17391

1
0

А
1
0

Н
1
0

1
0

1
0

Рисунок 2. Кодовое дерево для кода Хаффмана
Код Фано.

Делим таблицу частоты вхождения символов на две части, так чтобы суммы частот в обоих частях были как можно более одинаковыми. Первой части присваиваем 0, второй 1.
Далее, каждую из полученных половинок делим на две по такому же принципу и так далее, пока весь список не разобьется на части, содержащие по одной букве.

Таблица 3. Код Фано

Символ Частота вхождения, p Кодовое слово Длина кода, L
А 0,17391 0 0 2
И 0,17391 0 1 0 3
Н 0,17391 0 1 1 3
Р 0,08695 1 0 0 0 4
Б 0,04348 1 0 0 1 4
В 0,04348 1 0 1 0 4
Е 0,04348 1 0 1 1 0 5
Й 0,04348 1 0 1 1 1 5
Л 0,04348 1 1 0 0 4
М 0,04348 1 1 0 1 4
О 0,04348 1 1 1 0 4
У 0,04348 1 1 1 1 0 5
Х 0,04348 1 1 1 1 1 5

Средняя длина построенного кода Фано:

Lср=0,17391*2+0,17391*3+0,17391*3+0,08695*4+0,04348*4+0,04348*4+0,04348*5+0,04348*5+0,04348*4+0,04348*4+0,04348*4+0,04348*5+0,04348*5=3,4783
Построим кодовое дерево для кода Фано:

1
0

0

0
1

1

1
0

0
1
1
0
0

0
0
1
1

1
0

1
0

0
1

0

1

Рисунок 3. Кодовое дерево для кода Фано

Код Шеннона.

Упорядоченные символы исходного алфавита с упорядоченными символами по убыванию берем из таблицы 1. Вычислим кумулятивные вероятности Q. Представим Qi-1 в двоичной системе счисления и возьмем в качестве кодового слова первые –log pi двоичных знаков после запятой.

Длину кодового слова Li берем из соотношения 1/2Li ≤ pi < 1/2Li-1

Таблица 4. Код Шеннона

Символ Частота вхождения, p Qi Qi в двоичной системе Длина кода, Li Кодовое слово
А 1/23≤0,17391<1/22 0 0 3 000
И 1/23≤0,17391<1/22 0,17391 0,0010 3 001
Н 1/23≤0,17391<1/22 0,34782 0,0101 3 010
Р 1/24≤0,08695<1/23 0,52173 0,10000 4 1000
Б 1/25≤0,04348<1/24 0,60868 0,100110 5 10011
В 1/25≤0,04348<1/24 0,65216 0,101001 5 10100
Е 1/25≤0,04348<1/24 0,69564 0,101100 5 10110
Й 1/25≤0,04348<1/24 0,73912 0,101111 5 10111
Л 1/25≤0,04348<1/24 0,78260 0,110010 5 11001
М 1/25≤0,04348<1/24 0,82608 0,110100 5 11010
О 1/25≤0,04348<1/24 0,86956 0,110111 5 11011
У 1/25≤0,04348<1/24 0,91304 0,111010 5 11101
Х 1/25≤0,04348<1/24 0,95652 0,111101 5 11110

Средняя длина построенного кода Шеннона:

Lср=0,17391*3+0,17391*3+0,17391*3+0,08695*4+0,04348*5+0,04348*5+0,04348*5+0,04348*5+0,04348*5+0,04348*5+0,04348*5+0,04348*5+0,04348*5= 3,8696
Арифметический код.

Закодируем первые три буквы своего имени арифметическим кодом. Это символы: И, Р и И, с вероятностями: 0,17391, 0,08695 и 0,17391 соответственно.
Кумулятивные вероятности, возьмем из Таблицы 4:

Q0=0,
Q1= p1=0,17391,
Q2= p1+p2=0,34782,
Q3= p1+p2+p3=0,52173,
Q4= p1+p2+p3+p4=0,60868,
Q5= p1+p2+p3+p4+p5=0,65216,
Q6= p1+p2+p3+p4+p5+p6=0,69564,
Q7= p1+p2+p3+p4+p5+p6+p7=0,73912,
Q8= p1+p2+p3+p4+p5+p6+p7+p8=0,78260,
Q9= p1+p2+p3+p4+p5+p6+p7+p8+p9=0,82608,
Q10= p1+p2+p3+p4+p5+p6+p7+p8+p9+p10=0,86956,
Q11= p1+p2+p3+p4+p5+p6+p7+p8+p9+p10+p11=0,91304,
Q12= p1+p2+p3+p4+p5+p6+p7+p8+p9+p10+p11+p12=0,95652.

Получим границы интервала, соответствующего первому символу кодируемого сообщения И (второй символ в таблице 4):

l1=l0+r0∙Q2-1=0+1∙0,17391=0,17391,
h1= l0+ r0∙Q2=0+1∙0,34782=0,34782,
r1= h1- l1=0,34782 – 0,17391=0,17391 .

Для второго символа Р (четвертый символ в таблице 4) кодируемого сообщения границы интервала будут следующие:

l2=l1+r1∙Q4-1=0,17391+0,17391∙0,52173= 0,2646440643,
h2= l1+ r1∙Q4=0,17391+0,17391∙0,60868=0,2797655388,
r2= h2- l2=0,2797655388-0,2646440643=0,0151214745.

Для третьего символа И (второй символ в таблице 4) кодируемого сообщения границы интервала будут следующие:

l3=l2+r2∙Q2-1=0,2646440643+0,0151214745∙0,17391= 0,26727383993,
h3= l2+ r2∙Q2=0,2646440643+0,0151214745∙0,34782=0,269903615561,
r3= h3- l3=0,269903615561-0,26727383993=0,00262977563029
.
В результате всех вычислений получаем следующую последовательность интервалов для сообщения ИРИ:

В начале: [0.0, 1.0)
После просмотра И: [0.17391, 0.34782)
После просмотра Р: [0.2646440643, 0.2797655388)
После просмотра И: [0.26727383993, 0.269903615561)

Кодом последовательности ИРИ будет двоичная запись любой точки из интервала [0.26727383993, 0.269903615561), например, 0.268. Для однозначного декодирования возьмем
−logr3=−log0,00262977563029=9разрядов, получим код 010001001.

Адаптивный код Хаффмана.

Закодировать последовательность из 10 букв ФИО адаптивным кодом Хаффмана (размер окна 6). Последовательность и окно:

бурени наир

В начале кодирования символы, входящие в окно кодируются кодом Хаффмана, который строится для оценочного распределения вероятностей. Для этого подсчитываются частоты и вероятности:

Таблица 5.

Символ Вероятность, p Построение кода Кодовое слово
Б 1/6 10
Е 1/6 11
Н 1/6 000
Р 1/6 001
У 1/6 010
И 1/6 0110
А 0 0111

Кодируем символ Н кодовым словом 000.

Далее сдвигаем окно на 1 символ вправо

б уренин аир

Снова символы входящие в окно кодируются кодом Хафманна:

Таблица 6.

Символ Вероятность, p Построение кода Кодовое слово
Б 0 00110
Е 1/6 10
Н 1/3 01
Р 1/6 11
У 1/6 000
И 1/6 0010
А 0 00111

Кодируем символ А кодовым словом 00111.

Далее сдвигаем окно еще на 1 символ вправо

бу ренина ир

Снова символы входящие в окно кодируются кодом Хафманна:

Таблица 7.

Символ Вероятность, p Построение кода Кодовое слово
Б 0 00110
Е 1/6 10
Н 1/3 01
Р 1/6 11
У 0 00111
И 1/6 000
А 1/6 0010

Кодируем символ И кодовым словом 000.

Далее сдвигаем окно еще на 1 символ вправо

бур енинаи р

Снова символы входящие в окно кодируются кодом Хафманна:

Таблица 8.

Символ Вероятность, p Построение кода Кодовое слово
Б 0 1110
Е 1/6 10
Н 1/3 00
Р 0 11110
У 0 11111
И 1/3 01
А 1/6 110

Кодируем символ Р кодовым словом 11110.

Таким образом последовательность буренинаир получает кодовую последовательность: 10 010 001 11 000 0110 000 00111 000 11110

alinasibem 4.7

Являюсь магистром Кубанского государственного университета. Кафедры Мировой экономики и менеджмента. Имею большой опыт в написании работ по экономики и статистики, а также в решении финансовых задач.

Нанять автора