реши задания на условие фано с 1 по 10 включительн...

Question

реши задания на условие фано с 1 по 10 включительно со всеми деревьями и подробным обьяснением и с тем какие комбинации соответствуют какой букве

Answer 1

Разберу все 10 заданий, построю деревья и укажу полный набор кодов для каждой буквы. В № 3, 5 и 8 отдельно проверю однозначное декодирование: там условие Фано не требуется, а известные коды даже не являются префиксными. Для этих заданий нужен другой способ проверки.

Answer 2

Text version

Задача 4. Подробное решение заданий № 1–10

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

Как решать задачи на условие Фано

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

Например, коды 00, 01, 10 удовлетворяют условию Фано, а коды 0, 01, 10 — нет, потому что 0 является началом 01.

Обратное условие Фано: никакое кодовое слово не может быть концом другого кодового слова.

Например, коды 00, 01, 11 удовлетворяют обратному условию Фано, а коды 0, 10, 11 — нет, поскольку 0 является концом 10.

Оба условия позволяют однозначно декодировать сообщения. При этом существует и более общее понятие — однозначно декодируемый код. Такой код не обязан удовлетворять ни прямому, ни обратному условию Фано.

В частности, в заданиях № 3, 5 и 8 требуется именно однозначное декодирование. Мы подберём для них коды, удовлетворяющие обратному условию Фано.

Как читать деревья

В каждом дереве от корня выходят ветви 0 и 1.
При обычном условии Фано читаем путь от корня до буквы.
При обратном условии Фано построим дерево перевёрнутых кодов: путь от корня до буквы нужно прочитать справа налево, чтобы получить исходный код.
Если буква находится в конце ветви, её код указан в скобках.

№ 1. Кодирование слова «ПЕРЕПЕЛ»

Дано:

Алфавит: Е, Л, П, К, Р, С.

Известные коды:

К = 011
Р = 11

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

Шаг 1. Найдём свободные ветви

Буквы К и Р уже занимают пути 011 и 11.

Поэтому свободны ветви:

00, 010, 10.

Нужно разместить четыре оставшиеся буквы: Е, Л, П, С.

В слове ПЕРЕПЕЛ буквы встречаются:

Буква	Количество
Е	3
П	2
Р	1
Л	1
К, С	0

Букве Е желательно дать короткий код, поскольку она встречается трижды. Букве П — тоже короткий, так как она встречается дважды.

Для размещения четырёх букв разделим свободную ветвь 010 на 0100 и 0101.

Шаг 2. Назначим коды

Буква	Код	Длина
П	`00`	2
Е	`10`	2
Р	`11`	2
Л	`0100`	4
К	`011`	3
С	`0101`	4

Букве П даём 00, а не 10, чтобы закодированное слово имело меньшее числовое значение. Из двух возможных четырёхбитных кодов букве Л даём меньший — 0100.

Шаг 3. Построим дерево Фано

text
                   КОРЕНЬ
                  /      \
                 0        1
               /   \     / \
              0     1   0   1
              П    / \  Е   Р
                  0   1
                 / \  К
                0   1
                Л   С

Точное дерево с указанием битов на каждом ребре:

text
корень
├──0
│   ├──0 → П (00)
│   └──1
│       ├──0
│       │   ├──0 → Л (0100)
│       │   └──1 → С (0101)
│       └──1 → К (011)
└──1
    ├──0 → Е (10)
    └──1 → Р (11)

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

Шаг 4. Закодируем слово

П Е Р Е П Е Л:

text
П     Е     Р     Е     П     Е     Л
00 | 10 | 11 | 10 | 00 | 10 | 0100

Соединяем:

0010111000100100

Длина:

2+2+2+2+2+2+4=\boxed{16\text{ бит}}

Шаг 5. Переведём в восьмеричную систему

Дополняем двоичное число слева нулями до числа разрядов, кратного трём:

text
000 010 111 000 100 100
 0   2   7   0   4   4

Получаем 027044, или без незначащего ведущего нуля — 27044.

Ответ № 1:

\boxed{27044_8}

Почему это минимум: доступные ветви имеют длины 2, 3 и 2. Чтобы получить четыре кодовых слова, надо разделить одну ветвь. Разделение 010 даёт длины 2, 2, 4, 4 и суммарно 16 бит для слова. Разделение одной из двухбитных ветвей даёт длины 2, 3, 3, 3 и минимум 17 бит. Поэтому 16 бит — оптимально.

