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

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

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

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

...
Я вот что подумал - текст, как один из видов сжимаемых данных, не очень хорошо подходит для такого сжатия:

1. ГПСЧ старается генерить последовательность разных чисел, т.е. повторы достаточно редки. А у нас идут повторы букв и слогов.

2. ГПСЧ выдает значения из всего заданного диапазона, а в тексте используется только часть.

ИМХО таким алгоритмом лучше всего будет белый шум сжиматься.

BarloneНу вы хоть какие-то оценки пробовали делать? Вот какая вероятность найти хотя бы одну совпадающую последовательность битов длины M в двух последовательностях длины N, одна из которых случайная? Приблизительно (N-M)/(2^M). Не сожмется у вас ничего.
+1

Немного по-другому рассуждаю: ГСПЧ должен генерить последовательность всех возможных вариантов комбинаций по M байт или M*8 бит, Т.е. всего 2^(M*8). Таким образом для инициализации ГСПЧ потребуется значение размером M*8 бит. Плюс надо указывать размер сколько байт прочитать. В итоге имеем "архив" размером больше оригинала.

Я понимаю что могут попасться последовательности длиннее М, но это редкий случай и им можно пренебречь. Поэтому считаю что "архив" почти всегда будет размером больше оригинала.

Иван FXSDima T,

не могу понять, что вы написали. Зачем вообще скакать -- в рассуждении и изложении - с битов на байты и обратно?
Незачем, полет мысли так шел, но сути это не меняет :)

Иван FXS"ГПСЧ должен генерить" ... (псевдо-)случайную последовательность битов указанной длины. Всё, больше ничего от него не требуется.
Я к тому что для инициализации ГПСЧ, который может выдать нужную последовательность в M-бит, потребуется не менее M-бит. Это в лучшем случае.

Еще раз, кратко, в битах:

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

Вывод: ничего не сожмется.

Иван FXSDima T,

а, сорри, я тут точно запутался в обозначениях длин (N и М) ... но и вы, кажется, тоже:
Есть такое, но я тебя понимаю :)

Иван FXSчто значит, например, ваше
Dima TНам надо M бит найти?

Мы сравниваем две строки и, если находим локальное совпадение, то у него есть длина (которую я обозначил М).

У строк
"11111111111111111111111111111111" и
"00011111000000000000000000000000" - есть совдадение с М=5 начиная с 4-й позиции.
Ты рассматриваешь редкий частный случай, когда есть совпадение. Я рассматриваю вариант что в последовательности есть все комбинации для М=5. Т.к. если они не все, то запись будет еще неэффективнее, т.к. придется использовать более короткие подстроки.


Давай чуть упростим задачу: есть строка М бит и какая-то последовательность. Без разницы откуда она берется (ГПСЧ, массив и т.д.).

Чтобы случайная строка размером М гарантированно присутствовала в последовательности, необходимо последовательность размером 2^М строк, т.к. всего возможно 2^М комбинаций по М бит.
Следовательно наша последовательность должна содержать все возможные комбинации. Для указания нужной комбинации надо переменную размером М бит.

Или другими словами: чтобы идентифицировать нужную комбинацию из М бит надо хранить М бит.

А то что ты думаешь что в последовательности найдется чудесное место где за искомой строкой в М бит будет стоять строка, которую ты будешь искать на следующем шаге, то тут ты сильно заблуждаешься, т.к. вероятность такого события почти нулевая.

Вывод: хоть сколько переборов делай, но в итоге "архив" будет больше исходного файла. За исключением некоторых частных случаев.

Иван FXSDima TДавай чуть упростим задачу это мне кажется, или вы в самом деле (пока) обсуждаете только один (служебный) пункт -- выбор "флага" (для конкретной входной строки)?

Просто я перечитал (наконец) свои собственные обозначения в задаче. М - это длина флага.
Это только кажется. У тебя же на каждой итерации какая-то одна конкретная строка (или флаг) конкретной длины М бит.

По моим рассуждениям на каждой итерации будет записано не менее М бит. И не влияет что на разных итерациях у М разные значения.

Алгоритм не рабочий. Не будет он жать.

Иван FXSDima Tна каждой итерации какая-то одна конкретная ... флаг)нет, флаг выбирается один раз -- для исходной строки. Если она: "101010111001110101011111100111001111111111", то флаг "000" и точка.
Я не совсем понял суть флага. Он для чего?

Объясняю как понял: есть ГПСЧ и данные, т.е. то что сжимаем.
В результате данные надо привести к такому виду:

где
seed _i инициализация ГПСЧ
len _i сколько бит прочитать из ГПСЧ

В итоге ищем результат, имеющий наименьшую длину. Правильно?

Понял про флаг. Ты немного другим путем пошел.

Имеем Данные. Придумываем флаг чтобы не было внутри данных.
Подбираем: подстроку данных (М бит) и seed, так чтобы ГПСЧ(seed) выдавал эти М бит.
Заменяем подстроку на {флаг, seed, М} в том случае если они меньше M, т.е. получаем пожатые Данные.

Правильно?

Dima TЗаменяем подстроку на {флаг, seed, М} в том случае если они меньше M, т.е. получаем пожатые Данные.
Если так, то не найдется таких комбинаций, т.к. для хранения seed потребуется места столько же сколько занимает исходная подстрока, это я выше доказал. За исключением редких частных случаев.