Возможно ли создать алгоритм сжатия, который использует огромный (100 ГБ?) Файл псевдослучайного поиска?

Question

Было бы возможно / практично создать алгоритм сжатия, который разбивает файл на куски, а затем сравнивает эти куски с огромным (100 ГБ ?, 200 ГБ?) Псевдослучайным файлом?

Полученный «сжатый» файл будет содержать упорядоченный список смещений и длин. Каждому, кто использует алгоритм, понадобится один и тот же огромный файл для сжатия / распаковки файлов.

Будет ли это работать? Я предполагаю, что кто-то еще думал об этом раньше и попробовал это, но это трудно для Google.

Answer 1

Это обычная уловка, используемая многими «претендентами на сжатие», которые регулярно объявляют «революционную» степень сжатия, вплоть до нелепых уровней.

Трюк, очевидно, зависит от того, что в справочнике.

Если такой словарь просто "случайный", как это предлагается, то он бесполезен. Простая математика покажет, что смещение будет стоить в среднем столько же, сколько и данные, на которые оно ссылается.

Но если словарь содержит большие части или весь входной файл, то он будет "волшебным образом" сжат до ссылки или серии ссылок.

Такие уловки называются «сокрытием энтропии». Мэтт Махони написал простую программу ( barf ), чтобы продемонстрировать эту технику, вплоть до уменьшения чего-либо до 1 байта.

Решение этой хитрости заключается в том, что для сравнения всегда должны использоваться сжатые данные, программа распаковки и любой внешний словарь, который она использует. Когда все эти элементы подсчитаны в уравнении, то больше невозможно «спрятать» энтропию где-либо. И чит раскрывается ....

Answer 2

Циан это правильно. Более того: вам не нужно иметь такой файл. Вы можете детерминистически создать одну и ту же псевдослучайную последовательность, даже не сохраняя ее. Глядя на это таким образом, вы видите, что ваш файл случайного поиска не имеет значения.