DVBogdanov.ru / Тренировочный вариант по информатике, задание 5

Задание №1701/05

Задание

По каналу связи передаются сообщения, содержащие только буквы из набора \(\left\{ \gamma,\vartheta,\xi,\chi,\omega\right\}\). Вероятности появления каждой буквы приведены в таблице.

Буква\(\gamma\)\(\vartheta\)\(\xi\)\(\chi\)\(\omega\)
Вероятность0,50,250,120,120,01

Для букв \(\gamma\), \(\omega\) используются следующие кодовые слова: \(\gamma-0\) и \(\omega-10\). Укажите кратчайшее кодовое слово для буквы \(\xi\), при котором код будет иметь минимальную длину и допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение

Для решения задачи воспользуемся алгоритмом Шеннона-Фано. Кодовые слова \(\gamma-0\) и \(\omega-10\) будем считать запрещёнными и не использовать в алгоритме. Таким образом, кратчайшим разрешённым кодовым словом является слово 11.

Оставшиеся символы \(\vartheta\), \(\xi\) и \(\chi\) имеют вероятности 0,25, 0,12 и 0,12 соответственно. Эти символы необходимо разделить на две группы таким образом, чтобы суммарные вероятности входящих в группы символов были максимально близки друг к другу. Если в первую группу выделить символ \(\vartheta\), а во вторую — \(\xi\) и \(\chi\), то суммарные вероятности символов первой и второй группы будут соответственно равны 0,25 и 0,12 + 0,12 = 0,24. В этом случае символ \(\vartheta\) получит кодовое слово 110, а кодовые слова символов второй группы будут начинаться на 111.

Но по условию задачи код для буквы \(\xi\) должен иметь наименьшее числовое значение, поэтому символу \(\vartheta\) лучше назначить код 111, а префикс 110 присвоить кодовым словам для символов \(\xi\) и \(\chi\). Стоит отметить, что после подобного обмена код останется префиксным и оптимальным по суммарной длине кодовых слов.

Повторяя шаги алгоритма, необходимо поделить на две группы оставшиеся символы \(\xi\) и \(\chi\). Очевидно, что в каждую из групп войдёт ровно один символ. Учитывая, что кодовое слово для \(\xi\) должно иметь минимальное числовое значение, из двух возможных кодовых слов 1100 и 1101 выберем первое.

Кодовое дерево
Рис. 1. Кодовое дерево

По построеному кодовому дереву (рисунок 1) легко убедиться, что полученный код является префиксным (все кодовые слова являются листьями этого дерева) и, следовательно, обладает свойством однозначного декодирования.

Подробнее...

Замечание

Важно отметить, что использование алгоритма Шеннона-Фано не гарантирует оптимальность кода по суммарной длине кодовых слов, хотя во многих случаях (в том числе, в данной задаче) получаемый код совпадает с оптимальным. Для вычисления оптимальных кодов можно использовать алгоритм Хаффмана.

Подробнее...

Ответ

1100

Подробнее...
Добавить комментарий
Комментарии (3)
#Задачи на кодирование информации #Кодирование текста #Метод Хаффмана #Метод Шеннона-Фано #Неравномерное кодирование #Определение количества информации #Подготовка к ЕГЭ по информатике