Как составить дерево фано

Привет! Сегодня узнаем, как решать 4 задание из ЕГЭ по информатике нового формата 2021.

Четвёртое задание из ЕГЭ по информатике раскрывает тему кодирование информации. Одним из центральных приёмов при решении задач подобного типа является построение дерева Фано. Рассмотрим на примерах этот метод.

Задача (стандартная)

По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А — 11, B — 101, C — 0. Укажите кодовое слово наименьшей возможной длины, которое можно использовать для буквы F. Если таких слов несколько, укажите то из них, которое соответствует наименьшему возможному двоичному числу.

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование

Решение:

Т.к. код букв должен удовлетворять условию Фано (т.е. однозначно декодироваться), то
расположим буквы, которые уже имеют код (A, B, C), на Дереве Фано.

Дерево Фано для двоичного кодирования начинается с двух направлений, которые означают 0(ноль) и 1(единицу) (цифры двоичного кодирования).

От каждого направления можно также рисовать только два направления: 0(ноль) и 1(единицу) и т.д. Для удобства будем рисовать 1(единицу) только вправо, а 0(ноль) только влево.

Получается структура похожая на дерево!

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

Такой подход позволяет однозначно декодировать сообщение, состоящее из этих букв.

Буква C заблокировала левую ветку, поэтому будем работать с правой частью нашего дерева.

Если мы расположим какую-нибудь букву на оставшуюся ветку (100), то эта ветка заблокируется, и нам некуда будет писать остальные 2 буквы. Поэтому продолжаем ветку (100) дальше.

Теперь свободно уже две ветки, а нам нужно закодировать ещё три буквы. Поэтому должны ещё раз продолжить дерево от какой-нибудь ветки.

Но уже видно, что букве F будет правильно присвоить код 1000, т.к. нам в условии сказано, что код буквы F должен соответствовать наименьшему возможному двоичному числу. Как расположить буквы D и E в данной задаче не принципиально.

Ответ: 1000.

Ещё один важный тип задания 4 из ЕГЭ по информатике нового формата 2021.

Задача (стандартная)

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, И, К, Л, С, Ц. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б — 00, К — 010, Л — 111. Какое наименьшее количество двоичных знаков потребуется для кодирования слова АБСЦИССА?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Решение:

Коды букв должны удовлетворять условию Фано. Некоторые буквы уже имеют заданные коды (Б, К, Л). Нам нужно, чтобы слово АБСЦИССА имело как можно меньше двоичных знаков. Заметим, что буква C встречается три раза, а буква A два раза, значит, этим буквам стараемся присвоить как можно меньшую длину!

Отметим на дереве Фано уже известные буквы (Б, К, Л).

У нас осталось 4 (четыре) буквы, а свободных веток 3(три), поэтому мы должны продолжить дерево. но какую ветку продолжить ?

1 вариант

Если продолжить линию 1-0, то получится такая картина :

Теперь получились 4(четыре) свободные ветки равной длины (3(трём) двоичным символам). Т.к. ветки равной длины, то не важно на какую ветку какую букву расположим.

Посчитаем общую длину слова АБСЦИССА.

3 + 2 + 3 + 3 + 3 + 3 + 3 + 3 = 23.

2 вариант

С мы присваиваем 1-0, т.к. это буква повторяется в сообщении самое большое количество раз, значит, ей присваиваем самый маленький код, чтобы всё сообщение имело наименьшую длину.

Из этих же соображений букве А присваиваем код из трёх двоичных символов 0-1-1.

Подсчитаем общее количество символов в сообщении.

3 + 2 + 2 + 4 + 4 + 2 + 2 + 3 = 22

Длина получилась меньше, чем в первом варианте. Других вариантов нет, поэтому ответ будет 22.

Ответ: 22.

Задача (не сложная)

Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А-10, Б-11, В-110, Г-0. Через канал связи передаётся сообщение: ВАГБААГВ. Закодируйте сообщение данным кодом. Полученное двоичное число переведите в восьмеричный вид.

Решение:

В этой задаче ничего не сказано про условие Фано. Здесь уже все буквы закодированы, осталось написать сам код.

