Для кодирования некоторой последовательности, состоящей из букв О, Н, А, К, Р, решили использовать неравномерный двоичный код, который удовлетворяет условию Фано. Для букв К и Р использовали соответственно кодовые слова 00, 011. Найдите наименьшую возможную длину кодовой последовательности для слова КОРОНА.
1 Ответ
Для буквы О можно использовать кодовое слово 01, так как оно не является началом других кодовых слов. Для буквы Н можно использовать кодовое слово 1, так как это единственная буква, которая не была использована. Для буквы А можно использовать кодовое слово 001, так как все другие буквы и кодовые слова имеют более двух символов. Для буквы Р можно использовать кодовое слово 010, так как 01 не может быть использовано для буквы Р, так как оно уже используется для буквы О.
Тогда кодовая последовательность для слова “КОРОНА” будет иметь вид: 01 1 010 011 001 01. Ее длина равна 14. Это наименьшая возможная длина, так как никакие другие кодовые слова не могут быть использованы, чтобы уменьшить длину.
Ответ: 14