ГДЗ по информатике, 10 класс, Поляков, номер 5.5: Как устроен компьютер

Рассмотрим первый вариант кодирования:

• А — 1
• И — 01
• С — 001
• Т — 000

Проверка на префиксность:

Код является префиксным, если ни одно кодовое слово не является началом другого.

• Слово «1» (для А) не является началом слов «01», «001», «000», так как они начинаются с «0».
• Слово «01» (для И) не является началом слов «001» или «000», так как после первого нуля в «01» идёт единица, а в других — ноль.
• Слово «001» (для С) не является началом слова «000» (для Т), так как третья цифра различается (1≠0).
• Слово «000» (для Т) не является началом других слов.

Таким образом, Код 1 является однозначно декодируемым .

Оценка эффективности:

Частоты букв: f(А)>f(С)>f(И)>f(Т).

Длины кодовых слов в Коде 1: L(А)=1, L(И)=2, L(С)=3, L(Т)=3.

Здесь самой частой букве «А» присвоен самый короткий код (длина 1). Это хорошо. Однако букве «С», которая встречается чаще, чем «И» и «Т», присвоен код длиной 3, такой же, как у самой редкой буквы «Т». Букве «И» (второй по редкости из трёх оставшихся) присвоен код длиной 2. Это не оптимально, так как более частая буква «С» имеет такую же длину кода, как и самая редкая «Т», а менее частая «И» имеет более короткий код.

Рассмотрим второй вариант кодирования:

• А — 101
• И — 11
• С — 0
• Т — 100

Проверка на префиксность:

• Слово «0» (для С) не является началом слов «101», «11», «100», так как они начинаются с «1».
• Слово «11» (для И) не является началом слов «101» или «100», так как вторая цифра в «11» — это «1», а в других — «0».
• Слово «101» (для А) не является началом слова «100» (для Т), так как третья цифра различается (1≠0).
• Слово «100» (для Т) не является началом других слов.

Таким образом, Код 2 также является однозначно декодируемым .

Оценка эффективности:

Длины кодовых слов в Коде 2: L(С)=1, L(И)=2, L(А)=3, L(Т)=3.

В этом коде самой короткой стала буква «С» (код «0»), а самой длинной — буква «А» (код «101»). Поскольку по условию буква «А» встречается чаще всего, присвоение ей самого длинного кода приведёт к увеличению общей длины сообщения. Это крайне невыгодно.

Нам нужно выбрать код, который даст наименьшую длину сообщения при заданных частотах: f(А)>f(С)>f(И)>f(Т).

Давайте сравним среднюю длину кода для обоих вариантов, используя условные веса частот. Пусть f(А)=4, f(С)=3, f(И)=2, f(Т)=1 (сохраняем порядок частот).

Для Кода 1: L_avg1=4·1+2·2+3·3+1·3/4+2+3+1=4+4+9+3/10=20/10=2 (Примечание: здесь мы подставили частоты в порядке А, И, С, Т согласно коду, но важно правильно сопоставить буквы и частоты. Давайте пересчитаем аккуратно.) Правильное сопоставление для Кода 1: - А (частота 4): длина 1 -> вклад 4×1=4 - И (частота 2): длина 2 -> вклад 2×2=4 - С (частота 3): длина 3 -> вклад 3×3=9 - Т (частота 1): длина 3 -> вклад 1×3=3 Сумма весов: 4+2+3+1=10. Общая длина: 4+4+9+3=20. Средняя длина: 20/10=2.

Для Кода 2: - А (частота 4): длина 3 -> вклад 4×3=12 - И (частота 2): длина 2 -> вклад 2×2=4 - С (частота 3): длина 1 -> вклад 3×1=3 - Т (частота 1): длина 3 -> вклад 1×3=3 Сумма весов: 10. Общая длина: 12+4+3+3=22. Средняя длина: 22/10=2.2.

Как видно из расчета, Код 1 дает меньшую среднюю длину кода (2 против 2.2). Это происходит потому, что в Коде 1 самой частой букве «А» присвоен самый короткий код (длина 1), что критически важно для минимизации общего объема данных. В Коде 2 самой частой букве «А» присвоен один из самых длинных кодов (длина 3), что резко увеличивает размер сообщения.

Хотя оба кода являются корректными (однозначно декодируемыми), задача требует выбрать тот, который обеспечивает наименьшую длину сообщения . Следовательно, следует выбирать Код 1.