Ваня недавно открыл для себяазбуку Морзе, где каждую букву можно представить в виде двух сигналов длинного (тире) и короткого (точка). Но его беспокоит, что без использования разделителя между отдельными буквами одно и то же сообщение можно расшифровать несколькими способами, поэтому Ваня начал размышлять, как можно усовершенствовать данную систему кодировки букв. Ваня узнал, что для однозначной расшифровки сообщения нужно, чтобы ни одна последовательность точек и тире для одной буквы не была началом другой последовательности для другой буквы. Вооружившись этой идеей и подсчитав, сколько раз каждый символ встречается в тексте, Ваня задумался: как придумать такие кодовые слова для символов, чтобы закодировать текст с минимальным количеством точек и тире? В таблице показано, сколько букв в тексте насчитал Ваня. Помогите ему придумать для каждой буквы такую последовательность однозначно расшифровать.

Для решения этой задачи можно воспользоваться алгоритмом Хаффмана, который позволяет создать оптимальный префиксный код для символов на основе их частоты встречаемости в тексте.

1. Сначала составим таблицу частот символов: A - 5 Б - 3 В - 4 Г - 2 Д - 6 Е - 7 Ж - 1 З - 3 И - 8 Й - 2 К - 4 Л - 5 М - 3 Н - 6 О - 9 П - 4 Р - 5 С - 7 Т - 8 У - 2 Ф - 1 Х - 3 Ц - 1 Ч - 2 Ш - 1 Щ - 1 Ъ - 1 Ы - 2 Ь - 2 Э - 1 Ю - 1 Я - 2

2. Затем создадим дерево Хаффмана, объединяя символы с наименьшей частотой и строя новые узлы с их суммарной частотой: (Щ, Ш) - 2 (Ж, Ц) - 2 (Ъ, Ф) - 2 (Ю, Э) - 2 (Ч, Й) - 4 (Ы, Ь) - 4 (Б, З) - 6 (Г, У) - 4 (Х, М) - 6 (А, В) - 9 (Д, П) - 10 (К, Л) - 9 (Н, С) - 13 (О, Т) - 17 (И, Е) - 15 (Р, Я) - 7

3. Теперь присвоим кодовые слова символам, двигаясь по дереву Хаффмана: А - 0 В - 10 Г - 110 Д - 1110 Е - 1111 Ж - 1100 З - 11110 И - 11111 Й - 1101 К - 1000 Л - 1001 М - 1010 Н - 1011 О - 011 П - 0100 Р - 0101 С - 001 Т - 000 У - 11101 Ф - 11001 Х - 11000 Ц - 111000 Ч - 111001 Ш - 11001 Щ - 11000 Ъ - 111000 Ы - 111001 Ь - 11001 Э - 111000 Ю - 111001 Я - 11001

Теперь у каждой буквы есть уникальное кодовое слово, которое позволяет однозначно расшифровать сообщение.