Задача сводится к переводу из двоичной системы в восьмеричную систему. На эту тему был урок на моём сайте.

Ответ: 151646.

На этом всё! Увидимся на следующих занятиях по подготовке к ЕГЭ по информатике.

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

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

Декодирование – процесс обратный кодированию, т.е. расшифровка кодов.

Кодирование информации может быть равномерным и неравномерным.

При равномерном кодировании каждому символу соответствует код одинаковой длины.

При неравномерном кодировании различным символам могут соответствовать коды различной длины.

Условие Фано

Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова.

Например пара кодовых слов 10 и 101 не выполняют условие Фано, потому что 101 является началом 10. А вот 100 и 101 уже выполняют условие Фано.

В конце статьи мы разберем задание в котором нужно найти кодовое слово для буквы удовлетворяющее условию Фано. На примере часто бывает проще разобраться!

Код который удовлетворяет условию Фано, называется префиксным. Префиксный код однозначно декодируется с начала.

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

Бинарное дерево на рисунке построено до значений из таблицы триад, можно продолжить строить дерево, но принцип я думаю понятен.

Для кодирования некоторой последовательности, состоящей из букв У, К, Е, Н, Г решили использовать неравномерный двоичный код удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для букв У, К, Е использовали соответственно кодовые слова 00, 010, 11. Для двух оставшихся букв – Н и Г – кодовые слова не известны.

Укажите кратчайшее возможное кодовое слово для буквы Н, при котором код будет удовлетворять указанному условию. Если таких кодов несколько, то укажите код с наименьшим числовым значением.

В тех местах где мы находим кодовые слова букв которые нам уже известны, ветка дерева обрывается. Если мы продолжим ее строить, то коды которые будем получать дальше не будут удовлетворять условию Фано.

Если вы уже знакомились с Разбором демоверсии 2021 и делали это внимательно, то вы заметите, что данная задача очень похожа на №4. Я вам предлагаю решить четвертый номер из демоверсии, будьте внимательны, там есть подвох!

Задание №4 по информатике. Демоверсия ЕГЭ. Разбор.

А свои ответы и разборы можете писать в комментариях. И не забывайте подписываться, чтобы не пропустить новые статьи!

Алгоритм вычисления кодов Шеннона-Фано

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

Далее каждое из этих подмножеств разбивается на два подмножества с примерно одинаковыми суммарными вероятностями. Им соответствуют вершины третьего уровня. Если подмножество содержит единственный элемент, то ему соответствует концевая вершина кодового дерева; такое подмножество разбиению не подлежит. Подобным образом поступаем до тех пор, пока не получим все концевые вершины. Ветви кодового дерева размечаем символами 1 и 0, как в случае кода Хаффмана.

При построении кода Шеннона-Фано разбиение множества элементов может быть произведено, вообще говоря, несколькими способами. Выбор разбиения на уровне n может ухудшить варианты разбиения на следующем уровне (n + 1) и привести к неоптимальности кода в целом. Другими словами, оптимальное поведение на каждом шаге пути ещё не гарантирует оптимальности всей совокупности действий.

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

Пример кодового дерева

Исходные символы:

A (частота встречаемости 50)

B (частота встречаемости 39)

C (частота встречаемости 18)

D (частота встречаемости 49)

E (частота встречаемости 35)

F (частота встречаемости 24)

Полученный код: A — 11, B — 101, C — 100, D — 00, E — 011, F — 010.

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

Пример 1. Закодируем буквы алфавита в коде Шеннона-Фано.

Пусть имеется случайная величина X (x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈), имеющая восемь состояний с распределением вероятностей

Для кодирования алфавита из восьми букв без учета вероятностей равномерным двоичным кодом нам понадобятся три символа:

Это 000, 001, 010, 011, 100, 101, 110, 111

Чтобы ответить, хорош этот код или нет, необходимо сравнить его с оптимальным значением, то есть определить энтропию

Определив избыточность L по формуле L=1-H/H₀=1-2,75/3=0,084, видим, что возможно сокращение длины кода на 8,4%.

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

X	P	Коды
x1	1/4	——-	——-
x2	1/4	——-	——-
x3,	1/8	——-
x4	1/8	——-
x5	1/16
x6	1/16
x7	1/16
x8	1/16

