Об одном парадоксе информационной энтропии

Возьмём файл сжатый очень хорошим (в пределе -- идеальным) архиватором. Содержимое этого сжатого файла можно рассматривать как строку битов S длины N. “Хорошее сжатие” означает, что информационная энтропия распределения битов в этой строке сильно минимизирована (в идеале -- сведена к минимальному значению, соответствующему “количеству информации” в исходном файле, подвергнутом сжатию).

Маленькая энтропия означает, в частности, что если мы нарежем рассматриваемую строку S на последовательные “слова” одинаковой длины М и составим частотный словарь этих слов, то не только всё множество возможных “слов” длины М будет присутствовать в этом словаре, но и разброс частот этих слов будет минимальным. То есть -- существенно меньшим, чем разброс частот в аналогично препарированной случайной строке битов той же длин N.

Можно сказать, что частоты “слов” в S “хорошо выровнены”.

Возьмём теперь датчик случайных чисел (ДПСЧ), выберем произвольное начальное значение Х (не слишком длинное в битовой записи) и создадим на основании последовательности значений, возвращаемых этим ДПСЧ -- начиная с ДПСЧ(Х)
-- (псевдо-)случайную строку Z той же самой длины N.

Сложим побитово S и Z. Получившаяся строка R будет, вообще говоря, столь же (псевдо-)случайна, как и строка Z. То есть частоты входящих в неё “слов” совершенно не будут выровнены. А это значит, что, прогнав её (Z) через тот же самый хороший архиватор, мы сможем дополнительно её сжать. И есть хорошие шансы надеяться, что “выигрыш” (в числе битов) от этого сжатия будет больше, чем длина в битах записи числа Х. И даже (возможно, особенно если N велико) больше, чем длина в битах алгоритма нашего ДПСЧ, записанного на каком-то “экономном” байт-коде...

Можно, наконец, явно произнести, что, зная только Х, мы всегда можем повторно сгенерировать строку Z и, вычтя её из R, получить исходную S.

Что-то не так. Хорошо сжатая последовательность как раз максимально похожа на случайную.

Вот сразу заявлю: не вижу paradoxa -- надеяться только можно.
Вообще, оно конечно, если на серии опытов существует плотность распред F( S AND Y), то она м.б. весьма разнообразна и не связана с индивидуальными плотностями (умозрительно говоря).

С другой стороны, давно уже было такое:
Строим словарь С1 из "текста", нарезая его на кусочки ограниченной в целом длины (аналог ЛЗВ).
Строим текст из ссылок на С1
Строим словарь С2 из текста.
Строим текст из ссылок на С2
......
На первых итерациях имеем квазикомбинаторный взрыв.
В дальнейшем - сужаемость, похожая на треугольник. Его высота и полнота зависит от начальной "энтропийности" "текста". Чем "белее шум", тем тр-к брюхастее и выше, а чем больше повторяемость - тем ниже и менее беременный.

Последний "текст"= единственная ссылка. Вот и сжатие. А есть ли paradox, хрз.
Писал "текст" - т.к. в компе всё можно свести к послед-сти {0,1}

Barlone,

в случайной последовательности частоты "слов" распределены по какому-нибудь Пуассону (на вскидку). Значит есть слова, встречающиеся (заметно?) чаще или реже среднего.

А префиксное кодирование, например, специально занимается тем, что выравнивает (как можно лучше) частоты слов. С учётом длин, конечно: все слова длиной 8 бит должны иметь частоты, в идеале, равные 1/256; а слова длиной 10 бит -- равные 1/1024 ...

Иван FXS
. “Хорошее сжатие” означает, что информационная энтропия распределения битов в этой строке сильно минимизирована

наоборот, максимизирована.

Иван, вы бы почитали что-нибудь про все это, наконец.

S.G.,

да, спасибо. Внимание всем: "энтропия минимизирована" читать (выше) как "энтропия максимизирована".

S.G.,

я просто физик по исходному. А там -- в термодинамике -- энтропия возрастает самопроизвольно, а чтобы её уменьшить, нужно специально усилия прикладывать.

Иван FXS
в случайной последовательности частоты "слов" распределены по какому-нибудь Пуассону (на вскидку)

Да с чего бы? Равномерно.

в смысле "равномерно" это как?

https://ru.wikipedia.org/wiki/Дискретное_равномерное_распределение