Кодирование Хаффмана в основном использует битовые строки переменной длины для представления токенов (обычно это символы с несколькими исключениями). Чем более распространен токен, тем короче его длина в битах, и он (обычно) динамический при обработке потока.
Обычно есть два специальных токена, ESCAPE и END-STREAM.
Кодирование поддерживает словарь, который является в основном поиском битовых последовательностей для получения токена. Первоначально он содержит только два специальных токена.
Начальные битовые последовательности для ESCAPE и END_STREAM могут быть 0 и 1 (что на самом деле не имеет значения в начале). Когда кодировщик получает символ, которого нет в словаре, он выводит ESCAPE и токен полной длины, затем добавляет его и назначает новые битовые последовательности на основе частоты всех токенов.
Таким образом, ваш 'N' может привести к выходному потоку:
0 xxxxxxxx
| +- token code for N
+--- ESCAPE
и новый словарь:
ESCAPE:00
END-STREAM:01
N:1
Тогда ваш 'E' может привести к выходному потоку:
0 xxxxxxxx 0 yyyyyyyy
+- token code for E
и новый словарь:
ESCAPE:00
END-STREAM:01
N:10
E:11
Ваш следующий E не приведет к выводу ESCAPE, поскольку он уже находится в словаре, поэтому вы просто выводите его код (11). Это изменит словарь, так как E теперь имеет большее количество. В нашей ситуации это не будет иметь значения, поскольку все символы представляют собой две двоичные цифры, но в более сложном примере длина в битах токена «E» будет сокращена.
Когда прибывает D, выходной поток становится:
0 xxxxxxxx 0 yyyyyyyy 11 0 zzzzzzzz
| +- token code for D
+------ second E
и новый словарь:
ESCAPE:00
END-STREAM:011
N:010
E:11
D:10
Итак, вы можете видеть, что с увеличением количества символов длина битов общих сокращается, а длина необычных увеличивается, обеспечивая вам сжатие. N (или D) в этом случае получает трехзначный код, а E придерживается двухзначного кода, потому что их больше.
Прелесть в том, что вам не нужно хранить словарь вместе с файлом, так как разделы ESCAPE создают его динамически и для распаковки.
Кроме того, поскольку токен END-STREAM НИКОГДА не до конца, его длина в битах продолжает увеличиваться. Аналогично для ESCAPE, хотя в нем все еще много новых персонажей, его длина в битах остается короткой, но, когда новых персонажей не приходит, он испытывает ту же участь, что и END-STREAM.
Наилучшим случаем для (8-битного ASCII) входного потока является файл, содержащий только миллионы одинаковых символов. Это стоит 9 бит для первого символа, затем 1 бит для каждого дополнительного символа, затем 2 бита для конца потока. Это быстро приближается к степени сжатия 1 к 8 (97,5%).
Наихудший случай - ровно один из каждого символа, который стоит 9 бит на символ плюс конец потока - это фактически расширяет поток на 12,5%.