№ 2. Кодирование слова «КОЛОКОЛ»

Дано:

Алфавит: А, К, Л, О, С, Т.

Известные коды:

А = 10
К = 111

Слово: КОЛОКОЛ.

Шаг 1. Посчитаем частоты

Буква	Количество
О	3
К	2
Л	2
А, С, Т	0

Код К фиксирован и содержит три бита.

Оставшиеся свободные ветви — 0 и 110.

Чтобы получить четыре кода для О, Л, С, Т, разделим обе эти ветви:

0 превращается в 00 и 01;
110 превращается в 1100 и 1101.

Шаг 2. Назначим коды

Буква	Код	Длина
К	`111`	3
О	`00`	2
Л	`01`	2
А	`10`	2
С	`1100`	4
Т	`1101`	4

Коды О и Л можно поменять местами без изменения длины сообщения. Но 00 меньше 01, поэтому букве О, появляющейся раньше в слове, назначаем 00.

Шаг 3. Дерево Фано

text
корень
├──0
│   ├──0 → О (00)
│   └──1 → Л (01)
└──1
    ├──0 → А (10)
    └──1
        ├──0
        │   ├──0 → С (1100)
        │   └──1 → Т (1101)
        └──1 → К (111)

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

Шаг 4. Кодируем слово

К О Л О К О Л:

text
К      О    Л    О    К      О    Л
111 | 00 | 01 | 00 | 111 | 00 | 01

Результат:

1110001001110001

Длина:

3+2+2+2+3+2+2=\boxed{16\text{ бит}}

Шаг 5. Перевод в восьмеричную систему

text
001 110 001 001 110 001
 1   6   1   1   6   1

Ответ № 2:

\boxed{161161_8}

Почему это минимум: при кодах О = 00, Л = 01 длина слова равна 16 битам. Если использовать О = 0, для размещения Л, С, Т придётся углубиться в ветвь 110. Тогда Л получит минимум четыре бита, а слово будет занимать 17 бит. Другие размещения также не дают меньше 16 бит.

№ 3. Найти кратчайший код для буквы D

Дано:

A = 10
B = 1
C = 100
D = ?

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

Шаг 1. Проверяем однобитные коды

Вариант D = 0 не подходит, потому что:

text
A = 10
B D = 1 0 = 10

Получается, что одна последовательность 10 обозначает и A, и BD.

Вариант D = 1 уже занят буквой B.

Значит, код длиной 1 бит невозможен.

Шаг 2. Проверяем двухбитные коды

Код D	Почему не подходит
`00`	C = `100` и BD = `1 00`
`01`	AB = `10 1` и BD = `1 01`
`10`	Уже занят буквой A
`11`	BВ = `1 1` совпадает с D

Ни один двухбитный код не подходит.

Шаг 3. Проверяем трёхбитный код

Возьмём D = 000.

Получаем:

Буква	Код
A	`10`
B	`1`
C	`100`
D	`000`

Проверим обратное условие Фано.

Перевернём коды:

Буква	Исходный код	Перевёрнутый
A	`10`	`01`
B	`1`	`1`
C	`100`	`001`
D	`000`	`000`

Перевёрнутые коды удовлетворяют прямому условию Фано.

Дерево перевёрнутых кодов

text
корень
├──0
│   ├──0
│   │   ├──0 → D (000)
│   │   └──1 → C (100)
│   └──1 → A (10)
└──1 → B (1)

Здесь подписи в скобках — исходные коды.

Раз перевёрнутые коды образуют корректное дерево Фано, исходные коды удовлетворяют обратному условию Фано. Значит, однозначное декодирование возможно.

Ответ № 3:

\boxed{000}

Минимальная длина — 3 бита.

№ 4. Обратное условие Фано, найти код D

Дано:

Алфавит: A, B, C, D, E, F.

A = 1
B = 100
C = 010

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

Шаг 1. Переворачиваем известные коды

Буква	Код	Перевёрнутый код
A	`1`	`1`
B	`100`	`001`
C	`010`	`010`

Теперь строим обычное префиксное дерево для перевёрнутых кодов.

После размещения A, B и C свободны две ветви:

000 и 011.

Обе имеют длину 3.

Нужно закодировать ещё три буквы: D, E, F.

Если отдать одну трёхбитную ветвь букве D, вторую можно разделить на два четырёхбитных кода для E и F.

Шаг 2. Выбираем код D

