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

[Kharitonov A. Dmitry]

Vladislav Zavjalov wrote:
> 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 бит на число...
>   
Тот же LZMA намного эффективней.
А чем он собсвенно не подходит? хороший потоковый упаковщик с 
динамической кодовой книгой те требует не много памяти.