Максимальное количество разных чисел, сжатие Хаффмана
Я хочу сжать многие 32-битные числа, используя сжатие Хаффмана.
Каждое число может появляться несколько раз, и я знаю, что каждое число будет заменено некоторыми битовыми последовательностями:
111 010 110 1010 1000 и т. Д.
Теперь вопрос: сколько разных чисел можно добавить в дерево Хаффмана до того, как длина двоичной последовательности превысит 32 бита?
Правило генерации последовательностей (для тех, кто не знает) заключается в том, что каждый раз, когда добавляется новый номер, вы должны назначить ему наименьшую возможную двоичную последовательность, которая не является префиксом другой.
2 ответа
Вы, кажется, понимаете принцип префиксных кодов.
Многие люди (смущенно) называют все префиксные коды "кодами Хаффмана".
Существует много других видов префиксных кодов - ни один из них не сжимает данные в меньшее количество бит, чем сжатие Хаффмана (если мы пренебрегаем издержками передачи таблицы частот), но многие из них довольно близки (с некоторыми видами данных) и имеют другие преимущества, такие как выполнение намного быстрее или обеспечение некоторой максимальной длины кода ("префиксные коды с ограниченной длиной").
Если у вас большое количество уникальных символов, накладные расходы таблицы частот Хаффмана становятся большими - возможно, какой-то другой префиксный код может дать лучшее сетевое сжатие.
Многие люди, выполняющие сжатие и декомпрессию в аппаратных средствах, имеют фиксированные ограничения на максимальный размер кодового слова - многие алгоритмы сжатия изображений и видео определяют "код Хаффмана с ограниченной длиной".
Самые быстрые префиксные коды - универсальные коды - фактически включают серию битовых последовательностей, которые могут быть сгенерированы заранее без учета фактических частот символов. Программы сжатия, использующие эти коды, как вы упомянули, связывают наиболее частый входной символ с самой короткой битовой последовательностью, следующий наиболее часто встречающийся входной символ со следующей закороченной битовой последовательностью и так далее.
Например, некоторые программы сжатия используют коды Фибоначчи (разновидность универсального кода) и всегда связывают наиболее частый символ с битовой последовательностью "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 . И, таким образом, 3524577 уникальных символов могут быть представлены кодами Фибоначчи размером 32 бита или менее.
Одна из наиболее противоречивых особенностей префиксных кодов заключается в том, что некоторые символы (редкие символы) "сжимаются" в намного более длинные битовые последовательности. Если на самом деле у вас есть 2^32 уникальных символа (все возможные 32 -битные числа), невозможно получить какое-либо сжатие, если вы заставите компрессор использовать префиксные коды, ограниченные 32 битами или менее. Если у вас фактически есть 2^8 уникальных символов (все возможные 8-битные числа), невозможно получить какое-либо сжатие, если вы заставите компрессор использовать префиксные коды, ограниченные 8 битами или менее. Позволяя компрессору расширять редкие значения - использовать более 8 бит для хранения редкого символа, который, как мы знаем, можно сохранить в 8 битах, или использовать более 32 бит для хранения редкого символа, который, как мы знаем, может быть сохранен в 32 бита - это освобождает компрессор от использования менее 8 бит - или менее 32 бит - для хранения наиболее частых символов.
В частности, если я использую коды Фибоначчи для сжатия таблицы значений, где значения включают все возможные 32 -битные числа, необходимо использовать коды Фибоначчи длиной до N бит, где F(N) = 2^32 - решение для N I получить N = 47 битов для наименее часто используемого 32 -битного символа.
Хаффман говорит о сжатии, а сжатие требует "перекошенного" распределения для работы (при условии, что мы говорим о нормальном, порядка 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 бит, что означает, в основном, никаких ограничений.