Тема 02. Кодирование и декодирование информации

🏠 Главная / Теория / Тема 02. Кодирование и декодирование информации

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

---

## 1. Что такое префиксный код

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

**Условие Фано (условие однозначного декодирования):**
> Ни один кодовый символ не должен быть **началом** другого кодового символа.

### Пример допустимой таблицы:

| Буква | Код |
|-------|-----|
| А | 0 |
| Б | 10 |
| В | 110 |
| Г | 111 |

Здесь `0` не является началом `10`, `110`, `111` → условие Фано выполнено ✓

### Пример недопустимой таблицы:

| Буква | Код |
|-------|-----|
| А | 0 |
| Б | 01 |

Код `А = 0` — это начало кода `Б = 01` → однозначное декодирование **невозможно** ✗

---

## 2. Дерево кодирования

Самый надёжный способ проверить условие Фано — построить **двоичное дерево**.

**Правила построения:**
- Из каждого узла выходит 2 ветки: **0** (влево) и **1** (вправо).
- Буква помещается в **листовой узел** (из него нет продолжений).
- Если в узле уже стоит буква — дальше по этой ветке идти нельзя.

```
        [ ]
       /   \
      0     1
     / \   / \
    А   [B] [C] [D]
       /  \
     Б    В
```

> **Совет:** Рисуйте дерево при каждой задаче. Это занимает 1-2 минуты, но исключает ошибки.

---

## 3. Типы задач на ОГЭ

### Тип 1: Декодирование сообщения

**Задача:** Дана строка из 0 и 1, дана кодовая таблица. Расшифровать сообщение.

**Алгоритм:**
1. Берём первый символ строки.
2. Проверяем — есть ли такой код в таблице?
   - Если да — записываем букву, переходим к следующему символу.
   - Если нет — добавляем следующий символ и снова проверяем.
3. Повторяем до конца строки.

**Пример:**
Таблица: А=0, Б=10, В=110, Г=111. Строка: `01011010`

- `0` → А
- `1` — нет. `10` → Б
- `1` — нет. `10` → Б
- `1` — нет. `10` → Б

Ответ: А Б Б Б (но проверьте сами — задача может иметь другое решение)

---

### Тип 2: Проверить, выполнено ли условие Фано

**Алгоритм:**
1. Для каждой пары кодов проверяем: является ли более короткий код началом более длинного?
2. Если хотя бы одна такая пара найдена — условие НЕ выполнено.

**Быстрая проверка:** Нарисуйте дерево. Если все буквы оказались в листовых узлах — условие выполнено.

---

### Тип 3: Добавить новую букву с минимальным кодом

**Задача:** Дана таблица. Добавить новую букву так, чтобы суммарная длина сообщения была минимальной.

**Алгоритм:**
1. Нарисовать дерево с существующими кодами.
2. Найти свободные листовые узлы, ближайшие к корню (короткие коды).
3. Выбрать узел с наименьшей глубиной — это и будет новый код.

> **Совет:** Минимальный код — самый короткий из доступных. Смотрите на свободные "ветки" дерева.

---

## 4. Типичные ошибки

- **Читать слева направо без проверки.** Некоторые строки можно декодировать несколькими способами — если это так, значит условие Фано нарушено.
- **Не строить дерево.** Без дерева легко пропустить конфликты.
- **Забыть нули.** Код `0` и код `00` — разные! И `0` является началом `00`, что нарушает условие Фано.
- **Перепутать "начало" и "конец".** Условие Фано — это про **начало** (префикс), а не конец суффикс кода.

---

## 5. Лайфхаки для ОГЭ

> **Совет:** Если все коды имеют одинаковую длину — условие Фано всегда выполнено автоматически.

> **Совет:** Для декодирования удобно подчёркивать каждую найденную букву в строке.

> **Совет:** Чтобы быстро добавить новую букву — найдите в дереве самую "свободную" ветку. Если у узла на глубине 2 обе ветки свободны — возьмите одну из них (глубина 3 — это код из 3 символов).

> **Совет:** Популярная ловушка — код "0" уже занят буквой А, а вы пытаетесь поставить "01" для новой буквы. Это нарушает Фано! В дереве у узла А нет потомков.

Назад к списку