вторник, 23 октября 2012 г.

Ещё раз про однозначное декодирование

Введение

В последние годы в заданиях КИМ ЕГЭ по информатике, как в демо-версиях, так и в реальных вариантах, неизменно присутствует задача на кодирование данных следующего типа [1, задание А9]:

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А — 00, Б — 01, В — 100, Г — 101, Д — 110. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
1) для буквы Д — 11; 2) это невозможно; 3) для буквы Г — 10; 4) для буквы Д — 10

Как показывает практика, эта задача вызывает серьезные трудности не только у многих учеников, но даже у учителей информатики.

Нужно сказать, что этот материал практически не рассматривается в существующих школьных учебниках информатики, поэтому все (как ученики, так и учителя) вынуждены разбираться самостоятельно. В то же время вузовские учебники [2-5], где соответствующая теория изложена строго и научно, достаточно сложны для понимания. Попробуем разобраться в сути кодирования и декодирования на школьном уровне, то есть так, как можно объяснить ученикам 8-11 классов.

В чём проблема?

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

Пример 1. Пусть для кодирования фразы «МАМА МЫЛА ЛАМУ» выбран такой код:
МАЫЛУпробел (1)
0010101011
Коды букв «сцепляются» в одну битовую строку и передаются, например, по сети:
МАМА МЫЛА ЛАМУ → 0010011100010111010010
Эта цепочка битов приходит в пункт назначения, и тут возникает проблема — как восстановить исходное сообщение (конечно, при условии, что мы знаем код, то есть знаем все пары «символ–кодовое слово», которые использовались при кодировании).

Итак, мы получили 0010011100010111010010. Легко понять, что при использовании кода (1) раскодировать такое сообщение можно самыми разными способами. Например, можно предположить, что оно составлено только из букв А (код 1) и Л (код 0). Тогда получаем
ЛЛАЛЛАААЛЛЛАЛАААЛАЛЛАЛ
В общем, ни мамы, ни ламы.

Определение. Код называется однозначно декодируемым, если любое кодовое сообщение можно расшифровать единственным способом (однозначно).

Сказанное выше означает, что код (1) НЕ является однозначно декодируемым. Как же определить, является ли заданный код однозначно декодируемым? Этим вопросом мы и займемся.

Равномерные коды

Проблема состоит в том, чтобы правильно разбить полученную битовую цепочку на отдельные кодовые слова. Для того, чтобы её решить, можно, например, использовать равномерный код, то есть код, в котором все кодовые слова имеют одинаковую длину. Например, в нашей фразе 6 символов, поэтому можно использовать 3-битный код (который позволяет закодировать 8 = 23 различных символов).

Пример 2. Закодируем фразу из примера 1, используя код:
МАЫЛУпробел (2)
000001010011100101
Получаем закодированное сообщение
МАМА МЫЛА ЛАМУ → 000001000001101000010011001101011001000100
Длина этого сообщения — 42 бита вместо 22 в предыдущем варианте, зато его легко разбить на отдельные кодовые слова и раскодировать («_» обозначает пробел):
000 001 000 001 101 000 010 011 001 101 011 001 000 100
 М   А   М   А   _   М   Ы   Л   А   _   Л   А   М   У    
Видим, что равномерные коды неэкономичны (закодированное сообщение в примере 2 почти в два раза длиннее, чем в примере 1), но зато декодируются однозначно.

Неравномерные коды

Для того, чтобы сократить длину сообщения, можно попробовать применить неравномерный код, то есть код, в котором кодовые слова, соответствующие разным символам исходного алфавита, могут иметь разную длину.

Пример 3. Используем для кодирования фразы из примера 1 следующий код:
МАЫЛУпробел (3)
01001011100101011
Получаем
МАМА МЫЛА ЛАМУ → 0100010011011011100001110000011010
Здесь 34 бита. Это, конечно, не 22, но и не 42.

