дисциплина «Теоретические основы информатики» Задача 1 Текст закодирован восьмеричными числами. Подсчитали частоты всех 8 цифр и их вероятности (для этого нужно найти число повторений цифры в тексте и разделить на общее число цифр). Построить неравномерные коды Хафмена и Шеннона и определить среднюю длину кодов и % сжатия сообщения закодированного в 8 системе счисления при заданной статистике в среднем на 10000 цифр.

Ответ: Необходимо подсчитать частоты восьмеричных цифр в тексте, найти их вероятности, построить коды Хаффмена и Шеннона, определить среднюю длину кодов и процент сжатия сообщения.

Пошаговое решение:

1. Шаг 1: Анализ текста и подсчет частот цифр

   • Проанализируйте заданный текст, закодированный восьмеричными числами.
   • Подсчитайте, сколько раз встречается каждая из 8 цифр (0, 1, 2, 3, 4, 5, 6, 7) в тексте.

2. Шаг 2: Определение вероятностей цифр

   • Разделите число повторений каждой цифры на общее число цифр в тексте (10000) для определения вероятности каждой цифры.
   • Формула для вероятности: \[ P(цифра) = \frac{Число\ повторений\ цифры}{Общее\ число\ цифр} \]

3. Шаг 3: Построение кода Хаффмена

   • Используйте алгоритм Хаффмена для построения неравномерного кода:
   • Создайте узлы для каждой цифры, вес каждого узла равен вероятности цифры.
   • Объединяйте узлы с наименьшими весами, пока не останется один узел.
   • Присвойте 0 и 1 ветвям дерева.

4. Шаг 4: Построение кода Шеннона

   • Используйте алгоритм Шеннона для построения неравномерного кода:
   • Расположите цифры в порядке убывания вероятностей.
   • Разделите список на две части так, чтобы суммы вероятностей частей были примерно равны.
   • Присвойте первой части код 0, второй части код 1.
   • Рекурсивно повторите процесс для каждой части.

5. Шаг 5: Определение средней длины кодов

   • Определите длину кода для каждой цифры в кодах Хаффмена и Шеннона.
   • Вычислите среднюю длину кода для каждого алгоритма:
   • Формула для средней длины: \[ L_{средняя} = \sum_{i=1}^{8} P(цифра_i) \cdot Длина(код_i) \]

6. Шаг 6: Определение процента сжатия сообщения

   • Определите длину исходного сообщения (в восьмеричной системе каждая цифра требует 3 бита).
   • Вычислите длину сжатого сообщения, используя коды Хаффмена и Шеннона.
   • Определите процент сжатия:
   • Формула для процента сжатия: \[ Сжатие = \frac{Длина_{исходная} - Длина_{сжатая}}{Длина_{исходная}} \cdot 100\% \]

Ответ: Необходимо подсчитать частоты восьмеричных цифр в тексте, найти их вероятности, построить коды Хаффмена и Шеннона, определить среднюю длину кодов и процент сжатия сообщения.