Разберем решение аналогичной задачи на примере слова СЛОНОПОТАМ
Сначала определим число вхождений букв в слово
СЛОНОПОТАМ: {О}*3+{А,Л,М,Н,П,С,Т}*1
В слово входит восемь различных букв и еще одну позицию ("форточку")
надо оставить для того, чтобы была возможность закодировать остальные знаки.
Можно обозначить "форточку" знаком * и кодировать из расчета 9 букв (знак * должен иметь самый длинный код)
Для 9 букв явно достаточно равномерного кода из 4 знаков, тогда длина кода для слова была бы 36 знаков.
Если использовать для самой частой буквы код из 3 знаков, то еще для 6 букв можно использовать код из 3 знаков, а для двух из 4 знаков (одна из них *).
В этом случае длина кода будет 9*3+4=31 знаку.
Если использовать для самой частой буквы код из 2 знаков, то еще для двух букв придется использовать коды из 4 знаков.
В этом случае длина кода будет 3*2+4*3+4*3=30
Если использовать для самой частой буквы код из 1 знака, то для оставшихся букв придется использовать код из 4 знаков.
В этом случае длина кода будет 3*1+7*4=31.
Пример оптимального кода (один из возможных вариантов)
| О |
А |
Л |
М |
Н |
П |
С |
Т |
* |
| 00 |
010 |
011 |
100 |
101 |
1100 |
1101 |
1110 |
1111 |
|
