Какова лучшая схема энтропийного кодирования для сжатия символов с известным распределением вероятностей?

Question

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

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

Ответ должен указывать не только на схему сжатия, но и на реализациюэта схема кодирования.

Answer 1

@ conradlee: re "В каких случаях арифметическое кодирование лучше, чем кодирование Хаффмана?" С точки зрения сжатия почти всегда. Если у вас есть символ S с вероятностью Ps, то идеальным числом битов для его кодирования, bs, является -log (Ps) / log (2). Например, если Ps равно 1/3, то bs равно ~ 1,585 бит. С Хаффманом у вас есть для округления в большую или меньшую сторону до ближайшего целого числа битов (поэтому степень сжатия будет уменьшаться). Арифметическое кодирование сохранит его с дробным числом битов.

Answer 2

Для общего кодирования без потерь с известным распределением вероятностей, кроме кодирования Хаффмана, другой «учебник» отвечает: арифметическое кодирование .

На практике существует множествореализации.См. эти универсальные кодеры .У каждого свои свойства.Без дополнительной информации мы не сможем дать вам более точный ответ.