Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили...

Question

Для кодирования некоторой последовательности, состоящей из букв И, К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К – кодовое слово 10. Какова наименьшая возможная суммарная длина всех кодов?

Answer 1

Нель­зя ис­поль­зо­вать ко­до­вые слова, ко­то­рые на­чи­на­ют­ся с 0 или с 10. 11 также не можем ис­поль­зо­вать, по­сколь­ку тогда мы боль­ше не смо­жем взять ни­ка­кое дру­гое ко­до­вое слово, а нам их нужно пять. По­это­му берём трёхзнач­ное 110. По Условию Фано, если есть a, то ab существовать не может. Другими словами, мы не можем использовать начало с 0, а если возьмем 11, то начинать другие числа не сможем. Поэтому остается брать числа 110,1110,1111(последний берем без 0, т.к. он последний и других чисел уже не нужно, но если бы и было нужно, то стоит взять число 11110 не нарушая условия Фано)