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

[Alexey Tourbin]

Сгенирируем n случайных чисел из диапазона 0..2^m-1 и упорядочим их
по возрастанию.  Для примера m=32, n порядка 10^3.

Вычислить энтропию и предложить оптимальную процедуру кодирования
(сжатия) последовательности.  Сколько битов на число можно получить?


(Вопрос связан с тем, что нам нужно придумать компактное представление
"множества строк".  Например каждую строку можно представить в виде её
m-битного хеша.  Соответственно множество n строк можно представить
в виде n*m битов.  Но всё-таки битов получается очень много, и их можно
неплохо сжать.  Неплохо наварить на этом можно, вот что.  Осталось только
придумать процедуру сжатия.

Иначе же существует эквивалентное представление в алфавите {0,1} с
постоянными вероятностями.  А именно, каждое число из диапазона 0..2^m-1
можно рассматривать как номер бита в битмапе из 2^m битов.  Тогда
последовательность чисел можно перевести в битмап и сжать битмап
побитово.  Проблема только в том что при побитовом кодировании/
декодировании получается очень большой битмап и очень большой цикл.)
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: not available
URL: <http://lists.altlinux.org/pipermail/devel/attachments/20091107/99f698bc/attachment.bin>