Средняя длина полученного кода будет равна

Итак, мы получили оптимальный код. Длина этого кода совпала с энтропией. Данный код оказался удачным, так как величины вероятностей точно делились на равновероятные группы.

Возьмем 32 две буквы русского алфавита. Частоты этих букв известны. В алфавит включен и пробел, частота которого составляет 0,145. Метод кодирования представлен в таблице

Буква	Рi	Код
?	0.145	—
о	0.095	—
е	0.074
а	0.064
и	0.064
н	0.056
т	0.056	…	…	—
с	0.047	…	…
.	…
ф	0.03

Средняя длина данного кода будет равна, бит/букву;

Энтропия H=4.42 бит/буква. Эффективность полученного кода можно определить как отношение энтропии к средней длине кода. Она равна 0,994. При значении равном единице код является оптимальным. Если бы мы кодировали кодом равномерной длины , то эффективность была бы значительно ниже.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

Источник

ЕГЭ по информатике 2021 — Задание 4 (Условие Фано)

Привет! Сегодня узнаем, как решать 4 задание из ЕГЭ по информатике нового формата 2021.

Четвёртое задание из ЕГЭ по информатике раскрывает тему кодирование информации. Одним из центральных приёмов при решении задач подобного типа является построение дерева Фано. Рассмотрим на примерах этот метод.

По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А — 11, B — 101, C — 0. Укажите кодовое слово наименьшей возможной длины, которое можно использовать для буквы F. Если таких слов несколько, укажите то из них, которое соответствует наименьшему возможному двоичному числу.

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование

Т.к. код букв должен удовлетворять условию Фано (т.е. однозначно декодироваться), то расположим буквы, которые уже имеют код (A, B, C), на Дереве Фано.

Дерево Фано для двоичного кодирования начинается с двух направлений, которые означают 0(ноль) и 1(единицу) (цифры двоичного кодирования).

От каждого направления можно также рисовать только два направления: 0(ноль) и 1(единицу) и т.д. Для удобства будем рисовать 1(единицу) только вправо, а 0(ноль) только влево.

Получается структура похожая на дерево!

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

Такой подход позволяет однозначно декодировать сообщение, состоящее из этих букв.

Буква C заблокировала левую ветку, поэтому будем работать с правой частью нашего дерева.

Если мы расположим какую-нибудь букву на оставшуюся ветку (100), то эта ветка заблокируется, и нам некуда будет писать остальные 2 буквы. Поэтому продолжаем ветку (100) дальше.

Теперь свободно уже две ветки, а нам нужно закодировать ещё три буквы. Поэтому должны ещё раз продолжить дерево от какой-нибудь ветки.

Но уже видно, что букве F будет правильно присвоить код 1000, т.к. нам в условии сказано, что код буквы F должен соответствовать наименьшему возможному двоичному числу. Как расположить буквы D и E в данной задаче не принципиально.

Ещё один важный тип задания 4 из ЕГЭ по информатике нового формата 2021.

По каналу связи передаются сообщения, содержащие только семь букв: А, Б, И, К, Л, С, Ц. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б — 00, К — 010, Л — 111. Какое наименьшее количество двоичных знаков потребуется для кодирования слова АБСЦИССА?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Коды букв должны удовлетворять условию Фано. Некоторые буквы уже имеют заданные коды (Б, К, Л). Нам нужно, чтобы слово АБСЦИССА имело как можно меньше двоичных знаков. Заметим, что буква C встречается три раза, а буква A два раза, значит, этим буквам стараемся присвоить как можно меньшую длину!

Отметим на дереве Фано уже известные буквы (Б, К, Л).

У нас осталось 4 (четыре) буквы, а свободных веток 3(три), поэтому мы должны продолжить дерево. но какую ветку продолжить ?

Если продолжить линию 1-0, то получится такая картина :

Теперь получились 4(четыре) свободные ветки равной длины (3(трём) двоичным символам). Т.к. ветки равной длины, то не важно на какую ветку какую букву расположим.

Посчитаем общую длину слова АБСЦИССА.

