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

s/последовательность/неупорядоченное множество/


-- 
ldv