компрессия

[sab123]

А ведь генераторы случайных чисел, описанные в http://www.pcg-random.org/party-tricks.html (через http://juan-gandhi.dreamwidth.org/4013708.html) - это получается чуть ли не идеальный способ компрессии. Если его можно заставить выдавать произвольную последовательность, то получается, что эта последовательность сжимается до начального состояния генератора. Последовательность любой длины в очень широких пределах - до фиксированного размера.

Или я что-то тут упускаю?

Comments

[rezky]

да, но этот фиксированный размер генератора никак не может быть короче колмогоровской сложности самой последовательности.

[spamsink]

Может быть короче - на колмогоровскую сложность алгоритма генератора. :)

[sab123]

Вот и я подозреваю, что может последовательности там все же не совсем любые.

[vit_r]

А как происходит декомпрессия?

[sab123]

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

[gb0]

ну да, а в любом трансцендетном иррациональном числе (а-ля #pi = 3.1415926...) "зашита" вся информация о Вселенной.

Практическая ценность – отсутствует :(

[sab123]

Отличие в том, что тут известно, с какой цифры начинать смотреть. И есть быстрая перемотка к будущим цифрам.

[gb0]

А в чем вообще прикол, изначальный? В том, чтобы превзойти лимит Шэннона?

[sab123]

Я подозреваю, что в реальности оно может генерить не любую последовательность, .и предсказуемые последовательности должны быть достаточно короткими чтобы уложиться в этот предел. Собственно, наверное он не случайно использовал зипованные файлы :-)

[alll]

емнип пытались делать что-то такое "а-ля фракталы", но почему-то не взлетело

Очевидно вычислительная сложность поиска начального состояния для генератора несколько превышает возможности современной техники. :)