Как декодировать сообщение из битового потока, закодированного Хаффманом?

Question

Как декодировать сообщение из битового потока, закодированного Хаффманом?Мне не ясна идея Алгоритма Хаффмана.

Насколько я понимаю, предположим, мне выдается текстовое сообщение "Меня зовут XYZ".

Тогда процесс кодирования идет такСпособ: 1. Подсчитайте частоту символов.2. Сортировать частоту по значениям.3. Построить дерево.4. Пройдите по дереву, рассматривая левый край как 0 и правый край как 1, чтобы добраться до нужного символа сообщения.5. Объедините коды, чтобы найти поток битов.

Теперь проблема в том, как найти исходное сообщение из закодированного потока битов?

Я думаю, нам нужно построить дерево Хаффмана.снова.

Но как мне построить дерево Хаффмана из потока битов?

Answer 1

Сообщение не может быть декодировано без оригинального дерева.Поэтому отправляющая сторона должна включить его в сообщение (в случае, если длинные сообщения с небольшим объемом служебной информации будут небольшими), или обе стороны договариваются о дереве перед отправкой сообщений.Тогда процесс обратный: вы читаете по крупицам из потока и дерева обхода.Как только вы нажмете на лист, испустите символ.

Answer 2

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

Для описанного вами двухпроходного алгоритма Хаффмана вы в значительной степени застряли в передаче дерева (в некоторой форме) вместе с данными.

Вы также можете использовать динамическое дерево Хаффмана, где вы (например) начинаете с дерева, как указано в первом параметре выше, но по мере обработки данных передатчик и приемник корректируют дерево в соответствии с наблюдаемыми частотами.Единственная хитрость заключается в том, что каждый символ должен быть закодирован с использованием дерева перед настройкой , затем выполнить настройку, а затем обработать следующий символ.Таким образом, принимающая сторона может синхронизироваться с отправляющей стороной.