Как сжимать последовательность бит N бит повторного номера?

Question

Im, пытаясь сжать последовательность неотрицательных чисел, где:

• Диапазон значений каждого числа от 0 до 2^N-1

• Каждое число появляется только один раз (это означает, что это всего 2^N чисел)

  Пример для N = 4:

  [14, 1, 8, 2, 12, 6, 0, 10, 4, 13, 5, 7, 15, 9, 3, 11]

Так обычно каждый номер будет стоить 4 бита, а для 16 номеров нам потребуется использовать 16x4 = 64 бит для их хранения.

В настоящее время я просто подумал, сжимая их, как показано ниже:

• За первые 8 номеров -> Использование 4 бит для хранения каждого из них.
• В течение следующих 4 цифры ---> только 3 бит/каждый
• В течение следующих 2 номера ---> только 2 бита/каждый
• В течение следующих 1 чисел ---> только 1 бит для Это.
• Для последнего, на самом деле его не necesssary хранить (Очевидно, что мы должны знать, что последний номер, если мы знаем, все остальные 15 номеров)

Так сжатый размер данных будет:

Z = 8 * 4 + 4 * 3 + 2 * 2 + 1 * 1 + 1 * 0 = 49 bits 

Коэффициент сжатия составляет около 76%, что довольно хорошо (я думаю).

Но при больших значениях N, отношение, кажется, уменьшается (при N = 2048, отношение только 91%)

Так что я хотел бы услышать ваши предложения для лучшего сжатия.

спасибо.

Answer 1

Как указано в комментариях, оптимальное кодирование - если все перестановки равновероятны - заключается в замене всей перестановки на ее индекс в перечислении перестановок. Поскольку есть n! возможные перестановки, необходим индекс n! бит, и, следовательно, степень сжатия от наивного кодирования с помощью лога п бит для каждого элемента (лог п!)/(п лога п).

Используя Stirling's approximation, можно переписать, что, как (п лог п - п + O (журнал п))/(п журнал п), который является 1 - 1/(log n) + O (1/n), который, по-видимому, асимптотически приближается к 1, поскольку n растет. Поэтому неизбежно, что коэффициент сжатия будет уменьшаться для больших n.

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

Answer 2

Для этой конкретной проблемы наиболее эффективной кодировкой является просмотр перестановки [0 .. 2^N-1] в виде цифры в factorial number system и сохранение Lehmer code для этой перестановки.

Это дает требование ceil(log2((2^N)!)) бит. Для N = 4 это использует 45 бит (70,3%); для N = 11 (2^N = 2048), 19581 бит (86,9%).

Коэффициент сжатия ухудшается по мере увеличения N; используя простое приближение , мы достигаем минимума для log2((2^N)!)/(N 2^N)1 - ((2^N - 1)/(2^N))*(1/(N * log(2))), который приближается к 1, так как N стремится к бесконечности.

Учитывая эту абсолютную оценку степени сжатия, любой подход, который вы можете найти, который достаточно эффективен, стоит потратить; для значений, меньших N = 15, невозможно сделать лучше, чем 90%.

Answer 3

В настоящее время вы используете бит N * 2^N.

В основном то, что у вас есть, является перестановкой чисел, и каждая перестановка является уникальной, а для перестановки вы можете рассчитать уникальный идентификатор. Так как существуют (2^N)! перестановок, вам понадобится только ceil (log2 ((2^N)!)) бит. Например, это 45 бит.