Деревья Хаффмана для недвоичных алфавитов?

Question

Существует ли простое обобщение деревьев кодирования Хаффмана для ситуаций, когда результирующий алфавит не является двоичным? Например, если бы я хотел сжать какой-то текст, написав его в троичной форме, я все равно мог бы создать систему кодирования без префиксов для каждого символа, который я пишу. Будет ли прямое обобщение конструкции Хаффмана (с использованием k-арного дерева, а не бинарного дерева) работать правильно и эффективно? Или эта конструкция приводит к крайне неэффективной схеме кодирования?

Answer 1

Алгоритм все еще работает, и он все еще прост - фактически Википедия имеет краткую ссылку на n-арное кодирование Хаффмана со ссылкой на оригинальную статью Хаффмана в качестве источника.

Мне, однако, приходит в голову, что точно так же, как Хаффман немного неоптимален, поскольку он выделяет целое число бит для каждого символа (в отличие, например, Арифметическое кодирование ), троичное Хаффман должно быть немного more suboptimal, потому что ему нужно выделить целое число trits . Не ограничитель показа, особенно для 3, но он показывает, что n-арный Хаффман будет отставать от других алгоритмов кодирования при увеличении n.

Answer 2

В качестве эмпирического теста я построил двоичные и тройные деревья Хаффмана для распределения тайлов Скрэббла.

Энтропия распределения показывает, что нельзя получить лучше, чем 4,37 бит на букву.

Бинарное дерево Хаффмана использует в среднем 4,41 бит на букву.

Тройное дерево Хаффмана использует в среднем 2,81 тритов на букву, плотность информации которого равна 4,45 битам на букву.