Char Code
==== ====
E 0000
i 0001
y 0010
l 0011
k 0100
. 0101
space 011
e 10
r 1100
s 1101
n 1110
a 1111
Первоначальный текст:
Жуткие глаза видны возле озера
Кодирование:
0000101100000110011100010101101101001111101011111100011001111110100100101
Почему не требуется разделитель в кодировке Хаффмана?
Eerie eyes seen near lake(ну, кроме символа пробела). Но сами персонажи не нуждаются в разделителях. Почему не так?cat cheat for mice≠catch eat form ice. Ваша аналогия ошибочна: каждая буква атомарна; буквы тривиально различимы и неразделимы. Лучшей аналогией будет «Почему вы можете читать рукописный (рукописный) сценарий, когда каждое слово представляет собой одну длинную, извивающуюся, самопересекающуюся строку?», И даже это плохая аналогия, поскольку вы можете посмотреть на рукописное слово ( или даже часть одного) и различать отдельные буквы - тогда как строка в кодировке Хаффмана - это бред, если вы не видите начало.Ответы:
Вам не нужен разделитель, потому что коды Хаффмана - это коды без префиксов (также бесполезно известные как «префиксные коды»). Это означает, что ни одно кодовое слово не является префиксом любого другого кодового слова. Например, кодовое слово «e» в вашем примере равно 10, и вы можете видеть, что никакие другие кодовые слова не начинаются с цифр 10.
Это означает, что вы можете жадно декодировать, читая закодированную строку слева направо и выводя символ, как только увидите кодовое слово. Например, 0, 00 и 000 ничего не кодируют, поэтому вы продолжаете читать биты. Когда вы читаете 0000, это кодирует «E» и, поскольку в коде нет префиксов, вы знаете, что другого кодового слова 0000x нет, поэтому теперь вы можете вывести «E» и начать читать следующее кодовое слово. Опять же, 1 ничего не кодирует, но 10 кодирует «е». Никакие другие кодовые слова не начинаются с «10», поэтому вы можете вывести «e». И так далее.
источник
Полезно представить это как дерево. Вы просто пересекаете дерево, пока не дойдете до листового узла, а затем перезапустите его из корня. Из алгоритма, который выполняет кодирование Хаффмана, вы можете видеть, что такая структура создается в процессе.
https://en.wikipedia.org/wiki/File:HuffmanCodeAlg.png
источник
Никакой код, кроме E, не начинается с 0000. Никакой код, кроме I, не начинается с 0001. И так далее. В крайнем случае, никакой код, кроме e, не начинается с 01. У вас нет таких вещей, как E = 0000, пробел = 000, где вы не знаете, что делать, если найдете три нуля.
Посмотрите на вашу закодированную строку: 0000101100000 ...
Вы читаете первый ноль. Вы знаете, что код - это E, i, y, l, k, запятая или пробел. Следующий ноль означает, что это не k, запятая или пробел, а E, i, y или l. Следующий ноль означает, что это E или я. Следующий ноль означает, что это E. Когда вы знаете, какой это код, вы знаете, что проанализировали все биты для этого кода.
Тогда у вас есть 101100000 ... 1 означает, что у вас есть e, r, s, n или a. Следующий бит равен 0, поэтому код равен e. Опять же, вы закончили с этим персонажем.
источник
Мы не можем использовать разделитель в кодировке Хаффмана, потому что двоичный эквивалент каждой буквы не соответствует префиксному коду любой буквы, поэтому мы можем обойтись даже без использования разделителя.
источник