Несложно показать, что эта битовая цепочка декодируется однозначно. Действительно, первая буква — М (код 01), потому что ни одно другое кодовое слово не начинается с 01. Аналогично определяем, что вторая буква — А. Действительно, за 01 следует 00 (код буквы А) и никакое другое кодовое слово не начинается с 00. Это же свойство, которое называется условием Фано, выполняется не только для кодовых слов 01 и 00, но и кодовых слов всех других букв (проверьте это самостоятельно).

Условие Фано. Никакое кодовое слово не совпадает с началом другого кодового слова.

Коды, для которых выполняется условие Фано, называют префиксными (префикс слова — это его начальный фрагмент). Все сообщения, закодированные с помощью префиксных кодов, декодируются однозначно.
Префиксные коды имеют важное практическое значение — они позволяют декодировать символы полученного сообщение по мере его получения, не дожидаясь, пока всё сообщение будет доставлено получателю.

Упражнение. Расшифруйте сообщение, закодированное кодом (3). При расшифровке кода очередной буквы не заглядывайте вперёд!
1000001101011010001001101101110000 
Термины «условие Фано» и «префиксный код» не используются в заданиях ЕГЭ и ГИА, однако для решения этих задача важно, чтобы ученики понимали содержание условия Фано.

Пример 4. Рассмотрим ещё один код
МАЫЛУпробел (4)
10001101001010111
Ясно, что он не является префиксным: код буквы А (00) совпадает с началом кода буквы Л (001) и код пробела (11) совпадает с началом кода буквы Ы (11). Закодированное сообщение
МАМА МЫЛА ЛАМУ → 1000100011101101001001100100100101
также имеет длину 34 бита, как и при использовании кода (3). Начнем раскодировать с начала. Ясно, что первой стоит буква М, потому что ни один другой код не начинается с 10. Затем — комбинация 001, которая может быть кодом буквы Л или кодом буквы А (00), за которым следует код буквы Ы или пробела. Получается, что для декодирования сообщения нам нужно «заглядывать вперёд», что очень неудобно.

Попробуем декодировать с конца битовой строки. Последние биты 0101 могут представлять только букву У, следующие 10 — только букву М и т.д. Можно проверить, что теперь сообщение однозначно декодируется с конца! Это происходит потому, что выполняется условие, которое можно назвать «обратным» условием Фано: никакое кодовое слово не совпадает с окончанием другого кодового слова. Коды, для которых выполняется обратное условие Фано, называют постфиксными (постфикс или суффикс слова — это его конечный фрагмент). В этом случае тоже обеспечивается однозначное декодирование. Таким образом,

Сообщение декодируется однозначно, если для используемого кода выполняется прямое или обратное условие Фано.

Обратим внимание на то, что условие Фано (и обратное условие Фано) — это достаточное, но не необходимое условие однозначной декодируемости. Это значит, что
  • для однозначной декодируемости достаточно выполнение хотя бы одного из двух условий, или прямого, или обратного;
  • могут существовать коды, для которых не выполняется ни прямое, ни обратное условие Фано, но они, тем не менее, обеспечивают однозначное декодирование.
Наиболее интересен второй вывод, который сразу вызывает два вопроса: 1) что это за коды? и 2) как в общем случае установить, что код декодируется однозначно? Обсудим это в следующем разделе.

Однозначно декодируемые коды

Пример 5. Рассмотрим код, предназначенный для кодирования сообщений, состоящих только из букв А, Б и В:
АБВ (5)
011010
Так как код буквы А (0) совпадает как с началом, так и с концом кода буквы В (010), для этого кода не выполняются ни прямое, ни обратное условие Фано. Поэтому пока мы не можем с уверенностью сказать, декодируется ли он однозначно.

Закодируем сообщение
АББААВВА → 01111000100100
и попытаемся раскодировать эту строку, используя код (5). В первую очередь, замечаем, что две соседние единицы могут появиться только при использовании буквы Б (код 11), поэтому сразу выделяем две таких группы:
0ББ000100100
Здесь жёлтым фоном выделена уже декодированная часть сообщения. В оставшейся части единица может появиться только в коде буквы В (010), в битовой строке находим две такие группы:
0ББ00ВВ0
Оставшиеся нули — это коды букв А. Анализ алгоритма показывает, что такой код всегда однозначно декодируется.

