Об одном способе ресурсоёмкого сжатия данных

Есть данные Д - битовая последовательность длины N, - которые требуется сжать, и стандартный ГПСЧ.

1. Находим битовую последовательность минимальной длины M, которая ни разу не встречается в Д. Назовём её "флаг" (Ф).

2. В цикле перебираем значения seed (s), используемые для инициации ГПСЧ: ГПСЧ(s).

3. Посредством ГПСЧ(s) генерируем случайную последовательность (СП) той же длины N.

4. Сравниваем побитово Д и СП. Все совпадающие - в Д и СП - последовательности битов, длиной больше М заменяем (в Д !) на флаг Ф. При этом следим, чтобы "на стыках" вставляемого флага и соседних исходных битов Д не возникали "паразитные флаги".

5. В результате замен получается битовая последовательность Д' длины N' (меньше N !).

6. Продолжаем перебор (цикл в п.2) до тех пор, пока не найдём значение seed, дающее удовлетворяющую нас степень сжатия К= N/N'

7. Архивный файл представляет собой структуру из трёх элементов: Ф, s, Д' .
______________________________

PS. Как вариант, в качестве флага Ф можно использовать вообще любую последовательность битов, желательно редко встречающуюся в Д, поскольку "естественные" вхождения Ф в Д нужно будет маркировать посредством, например, удвоения: Ф -> ФФ. (И потом нужно будет следить, чтобы дополнительные ФФ не возникали в процессе сжатия.)

... кстати, файл, сжатый с применением одной пары параметров (Ф1, s1), можно дальше пытаться сжимать с каким то другим Ф2, подбирая какое-то другое значение s2. И так пока не надоест.

Иван FXS,

Если ГПСЧ качественный, т.е. распределение битов равновероятно, оцените количество циклов для достижения нужной степени сжатия. Задачка не выглядит очень уж сложной и, я думаю, ответ вам не понравится.

Задачу можно свести к вырожденной заменив гпсч на последовательность целых чисел.

Это обычный алгоритм LZW, только с ошибками и случайно-генеруемым словарем :fail:

scf,

по секрету, этот топик вынесен в автономную тему из темы http://www.sql.ru/forum/1281135/dispersiya-dliny-arhiva -- где как раз обсуждалось сильное (желательно) сжатие с расходованием большого (в пределе - не ограниченного) количества ресурсов.

Siemargl,

Сюрприз: словарь не нужно запихивать в архивный файл!

Точно такое же первое впеч, как у Siemargl - типа ЛЗВ, но только словарь заменён алгоритмом. Т.е. как бы , отталкиваясь от идей ЛЗВ, строим нечто из класса "сжатие посредством алгоритма". В связи с этим (и учитывая корни этой темы) есть мнение, что 1 из 2-х: либо нужно уметь восстанавливать исходник, либо нужна воспроизводимость кодирования данной Д. Во всяк я так понимаю термин pow. В случае же ГСПЧ да ещё стандартного я сомневаюсь в воспроизводимости. По моему мнению, при одном и том же СИДЕ СП будут разные (а лень проверять).

exp98,

вы, наверное, полагаете, что если повторно вызвать ГПСЧ с тем же аргументом (seed-ом), то он возвратит другой результат ...

Иван FXS, пример кода будет? Желательно со статистикой.