- Главная
- Вопросы и ответы
- Марина недавно изучила алгоритм Хаффмана. Она помнит, что идея, положенная в основу кодировании Хаффмана, основана на частоте появления символа в последовательности. Символ, который встречается в последовательности чаще всего, получает очень маленький код, а символ, который встречается реже всего, получает, наоборот, очень длинный код. Марина решила поупражняться в кодировании на примере своей любимой скороговорки: флюорографист флюорографировал флюорографистку Определите, сколько бит будет содержать скороговорка после кодирования. Не забудьте, что пробелы также кодируются, как и все остальные символы (буквы). Слова разделены одинарными пробелами, перед первым словом и после последнего пробелов нет. В качестве ответа выведите одно целое число — количество бит в сжатой строке, например, 1.
Марина недавно изучила алгоритм Хаффмана. Она помнит, что идея, положенная в основу кодировании Хаффмана, основана на частоте появления символа в последовательности. Символ, который встречается в последовательности чаще всего, получает очень маленький код, а символ, который встречается реже всего, получает, наоборот, очень длинный код. Марина решила поупражняться в кодировании на примере своей любимой скороговорки: флюорографист флюорографировал флюорографистку Определите, сколько бит будет содержать скороговорка после кодирования. Не забудьте, что пробелы также кодируются, как и все остальные символы (буквы). Слова разделены одинарными пробелами, перед первым словом и после последнего пробелов нет. В качестве ответа выведите одно целое число — количество бит в сжатой строке, например, 1.
Частота Буквы Код
7 о 11
7 р 101
6 ф 100
4 а 0111
4 л 0110
3 г 0101
3 и 0100
3 ю 00111
3 _ 00110
2 с 00101
2 т 00100
1 в 00011
1 к 00010
1 у 00001
Итого: 7*2+7*3+6*3+4*4+4*4+3*4+3*4+3*5+3*5+2*5+1*5+1*5+1*5 = 164
Главное помнить, что структура кода префиксная, т.е код любого символа не должен совпадать с началом другого. Удачи!