Полный ответ на вопрос об однозначной декодируемости получил в начале 1960-х годов советский математик Ал.А. Марков, предложивший решение с помощью графов [2]. Продемонстрируем его метод на примере.

Пример 6. Рассмотрим код
АБВГД (6)
0101001111101
Здесь не выполняется ни «прямое», ни «обратное» условие Фано, поэтому возможно, что декодировать сообщение однозначно не удастся. Но утверждать это заранее нельзя.

Следуя методу Ал.А. Маркова, построим граф следующим образом:
  1. Определяем все последовательности (строки), которые
       а) совпадают с началом какого-то кодового слова и одновременно с концом какого-то кодового слова и
       б) сами не являются кодовыми словами.
    В данном случае это две последовательности:
       0 (начало кода буквы А и конец кода буквы Б) и
       1 (начало кода буквы Г и конец кода буквы Д);
       10 (начало кода буквы Д и конец кода буквы Б);
    последовательности 01 и 11 не учитываем, потому что они совпадают с кодами букв А и Г;
  2. Добавляем к этому множеству {0, 1, 10} пустую строку, которую обычно обозначают греческой буквой Λ; элементы полученного множества {Λ, 0, 1, 10} будут вершинами графа:
  3. Соединяем вершины дугами (направленными ребрами) по такому правилу: две вершины X и Y соединяются дугой, если последовательная запись кода вершины X, кода некоторой буквы (или нескольких букв) и кода вершины Y дает код ещё одной буквы:
    Надпись «W→Z» на дуге, ведущей из X в Y, означает, что если между словами X и Y вставить последовательность букв W (она может состоят из нескольких символов), то полученная цепочка кодов совпадёт с кодом буквы Z. Например, последовательная запись пустой строки (Λ), кода буквы А (01) и цепочки 0 дает цепочку 010 (код буквы Б); поэтому рисуем дугу из вершины «Λ» в вершину «0» и у этой дуги пишем «А→Б», и т.д. Поскольку код буквы Г можно записать как 11 = 1Λ1, у вершины «1» появляется петля «Λ→Г».
Результат Ал.А. Маркова состоит в следующем:

Код является однозначно декодируемым тогда и только тогда, когда в построенном таким образом графе нет ориентированных циклов, включающих вершину Λ.

Иначе говоря,
  1. если есть сообщение, которое декодируется неоднозначно, то в графе есть цикл, проходящий через вершину Λ;
  2. если в графе есть цикл, проходящий через вершину Λ, то можно построить сообщение, которое декодируется неоднозначно; для этого нужно, проходя по циклу, последовательно выписывать коды всех встречающихся вершин и дуг;
С сайта автора можно скачать программу на языке Python 3, которая строит граф Ал.А. Маркова, обнаруживает в нём циклы, проходящие через вершину Λ, и определяет соответствующие им кодовые последовательности, которые декодируются неоднозначно.

В нашем графе есть, по крайней мере, четыре таких цикла:
  1. цикл «Λ0Λ», соответствующий сообщению ΛА0ГΛ = 01011; это сообщение может быть расшифровано как АВ и как БГ;
  2. цикл «Λ1Λ», соответствующий сообщению ΛА1АΛ = 01101; это сообщение может быть расшифровано как АД и как ВА;
  3. цикл «Λ01Λ», соответствующий сообщению ΛА01АΛ = 010101; это сообщение может быть расшифровано как ААА и как БД;
  4. цикл «Λ0101Λ», соответствующий сообщению ΛА0101АΛ = 01010101; это сообщение может быть расшифровано как АБД и как БДА;
