Придумал зоймечательный алгоритм архивации: хранить пары смещение-длина, указывающие на куски в двоичной записи числа e. Или π. Или ещё какого трансцендентного.
Жаль, для хорошей степени сжатия потребуется совсем не полиномиальное время.
Ну, хм, есть надежда, что данный способ хорош хотя бы асимптотически... С другой стороны, он хорош только для очень определённого вида последовательностей...
А расскажите мне глупой, как доказывается тот факт, что в двоичной записи трансцендентного числа будут содержаться все возможные конечные подпоследовательности?
Способ-то конечно все равно бредов, сведется при оптимизации в обычное арифметическое кодирование с предварительным сбором статистики в таблицу.
no subject
Date: 2009-07-19 04:02 pm (UTC)Например, кусок '00000' находится на месте 95 ( 1011111 ), '101' на 15-ом, '11101101' на 3779.
С днём рождения!!!
no subject
Date: 2009-07-19 09:04 pm (UTC)no subject
Date: 2009-07-19 09:20 pm (UTC)no subject
Date: 2009-07-19 09:29 pm (UTC)Способ-то конечно все равно бредов, сведется при оптимизации в обычное арифметическое кодирование с предварительным сбором статистики в таблицу.
no subject
Date: 2009-07-19 09:34 pm (UTC)no subject
Date: 2009-07-19 09:57 pm (UTC)Не вижу преимуществ перед табличным кодированием с заранее зашитой таблицей.
Недостатков вижу, кучу.
Впрочем, тебе ж это неважно.
С прошедшим!
no subject
Date: 2009-08-04 06:57 pm (UTC)Спасибо. Правда, ты меня тогда же по смс поздравила же.
no subject
Date: 2009-08-04 07:44 pm (UTC)Забыла, ну да больше не меньше же.
no subject
Date: 2009-07-21 11:48 am (UTC)no subject
Date: 2009-07-21 11:24 am (UTC)no subject
Date: 2009-07-21 11:48 am (UTC)no subject
Date: 2009-08-04 03:53 am (UTC)no subject
Date: 2009-08-04 06:55 pm (UTC)