3 + 2 + 3 + 3 + 3 + 3 + 3 + 3 = 23.

Продлим линию 1-1-0 (можно и 0-1-1, не принципиально, т.к. эти ветки имеют одинаковую длину.), то получится:

С мы присваиваем 1-0, т.к. это буква повторяется в сообщении самое большое количество раз, значит, ей присваиваем самый маленький код, чтобы всё сообщение имело наименьшую длину.

Из этих же соображений букве А присваиваем код из трёх двоичных символов 0-1-1.

Подсчитаем общее количество символов в сообщении.

3 + 2 + 2 + 4 + 4 + 2 + 2 + 3 = 22

Длина получилась меньше, чем в первом варианте. Других вариантов нет, поэтому ответ будет 22.

Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г, используется неравномерный (по длине) код: А-10, Б-11, В-110, Г-0. Через канал связи передаётся сообщение: ВАГБААГВ. Закодируйте сообщение данным кодом. Полученное двоичное число переведите в восьмеричный вид.

В этой задаче ничего не сказано про условие Фано. Здесь уже все буквы закодированы, осталось написать сам код.

Задача сводится к переводу из двоичной системы в восьмеричную систему. На эту тему был урок на моём сайте.

На этом всё! Увидимся на следующих занятиях по подготовке к ЕГЭ по информатике.

Источник

Алгоритм Шеннона-Фано

Алгоритм метода Шеннона-Фано — один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано, и он имеет большое сходство с алгоритмом Хаффмана. Алгоритм основан на частоте повторения. Так, часто встречающийся символ кодируется кодом меньшей длины, а редко встречающийся — кодом большей длины.
В свою очередь, коды, полученные при кодировании, префиксные. Это и позволяет однозначно декодировать любую последовательность кодовых слов. Но все это вступление.

Для работы оба алгоритма должны иметь таблицу частот элементов алфавита.

Итак, алгоритм Хаффмана работает следующим образом:

1. На вход приходят упорядоченные по невозрастанию частот данные.
2. Выбираются две наименьших по частоте буквы алфавита, и создается родитель (сумма двух частот этих «листков»).
3. Потомки удаляются и вместо них записывается родитель, «ветви» родителя нумеруются: левой ветви ставится в соответствие «1», правой «0».
4. Шаг два повторяется до тех пор, пока не будет найден главный родитель — «корень».

Алгоритм Шеннона-Фано работает следующим образом:

1. На вход приходят упорядоченные по невозрастанию частот данные.
2. Находится середина, которая делит алфавит примерно на две части. Эти части (суммы частот алфавита) примерно равны. Для левой части присваивается «1», для правой «0», таким образом мы получим листья дерева
3. Шаг 2 повторяется до тех пор, пока мы не получим единственный элемент последовательности, т.е. листок

Таким образом, видно, что алгоритм Хаффмана как бы движется от листьев к корню, а алгоритм Шеннона-Фано, используя деление, движется от корня к листям.

Ну вот, быстро осмыслив информацию, можно написать код алгоритма Шеннона-Фано на паскале. Попросили именно на нем написать. Поэтому приведу листинг вместе с комментариями.

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

Источник

На этой странице вы узнаете

• Как закодировать сообщение “КУРЛЫК” правильно?
• Что такое равномерное кодирование?
• Так как кодировать сообщения максимально эффективно?

Понятие однозначного декодирования

Вы любите шпионов? А готовы почувствовать себя в их шкуре?

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

Главное — чтобы расшифровать было возможно.

Мы уже знаем, что для компьютера информацию надо представить в двоичномкоде — подробнее об этом рассказано в статье «Основные понятия об информации». Но сам процесс кодирования информации — не такая простая вещь. Есть несколько факторов, которые нужно соблюсти, чтобы кодирование прошло хорошо.

Но чтобы научиться делать что-то правильно, сначала надо разобраться, как сделать неправильно. Давайте попробуем произвольным образом закодировать буквы К, У, Р, Л, Ы, чтобы составлять из них сообщения.

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

С помощью кодовых слов каждой отдельной буквы закодируем сообщение КУРЛЫК, для этого на место каждой буквы будем подставлять соответствующее ей кодовое слово:

С проблемой мы столкнемся при попытке расшифровать сообщение. Чтобы это сделать, надо выделить в коде сообщения отдельные кодовые слова и подставить на их место соответствующие буквы. Но при расшифровке этого кода можно получить другой вариант:

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

Но как можно соблюдать это условие? Или еще круче — как строить кодовые слова, которые заранее будут этому условию удовлетворять?

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

Кодируем сообщение КУРЛЫК:

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

Такой метод действительно прост и в освоении, и при составлении кодовых слов, и при расшифровке. Но есть один минус — он не всегда эффективен.

Выбирая длину одного кодового слова, мы можем заранее определить количество возможных кодов: так как на каждой позиции может быть либо 0, либо 1, количество возможных кодов N длины i будет равно

(N = 2^i).

Выбрав длину 3 для наших кодовых слов, мы имеем 8 различных кодов, хотя кодируем всего 5 букв.

В других ситуациях потери могут быть плачевнее: для кодирования, например, 33 букв русского алфавита длина кодового слова должна быть не меньше 6 (если выберем 5, получим максимум 2⁵ = 32 кодового слова, но тогда 1 буква останется незакодированной).

Но имея 2⁶ = 64 кодовых слова для 33-х букв алфавита, мы явно взяли кодов больше, чем нужно.

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

Естественно, равномерное кодирование — все еще возможный вариант, при котором код будет однозначно декодируемым, но нет ли более рационального подхода?

Условие Фано и дерево вариантов

Условие Фано гласит: «ни одно кодовое слово не должно быть началом другого кодового слова».

В составленных нами в самом начале статьи кодовых словах это условие нарушалось — код буквы К (010) начинался с кода буквы У (01), а код Ы (001) — с кода Р (00). Из-за этого мы не могли быть точно уверены, где закончилось кодовое слово, а где оно продолжается.

Очень просто строить код, который будет удовлетворять условию Фано, с помощью дерева вариантов — структуры, в нашем случае помогающей получить кодовые слова максимально просто и понятно. Принцип работы дерева состоит в том, что в его узлах будут находиться кодовые слова, а из узла могут выходить два ребра, соответствующие добавлению в конец кодового слова 0 и 1, таким образом заменяя одно кодовое слово на два новых, которые длиннее на один символ.

Давайте попробуем таким образом получить ровно 5 кодовых слов, чтобы закодировать наши буквы К, У, Р, Л, Ы.

1. Первые два кодовых слова, которые мы можем получить из ничего — 0 и 1.
   Чтобы продолжить построение дерева, выбираем любой из конечных узлов и также добавляем ему 0 и 1 в конец.

1. Допустим, мы добавим 0 и 1 к кодовому слову 1, и вместо него теперь получим два новых — 10 и 11. Теперь кодовых слов у нас уже три — 0, 10 и 11.
   Все еще мало, продолжаем построение дерева.

1. Мы проделали ту же операцию с кодовым словом 0, заменив его на 2 новых — 00 и 01.
   Кодовых слов стало 4, этого все еще мало, нужно продолжить построение дерева.

1.  Из конечных узлов можно выбрать любой для продолжения построения, например — 01, продолжив это кодовое слово, получаем два новых — 010 и 011.

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

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

Так, код 010110010011010 мы можем однозначно декодировать, читая его слева направо:

И код 010110001110010 будет читаться уже в другую сторону – из конца в начало:

Практика

В жизни чаще всего используются равномерные кодировки в силу многих причин, таких как:

1. Большая устойчивость. 

Представим, что мы передаем слово КУРЛЫК разными вариантами, но при передаче допускаем ошибку в четвертом бите (в четвертом символе нашего кода). Посмотрим, что получится в итоге.

Выводы: 

• В первом случае из-за одного неправильного бита сломалась половина символов текста, и даже поменялось количество этих символов.
• Во втором случае текст отличается от первоначального только тем символом, на который влиял сломанный бит.

Таким образом, мы видим большую устойчивость равномерного кодирования.

2. Простота расширения. 

