Для передачи сообщений, содержащих только буквы К, Л, М, Н, О, П, Р, решили использовать неравномерный двоичный код, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известны кодовые слова, использованные для некоторых букв: К — 0001, Л — 01. П — 001, Р — 1110. Какое кодовое слово надо назначить для буквы Н, чтобы код удовлетворял указанному условию и при этом длина слова ПОРОЛОН после кодирования была наименьшей? Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение:

Задача состоит в том, чтобы найти кодовое слово для буквы Н, которое бы удовлетворяло условию префиксного кода (никакое кодовое слово не является началом другого) и минимизировало бы длину закодированного слова ПОРОЛОН.

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

• К — 0001 (длина 4)
• Л — 01 (длина 2)
• П — 001 (длина 3)
• Р — 1110 (длина 4)

Слово ПОРОЛОН состоит из следующих букв: П, О, Р, О, Л, О, Н.

Известные кодовые слова уже имеют следующие префиксы:

• 0
• 00
• 000
• 0001
• 01
• 1
• 11
• 111
• 1110

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

Рассмотрим возможные короткие кодовые слова для буквы Н, начиная с наименьшей длины:

• 0000: Начинается с 000. Не подходит.
• 0010: Начинается с 001. Не подходит.
• 0011: Начинается с 001. Не подходит.
• 010: Начинается с 01. Не подходит.
• 011: Начинается с 01. Не подходит.
• 10: Это новое кодовое слово. Оно не является префиксом существующих слов, и ни одно из существующих слов не является его префиксом. Длина 2.
• 110: Начинается с 11. Не подходит.

Если мы назначим Н = 10 (длина 2), то длина слова ПОРОЛОН будет:

• П (3) + О (?) + Р (4) + О (?) + Л (2) + О (?) + Н (2) = 11 + длина(О) * 3

Для минимизации общей длины слова ПОРОЛОН, нужно чтобы кодовое слово для буквы О было как можно короче.

Рассмотрим все буквы, которые нужно закодировать: К, Л, М, Н, О, П, Р. Алфавит: {К, Л, М, Н, О, П, Р}.

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

• К: 0001
• Л: 01
• П: 001
• Р: 1110

Недостающие буквы: М, Н, О.

Используем построение дерева кодов для наглядности.

Корневой узел:

• 0 ->
• 1 ->

Узел 0:

• 00 ->
• 01 (Л)

Узел 00:

• 000 ->
• 001 (П)

Узел 000:

• 0001 (К)

Узел 1:

• 10 ->
• 11 ->

Узел 11:

• 110 ->
• 111 ->

Узел 111:

• 1110 (Р)

Теперь нам нужно назначить коды для М, Н, О. При этом Н и О входят в слово ПОРОЛОН.

Наиболее короткие доступные префиксы (не занятые и не являющиеся префиксами других кодов):

• 10 (длина 2)
• 110 (длина 3)
• 1111 (длина 4)
• 0000 (длина 4)
• 0010 (длина 4)
• 0011 (длина 4)
• 010 (длина 3)
• 011 (длина 3)

Чтобы минимизировать длину слова ПОРОЛОН, нужно назначить наименьшие возможные коды для букв Н и О, а также для М (если он используется в слове). В слове ПОРОЛОН есть буква О, но нет буквы М.

Нам нужны коды для Н и О.

Наиболее короткие свободные коды: 10 (2), 010 (3), 011 (3), 110 (3).

Назначим Н = 10 (длина 2).

Теперь осталось назначить код для О. Из коротких свободных кодов остаются: 010, 011, 110.

Выберем кратчайший из них: 010 (длина 3).

Таким образом, кодовые слова:

• К: 0001
• Л: 01
• П: 001
• Р: 1110
• Н: 10
• О: 010

Проверим, что это префиксный код:

• 01 (Л) является префиксом 010 (О) - НЕ ПОДХОДИТ.

Значит, назначение О = 010 некорректно, так как 01 (Л) является префиксом 010 (О).

Нужно найти такой набор кодов для М, Н, О, чтобы:

1. Все коды были уникальны и не являлись префиксами друг друга.
2. Длина слова ПОРОЛОН была минимальной.

Слово ПОРОЛОН: П(3), О(?), Р(4), О(?), Л(2), О(?), Н(?).

Для минимизации длины, нам нужны как можно более короткие коды для О и Н.

Давайте снова построим дерево и посмотрим на доступные ветви:

0
├─ 00
│  ├─ 000
│  │  └─ 0001 (К)
│  └─ 001 (П)
│     └─ 0010 (свободно)
│     └─ 0011 (свободно)
│     └─ 001X... (свободно)
└─ 01 (Л)
   └─ 010 (свободно)
   └─ 011 (свободно)
   └─ 01X... (свободно)

1
├─ 10 (свободно)
├─ 11
│  ├─ 110 (свободно)
│  └─ 111
│     └─ 1110 (Р)
│     └─ 1111 (свободно)
└─ 11XX... (свободно)

Доступные кратчайшие свободные коды (в порядке возрастания длины и числового значения):

• 10 (длина 2)
• 110 (длина 3)
• 0010 (длина 4)
• 0011 (длина 4)
• 010 (длина 3)
• 011 (длина 3)
• 1111 (длина 4)

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

Самый короткий свободный код - 10 (длина 2).

Назначим его для Н.

Теперь нам нужен код для О. Из оставшихся коротких свободных кодов:

• 010 (длина 3)
• 011 (длина 3)
• 110 (длина 3)

