Question

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

Answer 1

Для трёх букв ко­до­вые слова уже из­вест­ны, оста­лось по­до­брать для букв Г и Д такие ко­до­вые слова, ко­то­рые будут яв­лять­ся крат­чай­шим и удо­вле­тво­рять усло­вию Фано.

Ко­до­вым сло­вом не могут быть ни 0, ни 1, по­то­му что есть ко­до­вые слова, на­чи­на­ю­щи­е­ся с 0 и 1. Для остав­ших­ся букв можно ис­поль­зо­вать ко­до­вые слова 011 и 0101. Сумма длин этих ко­до­вых слов равна 7.