Как Хаффман при кодировании выяснил свойство уникальности кодов

Question

Я только что прочитал это :

Вот тут-то и приходит действительно умная идея, называемая кодированием Хаффмана!Идея состоит в том, что мы представляем наших персонажей (например, a, b, c, d, ...) с помощью кодов, подобных

a: 00
b: 010
c: 011
d: 1000
e: 1001
f: 1010
g: 1011
h: 1111

Если вы внимательно посмотрите на них, вы заметите что-то особенное!Дело в том, что ни один из этих кодов не является префиксом любого другого кода.Поэтому, если мы запишем 010001001011, мы увидим, что это 010 00 1001 011 или baec!Не было никакой двусмысленности, потому что 0 и 01 и 0100 ничего не значат.

Я понимаю суть этого, но я не понимаю (а)как это выяснили, и (б) как вы знаете, как это работает, или (в) именно то, что это значит.В частности, эта строка описывает это:

Итак, если мы запишем 010001001011, мы увидим, что это 010 00 1001 011 ....

Я вижу, что этокоды, но я не понимаю, как вы знаете, не читать его как 0100 01 0010 11.Я вижу, что эти значения на самом деле не являются кодами в таблице.Тем не менее, я не понимаю, как вы могли бы понять это!Я хотел бы знать, как это обнаружить.Если бы я пытался повозиться с подобными кодами и битами, я бы сделал следующее:

1. Придумайте набор кодов, например 10 100 1000 101 1001
2. Попробуйте написать несколько примеровкодов.Так что, может быть, пример просто объединяет коды в указанном выше порядке: 1010010001011001.
3. Посмотрим, смогу ли я разобрать коды.Так что 10 или ой, нет 101 также ... Darnit, ну, может быть, я могу добавить приоритет к разбору кода, и поэтому 10 имеет более высокий приоритет, чем 101.Это заставляет меня 10 100 1000 10 x Нет, что последние 10 должны быть 101. Dangit.

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

Я не могу представить, как они выяснят, что эти коды в кодировке Хаффмана могут быть уникально проанализированы (я до сих пор не понимаю, как это происходит на самом делеправда, мне пришлось бы выписать несколько примеров, чтобы увидеть это, или, ... это часть вопроса, как увидеть это правда, как это доказать даже).Хотите знать, можно ли объяснить более подробно, как это работает, и как это было обнаружено (или как открыть что-то похожее на это самостоятельно).

Answer 1

Код Хаффмана работает путем размещения данных в дереве.Если у вас есть двоичное дерево, вы можете связать каждый лист с кодом, сказав, что левый дочерний элемент соответствует биту в 0, а правый дочерний - 1. Путь, который ведет от корня к листу, соответствует коду в ненеоднозначный способ.

Это работает для любого дерева, а свойство префикса основано на том факте, что лист является терминальным.Следовательно, вы не можете перейти к листу (иметь код), передавая другой лист (имея префикс другого кода).

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

Существует несколько алгоритмов для построения такого дерева.Например, предположим, что у вас есть набор элементов, которые вы хотите закодировать, скажем a..f.Вы должны знать вероятности появления каждого элемента благодаря модели источника или анализу фактических значений (например, путем анализа файла в коде).

Тогда вы можете:

1. сортировка элементов по вероятности
2. извлечение двух элементов с наименьшей вероятностью
3. удаление этих элементов, группировка их в новом составном узле и назначение одного элемента левому потомку (код0), а другой - справа (код 1).
4. Вероятность составного узла является суммой отдельных вероятностей и вставьте этот новый узел в список отсортированных элементов.
5. Перейти к 2в то время как количество элементов> 1

Для предыдущего дерева оно может соответствовать набору вероятностей

a (0,5) b (0,2) c (0,1) d (0,05) e (0,05) f (0,1)

Затем вы выбираете предметы с наименьшей вероятностью (d и e), группируете их в составном узле (de) и получаете новый список

a (0,5) b (0,2) c (0,1) (де) (0,1) f (0,1)

А тПоследовательные списки предметов могут быть

a (0,5) b (0,2) c (de) (0.2) f (0.1)

a (0.5) b (0.2) (c (de)) f (0,3)

a (0,5) b ((c (de)) f) (0.5)

a (b (((c (de)) f)) 1,0

Таким образом, свойство префикса застраховано строительством.