Кроме того, у вершины «1» есть петля, которая даёт более длинные циклы «из Λ в Λ». Действительно, проходя по стрелкам из вершины Λ, мы приходим в вершину 1, там «вертимся» какое-то количество раз, и возвращаемся обратно в вершину Λ, замыкая цикл. Поэтому неоднозначно декодируется любая последовательность вида 01…101, где многоточие обозначает любое количество единиц. Например, сообщение 0111101 может быть декодировано как АГД или ВГА.

Таким образом, код (6) не обладает свойством однозначной декодируемости.

Проверим таким же способом код (5), который, как мы уже выяснили, не является ни префиксным, ни постфиксным. Множество последовательностей, которые совпадают с началом и концом кодовых слов, состоит из пустой строки и единицы: {Λ, 1}. Граф, построенный с помощью приведённого выше алгоритма, содержит два узла и одну петлю:

В этом графе нет цикла, содержащего вершину Λ, поэтому любое сообщение, записанное с помощью такого кода, декодируется однозначно. Выше мы показали это с помощью простых рассуждений.

Нужно отметить, что на практике применяются, главным образом, префиксные коды, поскольку они позволяют декодировать сообщение по мере его получения, не дожидаясь окончания приёма данных.

Ещё примеры

Пример 7. Рассмотрим задачу А9 из демо-варианта КИМ ЕГЭ-2013 [1], которая сформулирована в начале статьи. Нужно оптимизировать код
А — 00, Б — 01, В — 100, Г — 101, Д — 110
выбрав один из вариантов
1) для буквы Д — 11    2) это невозможно
3) для буквы Г — 10    4) для буквы Д — 10
Решение. Сначала давайте посмотрим на исходный код, приведённый в условии. Можно заметить, что он префиксный — для него выполняется условие Фано: ни один из трехбитных кодов не начинается ни с 00 (код А), ни с 01 (код Б). Поэтому сообщения, закодированные с помощью такого кода, декодируются однозначно.

Заметим, что «обратное» условие Фано не выполняется: код буквы А (00) совпадает с окончанием кода буквы В (100), а код буквы Б (01) совпадает с окончанием кода буквы Г (101).

Теперь проверим, что получится, если сократить код буквы Д до 11 (вариант 1). Свойство однозначной декодируемости может быть потеряно только тогда, когда в результате такого сокращения нарушится условие Фано, то есть код буквы Д совпадёт с началом какого-то другого кодового слова. Видим, что этого не произошло — нет других кодовых слов, которые начинаются с 11, поэтому вариант 1 — это и есть верное решение.

Остается убедиться, что варианты 3 и 4 не подходят. Если мы сократим код буквы Г до 10 (вариант 3), условие Фано оказывается нарушенным, так как теперь код буквы Г (10) совпал с началом кода буквы В (100). Одновременно нарушено и «обратное» условие Фано: код буквы А (00) совпадает с окончанием кода буквы В (100). Но, как мы знаем, при этом код может всё-таки быть однозначно декодируемым.

Конечно, можно построить граф, как было сделано выше, и проверить, есть ли в нём циклы, включающие вершину Λ. В данном случае граф выглядит так:

Здесь два цикла, проходящих через вершину Λ (не считая петли у вершины 0):
  1. цикл, соответствующий сообщению ΛГ0Λ1АΛ = 100100; это сообщение может быть расшифровано как ГБА или как ВВ;
  2. цикл, соответствующий сообщению ΛГ0Λ1ГΛ = 100110; это сообщение может быть расшифровано как ГБГ или как ВД.
Таким образом, вариант 3 не обеспечивает однозначную декодируемость сообщений.

Построение и анализ графа — дело достаточно трудоемкое и требующее аккуратности. Обычно в таких случаях значительно легче просто подобрать последовательность, которая может быть декодирована двумя разными способами.

Наконец, нужно убедиться, что вариант 4 не удовлетворяет условию. Если мы сократим код буквы Д до 10, условие Фано оказывается нарушенным, так как теперь код буквы Д (10) совпал с началом кода буквы В (100). Как и раньше, нарушено «обратное» условие Фано: код буквы А (00) совпадает с окончанием кода буквы В (100) и код буквы Б (01) совпадает с окончанием кода буквы Г (101).

