Math
Код Хаффмана
Очередь частот превращается в дерево префиксного кода. Выберите букву, чтобы увидеть её биты; проходите слияния по шагам.
Что происходит
Каждый шаг объединяет два наименьших веса. Метки 0 и 1 задают код на пути от корня к символу. Выбор буквы выделяет весь этот путь. Меняйте частоты и сравнивайте результат. L — средняя длина кода, H — энтропия. Хаффман минимизирует L среди двоичных префиксных кодов отдельных символов и при L > H. Равенство достигается, когда вероятности имеют вид 2^(-k). Показанный объём в битах не учитывает таблицу кодов и заголовки файла.
Уравнения модуля
Уравнения построение: сливаем два самых лёгких узла, n−1 раз; код символа - это его путь от корня, влево 0, вправо 1 L = Σ p(i)·l(i) (бит на символ); H = −Σ p(i)·log₂ p(i); длина кода l(i) равна глубине листа Крафт: у любого префиксного кода Σ 2^(−l(i)) ≤ 1, и любой такой вектор - это дерево; дерево Хаффмана полное, поэтому сумма в точности равна 1 H ≤ L < H + 1 всегда; L = H в точности тогда, когда каждое p(i) есть степень двойки оптимальность проверяется перебором ВСЕХ допустимых по Крафту векторов длин - перебор ничего не знает об алгоритме равные частоты: 2(n − 2^k) символов получают длинный код, где 2^k - наибольшая степень двойки, меньшая n частоты Фибоначчи 1, 1, 2, 3, 5, … дают самое несбалансированное дерево: длины n−1, n−1, n−2, …, 1
