Как вы думаете, что такое информация? Происходит обсуждение вариантов ответов учеников.
Информация – это сведения, уменьшающие неопределённость нашего знания об окружающем нас мире.
А в каком виде можно представить ту или иную информацию? Происходит обсуждение вариантов ответов учеников в ходе которого необходимо их подвести к тому что даже простой осмысленный текст это код.
Код – система условных знаков для представления информации. Коды бывают равномерными и неравномерными.
Кодирование – это операция преобразования символов или группы символов одного кода в символы или группы символов другого кода.
Декодирование – процесс, обратный кодированию.
Длина кода – количество знаков в коде.
Код является равномерным, если все кодовые слова имеют одну длину (содержат одинаковое число двоичных символов). В противном случае код называется неравномерным.
В равномерных кодах не требуется специальных знаков, отделяющих кодовые слова друг от друга. При использовании неравномерных кодов встает задача однозначного декодирования. Неравномерный код является однозначно декодируемым, если ни одно более короткое кодовое слово не является началом другого более длинного кодового слова. Такой код называется префиксным.
Любой код, кодовые слова которого соответствуют различным вершинам дерева, является однозначно декодируемым, то есть префиксным. Если кодовые слова соответствуют некоторым промежуточным узлам, код не обладает свойством префиксности.
Пусть исходный алфавит включает 9 символов: А, Л, М, О, П, Р, У, Ы, -. Кодовый алфавит – двоичный. Кодовые слова:
А: 00
М: 01
-: 100
Л: 101
У: 1100
Ы: 1101
Р: 1110
О: 11110
П: 11111
Рассмотрим закодированный текст, полученный с помощью вышеуказанного кода.
0100010010001110110100100111000011100
Будем его декодировать таким способом. Двигаемся слева направо, пока не обнаружим код какой-то буквы. 0 – не кодовое слово, а 01 – код буквы М.
0100010010001110110100100111000011100
Значит, исходный текст начинается с буквы М: код никакой другой буквы не начинается с 01! «Отложим» начальные 01 в сторону и продолжим.
01 00010010001110110100100111000011100
М
Далее таким же образом находим следующее кодовое слово 00 – код буквы А.
01 00010010001110110100100111000011100
М А
Доведите расшифровку текста до конца самостоятельно. Убедитесь, что он расшифровывается (декодируется) однозначно.
Замечание. В расшифрованном тексте 14 букв. Т.к. в алфавите 9 букв, то при равномерном двоичном кодировании пришлось бы использовать кодовые слова длины 4. Таким образом, при равномерном кодировании закодированный текст имел бы длину 56 символов – в полтора раза больше, чем в нашем примере (у нас 37 символов).
Равномерное кодирование – это кодирование, при котором каждый элементарный код имеет одинаковую длину.
Например, если выбрать в качестве алфавита В цифры, то одноразрядным кодом можно закодировать 10 символов, а двухразрядными числами – 100.
Пусть алфавит В содержит к букв, а длина элементарного кода n букв. Сколько символов (m) при равномерном кодировании можно закодировать?
Элементарные коды – это кортежи из n букв, взятых из данных к, поэтому они являются размещениями с повторениями. По известной формуле их число равно.
m = кn (1)
Поставим обратную задачу. Имеется m букв алфавита А. Сколько букв должны содержать элементарные коды при равномерном кодировании?
Из формулы (1), логарифмируя, получим:
n = log к m(2)
Если же алфавит В={0,1} – двоичный, то закодировать n – битным кодом можно в силу формулы (1) имеем букв:
m = 2 n (3)
Пусть имеется алфавит А, состоящий из m символов. Сколько бит должен содержать каждый элементарный код при равномерном кодировании?
Из формулы (2) получим, если m – степень 2,
n = log 2m(4)
Если m – не степень 2, то по формуле:
n= logm | + 1 (5)
где |logm | - целая часть logm..
Решение задач по теме
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–00, Б–010, В–011, Г–101, Д–111. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
1) для буквы Б – 01 2) это невозможно
3) для буквы В – 01 4) для буквы Г – 01
Решение (1 способ, проверка условий Фано):
1. Для однозначного декодирования достаточно, чтобы выполнялось условие Фано или обратное условие Фано;
2. Проверяем последовательно варианты 1, 3 и 4; если ни один из них не подойдет, придется выбрать вариант 2 («это невозможно»);
3. Проверяем вариант 1: А–00, Б–01, В–011, Г–101, Д–111. «прямое» условие Фано не выполняется (код буквы Б совпадает с началом кода буквы В); «обратное» условие Фано не выполняется (код буквы Б совпадает с окончанием кода буквы Г); поэтому этот вариант не подходит;
4. Проверяем вариант 3: А–00, Б–010, В–01, Г–101, Д–111. «прямое» условие Фано не выполняется (код буквы В совпадает с началом кода буквы Б); «обратное» условие Фано не выполняется (код буквы В совпадает с окончанием кода буквы Г); поэтому этот вариант не подходит;
5. Проверяем вариант 4: А–00, Б–010, В–011, Г–01, Д–111. «прямое» условие Фано не выполняется (код буквы Г совпадает с началом кодов букв Б и В); но «обратное» условие Фано выполняется (код буквы Г не совпадает с окончанием кодов остальных буквы); поэтому этот вариант подходит;
6. Правильный ответ – 4.
Решение (2 способ, дерево):
1. Построим двоичное дерево, в котором от каждого узла отходит две ветки, соответствующие выбору следующей цифры кода – 0 или 1; разместим на этом дереве буквы А, Б, В, Г и Д так, чтобы их код получался как последовательность чисел на рёбрах, составляющих путь от корня до данной буквы (красным цветом выделен код буквы В – 011):
2. Здесь однозначность декодирования получается за счёт того, что при движении от корня к любой букве в середине пути не встречается других букв (выполняется условие Фано);
3. Теперь проверим варианты ответа: предлагается перенести одну из букв, Б, В или Г, в узел с кодом 01, выделенный синим цветом;
4. Видим, что при переносе любой из этих букв нарушится условие Фано; например, при переносе буквы Б в синий узел она оказывается на пути от корня до В, и т.д.; это значит, что предлагаемые варианты не позволяют выполнить прямое условие Фано;
5. Хочется уже выбрать вариант 2 («это невозможно»), но у нас есть еще обратное условие Фано, для которого тоже можно построить аналогичное дерево, в котором движение от корня к букве дает её код с конца (красным цветом выделен код буквы В – 011, записанный с конца:
видно, что обратное условие Фано также выполняется, потому что на пути от корня к любой букве нет других букв
6. В заданных вариантах ответа предлагается переместить букву Б, В или Г в синий узел; понятно, что Б или В туда перемещать нельзя – перемещённая буква отказывается на пути от корня к букве Г; а вот букву Г переместить можно, при этом обратное условие Фано сохранится;
7. Правильный ответ – 4.
