Адаптивный алгоритм сжатия Хаффмана

Алгоритм меняет дерево сжатия таким образом, чтобы наиболее частые последовательности кодировались наименьшим количесвом символов

пример:
aa bbb cccc ddddd eeeeee fffffffgggggggg

Алгоритмы FGK

В основе - свойство наследования:
Бинарное кодовое дерево имеет свойство наследования, если каждый узел кроме корневого имеет наследников и если узлы могут быть перечислены в порядке неувеличивающихся весов для каждого узла со стороны наследников
Бинарный префиксный ход - код Хаффмана тогда и только тогда, когда кодовое дерево имеет св-во наследования
Преимущества:

• Адаптивность кода
• Нужен 1 проход данных при кодировании
• Код изменяется так, чтобы оставаться оптимальным для текущих оценок

Алгоритм перестроения кодового дерева в процессе передачи исходных сообщений

Начало - корневой узел (0) - узел, в котором заключены оставшиеся $(n - k)$ сообщения

• Для каждого переданного сообщения обе стороны увеличивают веса и пересчитывают кодовое дерево для обеспечения свойства наследования
• В некий момент времени, когда t сообщений уже передано (из которых k - чёткие, k < n), кодовое дерево - кодовое дерево Хаффмана с количеством листьев k + 1, где k - для каждого из k сообщений и один для корневого узла (0)
• Если $t + 1$-ое сообщение - уже известное из k сообщений, алгоритм передаёт $t+1$-ый текущий код, увеличивает соответствующий счётчик и пересчитывает дерево