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

Решение:

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

1. Анализ имеющихся кодов:

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

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

2. Построение дерева префиксного кода:

Используем дерево для визуализации префиксных кодов:

• Р (1110): Позиция 1110 в двоичном дереве.
• К (0001): Позиция 0001 в двоичном дереве.
• П (001): Позиция 001 в двоичном дереве.
• Л (01): Позиция 01 в двоичном дереве.

Выделим занятые ветки:

• 0 -> 00 -> 001 (П)
• 0 -> 00 -> 000 -> 0001 (К)
• 0 -> 01 (Л)
• 1 -> 11 -> 111 -> 1110 (Р)

3. Поиск места для буквы Н:

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

Рассмотрим свободные кратчайшие коды:

• 0000: Является префиксом для К (0001), не подходит.
• 0002 (не существует в двоичной системе)
• 0010: Является префиксом для П (001), не подходит.
• 0011: Может быть использован.
• 010: Является префиксом для Л (01), не подходит.
• 011: Может быть использован.
• 1111: Может быть использован.

Чтобы минимизировать длину слова ПОРОЛОН, нам нужно выбрать самый короткий код для Н. Двухбитные коды (00, 01, 10, 11) заняты или являются префиксами. Трехбитные коды:

• 000: занят (префикс К)
• 001: занят (П)
• 010: занят (префикс Л)
• 011: свободен
• 100: свободен
• 101: свободен
• 110: свободен
• 111: занят (префикс Р)

Наиболее короткие свободные коды для Н — трехбитные: 011, 100, 101, 110.

4. Минимизация длины слова ПОРОЛОН:

Слово: ПОРОЛОН. Буквы и их частоты:

• П: 1
• О: 2
• Р: 1
• Л: 1
• Н: 1

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

Давайте построим дерево кодов для всех букв, включая Н, чтобы убедиться в корректности.

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

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

Свободные ветки для Н:

• 011
• 100
• 101
• 110

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

Так как таких кодов несколько (011, 100, 101, 110), мы должны выбрать код с наименьшим числовым значением.

Наименьшее числовое значение из предложенных — 011.

5. Проверка условия префиксного кода:

• Если Н = 011:

Коды:

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

Нет кода, который был бы префиксом другого.

Длина сообщения ПОРОЛОН:

• П(001) + О(?) + Р(1110) + О(?) + Л(01) + О(?) + Н(011)

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

Рассмотрим, какие коды свободны для О, если Н = 011.

• Дерево с Н = 011:
• 0 -> 00 -> 001 (П)
• 0 -> 00 -> 000 -> 0001 (К)
• 0 -> 01 -> 011 (Н)
• 1 -> 11 -> 111 -> 1110 (Р)

Свободные трехбитные коды: 100, 101, 110.

Если предположить, что для О мы можем взять код 100 (длина 3), то:

• П: 001 (3)
• О: 100 (3)
• Р: 1110 (4)
• Л: 01 (2)
• Н: 011 (3)

Длина ПОРОЛОН = 3 + 3 + 4 + 3 + 2 + 3 + 3 = 21.

Что если бы мы выбрали другой код для Н, например, 100?

• Дерево с Н = 100:
• 0 -> 00 -> 001 (П)
• 0 -> 00 -> 000 -> 0001 (К)
• 1 -> 11 -> 111 -> 1110 (Р)
• 1 -> 10 -> 100 (Н)

Свободные трехбитные коды: 011, 101, 110.

Если для О взять 011 (длина 3):

• П: 001 (3)
• О: 011 (3)
• Р: 1110 (4)
• Л: 01 (2)
• Н: 100 (3)

Длина ПОРОЛОН = 3 + 3 + 4 + 3 + 2 + 3 + 3 = 21.

Длина слова 'ПОРОЛОН' будет наименьшей, если коды для всех букв будут максимально короткими.

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

• Л: 01 (2 бита)
• П: 001 (3 бита)
• К: 0001 (4 бита)
• Р: 1110 (4 бита)

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

Рассмотрим доступные коды:

• 2 бита: 00, 10. Оба являются префиксами других кодов (00->001, 00->0001, 10->?). Нет.
• 3 бита: 000, 010, 011, 100, 101, 110, 111.
• 000: Префикс для К.
• 001: Код для П.
• 010: Префикс для Л.
• 011: Свободен.
• 100: Свободен.
• 101: Свободен.
• 110: Свободен.
• 111: Префикс для Р.

Самые короткие доступные коды для Н имеют длину 3 бита: 011, 100, 101, 110.

Условие: «чтобы код удовлетворял указанному условию и при этом длина слова ПОРОЛОН после кодирования была наименьшей».

Если мы назначим Н один из этих трехбитных кодов, то длина кодирования слова ПОРОЛОН будет:

Длина(П) + Длина(О) + Длина(Р) + Длина(О) + Длина(Л) + Длина(О) + Длина(Н)

3 + Длина(О) + 4 + Длина(О) + 2 + Длина(О) + 3

12 + 3 * Длина(О)

Чтобы эта длина была наименьшей, нам нужно, чтобы код для О был как можно короче, и при этом удовлетворял условию префиксного кода.

Давайте построим дерево и посмотрим, где еще есть места для О.

Занятые ветви:

• 0 -> 00 -> 001 (П)
• 0 -> 00 -> 000 -> 0001 (К)
• 0 -> 01 -> (Л)
• 1 -> 11 -> 111 -> 1110 (Р)

Если Н = 011:

• 0 -> 01 -> 011 (Н)

Свободные места для О:

• 100, 101, 110 (3 бита)
• А также более длинные, например, 1111 (4 бита)

Чтобы минимизировать общую длину, мы выберем для О самый короткий доступный код, который не пересекается с другими. Самый короткий доступный код — 100 (3 бита).

Тогда коды будут:

• Л: 01 (2)
• П: 001 (3)
• Р: 1110 (4)
• К: 0001 (4)
• Н: 011 (3)
• О: 100 (3)

Длина ПОРОЛОН = 3 + 3 + 4 + 3 + 2 + 3 + 3 = 21.

Если мы выберем Н = 100:

• 1 -> 10 -> 100 (Н)

Свободные места для О:

• 011, 101, 110 (3 бита)

Если для О выбрать 011 (3 бита):

• Л: 01 (2)
• П: 001 (3)
• Р: 1110 (4)
• К: 0001 (4)
• Н: 100 (3)
• О: 011 (3)

Длина ПОРОЛОН = 3 + 3 + 4 + 3 + 2 + 3 + 3 = 21.

Все 3-битные коды для Н (011, 100, 101, 110) дадут такую же минимальную длину, если для О будет выбран 3-битный код.

Так как таких кодов для Н несколько (011, 100, 101, 110), мы должны указать код с наименьшим числовым значением.

6. Выбор наименьшего числового значения:

Среди 3-битных кодов для Н: 011, 100, 101, 110, наименьшее числовое значение имеет 011.

Проверка:

Если Н = 011, то для О мы можем использовать 100 (или 101, 110). Все эти коды имеют длину 3, как и код для П. Л имеет длину 2. Р и К имеют длину 4.

Длина ПОРОЛОН = Длина(П) + Длина(О) + Длина(Р) + Длина(О) + Длина(Л) + Длина(О) + Длина(Н)

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

Если бы мы могли использовать более короткий код для Н, это было бы лучше, но 2-битные коды заняты или являются префиксами. Поэтому 3 бита — это минимальная длина для Н.

Ответ: 011