Обзорный практикум по содержанию ФГОС ко второй паре 11 класса
На n различных букв нужно по log₂n битов, округлённым вверх: на 5 букв — 3 бита, потому что 2² = 4 мало, а 2³ = 8 хватает. Запас неиспользованных слов — 8 − 5 = 3.
При совпадающих весах дерево можно построить по-разному, и коды отдельных букв получатся разными, — а сумма нет. Поэтому спрашивают именно её, а не «какой код у буквы Б».
Ни одно кодовое слово не должно быть началом другого. Тогда поток читается однозначно, слева направо, и разделители не нужны.
0, 10, 110 — годится. 0, 01 — нет:
0 есть начало 01.
Читать слева направо, накапливая биты, пока накопленное не совпадёт с кодовым словом; совпало — записать букву и начать заново. Возвращаться назад не приходится — за это и отвечает условие Фано.
K · (log₂n вверх) − (сумма слияний), где K — длина сообщения в буквах. Если частоты букв близки, дерево выходит ровным и выигрыша нет вовсе: Хаффман помогает там, где буквы встречаются по-разному часто.
Обзорный практикум по содержанию ФГОС ко второй паре 11 класса
На n различных букв нужно по log₂n битов, округлённым вверх: на 5 букв — 3 бита, потому что 2² = 4 мало, а 2³ = 8 хватает. Запас неиспользованных слов — 8 − 5 = 3.
При совпадающих весах дерево можно построить по-разному, и коды отдельных букв получатся разными, — а сумма нет. Поэтому спрашивают именно её, а не «какой код у буквы Б».
Ни одно кодовое слово не должно быть началом другого. Тогда поток читается однозначно, слева направо, и разделители не нужны.
0, 10, 110 — годится. 0, 01 — нет:
0 есть начало 01.
Читать слева направо, накапливая биты, пока накопленное не совпадёт с кодовым словом; совпало — записать букву и начать заново. Возвращаться назад не приходится — за это и отвечает условие Фано.
K · (log₂n вверх) − (сумма слияний), где K — длина сообщения в буквах. Если частоты букв близки, дерево выходит ровным и выигрыша нет вовсе: Хаффман помогает там, где буквы встречаются по-разному часто.