Цитата(Lived @ 19.10.2006, 14:17  ) | Значит если знать X, то можно представить его в виде 2^N,
где N и будет кол-во бит затрачиваемых на кодирование одной такой П. |
кстати, тот подход, который я предложил, использует похожее представление:
мы передаём всё-таки одну из 256^256 последовательностей, но избыток информации, появляющийся из-за того, что X<256^256, используем сразу для передачи следующей последовательности
| Цитата(Lived @ 19.10.2006, 14:17 ) | | P.S. Да, в алгоритме не учитывается что таких П. N-ное кол-во. Подозреваю что это тоже можно как-нибудь использовать. Но пока не знаю как. |
если они независимы, то много пользы от этого не получится
ну разве что иногда немного "размазывать" информацию по времени бывает удобнее, но не более того...
можно ещё посмотреть такой вариант:
берём разности соседних элементов
и используем что-то типа Хаффманна или арифметического кодирования
основная проблема в этом подходе - распределение вероятностей
можно использовать реальное: как показал nostromo, его можно передать довольно-таки сжато
а можно найти какую-то глобальную аппроксимацию, которая, конечно, не даст оптимального результата, но не потребует передачи самого распределения
то, что я показал с выделением разности, большей 128, - небольшое приближение
в принципе, может быть, получится найти такое распределение, которое будет давать достаточный _гарантированный_ результат...
Добавлено @ 15:37
касательно нахождения X
можно попробовать так:
f(n,m) - количество неубывающих последовательностей из n элементов, каждый из которых принадлежит [0..m-1]
тогда X=f(256,255)
дальше можно сделать рекурсивный подсчёт этой функции:
f(1,m)=m
f(n+1,m)=сумма[i=0..m-1] f(n,m-i)
(не исключено, что что-то где-то потерял, но смысл такой) |