Возможные трёхбитные перевёрнутые коды:

000 → исходный 000;
011 → исходный 110.

Оба имеют минимальную длину — 3 бита.

Численно 110 больше 000, поэтому выбираем:

D=110

Остальные буквы можно закодировать так:

Буква	Исходный код	Перевёрнутый код
A	`1`	`1`
B	`100`	`001`
C	`010`	`010`
D	`110`	`011`
E	`0000`	`0000`
F	`1000`	`0001`

Шаг 3. Дерево обратного Фано

Строим дерево по перевёрнутым кодам:

text
корень
├──0
│   ├──0
│   │   ├──0
│   │   │   ├──0 → E (0000)
│   │   │   └──1 → F (1000)
│   │   └──1 → B (100)
│   └──1
│       ├──0 → C (010)
│       └──1 → D (110)
└──1 → A (1)

Все перевёрнутые коды заканчиваются в отдельных листьях. Обратное условие Фано выполняется.

Ответ № 4:

\boxed{110}

Минимальная длина — 3 бита, выбран наибольший код.

№ 5. Кодирование слова STRENGHTS

Дано:

Алфавит: A, E, G, H, N, R, S, T.

Известные коды:

R = 0
N = 011
S = 1111

Слово: STRENGHTS.

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

Обрати внимание: R = 0 является началом N = 011. Поэтому прямое условие Фано для исходных кодов уже нарушено. Но можно построить код по обратному условию Фано.

Шаг 1. Считаем буквы

Буква	Количество
S	2
T	2
R	1
E	1
N	1
G	1
H	1
A	0

Сразу считаем длину известных частей:

S: $2\cdot4=8$ бит;
R: $1\cdot1=1$ бит;
N: $1\cdot3=3$ бита.

Итого:

8+1+3=12\text{ бит}

Осталось подобрать пять кодов для A, E, G, H, T.

Шаг 2. Найдём минимальные длины

Для любого однозначно декодируемого двоичного кода выполняется неравенство Крафта — Макмиллана:

\sum 2^{-l_i}\leq 1

где $l_i$ — длина кодового слова.

Уже известные коды занимают долю:

\frac12+\frac18+\frac1{16} =\frac{11}{16}

Значит, для пяти оставшихся кодов:

\sum 2^{-l_i}\leq \frac5{16}

Поскольку T встречается дважды, ей выгодно дать самый короткий из свободных кодов. Буквы E, G, H встречаются по одному разу, а A вообще не входит в слово.

Перебор допустимых целочисленных длин с учётом неравенства Крафта даёт:

Длина T	Минимальный вклад свободных букв
2	22 бита
3	19 бит
4	20 бит
5 и более	Не меньше 25 бит

Минимум достигается при длинах:

l_T=3,\quad l_E=l_G=4,\quad l_H=l_A=5

Шаг 3. Назначим коды

Подберём коды так, чтобы выполнялось обратное условие Фано.

Буква	Код	Длина
A	`11101`	5
E	`0101`	4
G	`0111`	4
H	`01101`	5
N	`011`	3
R	`0`	1
S	`1111`	4
T	`001`	3

Шаг 4. Дерево перевёрнутых кодов

text
корень
├──0 → R (0)
└──1
    ├──0
    │   ├──0 → T (001)
    │   └──1
    │       ├──0 → E (0101)
    │       └──1
    │           ├──0 → H (01101)
    │           └──1 → A (11101)
    └──1
        ├──0 → N (011)
        └──1
            ├──0 → G (0111)
            └──1 → S (1111)

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

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

Шаг 5. Кодируем слово

text
S      T     R   E      N     G      H       T     S
1111 | 001 | 0 | 0101 | 011 | 0111 | 01101 | 001 | 1111

Считаем длину:

4+3+1+4+3+4+5+3+4 =\boxed{31\text{ бит}}

Ответ № 5:

\boxed{31\text{ бит}}

№ 6. Обратное условие Фано, найти код Г

Дано:

Алфавит: А, Б, В, Г, Д, Е.

Известные коды:

А = 1
Б = 110
В = 00

Нужно найти кратчайший код для Г. Среди таких кодов выбрать наименьший по числовому значению — так написано в условии? Нет, в задании № 6 действительно требуется код с наименьшим числовым значением.

Здесь необходимо внимательно рассмотреть оба кандидата.

Шаг 1. Переворачиваем известные коды

