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

[Денис Смирнов]

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

1. Попробовать для начала представить это в виде последовательности
разностей соседних чисел? (сжимаем диапазон)

2. При кодировании результата разделяем на два потока значение количества
нулевых битов перед первым значащим битом в конечном числе и собственно
значение. Второе, я так понимаю, сжать невозможно, а первое должно
сжиматься неплохо -- во-первых для кодирования нужно не более чем log2 m
(в нашем случае 5) бит. Во вторых распределение вероятностей будет
неравномерным, и тут можно воспользоваться каким-нибудь арифметическим
кодером.

Как отправная точка сойдет?

-- 
С уважением, Денис

http://freesource.info
----------------------------------------------------------------------------
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://lists.altlinux.org/pipermail/devel/attachments/20091107/50bffcf0/attachment.bin>