@SergeySerge11

Доказано ли, и можно ли сжать произвольные данные до 20 байтов к примеру?

Возможно ли такое, или NP=P задача????
Как пример возьмем Алгоритмы Генерации Миров и игровых Карт, а порой и целых Вселенных, и планет. На вход попадает всего лишь одно число Зерно. А алгоритм уже по нему создает целый мир, который может быть терабайтных данных. По 1 числу можно генерировать, рельеф, города, диалоги, квесты, поведение NPC.....
В итоге 8 байтов превращаются в гигабайты. +память на сам алгоритм и его ресурсы.
Но так можно делать прямым путем? Как минимум, а вот возможен ли обратный алгоритм.
Допустим простая программа которая по 4 байтовому числу, создает поле игры Морского Боя с кораблями. 10*10. Реализовать реально. Зная задачу. Но понятно что не все возможные варианты могут быть созданы. А вот можно ли найти алгоритм Обратно, зная карту этого поля морского поля составить такой алгоритм, который сожмет все в Байт зерна, и получит это число.
Теперь усложнив, а можно ли любой набор данных, то есть ~случайных байтов, сжать до числа, и для них оставить такой алгоритм, который Сгенерирует эти данные.
Типа как Аппроксимация функции по точкам.
Есть ли теоретическая база такого вопроса.
  • Вопрос задан
  • 260 просмотров
Решения вопроса 1
@Akina
Сетевой и системный админ, SQL-программист.
Допустим, существует некий алгоритм, который преобразует последовательность X длины M в последовательность Y, причём существует обратное преобразование. Неважно, что это за алгоритм конкретно - сжатие, создание "зерна" и пр. Но очевидно, что:

1. Количество вариантов последовательности X составляет K в степени M, где K - размер словаря, т.е. количество возможных различимых значений одного элемента последовательности X. В случае байтовой последовательности это байт, т.е. K=256.

2. Каждая последовательность X после преобразования даёт последовательность Y, причём две разные последовательности X дают разные последовательности Y.

Соответственно количество возможных последовательностей Y равно количеству возможных последовательностей X. И соответственно если существует хотя бы одна последовательность Y короче последовательности X, то существует хотя бы одна последовательность Y длиннее последовательности X.

Что, собственно, и наблюдается на абсолютно любом алгоритме компрессии - существуют входные данные, для которых результат попытки сжатия имеет бОльший размер, чем исходные данные.

Что же до "зерна", которое разворачивается в гигабайты - во-первых, количество финальных миров определяется количеством значений "зерна", то есть вовсе даже не такое бесконечно большое, как кажется, во-вторых, созданный образ мира содержит значительное число повторяющихся элементов, а создание копий - это немножко не декомпрессия.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 5
@rPman
Объем seed для генерации универсальных данных будет больше или равен в среднем их размеру

Отличный пример - внутри числа pi есть все последовательности данных которые в принципе могут существовать и даже есть формула которая выдает позицию, начиная с которых она есть - πfs.

p.s. есть алгоритмы с потерей, например сжатие изображения и звука, вот тут поле не пахано да
ну и вишенка на торте - нейронная сеть размером несколько килобайт на видеокадр позволяет сгенерировать весь видеоряд (не смог найти, на хабре была статья, понятно там качество ужасное, нейросеть не справлялась с лицами но сама идея шикарная)
Ответ написан
Комментировать
Adamos
@Adamos
Все ныне широко используемые архиваторы эффективны исключительно по той причине, что данные, которые им нужно сжимать - не произвольны.
На произвольных же (случайных, например) данных они в среднем дают чуть больший размер результата за счет добавления своих заголовков к сжимаемой информации.
Ответ написан
Комментировать
gbg
@gbg
Любые ответы на любые вопросы
Посмотрите на этот вопрос с другой стороны - пусть есть алгоритм, который из N произвольнх байт делает N-1 байт и это обратимо.

Но тогда полученные N-1 байт - это произвольный набор байт, которые можно снова обработать Алгоритмом и получить уже N-2 байт.

Тогда получается, что любую последовательность байт за N шагов алгоритма можно урезать до 0, что очевидно, является абсурдом.
Ответ написан
Комментировать
trapwalker
@trapwalker
Программист, энтузиаст
Вы на свой вопрос можете ответить и сами, если посчитаете.
Произвольные данные не сжимаются. Вообще.
Доказываем на пальцах. Для детей.
1. Давайте получим произвольные данные. Для этого возьмём монетку и подбросим 10 раз. Таким образом мы получим 10 бит произвольных данных.
2. Доказываем, что эти 10 бит нам не сжать даже до 9 бит.
Сколько всего бывает разных 10-битных последовательностей? Два в степени 10, то есть 1024.
Сколько всего бывает разных 9-битных последовательностей? Два в степени 9, то есть 512. Это значит, что 9-битным числом можно как-нибудь закодировать только половину произвольных 10-битных последовательностей. Ни одного бита сэкономить не удалось для действительно произвольных (читай случайных) данных.