Буква	Исходный код	Перевёрнутый
А	`1`	`1`
Б	`110`	`011`
В	`00`	`00`

После размещения известных кодов в обратном дереве свободна только ветвь:

010.

Но требуется разместить три буквы: Г, Д, Е.

Чтобы получить три кодовых слова, нужно дважды разделить эту ветвь.

Получатся длины:

одно кодовое слово длиной 4;
два кодовых слова длиной 5.

Значит, минимальная длина Г — 4 бита.

Шаг 2. Выбираем код Г

Возможные четырёхбитные перевёрнутые коды:

0100 → исходный код 0010;
0101 → исходный код 1010.

По условию нужно выбрать код с наименьшим числовым значением:

0010<1010

Следовательно, правильный выбор:

\boxed{\text{Г}=0010}

Тогда можно использовать следующие коды:

Буква	Код	Перевёрнутый код
А	`1`	`1`
Б	`110`	`011`
В	`00`	`00`
Г	`0010`	`0100`
Д	`01010`	`01010`
Е	`11010`	`01011`

Шаг 3. Дерево обратного Фано

text
корень
├──0
│   ├──0 → В (00)
│   └──1
│       ├──0
│       │   ├──0 → Г (0010)
│       │   └──1
│       │       ├──0 → Д (01010)
│       │       └──1 → Е (11010)
│       └──1 → Б (110)
└──1 → А (1)

Все перевёрнутые коды расположены в листьях.

Ответ № 6:

\boxed{0010}

Минимальная длина — 4 бита. Выбран меньший из двух возможных кодов.

№ 7. Кодирование слова «АУДИОАППАРАТУРА»

Дано:

Алфавит: А, Г, Д, И, О, П, Р, Т, У.

Известные коды:

Д = 010
И = 10

Необходимо найти минимальное количество бит для слова АУДИОАППАРАТУРА.

Шаг 1. Считаем частоты

Буква	Количество
А	5
У	2
П	2
Р	2
Д	1
И	1
О	1
Т	1
Г	0

Самая частая буква — А, поэтому ей выгодно дать короткий код.

Шаг 2. Найдём оптимальные длины

Известные коды Д и И занимают:

\frac18+\frac14=\frac38

По неравенству Крафта для остальных семи букв остаётся:

1-\frac38=\frac58

Нужно минимизировать сумму:

L=3+2+5l_A+2l_У+2l_П+2l_Р+l_О+l_Т

Первые два слагаемых — длины фиксированных кодов Д и И.

При переборе допустимых длин получаем:

Длина А	Минимальный вклад остальных семи букв
1	48 бит
2	41 бит
3	42 бита
4 и более	Не меньше 52 бит

Оптимальна длина А = 2.

Один из оптимальных наборов длин:

\begin{aligned} l_A&=2,\\ l_П&=3,\\ l_Р=l_У=l_О&=4,\\ l_Т=l_Г&=5. \end{aligned}

Шаг 3. Назначим коды

Буква	Код	Длина
А	`00`	2
Г	`11111`	5
Д	`010`	3
И	`10`	2
О	`1110`	4
П	`011`	3
Р	`1100`	4
Т	`11110`	5
У	`1101`	4

Шаг 4. Построим дерево Фано

text
корень
├──0
│   ├──0 → А (00)
│   └──1
│       ├──0 → Д (010)
│       └──1 → П (011)
└──1
    ├──0 → И (10)
    └──1
        ├──0
        │   ├──0 → Р (1100)
        │   └──1 → У (1101)
        └──1
            ├──0 → О (1110)
            └──1
                ├──0 → Т (11110)
                └──1 → Г (11111)

Это обычное дерево Фано: каждое кодовое слово заканчивается в листе.

Шаг 5. Кодируем слово

Слово:

А У Д И О А П П А Р А Т У Р А

Подставляем коды:

text
А    У      Д     И    О      А    П     П     А    Р      А    Т       У      Р      А
00 | 1101 | 010 | 10 | 1110 | 00 | 011 | 011 | 00 | 1100 | 00 | 11110 | 1101 | 1100 | 00

Подсчёт по частотам:

\begin{aligned} L={}&5\cdot2+2\cdot4+2\cdot3\\ &+2\cdot4+3+2+4+5\\ ={}&10+8+6+8+3+2+4+5\\ ={}&46. \end{aligned}

Ответ № 7:

\boxed{46\text{ бит}}

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

