[devel] вопрос про числа

[Vladislav Zavjalov]

On Sat, Nov 07, 2009 at 10:34:02PM +0300, Alexey Tourbin wrote:
> Сгенирируем n случайных чисел из диапазона 0..2^m-1 и упорядочим их
> по возрастанию.  Для примера m=32, n порядка 10^3.
> 
> Вычислить энтропию и предложить оптимальную процедуру кодирования
> (сжатия) последовательности.  Сколько битов на число можно получить?

А вот еще одна идея, наоборот, для малых n.

Если у нас два числа, можно использовать 2m-1 бита для их хранения,
выиграть один бит, так как порядок чисел не важен.
Достигается это легко: если считать все по модулю 2^m, то у нас есть два
числа и два непрерывных диапазона остальных чисел.
Один из этих диапазонов меньше чем (2^m)/2.
То число, перед которым пустой диапазон больше, запишем явно, m битами.
Кроме того, запишем расстояние от него до второго числа, m-1 битами.

Если чисел n, будем действовать похоже: Выберем максимальное расстояние
между соседними числами (оно больше чем (m^2)/n). Запишем число, стоящее
после этого максимального пустого диапазона.
Оставшихся вне максимального диапазона чисел меньше чем (2^m)(1-1/n).
Повторим для них ту же процедуру, считая числа от начала этого нового
диапазона по модулю (2^n)(1-1/n).
Получим последовательную запись всех наших n чисел, причем ограничения
на их размер будут такими:

(2^m)
(2^m)(1 - 1/n)
(2^m)(1 - 1/n)(1 - 1/(n-1))
...
(2^m)(1 - 1/n)(1 - 1/(n-1)) ... ( 1 - 1/2)

Если я не ошибаюсь, энтропия такого набора:
m*n + \sum_{i=1}^{n-1} [ (n-i) \log (1 - 1/(n-i+1)) ]
Для n=1000 и m=32 это 30.6 бит на число...

Слава