Код Хаффмана и почему он такой классный

Жил-был Дэвид Хаффман. И вот подумал он: если у нас одни символы встречаются чаще других, то почему мы используем одинаковое количество бит для каждого?

Подумано - написано: подсчитав, сколько каких символов используется, мы можем построить бинарное дерево, где тем дальше от корня, чем реже встречается символ. Почему бинарное, и зачем вообще?

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

Понятие "таблица Хаффмана" же - это просто соотношение символа к его коду Хаффмана, чтобы не нужно было для каждого символа перебирать все дерево в поисках. Обычно - простая хэшмапа, хоть в некоторых ситуациях и можно выдумать что-то поинтереснее (например - LUT, который имеют O(1) доступ, отлично применимы для ascii; где-то даже был пост об этом).

Конечно, отправляя сжатое таким образом сообщение, необходимо другой стороне еще и таблицу отправить, чтобы принимающий понимал, как мы то сообщение кодировали вообще. Иногда, сообщение+таблица могут в сумме нивелировать выигрыш от сжатия, хоть для достаточно больших сообщений (что случается чаще всего) разница не является столь великой.