-- А как же работают архиваторы? - спросите вы.
А архиваторы сжимают не произвольные данные, а какие-то осмысленные. Осмысленных данных меньше чем любых. Это очевидно. Вот архиваторы этим и пользуются.
Давайте пример. Допустим наша "монетка" умеет падать не на две стороны, а на три. Ну циллиндрик такой. толстенький, который частенько падает на ребро. И мы его подбросили пять раз, но хотим почему-то записать полученную последовательность в вдоичной форме. Очевидно, что двумя значениями 1 и 0 мы не можем закодировать три стороны "монетки" (назовём её тринеткой). А два бита может кодировать уже четыре разных состояния: 00, 01, 10, 11. Нам хватит трёх из них, а четвертое, скажем 11, пусть будет ненужным.
Тогда 5 бросков тринетки мы можем записать 10 двоичными битами. Но данных в этих 10 битах будет на самом деле храниться только 3 в степени 5 = 3*3*3*3*3=243. То есть 243 состояния тринетки кодируются 10 битами, в которые помещается на самом деле 1024 разных произвольных значений.
Это как раз и есть то место, где можно успешно сжать данные.

А насколько можно сжать? Давайте считать. 8 бит может представить 2*2*2*2*2*2*2*2=256 разных произвольных значений. А нам надо 243. Это значит, что любые 5 бросков тринетки мы можем закодировать не 10-ю битами, а всего лишь 8-ю. Сэкономили два бита, но больше сэкономить не получится ни одного бита!

А откуда ж берутся огромные коэффициенты сжатия? Например тексты на человеческих языках довольно неплохо сжимаются. А всё просто. Мы кодировали каждый бросок тринетки для простоты 2-мя битами, и там одно сочетание было нам не нужно. А представьте, если бы нам не хотелось бы возиться с битами и мы посчитаи более простым хранить броски тринетки каждый в одном байте!
То есть нам бы хватило и 2 бит слихвой, но м ырешили на каждый бросок использовать 8 только потому, что у нас компьютеры не сильно приспособлены быстро работать с более мелкими кусками данных.
Получается, что 5 бросков тринетки мы закодируем в 8*5байт=40бит, а мы уже уяснили что и 10 бит хватило бы, и даже 8, но никак уж не меньше восьми.
Получается, что расточительную 40-битную запись пяти бросков тринетки мы могли бы сжать аж в 5 раз до 8 бит! То есть мы используем 5 байт там, где хватило бы одного, вот и получилось, что можно сделать сжатие.

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

Расписал как мог просто. Если у вас после этого остались иллюзии, что можно сжать гигабайтный фильм до одного байта, а потом распаковать его обратно, то вам уже ничто не поможет. Потому что фильмов человечество наснимала уже гораздо больше 256, а значений одного байта всего как раз столько.
Вы можете написать архиватор, который будет сжимать произвольный фильм из ваших любимых 256 фильмов. Но при этом сам архиватор будет размером 256 гигабайт, а байт будет просто номером в библиотеке ваших любимых фильмов. Но да, вполне реально назвать вашему другу по телефону тремя байтами три любых фильма из вашей общей коллекции, а у друга на винте такой же "архиватор", как бы, "распакует" эти числа в целые три фильма, которые на самом деле и так уже были у друга.

Других чудес не бывает.
Ответ написан
mayton2019
@mayton2019
Bigdata Engineer
В 4 байта можно втиснуть 4 миллиарда состояний. Или в терминах игровой индустрии - возможно создать процедуральный генератор миров или локаций где из одного целого числа можно создать 4 млрд миров. Но качество самих миров будет скорее всего плохое. Как раз по причине этих жалких четырех байтов. У нас не будет детального контроля над ландшафтом и другими свойствами мира. Согласитесь иметь 32 переключателя или 4 регулятора по 250 уровней (как угодно смотреть на это) - это маловато.

По поводу обратной задачи. Всё будет зависеть от формы как представлены исходные данные. Но мне кажется что делать такой архиватор безсмысленно. Достаточно просто грамотно сохранить тот мир который нарисовал дизайнер миров. В игре kkreiger достаточно лаконично в 64 килобайта была втиснута Quake-подобная локация.

Хотя если долго в нее поиграть видны дефекты мира. Процедуральные текстуры как будто повторяются. И геометрия мира какая-то повторяющася.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы