Блог

Существует ли способ вычисления кодирования без префиксов для данного словаря букв и их частот. Похоже на кодирование Хаффмана, но вычисляется динамически — как выглядит функция оптимизации?

Проблема с построением дерева только в позиции i словаря заключается в том, что могут измениться самые низкие частотные буквы, и, следовательно, структура всего дерева.

Да, существует несколько способов динамической генерации кодов без префиксов.

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

Многие другие алгоритмы сжатия данных также генерируют коды без префиксов динамически, намного быстрее, чем любой адаптивный алгоритм Хаффмана, при небольшой потере сжатия — такие как полярные коды или кодирование Энгеля, или универсальные коды, такие как дельта-кодирование Элиаса.

Алгоритм сжатия данных арифметического кодирования технически не является кодом без префиксов, но обычно обеспечивает несколько лучшее сжатие (но выполняется медленнее), чем статическое кодирование Хаффмана или адаптивное кодирование Хаффмана. Арифметическое кодирование обычно реализуется адаптивно, отслеживая частоты всех используемых на данный момент букв. (Многие реализации арифметического кодирования отслеживают еще больше контекста — если предыдущей буквой была «t», она запоминает, что наиболее частой буквой в этом контексте является «h», и точно, насколько частой она была и т.д., Обеспечивая еще лучшее сжатие).