Может ли эта идея сжать истинные случайные данные без потерь? - PullRequest
0 голосов
/ 22 октября 2018

Я знаю, что сжатие без потерь основано на статистической избыточности.У меня была идея сжатия случайной двоичной строки, и я хотел бы знать, может ли (и почему) она работать или не работать:

Поскольку двоичная строка является случайной, ожидается, чтовероятность отличия от последнего бита равна половине.То есть, если строка битов ... 01101, вероятность того, что следующий бит будет равен 0, равна половине.При этом ожидается, что половина данных «изменит свой поток цифр» на «один», скажем.Давайте назовем N последовательных двоичных цифр «последовательностью» (примечание: последовательность единиц полагается между нулями и наоборот).

При этом, случайным образом, ожидается: 1/2 (50%)последовательностей из одной цифры 1/4 (25%) последовательностей из двух цифр 1/8 (12,5%) последовательностей из трех цифр 1/16 (6,25%) последовательностей из четырех цифр ... 1 / (2 ^ N) последовательностей из N цифр

Можно ли это использовать для сжатия данных?Например:

Рассматривая бесконечную случайную двоичную строку, выбирая образец из 2 ^ M последовательностей, мы знаем, что половина из них будет последовательностями из одной, одна четвертая будет последовательностями из двух и так далее.Какую логику применять, чтобы сжимать случайные данные с эффективностью?И, если это невозможно, то почему невозможно?

1 Ответ

0 голосов
/ 23 октября 2018

Нет.Не за что.

Если все файлы сжаты хотя бы одним битом, то при простом подсчете вы гарантируете, что по крайней мере два отдельных файласжатый до точно такой же вещи.(На самом деле это гораздо больше, но мне нужно только два, чтобы понять это.) Теперь ваш декомпрессор будет выдавать один результат из этого сжатого ввода.Этот единственный результат может соответствовать не более одного из отдельных файлов.Поэтому он не может сжимать и распаковывать без потерь тот, который ему не соответствует.

...