№ 8. Кодирование слова «ФЕЛЬДЪЕГЕРЬ»

Дано:

Алфавит: А, Г, Д, Е, Л, Р, Ф, Ь, Ъ.

Известные коды:

Л = 10
Ф = 101

Нужно определить минимальное количество бит для слова ФЕЛЬДЪЕГЕРЬ.

Шаг 1. Определим, какое условие подходит

Обрати внимание:

10 является началом 101.

Поэтому прямое условие Фано уже нарушено. Но код может быть однозначно декодируемым.

Используем обратное условие Фано.

Шаг 2. Подсчитаем буквы

Буква	Количество
Е	3
Ь	2
Ф	1
Л	1
Д	1
Ъ	1
Г	1
Р	1
А	0

Для известных букв:

L_{\text{известные}}=3+2=5

Известные коды занимают долю:

\frac14+\frac18=\frac38

Для остальных букв остаётся:

\frac58

Для получения минимального сообщения букве Е выгодно дать длину 2, а букве Ь — длину 3.

Минимальные длины свободных букв:

Буква	Длина
Е	2
Ь	3
Д	4
Ъ	4
Г	4
Р	5
А	5

Проверка неравенства Крафта показывает, что при длине Е = 1 вклад свободных букв был бы не меньше 36 бит, при длине Е = 3 — не меньше 30 бит, а выбранные длины дают 29 бит.

Шаг 3. Назначаем коды

Буква	Исходный код	Перевёрнутый код
А	`11111`	`11111`
Г	`0111`	`1110`
Д	`0011`	`1100`
Е	`00`	`00`
Л	`10`	`01`
Р	`01111`	`11110`
Ф	`101`	`101`
Ь	`001`	`100`
Ъ	`1011`	`1101`

Шаг 4. Дерево обратного Фано

Строим дерево перевёрнутых кодов:

text
корень
├──0
│   ├──0 → Е (00)
│   └──1 → Л (10)
└──1
    ├──0
    │   ├──0 → Ь (001)
    │   └──1 → Ф (101)
    └──1
        ├──0
        │   ├──0 → Д (0011)
        │   └──1 → Ъ (1011)
        └──1
            ├──0 → Г (0111)
            └──1
                ├──0 → Р (01111)
                └──1 → А (11111)

Дерево корректное, поскольку перевёрнутые кодовые слова не являются началом друг друга.

Шаг 5. Кодируем слово

Ф Е Л Ь Д Ъ Е Г Е Р Ь:

text
Ф      Е    Л    Ь     Д      Ъ      Е    Г      Е    Р       Ь
101 | 00 | 10 | 001 | 0011 | 1011 | 00 | 0111 | 00 | 01111 | 001

Считаем длину:

\begin{aligned} L={}&3+3\cdot2+2+2\cdot3\\ &+4+4+4+5\\ ={}&3+6+2+6+4+4+4+5\\ ={}&34. \end{aligned}

Ответ № 8:

\boxed{34\text{ бита}}

№ 9. Найти самое длинное кодовое слово

Дано:

Алфавит: А, Т, З, Н, И, Е.

Известные коды:

А = 01
Т = 00

Слово: АНТИТЕЗА.

Известно, что оно закодировано 21 битом.

Нужно найти кодовое слово наибольшей длины. Среди возможных ответов выбрать наименьшее числовое значение.

Шаг 1. Распишем длины

Слово:

А Н Т И Т Е З А

Частоты:

А — 2 раза;
Т — 2 раза;
Н, И, Е, З — по одному разу.

Для А и Т уже потрачено:

2\cdot2+2\cdot2=8\text{ бит}

Всего 21 бит.

Значит, на остальные четыре буквы должно приходиться:

21-8=13\text{ бит}

Получаем:

l_Н+l_И+l_Е+l_З=13

Шаг 2. Построим дерево

Коды А = 01 и Т = 00 полностью занимают ветвь, начинающуюся с 0.

Все оставшиеся коды должны начинаться с 1.

Чтобы суммарная длина четырёх кодов была равна 13, можно использовать длины:

3+3+3+4=13

Один код длины 4, три кода длины 3.

Назначим их так:

Буква	Код	Длина
А	`01`	2
Т	`00`	2
Н	`1000`	4
И	`101`	3
Е	`110`	3
З	`111`	3

Шаг 3. Дерево Фано

