Confused о Хаффмана Деревья

Question

A quick tutorial on generating a huffman tree

Confused о Хаффмана деревьев. В конце этой ссылки выше показано дерево с двумя элементами слева, а затем завершенное дерево. Я смущен тем, что он разветвлен. Существует ли конкретный способ, чтобы дерево хаффмана было разветвленным?

Например, 57: * с его правым дочерним элементом 35: * разветвляется вправо. Может ли это быть 35 разветвленных слева с 22 разветвленной вправо? Кроме того, почему не было 22: * в паре с 15: 4 - он просто спарен с 20: 5, чтобы создать новое дерево.

От первоначальных обвинений кажется, что дерево не нужно балансировать или иметь какой-либо конкретный порядок, отличный от того, что частоты листа дополняют значение родительского узла. Могут ли два человека, создающих дерево huffman с одинаковыми данными, получить разные значения кодировки?

Answer 1

Ключ к деревьев Хаффмана заключается в следующем:

Сортировать этот список по частоте и сделать две самые низкие элементы в листьях

Если у вас есть более двух элементов, которые имеют самая низкая частота (например, 3,4,4 ...), любые два будут делать (3 и любой из 4s - не два 4s). Кроме того, не важно, какой из этих наименьших элементов присваивается 0 и который равен 1. Эти два факта позволяют разным, но действительным законам Хаффмана возникнуть из одних и тех же данных.

Дерево Хаффмана должно быть сбалансировано по частотам, а не по количеству узлов. Таким образом, в следующем сбалансирован:

(100 (50 (25 (12 (12 1))))) 

и это не является:

(((100 50) 25) ((12 12) 1))) 

Конкретно в вашем вопросе, 15 в паре с 20, а не 22, потому что 15 и 20 представляют собой две нижние остальные значения (оба ниже 22). Либо разветвление (левое или правое) было бы прекрасным, если бы оно было согласованным (всегда меньшим - левым или всегда меньшим - правильным, в рамках одного и того же алгоритма, чтобы кодировка могла быть восстановлена ​​на другом конце).

Answer 2

Все объяснено на странице. 22: * не было сопряжено с 15: 4, потому что на каждом шаге объединяются два узла с наименьшими элементами. Это создает уникальный порядок.

Коды Хаффмана могут быть разными (если у вас есть несколько значений с одинаковой частотой или обмениваются 0 и 1 изображением слева/справа), но длина huffman не может быть.

Ветвление влево/вправо - это вопрос о том, как рисовать дерево или представлять его графически, поэтому это не имеет значения.

Answer 3

Должности до сих пор являются неправильными и вводящими в заблуждение: выбор листьев с равными весами делает вопрос, и они действительно меняют, насколько хорошо они сжимают данные.

Вот счетчик пример, который демонстрирует, как различные варианты приводят к различной степени сжатия: ABBBCCCDDDDEEEEEEEE

А: 1, В: 3, С: 3, D: 4, Е: 8. Первый шаг: возьмите A и B, чтобы сформировать узел с весом 4. Второй шаг:

Если вы вновь созданный узел на первом этапе с C, то вы получите (19 (11 (7 (4 (1-A) (3-B)) (3-C)) (4-D)) (8-E)) который дает 37 битов сжатых данных.

Если, с другой стороны, вы берете D, у которого также есть вес 4, вместо вновь созданного узла вы получаете (19 (11 (4 (1-A) (3-B)) (7 (3-C) (4-D))) (8-E)), который дает 41-битные сжатые данные.