Задача 1 Текст закодирован восьмеричными числами. Подсчитали частоты всех 8 цифр и их вероятности (для этого нужно найти число повторений цифры в тексте и разделить на общее число цифр). Построить неравномерные коды Хафмена и Шеннона и определить среднюю длину кодов и % сжатия сообщения закодированного в 8 системе счисления при заданной статистике в среднем на 10000 цифр. Вариант 3 Цифра 0 1 2 3 4 5 6 7 Частота 700 700 900 1600 3200 1600 500 800 Вероятность 0,07 0,07 0,09 0,16 0,32 0,16 0,05 0,08

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

Построим код Хаффмана для заданных частот:

1. Упорядочиваем частоты по возрастанию: 500, 700, 700, 800, 900, 1600, 1600, 3200.
2. Соединяем две наименьшие частоты: 500 и 700 → 1200.
3. Новый список частот: 700, 800, 900, 1200, 1600, 1600, 3200.
4. Соединяем две наименьшие частоты: 700 и 800 → 1500.
5. Новый список частот: 900, 1200, 1500, 1600, 1600, 3200.
6. Соединяем две наименьшие частоты: 900 и 1200 → 2100.
7. Новый список частот: 1500, 1600, 1600, 2100, 3200.
8. Соединяем две наименьшие частоты: 1500 и 1600 → 3100.
9. Новый список частот: 1600, 2100, 3100, 3200.
10. Соединяем две наименьшие частоты: 1600 и 2100 → 3700.
11. Новый список частот: 3100, 3200, 3700.
12. Соединяем две наименьшие частоты: 3100 и 3200 → 6300.
13. Новый список частот: 3700, 6300.
14. Соединяем две наименьшие частоты: 3700 и 6300 → 10000.

Присваиваем коды:

• 0: 1110
• 1: 1111
• 2: 1101
• 3: 101
• 4: 0
• 5: 100
• 6: 1100
• 7: 101

2. Код Шеннона

Код Шеннона для заданных вероятностей:

• Упорядочиваем вероятности по убыванию: 0.32, 0.16, 0.16, 0.09, 0.08, 0.07, 0.07, 0.05
• Вычисляем длины кодов:
• \( l_i = \lceil -log_2(p_i) \rceil \)
• Коды Шеннона:
• 4: 00
• 3: 010
• 5: 011
• 2: 100
• 7: 1010
• 0: 1011
• 1: 1100
• 6: 1101

3. Средняя длина кода Хаффмана

Средняя длина кода Хаффмана:

\( L_{avg} = \sum_{i=0}^{7} p_i \cdot l_i \)

\( L_{avg} = 0.07 \cdot 4 + 0.07 \cdot 4 + 0.09 \cdot 4 + 0.16 \cdot 3 + 0.32 \cdot 1 + 0.16 \cdot 3 + 0.05 \cdot 4 + 0.08 \cdot 3 = 2.46 \)

4. Средняя длина кода Шеннона

Средняя длина кода Шеннона:

\( L_{avg} = \sum_{i=0}^{7} p_i \cdot l_i \)

\( L_{avg} = 0.32 \cdot 2 + 0.16 \cdot 3 + 0.16 \cdot 3 + 0.09 \cdot 3 + 0.08 \cdot 4 + 0.07 \cdot 4 + 0.07 \cdot 4 + 0.05 \cdot 4 = 2.95 \)

5. Энтропия

Энтропия:

\( H(X) = - \sum_{i=0}^{7} p_i \cdot log_2(p_i) \)

\( H(X) = -(0.07 \cdot log_2(0.07) + 0.07 \cdot log_2(0.07) + 0.09 \cdot log_2(0.09) + 0.16 \cdot log_2(0.16) + 0.32 \cdot log_2(0.32) + 0.16 \cdot log_2(0.16) + 0.05 \cdot log_2(0.05) + 0.08 \cdot log_2(0.08)) = 2.417 \)

6. Процент сжатия для кода Хаффмана

Исходная длина сообщения: \( L_{исх} = 10000 \cdot log_2(8) = 10000 \cdot 3 = 30000 \)

Длина сжатого сообщения: \( L_{сжат} = 10000 \cdot L_{avg} = 10000 \cdot 2.46 = 24600 \)

Процент сжатия: \( Сжатие = \frac{L_{исх} - L_{сжат}}{L_{исх}} \cdot 100 \% = \frac{30000 - 24600}{30000} \cdot 100 \% = 18 \% \)

7. Процент сжатия для кода Шеннона

Исходная длина сообщения: \( L_{исх} = 10000 \cdot log_2(8) = 10000 \cdot 3 = 30000 \)

Длина сжатого сообщения: \( L_{сжат} = 10000 \cdot L_{avg} = 10000 \cdot 2.95 = 29500 \)

Процент сжатия: \( Сжатие = \frac{L_{исх} - L_{сжат}}{L_{исх}} \cdot 100 \% = \frac{30000 - 29500}{30000} \cdot 100 \% = 1.67 \% \)