text
корень
├──0
│   ├──0 → Т (00)
│   └──1 → А (01)
└──1
    ├──0
    │   ├──0
    │   │   └──0 → Н (1000)
    │   └──1 → И (101)
    └──1
        ├──0 → Е (110)
        └──1 → З (111)

Ветвь 1001 не используется.

Шаг 4. Проверим общую длину

text
А    Н      Т    И     Т    Е     З     А
01 | 1000 | 00 | 101 | 00 | 110 | 111 | 01

2+4+2+3+2+3+3+2=21

Условие выполняется.

Шаг 5. Почему самое длинное слово не может содержать 5 бит?

Все четыре новых кодовых слова находятся в ветви 1. Поэтому их суммарная доля по неравенству Крафта не может превышать $\frac12$ .

Если один код имеет длину 5, остальные три должны иметь суммарную длину 8.

Наиболее благоприятный вариант — длины 2, 3 и 3. Но тогда:

\frac1{2^2}+\frac1{2^3}+ \frac1{2^3}+\frac1{2^5} =\frac{17}{32}>\frac12

Это невозможно. Остальные распределения длин с суммой 8 также не подходят. Длины 6 и более приводят к ещё более жёстким ограничениям.

Следовательно, максимальная возможная длина — 4 бита.

Самое маленькое четырёхбитное число, начинающееся с 1, — 1000. Мы показали, что такой код действительно можно использовать.

Ответ № 9:

\boxed{1000}

Максимальная длина — 4 бита.

№ 10. Найти код буквы С для слова «УСЛОВИЕ ФАНО»

Дано:

Алфавит: А, В, Е, Л, И, Н, О, С, У, Ф и пробел.

Известные коды:

Буква	Код
О	`0000`
У	`10`
А	`0001`
И	`1101`
В	`0010`
Н	`11001`
Е	`0011`
Ф	`110001`

Нужно найти код для буквы С, чтобы словосочетание УСЛОВИЕ ФАНО занимало наименьшее количество бит. Среди вариантов выбрать наибольшее числовое значение кода С.

Шаг 1. Разберём известные коды

Первая группа:

text
0000 → О
0001 → А
0010 → В
0011 → Е

Эти коды полностью занимают ветвь 00.

Ещё есть:

text
10     → У
1101   → И
11001  → Н
110001 → Ф

Необходимо закодировать три оставшихся символа:

С;
Л;
пробел.

Шаг 2. Найдём свободные ветви

С учётом известных кодов свободны ветви:

01, 111, 110000.

Если каждой из трёх букв отдать по одной из этих ветвей, суммарная длина будет:

2+3+6=11

Но можно получить более выгодный вариант.

Разделим ветвь 01 на:

010;
011.

Тогда для трёх букв можно использовать:

010, 011, 111.

Их общая длина:

3+3+3=\boxed{9\text{ бит}}

Это минимум: комбинация длин 2, 3, 3 невозможна, потому что после использования ветвей 01 и 111 третьего свободного трёхбитного кода уже нет.

Шаг 3. Выбираем код буквы С

Возможные трёхбитные коды:

010, 011, 111.

По условию требуется выбрать для С код с наибольшим числовым значением:

111>011>010

Поэтому:

\boxed{\text{С}=111}

Оставшиеся коды назначим:

Л = 010;
пробел = 011.

Шаг 4. Полная таблица кодов

Символ	Код	Длина
А	`0001`	4
В	`0010`	4
Е	`0011`	4
Л	`010`	3
И	`1101`	4
Н	`11001`	5
О	`0000`	4
С	`111`	3
У	`10`	2
Ф	`110001`	6
Пробел	`011`	3

Шаг 5. Полное дерево Фано

text
корень
├──0
│   ├──0
│   │   ├──0
│   │   │   ├──0 → О (0000)
│   │   │   └──1 → А (0001)
│   │   └──1
│   │       ├──0 → В (0010)
│   │       └──1 → Е (0011)
│   └──1
│       ├──0 → Л (010)
│       └──1 → пробел (011)
└──1
    ├──0 → У (10)
    └──1
        ├──0
        │   ├──0
        │   │   ├──0
        │   │   │   └──1 → Ф (110001)
        │   │   └──1 → Н (11001)
        │   └──1 → И (1101)
        └──1 → С (111)

Ветка 110000 остаётся неиспользованной.

Проверяем: ни один код не является началом другого. Прямое условие Фано выполняется.

Шаг 6. Кодируем «УСЛОВИЕ ФАНО»

В словосочетании 12 символов, включая пробел:

