Эффективность Huffman Coding ограничена?

Question

Моя проблема в том, что у меня более 100 000 различных элементов, и, насколько я понимаю, Хаффман работает, присваивая наиболее распространенному элементу код 0, а следующие 10, следующие 110, 1110, 11110 и так далее.У меня вопрос: если код для n-го элемента имеет длину n-бит, то, конечно же, после того, как я передал 32-й член, будет ли более эффективно использовать пространство, чтобы просто отправлять 32-разрядные типы данных такими, как они есть, например, int?Я что-то пропустил в методологии?

Большое спасибо за любую помощь, которую вы можете предложить.Моя текущая реализация работает с помощью

code = (code << 1) + 2;

для генерации каждого нового кода (что кажется правильным!), Но единственный способ, которым я мог бы кодировать более 100 000 элементов, - это использовать int [] во временном порядке.новый тип данных, где получить доступ к значению, которое мы будем читать из массива int как один непрерывный длинный символ ... это не так эффективно с точки зрения пространства, как просто передача 32-битного int?Или это скорее случай использования Хаффмана с его префиксными кодами и возможностью однозначно определять каждое уникальное значение в непрерывном битовом потоке?

Спасибо

Answer 1

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

Не могли бы вы рассказать нам немного больше об этих более 100 000 различных элементов, которые вы упомянули?

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

То, что вы описываете, представляет собой особый вид префиксного кода: унарное кодирование . Другой популярный вариант унарной системы кодирования назначает элементы в порядке частоты фиксированным кодам «1», «01», «001», «0001», «00001», «000001» и т. Д.

Некоторые программы сжатия используют другой популярный префиксный код: Elias gamma coding . Гамма-кодирование Elias присваивает элементы в порядке частоты фиксированному набору кодовых слов

1
010
011
00100
00101
00110
00111
0001000
0001001
0001010
0001011
0001100
0001101
0001110
0001111
000010000
000010001
000010010
...

32-е гамма-кодовое слово Elias имеет длину около 10 битов, примерно вдвое меньше 32-го унарного кодового слова. 100-тысячное кодовое слово Elias gamma будет иметь длину около 32 бит.

Если вы посмотрите внимательно, то увидите, что каждое кодовое слово Elias gamma можно разделить на 2 части - первая часть более или менее знакома с унарным кодом, с которым вы знакомы. Этот унарный код сообщает декодеру, сколько еще битов следует в оставшейся части этого конкретного кодового слова Elias gamma.

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

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

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

Алгоритм Хаффмана не очень хорошо сжимается, когда у нас действительно есть 100 000+ уникальных элементов - издержки таблицы частот Хаффмана становятся настолько большими, что мы часто можем найти какой-то другой «неоптимальный» префиксный код, который фактически дает лучшее сетевое сжатие. Или, может быть, какой-то совершенно другой алгоритм сжатия данных может работать даже лучше в вашем приложении.

Реализация Huffword, кажется, работает с около 32 000 уникальных элементов, но подавляющее большинство реализаций кода Хаффмана, которые я видел, работают с примерно 257 уникальными элементами (256 возможных значений байтов и индикатор конца текста).

Вы можете подумать о том, чтобы как-то сохранить ваши данные на диске в каком-то необработанном «несжатом» формате. (Имея более 100 000 уникальных элементов, вы неизбежно будете хранить многие из этих элементов в 3 или более байтах). Эти 257-значные реализации сжатия Хаффмана смогут сжать этот файл; они повторно интерпретируют байты этого файла как 256 различных символов.

У меня вопрос: если код для n-го элемента имеет длину n бит, тогда конечно, после того, как я прошел 32-й срок, это более эффективное пространство для только что отправил 32-битные типы данных, как они есть, например, int? Я что-то пропустил в методологии?

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

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

Answer 2

Ваше понимание немного неверно - взгляните на http://en.wikipedia.org/wiki/Huffman_coding. И вам необходимо упаковать закодированные биты в машинные слова, чтобы получить сжатие - закодированные данные Хаффмана лучше всего рассматривать как поток битов.