Сочетание низких частот в кодировании Хаффмана
Я готовлюсь к своему последнему экзамену и в настоящее время сосредотачиваюсь на кодировании Хаффмана.
Как я понимаю... вы берете две самые низкие частоты и объединяете их... строите дерево снизу вверх.
Мой вопрос... что вы делаете, когда 3 или более частот одинаковы? Имеет ли значение, какие два вы выбираете для объединения? Вы объединяете их всех?
Имеет ли значение порядок букв? Как очевидно после того, как вы выполните кодирование, буквы могут отличаться в зависимости от того, что вы выберете.
Я нашел несколько учебных пособий и примеров в Интернете, но ни один из них не демонстрирует этот сценарий. Любой совет приветствуется. Спасибо!
ПРИМЕР:
Скажем, мне дан массив букв как таковой: [a,b,c,d,e,f,g] со следующими частотами:
a = 3 b = 2 c = 6 d = 2 e = 4 f = 2 g = 4
2 ответа
Просто выберите 2. Любой 2. Неважно, какие 2 вы выберете. Единственная значимая метрика здесь - это их частота, и все частоты одинаковы, независимо от того, какие 2 вы выберете.
Вы не можете объединить все 3 из них.
Помните, что дерево Хаффмана - это двоичное дерево, потому что каждая ветвь соответствует битам: 0 а также 1, Для дерева Хаффмана не имеет смысла иметь 3 ветви, потому что у вас нет 3 различных типов битов.
Вы не можете объединить их все. Объедините два и повторите. Если вы объединяете их все, вам нужна совершенно новая логика, например троичная, четырехугольная и т. Д.