Алгоритм Шеннона - Фано

[oleg_549]

У меня преподаватель спрашивает, почему алгоритм Шеннона-Фано делит алфавит на лево и право, а не лево и право, и середину, например. Я говорю, что это традиционно так устоялось, в связи с бинарным кодированием, этот метод наиболее эффективен для вычислительных машин. Он говорит: "и что, так, а почему именно так". Помогите пожалуйста, я немного не понимаю что от меня требуется

Также он сказал, что в коде у меня это есть, поэтому вот код:

Используется синтаксис Python

def generirovat_kody(self, uzly):
        # проверяем, состоит ли список узлов более чем из одного элемента
        if len(uzly) > 1:
            # суммируем вероятности всех узлов, чтобы найти общую вероятность
            vsego_veroyatnostey = sum(uzel.veroyatnost for uzel in uzly)
            # инициализируем переменную для хранения наилучшего отклонения (разницы сумм вероятностей групп после разделения)
            luchshee_otkloenenie = vsego_veroyatnostey
            # инициализируем переменную для хранения индекса, при котором достигается наилучшее разделение
            luchshiy_indeks = 0

            # для подсчета текущей суммы вер.
            tekushchaya_summa = 0
            #  ищем  место для разделения списка
            for i, uzel in enumerate(uzly):
                # прибавляем вероятность текущего узла к текущей сумме
                tekushchaya_summa += uzel.veroyatnost
                # вычисляем разницу между суммами вероятностей двух групп после разделения
                razlichie = abs((vsego_veroyatnostey - tekushchaya_summa) - tekushchaya_summa)
                # если найденное различие меньше текущего наилучшего, обновляем наилучшее отклонение и индекс
                if razlichie < luchshee_otkloenenie:
                    luchshee_otkloenenie = razlichie
                    luchshiy_indeks = i + 1

            # разделяем список узлов на две группы по найденному индексу
            levo = [uzel for uzel in uzly[:luchshiy_indeks]]
            pravo = [uzel for uzel in uzly[luchshiy_indeks:]]

            # присваиваем коды узлам в левой группе
            for uzel in levo:
                uzel.kod += '0'
            # присваиваем коды узлам в правой группе
            for uzel in pravo:
                uzel.kod += '1'

            #  применение функции к обеим группам
            self.generirovat_kody(levo)
            self.generirovat_kody(pravo)

[mihaild]

Странный вопрос. Важно, что делят на две части. Потому что мы строим бинарный префиксный код, а в нём первый символ делит на две группы. Если бы строили троичный код, то делили бы на три части.
Называть эти части можно как угодно. Традиционно называют левой и правой (потому что дерево рисуют по вертикали, и левая ветка соответствует нулю, правая единице), но можно было бы назвать и зеленой и сиреневой, или ботинком и тапочком.

[sergey zhukov]

Вопрос, видимо, в том, почему именно бинарный код используем, а не троичный, например. Наверное, потому, что бинарный код - это простейшее, предельно возможное "цифровое" представление информации. Троичный и более высокие коды приближаются к аналоговому представлению.

[MGM]

Где-то в седые 80е ходила мулька, что троичный код - самый оптимальный для вычислений. И что кто-то это даже доказал. Видимо, кто-то из группы создателей троичного процессора на Мехмате.

[mihaild]

Не для вычислений, а для представления. Если для каждого возможного значения каждого разряда мы заводим по лампочке, то минимальное число лампочек понадобится в троичной системе. Например для чисел от 0 до $2^{20}$ нам понадобится 20 двоичных разрядов (40 лампочек), но только 13 троичных (39 лампочек).

[juna]

MGM в сообщении #1626033 писал(а):

Где-то в седые 80е ходила мулька, что троичный код - самый оптимальный для вычислений. И что кто-то это даже доказал. Видимо, кто-то из группы создателей троичного процессора на Мехмате.

Если память не изменяет: Горбатов. Основания дискретной математики