У С Л О В И Е [пробел] Ф А Н О

Подставим коды:

text
У    С     Л     О      В      И      Е      пробел  Ф        А      Н       О
10 | 111 | 010 | 0000 | 0010 | 1101 | 0011 | 011   | 110001 | 0001 | 11001 | 0000

Посчитаем длину:

\begin{aligned} L={}&2+3+3+4+4+4\\ &+4+3+6+4+5+4\\ ={}&46. \end{aligned}

Из них 37 бит приходятся на символы с известными кодами, а 9 бит — на С, Л и пробел.

Ответ № 10:

\boxed{111}

Минимальная длина словосочетания — 46 бит.

Итоговая таблица ответов

№	Что требуется найти	Ответ
1	Восьмеричный код слова «ПЕРЕПЕЛ»	27044₈
2	Восьмеричный код слова «КОЛОКОЛ»	161161₈
3	Кратчайший код D	000
4	Кратчайший наибольший код D	110
5	Минимальная длина STRENGHTS	31 бит
6	Кратчайший наименьший код Г	0010
7	Минимальная длина «АУДИОАППАРАТУРА»	46 бит
8	Минимальная длина «ФЕЛЬДЪЕГЕРЬ»	34 бита
9	Наибольшая длина кода, минимальное значение	1000
10	Оптимальный наибольший код С	111

Что важно запомнить для таких заданий

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

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

Câu hỏi

Suy nghĩ

Trả lời

Suy nghĩ

Suy nghĩ

Suy nghĩ

Suy nghĩ

Trả lời

Задача 4. Подробное решение заданий № 1–10

Как решать задачи на условие Фано

Как читать деревья

№ 1. Кодирование слова «ПЕРЕПЕЛ»

Шаг 1. Найдём свободные ветви

Шаг 2. Назначим коды

Шаг 3. Построим дерево Фано

Шаг 4. Закодируем слово

Шаг 5. Переведём в восьмеричную систему

№ 2. Кодирование слова «КОЛОКОЛ»

Шаг 1. Посчитаем частоты

Шаг 2. Назначим коды

Шаг 3. Дерево Фано

Шаг 4. Кодируем слово

Шаг 5. Перевод в восьмеричную систему

№ 3. Найти кратчайший код для буквы D

Шаг 1. Проверяем однобитные коды

Шаг 2. Проверяем двухбитные коды

Шаг 3. Проверяем трёхбитный код

Дерево перевёрнутых кодов

№ 4. Обратное условие Фано, найти код D

Шаг 1. Переворачиваем известные коды

Шаг 2. Выбираем код D

Шаг 3. Дерево обратного Фано

№ 5. Кодирование слова STRENGHTS

Шаг 1. Считаем буквы

Шаг 2. Найдём минимальные длины

Шаг 3. Назначим коды

Шаг 4. Дерево перевёрнутых кодов

Шаг 5. Кодируем слово

№ 6. Обратное условие Фано, найти код Г

Шаг 1. Переворачиваем известные коды

Шаг 2. Выбираем код Г

Шаг 3. Дерево обратного Фано

№ 7. Кодирование слова «АУДИОАППАРАТУРА»

Шаг 1. Считаем частоты

Шаг 2. Найдём оптимальные длины

Шаг 3. Назначим коды

Шаг 4. Построим дерево Фано

Шаг 5. Кодируем слово

№ 8. Кодирование слова «ФЕЛЬДЪЕГЕРЬ»

Шаг 1. Определим, какое условие подходит

Шаг 2. Подсчитаем буквы

Шаг 3. Назначаем коды

Шаг 4. Дерево обратного Фано

Шаг 5. Кодируем слово

№ 9. Найти самое длинное кодовое слово

Шаг 1. Распишем длины

Шаг 2. Построим дерево

Шаг 3. Дерево Фано

Шаг 4. Проверим общую длину

Шаг 5. Почему самое длинное слово не может содержать 5 бит?

№ 10. Найти код буквы С для слова «УСЛОВИЕ ФАНО»

Шаг 1. Разберём известные коды

Шаг 2. Найдём свободные ветви

Шаг 3. Выбираем код буквы С

Шаг 4. Полная таблица кодов

Шаг 5. Полное дерево Фано

Шаг 6. Кодируем «УСЛОВИЕ ФАНО»

Итоговая таблица ответов

Что важно запомнить для таких заданий

Chia sẻ Q&A này