Dima T,

тоже нужно будет передавать, это уже написано - в п.7 исходного поста.

Dima Tдля хранения seed потребуется места столько же сколько занимает исходная подстрока, это я выше доказал я это ваше доказательство не вкурил, извините. Что за "исходная под -строка"?

Dima T,

"Например чтобы нашлось 1111 (это исходная подстрока)" ... в одной конкретной позиции ... "ГПСЧ должен иметь минимум 2^4 вариантов seed"

-- но нам совершенно не обязательно, чтобы нашлось именно "1111" и именно в этой позиции.

SiemarglЭто обычный алгоритм LZW, только с ошибками и случайно-генеруемым словарем :fail:
только вы то ли не заметили, то ли решили умолчать о том, что "генерируемый словарь" означает, что словарь не класть в выходной файл (увеличивая его размер), как это делается в LZW.

("С ошибками" я не понял, поэтому отнестись не могу.)

Иван FXSсловарь не нужно класть в выходной файл

Сейчас, почти через две недели, я бы по-другому сформулировал концепцию сжатия (гипотетическую, конечно, поскольку осуществимость её не доказана). А именно, я бы заменил "флаг" (который непонятно-какой-длины) на "цепную адресацию":

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

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

2. Записываем s в начало выходного файла.

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

4. Устанавливаем "счётчик цепной адресации" в ноль: А=0.

5. Сравнивая побитово Д и СП, движемся вдоль них обеих до тех пор, пока не находим в них (по "цепному адресу" А) одинаковую подстроку (П) длиной М.

6. Если используемая нами нотация записи целых чисел позволят записать эти два числа (А и М) короче, чем М битов, то записываем их в начало выходного файла. И записываем в его конец очередную порцию несжатых битов - те, что шли до П (то есть подстроку П "выбрасываем", не пишем в выходной файл).

(6.1. Кстати, мы можем постановить, что с подстроками короче М0 связываться принципиально не следует; тогда записывать нужно не М, а разницу М-М0, что чуточку выгоднее.)

7. Если условие, описанное в п. 6, выполнено, переходим на п.4; если не выполнено -- переходим на п.5. Дальнейшее сканирование строк -- в любом случае -- продолжается с первого бита после подстроки П.

8. Дойдя до конца строки Д, оцениваем полученный вариант сжатия: если он лучше всех предыдущих, сохраняем его, если нет -- забываем. И переходим к п.1 .