букв ФИО адаптивным кодом Хаффмана (размер окна 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
Являюсь магистром Кубанского государственного университета. Кафедры Мировой экономики и менеджмента. Имею большой опыт в написании работ по экономики и статистики, а также в решении финансовых задач.
На странице представлен фрагмент
Уникализируй или напиши новое задание с помощью нейросети
Похожие работы
Определить сопротивление растеканию сложного заземления
Определить сопротивление растеканию сложного заземления, состоящего из вертикальных стержневых заземлителей и горизонтальной полосы. Исходные данные принять по варианту, номер которого совпадает с последней...
3 Заносим числовые данные по задаче в 5 столбец и 6 столбец
3. Заносим числовые данные по задаче в 5 столбец и 6 столбец. Данные столбца 5 – это данные уровня притязаний, а столбца 6 – силы воли Кодируем переменные: для этого переходим с листа «представление...