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

    @Akina
    Сетевой и системный админ, SQL-программист.
    Допустим, существует некий алгоритм, который преобразует последовательность X длины M в последовательность Y, причём существует обратное преобразование. Неважно, что это за алгоритм конкретно - сжатие, создание "зерна" и пр. Но очевидно, что:

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

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

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

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

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