Закодируй слово минимальной длины
Длина закодированного слова — это . Расставь коды так, чтобы самым частым буквам достались самые короткие коды, и слово стало короче.
Частым буквам — короткие коды
Когда кодируется не набор букв, а слово, важна частота буквы: длина сообщения — это . Поэтому самым частым буквам — самые короткие коды.
Пример — слово ТЕТЕРЕВ (Е — 3 раза, Т — 2, Р — 1, В — 1). Сравним два варианта кодов:
Плохо: частым символам — длинные коды
| буква | Е | Т | Р | В |
|---|---|---|---|---|
| код | 1111 | 110 | 10 | 0 |
ТЕТЕРЕВ — закодированное слово
с разделителями: 110|1111|110|1111|10|1111|0
слитно: 110111111011111011110
Длина
Хорошо: частым символам — короткие коды
| буква | Е | Т | Р | В |
|---|---|---|---|---|
| код | 0 | 10 | 110 | 1110 |
ТЕТЕРЕВ — закодированное слово
с разделителями: 10|0|10|0|110|0|1110
слитно: 10010011001110
Длина
Вывод: частым буквам — короткие коды
| буква | Е | Т | Р | В |
|---|---|---|---|---|
| частота | 3 | 2 | 1 | 1 |
Чем чаще буква встречается в слове, тем короче должен быть её код — тогда закодированное сообщение короче.
Как пользоваться этим режимом. Расставь коды оставшихся букв так, чтобы длина закодированного слова стала минимальной.