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

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

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

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

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

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

Barlone,

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

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

S.G.,

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

S.G.,

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

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

Соколинский Борис,

так можно слова длиной 15 с частотами из правого крыла Пуассона (их, 15-буквенного Пуассона) перекодировать словами длины 14 с частотами из левого крыла Пуассона (их, 14-буквенного Пуассона).

И наоборот, то есть взаимно?

читать:Иван FXS(их, 14-буквенного Пуассона) ?

Кстати, в тему максимизации/минимизации энтропии: из двух сообщений одинаковой длины лучше будет сжиматься ("хорошим" архиватором) то, в котором больше информации? Или, наоборот, то, в котором меньше информации?

exp98, лучше будет сжиматься то сообщение, в котором удельная ("на единицу длины") инфа выше, -- я правильно вас понял?

А как связана "фреймворковость" с обсуждением сравнительной сжимаемости (податливости сжатию) строк (сообщений) типа приведённого вами: " Там ооооооооооооооооочень ХооооЛоооооооДНооооооо " -- против " Там очень ХоЛоДНо ", например?

Dima T,

потому и "парадокс".

Соколинский БорисИван FXSтак можно слова длиной 15 с частотами из правого крыла Пуассона (их, 15-буквенного Пуассона) перекодировать словами длины 14 с частотами из левого крыла Пуассона (их, 14-буквенного Пуассона).

Это все равно что повторно архивировать.
задачка в том, как при таком перекодировании обойтись без "словаря перевода", либо с таким словарём, который не перекрыл бы (своей длиной) весь эффект сжатия.

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