Максимальное количество разных чисел, сжатие Хаффмана

Question

Я хочу сжать многие 32-битные числа, используя сжатие Хаффмана.

Каждое число может появляться несколько раз, и я знаю, что каждое число будет заменено некоторыми битовыми последовательностями:

111 010 110 1010 1000 и т.д ...

Теперь вопрос: сколько разных чисел можно добавить в дерево Хаффмана до того, как длина двоичной последовательности превысит 32 бита?

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

Answer 1

Похоже, вы понимаете принцип кодов префиксов.

Многие люди (смущенно) называют все коды префиксов "кодами Хаффмана".

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

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

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

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

Например, некоторые программы сжатия используют коды Фибоначчи (разновидность универсального кода) и всегда ассоциируют наиболее часто встречающийся символ с битовой последовательностью «11», следующий наиболее часто встречающийся символ с битовой последовательностью«011», следующий за «0011», следующий за «1011» и т. Д.

Алгоритм Хаффмана создает код, во многих отношениях похожий на универсальный код - оба являются префиксными кодами,Но, как указывает Cyan, алгоритм Хаффмана немного отличается от этих универсальных кодов.Если у вас есть 5 разных символов, дерево Хаффмана будет содержать 5 разных битовых последовательностей - однако точные битовые последовательности, сгенерированные алгоритмом Хаффмана , зависят от точных частот.Один документ может иметь количество символов {10, 10, 20, 40, 80}, что приводит к битовым последовательностям Хаффмана {0000 0001 001 01 1}.Другой документ может иметь количество символов {40, 40, 79, 79, 80}, что приводит к битовым последовательностям Хаффмана {000 001 01 10 11}.Несмотря на то, что обе ситуации имеют ровно 5 уникальных символов, фактический код Хаффмана для наиболее часто встречающегося символа в этих двух сжатых документах сильно отличается - код Хаффмана «1» в одном документе, код Хаффмана «11» в другом документе.Однако, если вы сжали эти документы с помощью кода Фибоначчи, код Фибоначчи для наиболее часто встречающегося символа всегда одинаков - «11» в каждом документе.

В частности, для Фибоначчи первые 33-битовый код Фибоначчи - «31 нулевой бит, за которым следуют 2 однобитных», представляющий значение F (33) = 3,524,578.Таким образом, 3 524 577 уникальных символов могут быть представлены кодами Фибоначчи длиной 32 бита или менее.

Одна из наиболее противоречивых особенностей префиксных кодов заключается в том, что некоторые символы (редкие символы) «сжимаются» в гораздо более длинныебитовые последовательности.Если у вас фактически есть 2 ^ 32 уникальных символа (все возможные 32-битные числа), невозможно получить какое-либо сжатие, если вы заставите компрессор использовать префиксные коды, ограниченные 32 битами или менее.Если у вас фактически есть 2 ^ 8 уникальных символов (все возможные 8-битные числа), невозможно получить какое-либо сжатие, если вы заставите компрессор использовать префиксные коды, ограниченные 8 битами или менее.Позволяя компрессору расширять редкие значения - использовать более 8 бит для хранения редкого символа, который, как мы знаем, можно хранить в 8 битах - или использовать более 32 бит для хранения редкого символа, которыймы знаем, что может храниться в 32 битах - это освобождает компрессор от использования менее 8 бит - или менее 32 бит - для хранения более частых символов.

В частности, если я использую коды Фибоначчи для сжатия таблицы значений,где значения включают все возможные 32-битные числа, нужно использовать коды Фибоначчи длиной до N бит, где F (N) = 2 ^ 32 - решение для N я получаю N = 47 бит для наименее часто используемого 32-разрядного символа.

Answer 2

Хаффман - это сжатие, а сжатие требует "перекошенного" распределения для работы (при условии, что мы говорим о нормальном, порядок-0, энтропия).

Худшая ситуация с глубиной дерева Хаффмана - это когда алгоритмсоздает вырожденное дерево, т.е. только с одним листом на уровень.Такая ситуация может возникнуть, если распределение выглядит как серия Фибоначчи.

Следовательно, наихудшая последовательность распределения выглядит следующим образом: 1, 1, 1, 2, 3, 5, 8, 13, ....

В этом случае вы заполняете полное 32-битное дерево только 33 различными элементами.

Обратите внимание, однако, что для достижения 32-битной глубины только с 33 элементами, самый многочисленный элементдолжно появиться 3 524 578 раз.

Следовательно, поскольку при суммировании всех чисел Фибоначчи вы получаете 5 702 886, вам нужно сжать не менее 5 702 887 чисел, чтобы начать иметь риск невозможности представить их с помощью 32-битного дерева Хаффмана.

При этом использование дерева Хаффмана для представления 32-битных чисел требует значительного объема памяти для вычисления и обслуживания дерева.

[ Редактировать ] Более простой формат, называемый «логарифмическим приближением», дает почти одинаковый вес всем символам.В этом случае требуется только общее количество символов.

Он вычисляется очень быстро: скажем, для 300 символов некоторые из них будут использовать 8 бит, а другие - 9 бит.Формула для определения количества каждого типа:

9 бит: (300-256) * 2 = 44 * 2 = 88;8 бит: 300 - 88 = 212

Затем вы можете распределить числа по своему желанию (желательно наиболее часто используемые с использованием 8 бит, но это не важно).

Эта версия масштабируется до32 бита, что означает отсутствие ограничений.