Мы обсуждали, что проблема равномерного кодирования — в большом количестве «пустых мест». Но эти пустые места могут быть полезны. Например, захочет разработчик добавить в код несколько новых эмодзи. У него как раз есть незанятые коды для этих символов. Согласитесь, это удобнее, чем переписывать всю кодировку целиком. 

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

Также применение неравномерной кодировки есть в 4 задаче ЕГЭ и во 2 задаче ОГЭ.

Разберем задачу №4 ЕГЭ:

По каналу связи передаются закодированные сообщения о состоянии системы, состоящие из пяти символов: A, B, C, D, E. При передаче сообщений используется двоичный код, при этом он допускает однозначное декодирование. Для символов A, B, C используются эти кодовые слова: 1, 010 и 001 (соответственно).

В ответе нужно указать наименьшее по длине кодовое слово для буквы D. Если таких кодов несколько, то в ответе укажите наименьший по значению.

Решение.

Шаг 1. Построим дерево вариантов кодовых слов и отметим на нем уже известные коды букв:

Шаг 2. Заметим, что раз для символа A кодовое слово 1, то в дальнейшем нам не подойдут любые коды, начинающиеся с 1, так как для них и символа A не будет выполняться условие однозначного декодирования.

Шаг 3. Начнем разбирать по возрастанию кодовые слова, начинающиеся с 0:

• 0 — не подойдет, будет началом для кодовых слов 001 и 010.
• 00 — не подойдет, будет началом слова 001.
• 01 — не подойдет, будет началом слова 010.
• 000 — подойдет.
• 001 — не подойдет, буква C.
• 010 — не подойдет, буква B.
• 011 — подойдет.

Шаг 4. Получаем два недостающих кодовых слова равной длины: 000 и 011. Значит, можем использовать их для букв Е и D, при этом сохранив однозначное декодирование. Для D нужно слово, меньшее по значению, тогда верным ответом будет 000.

Ответ: 000
В этой статье мы познакомились с условием Фано и научились правильно кодировать и декодировать сообщения. Но различные виды информации требуют собственных уникальных подходов. Приглашаем вас продолжить изучение темы в статьях «Кодирование изображения» и «Кодирование звука».

Фактчек

• Условие однозначного декодирования необходимо для того, чтобы у закодированного сообщения был ровно один вариант расшифровки — исходный.
• Однозначное декодирование может давать равномерное кодирование, при котором все кодовые слова имеют одинаковую длину, или кодовые слова, составленные по условию Фано, которое гласит: «ни одно кодовое слово не должно совпадать с началом другого кодового слова».
• Существует другая вариация этого условия — обратное условие Фано, оно гласит: «ни одно кодовое слово не должно совпадать с окончанием другого кодового слова».
• Для составления кодовых слов, удовлетворяющих условию Фано, используется дерево вариантов.

Проверь себя

Задание 1.
Для чего необходимо условие однозначного декодирования?

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

Задание 2.
Выберите верные утверждения:

1. При равномерном кодировании все кодовые слова имеют одну длину.
2. При равномерном кодировании кодовые слова не могут начинаться на один и тот же символ.
3. Для соблюдения условия Фано необходимо, чтобы ни одно кодовое слово не совпадало с окончанием другого кодового слова.
4. Обратное условие Фано не гарантирует однозначное декодирование.
5. Для составления кодовых слов, удовлетворяющих обратному условию Фано, используется дерево вариантов.

Задание 3.
Выберите наборы кодовых слов, которые удовлетворяют условию однозначного декодирования по любому из критериев, описанных в статье:

1. 1, 11, 111, 1111, 11111, 0.
2. 01, 001, 0001, 00001, 1
3. 000, 111, 100, 001
4. 10, 11, 00, 1001
5. 10, 100, 1000, 10000

Задание 4.
Для передачи сообщений используются буквы А, Б, В, Г, Д. Известны некоторые кодовые слова: А = 01, Б = 111, В = 00, Г = 110. Какое кодовое слово может соответствовать кодовому слову для буквы Д, чтобы весь код удовлетворял условию Фано?

1. 0
2. 11
3. 101
4. 1100

Ответы: 1. — 3; 2. — 1, 5; 3. — 2, 3, 4, 5; 4. — 3.