ФИО автора: Вафина Альбина Альтафовна
Место работы: МБОУ «СОШ №3» г. Реутов
Должность:учитель информатики
Виды и способы решения задания № 4 на тему «Кодирование и декодирование информации» единого государственного экзамена по информатике
Основные определения
Кодирование – преобразование входной информации в форму, воспринимаемую компьютером, т.е. двоичный код.
Декодирование–преобразование данных из двоичного кода в форму, понятную человеку.
Равномерный код – это код, в котором все кодовые слова имеют одинаковую длину.
Неравномерный код – это код, в котором все кодовые слова имеют разную длину.
Условие Фано: для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно декодировалось, достаточно, чтобы никакой код не был началом другого (более длинного) кода.
Обратное условие Фано: для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно декодировалось, достаточно, чтобы никакой код не был окончанием другого (более длинного) кода.
СутьАлгоритма (дерева) Хаффмана – построение двоичного дерева, где каждый символ получает уникальную комбинацию битов, зависящую от частоты появления в исходной последовательности.
1. «Сообщение, содержащие только N букв. Условие Фано удовлетворяется»
Данный тип отличается тем, что в начале формулировки условия говорится, что кодируется не весь алфавит, а определенное количество букв алфавита.
Задача 1 (сайт Сдам ГИА: Решу ЕГЭ). По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 010, Б – 011, Г – 100. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?
Решение.
1) Выписываем из условия все буквы, которые передаются по каналу связи и их кодовые слова, а также слово, которое нужно закодировать:
… только 7 букв: А – 010 Б – 011 Г – 100 И – М – Р – Я – МАГИЯ – ? |
2) С помощью дерева Хаффмана покажем уже известные кодовые слова для букв А, Б, Г:
… только 7 букв: А – 010 Б – 011 Г – 100 И – М – Р – Я – МАГИЯ – ? |
3) Осталось четыре незаполненных ребра дерева Хаффмана и четыре буквы без кодового слова: И, М, Р, Я. Все эти буквы, кроме буквы Р, в слове МАГИЯ встречаются по одному разу, следовательно, нет отличия какие кодовые слова для какой буквы выбрать.
… только 7 букв: А – 010 Б – 011 Г – 100 И – 00 М – 101 Р – 110 Я – 111 МАГИЯ – ? |
4) Вычислим суммарное количество двоичных знаков, которое потребуется для кодирования слова МАГИЯ:
Полное решение выглядит следующим образом:
… только 7 букв: А – 010 Б – 011 Г – 100 И – 00 М – 101 Р – 110 Я – 111 МАГИЯ – ? 1 · 3 бит + 1 · 3 бит + 1 · 3 бит + 1 · 2 бит + 1 · 3 бит = 14 бит М А Г И Я Ответ: 14 |
2. «Сообщение, содержащие прописные буквы русского алфавита. Условие Фано не удовлетворяется»
Задача 2 (сайт Сдам ГИА: Решу ЕГЭ). По каналу связи передаются шифрованные сообщения, содержащие только прописные буквы русского алфавита. Для передачи используется неравномерный код. Для букв А, Б, В и Г используются кодовые слова 01, 10, 11 и 000 соответственно.
Укажите самое короткое кодовое слово для буквы Е, при котором не будет удовлетворять условию Фано, при этом в записи самого этого слова должно использоваться более одного символа, а само слово не должно совпадать ни с одним из используемых слов для кодирования букв А, Б, В и Г. Если таких слов несколько, то укажите слово с минимальным числовым значением.
Решение.
1) Выписываем из условия все буквы, которые передаются по каналу связи и их кодовые слова, а также слово, которое нужно закодировать:
… буквы русского алфавита: А – 01 Б – 10 В – 11 Г – 000 |
2) С помощью дерева Хаффмана покажем уже известные кодовые слова для букв А, Б, В, Г:
… буквы русского алфавита: А – 01 Б – 10 В – 11 Г – 000 |
3) Так как в условии сказано, что закодированы буквы русского алфавита, для них нужно оставить свободное ребро на дереве Хаффмана. Для буквы Е, код которой нужно найти по заданию, отдельного ребра оставлять не нужно, так как по условию её код не должен удовлетворять условию Фано.
… буквы русского алфавита: А – 01 Б – 10 В – 11 Г – 000 |
4) Чтобы код буквы Е не удовлетворял условию Фано, он должен состоять из уже существующих кодовых слов и иметь более чем один символ:
- код буквы Г как часть кода буквы Е: 00, 0000, 0001 и т.д.;
- код буквы А как часть кода буквы Е: 010, 011 и т.д.;
- код буквы Б как часть кода буквы Е: 100, 101 и т.д.;
- код буквы В как часть кода буквы Е: 110, 111 и т.д.;
- код остальных букв как часть кода буквы Е: 0010, 0011 и т.д.;
Код 00 имеет самый минимальное числовое значение.
Ответ: 00
