Условие Фано
Буквы кодируются двоичными словами разной длины, и ни одно слово не должно быть началом другого. Этот номер решаем руками. Рисуем дерево, находим свободные места и выбираем самые короткие.
- 1Что проверяет номер
- 2Дерево кодов
- 3Сумма длин для оставшихся букв
- 4Длина слова и код одной буквы
- 5Ловушки перед экзаменом
- 6Домашка
Что проверяет номер
Буквы кодируются двоичными словами разной длины. Чтобы сообщение разбиралось однозначно, нужно условие Фано: никакое кодовое слово не является началом другого. Коды 0 и 01 вместе нельзя: встретив 01, непонятно, это одна буква или 0 и что-то ещё.
Часть кодов уже дана. Для остальных букв надо подобрать коды так, чтобы получилось как можно короче. Виды задач различаются тем, что именно просят:
| Что просят | Что делаем |
|---|---|
| Наименьшая суммарная длина кодов оставшихся букв | Берём самые короткие свободные места |
| Наименьшая длина закодированного слова | Самой частой букве самый короткий код |
| Кратчайший код для одной буквы | Самое короткое свободное место, при равенстве наименьшее число |
Все три вида решаются одним рисунком, и код здесь не нужен.
Дерево кодов
Рисуем двоичное дерево: из каждого узла левая ветка это 0, правая это 1. Каждый узел соответствует слову, которое читается по веткам от вершины.
Условие Фано на дереве выглядит просто: кодовые слова должны быть листьями. Если слово заняло узел, то всё ниже него закрыто.
Пример. Заняты слова 01, 100 и 111, нужно закодировать ещё 3 буквы.
Порядок действий:
- Ставим занятые слова как листья.
- Находим свободные узлы. Чем выше узел, тем короче слово.
- Заполняем свободные узлы, начиная с самых высоких.
Здесь нужно ровно 3 места, и их как раз 3: длины 2, 3 и 3, сумма 8.
Заняты слова 00, 01, 101 и 110. Нарисуй дерево. Какой длины самое короткое слово, которое ещё можно добавить?
Сумма длин для оставшихся букв
Признак: «наименьшая возможная суммарная длина кодовых слов для остальных букв». Если свободных мест столько же, сколько букв, просто складываем их длины, как в примере выше. Сложнее, когда мест не хватает.
Мест меньше, чем букв
Свободный узел можно разделить на два: вместо него появятся два слова на один знак длиннее. Например, занято 1 и 01, а нужно 3 буквы. Свободен только узел 00. Делим его на 000 и 001, а один из них ещё раз:
Какой узел делить
Если свободных узлов несколько, делим самый короткий: так сумма вырастет меньше всего. Занято 0 и 100, нужно 3 буквы, свободны 11 и 101. Делим 11: получаем 110, 111 и 101, сумма 9. Если поделить 101, выйдет 11, 1010 и 1011, сумма 10.
Заняты слова 11, 100 и 0. Нужно закодировать ещё 2 буквы. Какова наименьшая суммарная длина их кодов?
Длина слова и код одной буквы
Наименьшая длина закодированного слова
Признак: «какое количество двоичных знаков требуется для кодирования слова». Теперь важно, сколько раз встречается каждая буква. Самая частая получает самый короткий код. Буквы, которых нет в слове, получают самые длинные места, их длина считается ноль раз.
Пример. Известно А = 1, Б = 000, В = 0010. Ещё нужны Г, Д, Е. В слове Д встречается три раза, Е два раза, а Г, А и Б по одному.
Свободны узлы 01 и 0011, а букв три, значит, один узел придётся делить. Сравним два варианта:
| Как делим | Д (3 раза) | Е (2 раза) | Г (1 раз) | Сумма |
|---|---|---|---|---|
| Делим 01 | 010, длина 3 | 011, длина 3 | 0011, длина 4 | 9 + 6 + 4 = 19 |
| Делим 0011 | 01, длина 2 | 00110, длина 5 | 00111, длина 5 | 6 + 10 + 5 = 21 |
Берём 19 и прибавляем известные буквы: А один раз длиной 1 и Б один раз длиной 3. Ответ 23.
Здесь выгоднее поделить короткий узел, но так бывает не всегда. Если одна буква встречается намного чаще других, ей лучше оставить короткий узел целым и делить длинный. Занято 0 и 100, свободны 11 и 101, в слове Д пять раз, Е и Г по одному. Делим 11: все три кода длиной 3, сумма 5 · 3 + 3 + 3 = 21. Делим 101: Д = 11, сумма 5 · 2 + 4 + 4 = 18. Поэтому в задаче на длину слова считай все варианты деления.
Кратчайший код для одной буквы
Признак: «укажите кратчайшее кодовое слово для буквы». Находим самый высокий свободный узел и читаем слово по веткам. Если таких узлов несколько, в условии обычно просят код с наименьшим числовым значением: на дереве это самый левый из них. Заняты 00, 01, 101 и 110, свободны 100 и 111, значит, ответ 100.
Обратное условие Фано
Признак: «никакое кодовое слово не является концом другого». Разверни все слова задом наперёд и рисуй обычное дерево. Найденный код в конце тоже разверни обратно.
Известно: А = 00, Б = 01, В = 10. Ещё нужны Г и Д. В слове Г встречается три раза, Д один раз, А и Б по два раза, В ни разу. Какова наименьшая длина закодированного слова?
Ловушки перед экзаменом
| Ловушка | Как не попасться |
|---|---|
| Не учли буквы, которых нет в слове | Они считаются ноль раз, им достаются самые длинные места, но место занимают |
| Самый короткий код достался редкой букве | Частые буквы ставим на самые высокие узлы |
| Новое слово стало началом занятого | Новые слова только в свободных узлах, ниже занятых и выше занятых нельзя |
| Поделили не тот узел | Для суммы длин делим самый короткий. Для длины слова считаем все варианты |
| Спутали сумму длин и длину слова | Читай, что просят: суммарную длину кодов или длину закодированного слова |
| Забыли про известные буквы в слове | Их длины тоже входят в длину слова |
Домашка
Шесть задач с настоящих экзаменов и из банка ФИПИ. Решай на листе бумаги и вписывай ответ в карточку.
Перед тем как считать, сделай три вещи:
- выпиши, что просят: длину слова, сумму длин или один код;
- нарисуй дерево и отметь занятые слова;
- для слова посчитай, сколько раз встречается каждая буква.
В первых двух задачах в длину слова входят и известные буквы. В третьей и четвёртой ответ это само кодовое слово, а не его длина: нужен самый короткий код, а из равных наименьший по значению. В пятой и шестой просят сумму длин кодов, а не длину сообщения, и в пятой делить надо самый короткий свободный узел.
Ещё задачи этого вида лежат в разделе «Задания», №4.
Задачи «Попробуй сам» учебные, в домашке задачи с настоящих экзаменов и из банка ФИПИ. Рисуй деревья на листе бумаги, как на экзамене.