Построим граф по методу Ал.А. Маркова:

Здесь два цикла, проходящих через вершину Λ (не считая петли у вершины 0):
  1. цикл, соответствующий сообщению ΛД0Λ1АΛ = 100100; это сообщение может быть расшифровано как ДБА или как ВВ;
  2. цикл, соответствующий сообщению ΛД0Λ1БΛ = 100101; это сообщение может быть расшифровано как ДББ или как ВГ.
Таким образом, вариант 4 также не соответствует условию. Поэтому правильный ответ — 1.

Пример 8. Оптимизируйте код
А — 11, Б — 10, В — 011, Г — 000, Д — 001,
сохранив свойство однозначной декодируемости сообщений. Выберите один из вариантов:
1) для буквы Г — 00    2) это невозможно
3) для буквы В — 01    4) для буквы Б — 1
Решение. Определим, за счёт чего обеспечивается однозначная декодируемость исходного кода. Легко видеть, что код префиксный — для него выполняется условие Фано: ни одно из трёхбитовых кодовых слов не начинается ни с 11 (код А), ни с 10 (код Б). В то же время, обратное условие Фано не выполняется, потому что код буквы А (11) совпадает с окончанием кода буквы В (011).

Проверим вариант 1 — сократим код буквы Г до 00. При этом нарушилось условие Фано, которое обеспечивало однозначную декодируемость исходного варианта: теперь код буквы Г (00) совпадает с началом кода буквы Д (001). Но и обратное условие Фано тоже не выполняется для пары букв А-В. Поэтому можно предположить, что такой код не обладает свойством однозначной декодируемости. И действительно, легко находится цепочка 001011, которую можно раскодировать как ГБА (00 10 11) или ДВ (001 011).

Рассмотрим вариант 3 — сократим код буквы В до 01. При этом условие Фано выполняется, поскольку ни одно из кодовых слов не начинается с 01, то есть код является префиксным и однозначно раскодируется. Это и есть правильный ответ.

На всякий случай проверяем вариант 4 — сокращает код буквы Б до 1. При этом код перестает быть префиксным, и обратное условие Фано также не выполнено (код буквы Б совпадает с началом и концом кода буквы А). Сразу понятно, что последовательность 11 можно раскодировать как А или как ББ, поэтому этот вариант неверный.

Выводы

В заметке выполнен подробный анализ задачи на кодирование, которая предлагается на ЕГЭ в последние несколько лет. Нужно заметить, что в нём затрагивается вузовский курс дискретной математики. Понятно, что нельзя требовать от школьников знания теорем Ал.А. Маркова об однозначном декодировании, но учителю полезно более глубоко представлять себе эти вопросы, которые можно разбирать на факультативах. В качестве дополнительной литературы по этой теме можно рекомендовать [3-5].

С точки зрения практического подхода, для решения всех известных автору реальных задач подобного типа достаточно найти вариант, при котором выполняется условие Фано или обратное условие Фано (одно из двух!).

Литература

  1. Демонстрационный вариант контрольных измерительных материалов единого государственного экзамена 2013 года по информатике и ИКТ (проект).
  2. Ал.А. Марков, Введение в теорию кодирования. — М.: Наука, 1982.
  3. С.В. Яблонский, Введение в дискретную математику. — М.: Наука, 2000.
  4. Л.П. Жильцова. Современные проблемы теории кодирования. Учебно-методические материалы по программе повышения квалификации «Информационные технологии и компьютерное моделирование в прикладной математике». — Нижний Новгород: 2007.
  5. Л.П. Жильцова, Т.Г. Смирнова. Основы теории графов и теории кодирования в примерах и задачах: Учебное пособие. — Нижний Новгород: Издательство Нижегородского госуниверситета, 2008.
