Адаптивный Хаффман (FKG) против Хаффмана на средней длине

Question

Я пробовал много примеров и не могу понять, почему, казалось бы, правильный FKG дает более высокую среднюю длину, чем простой хаффман. Это нормально?

При построении кодов на aabcdad мы получаем:

1. Адаптивный Хаффман: a = 0, d = 10, c = 111, b = 1101
2. Простой Хаффман: а = 0, д = 10, с = 110, д = 111

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

Очевидно, что средняя длина для простого кодирования ниже.

Главный вопрос: является ли адаптивное кодирование Хаффмана оптимальным с точки зрения средней длины кода?

Пример адаптивного построения здесь

Пример простого построения здесь

Answer 1

У меня есть ответ.

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

Тем не менее, Adaptive Huffman иногда может выводить более длинные коды и теоретически не может быть лучше, чем Huffman (classic), его большим преимуществом является только один проход данных, а также нет необходимости хранить все дерево.