Закодировать фразу "Коней на переправе не меняют" методом Шеннона-Фано желательно подробно с построением дерева и описанием как его построили

Предыдущий
вопрос Следующий
вопрос

Метод Шеннона-Фано – это метод кодирования, который основан на принципе разделения последовательности символов на подгруппы с примерно равными вероятностями, после чего каждая подгруппа кодируется некоторой комбинацией битов.

Для кодирования фразы "Коней на переправе не меняют" методом Шеннона-Фано сначала определим вероятность появления каждого символа:

К: 1/23о: 2/23н: 2/23е: 3/23й: 1/23а: 2/23п: 1/23р: 2/23в: 1/23: 1/23м: 1/23я: 1/23т: 1/23ю: 1/23х: 1/23г: 1/23

Затем разделим символы на две примерно равные подгруппы, учитывая их вероятности. Далее для каждой подгруппы выберем префиксный код: для первой подгруппы – 0, а для второй – 1. Повторяем процедуру для каждой подгруппы до тех пор, пока каждый символ не будет закодирован.

Процесс построения дерева кодирования для данной фразы будет следующим:

Разбиваем все символы на две группы: (К, о, е, й, п, в, м, я, т, ю, х, г) и (н, а, р, , )Далее разбиваем каждую из групп на подгруппы и присваиваем им коды:
(К, о, е, й, п, в, м, я) – 0(т, ю, х, г) – 1(н, а, р) – 0( ) – 1Повторяем процесс для каждой из подгрупп и получаем окончательные коды:
К – 00о – 010е – 011й – 100п – 101в – 110м - 1110я – 1111т – 1000ю – 1001х – 1010г - 1011н - 00а - 010р – 011– 11

Таким образом, закодированная фраза "Коней на переправе не меняют" будет выглядеть следующим образом:
00 010 011 100 010 00 101 00 11 010 011 011 1000 11 011 110 00 010 011 1110 00 1011 11 1000 1010 00.