Автор благодарит М.А. Ройтберга за полезные замечания по материалу статьи и Л.Н. Евич за обсуждении вопросов однозначного декодирования на форуме egekp.unoforum.ru.


Ярлыки: , , ,

Комментарии: 16:

В 25 октября 2012 г. в 17:34 , Anonymous Анонимный сказал(а)...

Спасибо, что "на пальцах" объяснили еще раз!

 
В 31 октября 2012 г. в 22:51 , Anonymous Анонимный сказал(а)...

Действительно, спасибо. Очень понятно.

 
В 10 ноября 2012 г. в 17:45 , Anonymous Анонимный сказал(а)...

Просто великолепная статья!
Спасибо!

 
В 11 ноября 2012 г. в 18:58 , Anonymous Анонимный сказал(а)...

Уважаемый Константин! Бесконечно благодарна Вам за неоценимую помощь в подготовке детей к ЕГЭ по информатике.

 
В 29 мая 2013 г. в 16:53 , Anonymous Паша сказал(а)...

Спасибо), всё понятно)))

 
В 12 июня 2013 г. в 20:14 , Blogger Unknown сказал(а)...

Отличная статья! Спасибо!

 
В 12 января 2014 г. в 12:34 , Anonymous Анонимный сказал(а)...

Великолепно!

 
В 2 ноября 2014 г. в 21:56 , Anonymous Анонимный сказал(а)...

Отличная работа

 
В 17 сентября 2016 г. в 17:47 , Anonymous Тимофей сказал(а)...

Спасибо за статью. В учебнике информатики 10 класса Полякова содержится опечатка в последовательности построения графа Маркова, которая, при всей схожести текста, исправлена у вас. Порадовало также более ясное объяснение примеров.

 
В 18 сентября 2016 г. в 20:03 , Blogger КП сказал(а)...

> В учебнике информатики 10 класса Полякова содержится опечатка
Да, действительно была в первом издании. Сейчас исправлена.

 
В 24 мая 2017 г. в 21:28 , Anonymous mmmm1998 сказал(а)...

Программа, скачанная отсюда, на codeTable = {'A': '10', 'B': '01', 'C': '12', 'D': '012', 'E': '2100', 'F': '12011', 'G': '12010' } выдала следующий список вершин графа: ['Lambda', '0', '1'].
Но разве '2' не должна входит в список вершни, так как является началом 'E' и концом 'C' и не является кодовым словом?

 
В 25 мая 2017 г. в 09:51 , Blogger КП сказал(а)...

> Но разве '2' не должна входит в список вершин, так как является началом
> 'E' и концом 'C' и не является кодовым словом?
Программа предназначена только для обработки двоичных кодов.

 
В 20 октября 2017 г. в 22:28 , Anonymous Garry сказал(а)...

Ой, спасибо!

 
В 26 марта 2020 г. в 19:16 , Blogger Антон Куриленко сказал(а)...

А как можно доказать на пальцах, что из отсутствия данного граф-цикла следует однозначность декодируемости? А то зашел в учебник Маркова, а там просто жесть какая-то... Развитие моего ума не позволяет мне это изучить в разумные сроки.

 
В 26 марта 2020 г. в 20:45 , Blogger Антон Куриленко сказал(а)...

Последний граф для кода А — 00, Б — 01, В — 100, Г — 101, Д — 10 составлен не совсем точно.
Нужно еще из вершины Λ в вершину 1 провести дугу Д → Г.

 
В 26 марта 2020 г. в 21:23 , Blogger КП сказал(а)...

> Нужно еще из вершины Λ в вершину 1 провести дугу Д → Г.
Спасибо за замечание, вы правы. Исправлено.
По поводу доказательства "на пальцах" - тут сложно. В одну сторону очевидно: если цикл есть, то можно построить последовательность, которая не будет однозначно декодироваться. Поэтому отсутствие циклов необходимо. А вот простого доказательство достаточности я не знаю.

 

Отправить комментарий

Подпишитесь на каналы Комментарии к сообщению [Atom]

<< Главная страница