Если мы назначим О = 010, то код Л (01) станет префиксом кода О (010). Это недопустимо.

Если мы назначим О = 011, то код Л (01) станет префиксом кода О (011). Это недопустимо.

Если мы назначим О = 110, то код Л (01) не будет префиксом. Это допустимо.

Итак, назначим:

• Н = 10 (длина 2)
• О = 110 (длина 3)

Проверим дерево с этим назначением:

0
├─ 00
│  ├─ 000
│  │  └─ 0001 (К)
│  └─ 001 (П)
│     └─ 0010 (свободно)
│     └─ 0011 (свободно)
└─ 01 (Л)
   └─ 010 (свободно)
   └─ 011 (свободно)

1
├─ 10 (Н)
├─ 11
│  ├─ 110 (О)
│  └─ 111
│     └─ 1110 (Р)
│     └─ 1111 (свободно)

В этом случае, код Л (01) не является префиксом О (110). Код Н (10) не является префиксом Р (1110) и наоборот. Все коды уникальны и не являются префиксами друг друга.

Длина слова ПОРОЛОН:

• П (3) + О (3) + Р (4) + О (3) + Л (2) + О (3) + Н (2) = 3 + 3 + 4 + 3 + 2 + 3 + 2 = 20

Возможно ли назначить коды так, чтобы длина была еще меньше?

Для этого нужно, чтобы Н и О получили максимально короткие коды.

Самый короткий код - длина 2. Только 10 доступен.

Если Н = 10, то для О доступны коды длиной 3: 010, 011, 110.

Мы уже выяснили, что 010 и 011 недопустимы из-за префикса Л (01).

Следовательно, для О остается только 110.

Другой вариант: если О = 10 (длина 2).

Тогда для Н, из оставшихся коротких, нам нужно выбрать код, который не будет префиксом Р (1110) и не будет иметь префикс Л (01) или П (001).

Доступные коды длиной 3: 010, 011, 110.

• Если О = 10, то Н может быть 010, 011, 110.

Рассмотрим случай, когда Н = 10.

Слово ПОРОЛОН: П(3), О(?), Р(4), О(?), Л(2), О(?), Н(2).

Чтобы минимизировать длину, О должно получить максимально короткий доступный код.

Коды, которые не могут быть префиксами К, Л, П, Р и не имеют их в качестве префиксов:

• 10 (длина 2)
• 010 (длина 3)
• 011 (длина 3)
• 110 (длина 3)
• 0010 (длина 4)
• 0011 (длина 4)
• 1111 (длина 4)

Назначаем Н = 10 (длина 2, минимальная возможная).

Теперь ищем кратчайший код для О.

Из доступных: 010, 011, 110.

Проверяем на префиксы:

• 010: Л (01) является префиксом. Не подходит.
• 011: Л (01) является префиксом. Не подходит.
• 110: Не имеет префиксов из {0001, 01, 001, 1110}. И сам не является префиксом для них. Код Н (10) не префикс 110.

Значит, единственный допустимый кратчайший код для О при Н=10 это 110 (длина 3).

Суммарная длина слова ПОРОЛОН = 3 (П) + 3 (О) + 4 (Р) + 3 (О) + 2 (Л) + 3 (О) + 2 (Н) = 20.

Возможно ли получить меньшую длину? Для этого нужно, чтобы Н и О получили коды меньшей суммарной длины.

Предположим, мы назначим О = 10 (длина 2).

Тогда Н должно получить какой-то другой код. Кратчайший оставшийся код - 010 (3), 011 (3), 110 (3).

Если О = 10, то:

• Н = 010. Проверка: Л (01) - префикс 010. Не подходит.
• Н = 011. Проверка: Л (01) - префикс 011. Не подходит.
• Н = 110. Проверка: Л (01) не префикс 110. 10 (О) не префикс 110. 110 не префикс Р (1110). Это допустимо.

Если О = 10 и Н = 110:

Длина слова ПОРОЛОН = 3 (П) + 2 (О) + 4 (Р) + 2 (О) + 2 (Л) + 2 (О) + 3 (Н) = 3 + 2 + 4 + 2 + 2 + 2 + 3 = 18.

Эта длина (18) меньше, чем 20.

Таким образом, мы нашли комбинацию, которая дает меньшую длину.

Кодовые слова:

• К: 0001
• Л: 01
• П: 001
• Р: 1110
• О: 10
• Н: 110

Проверим префиксность:

• Л (01) не префикс О (10)
• О (10) не префикс Р (1110)
• Н (110) не префикс Р (1110)
• Л (01) не префикс Н (110)
• П (001) не префикс О (10) и Н (110)

Все коды уникальны и удовлетворяют условию префиксного кода.

Длина слова ПОРОЛОН: П(001) О(10) Р(1110) О(10) Л(01) О(10) Н(110) = 001 10 1110 10 01 10 110. Длина = 3+2+4+2+2+2+3 = 18.

Это наименьшая возможная длина, так как мы использовали два кода минимальной возможной длины (2) для О и Н.

Если бы существовал другой набор кодов, дающий длину 18, мы бы выбрали тот, у которого наименьшее числовое значение. Код для Н в данном случае — 110.

Если же Н=10, тогда О=110, длина 20.

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

Случай 1: Н = 10, О = 110. Длина 20. Код для Н: 10.

Случай 2: О = 10, Н = 110. Длина 18. Код для Н: 110.

Случай 2 дает меньшую длину слова ПОРОЛОН.

Значит, для буквы Н мы должны назначить код 110.

Ответ:

110