Наилучшее сжатие al go для случайной строки - PullRequest
0 голосов
/ 18 апреля 2020

У меня есть строка вроде ниже

ff8870fd30db56efd72e8b499a454c4e27be6ab70e23dd59a864563628e998a

, что составляет около 2 Кбайт. Я пытался сжать, но у меня не получается хорошая степень сжатия

с помощью gz. Я получил только 400 байтов и с defalte Я получил 450 снижение ..

Есть ли лучший алогоритам, чтобы иметь больше сжатия по крайней мере более чем на 50%.

1 Ответ

0 голосов
/ 21 апреля 2020

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

Общий контраргумент состоит в том, что при достаточных шансах даже строка со всеми 0 может быть сгенерирована ГСЧ, но дьявол находится в детали: все дело в шансах! Даже в крошечном пространстве 2 КБ у вас есть 2 ^ (2048 * 8) возможных строк, если данные генерируются истинным ГСЧ или надежным алгоритмом ГСЧ, засеянным с достаточным количеством шума, и подавляющее большинство этих строк не будет содержать никаких разумных количество «порядка», которое вы можете сжать.

Тот факт, что вы получаете сжатие 400 B / 450 B на 2 КБ, является сильным намеком на то, что строка, которую вы просматриваете, на самом деле не случайна, просто не читается человеком или «случайный вид».

Формат GZ основан на алгоритме сжатия Deflate, поэтому неясно, почему эти две цифры представлены отдельно - Deflate принимает различные параметры для точной настройки сжатия за счет скорости, поэтому различные настройки могут оправдывать разные результаты.

Чтобы получить лучшее сжатие на случайных (но не на самом деле!) данных, попробуйте использовать LZMA2 (7-Zip) или даже лучше ZPAQ (http://mattmahoney.net/dc/zpaq.html) ).

...