[devel] вопрос про числа
Dmitry V. Levin
ldv at altlinux.org
Sat Nov 7 20:09:22 UTC 2009
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
----------- ????????? ????? -----------
???? ??????? ???????? ?? ? ????????? ???????...
??? : ???????????
??? : application/pgp-signature
?????? : 198 ??????
????????: ???????????
Url : <http://lists.altlinux.org/pipermail/devel/attachments/20091107/48df7d4c/attachment.bin>
More information about the Devel
mailing list