Существует ли идеальное сжатие без потери данных?

[CodeMaster]

Определённого конкретного набора данных, если единственным критерием будет коэффициент сжатия? Если да, то каково (примерно) различие идеального с оптимальным значением коэффициент/время?

[Shiny]

http://krepeg-s.ru/files/tiski.jpg

[Bedazzle]

Да, существует. Любой набор данных можно упаковать в один байт (версия пакера), при условии что упаковщик/распаковщик будут модифицироваться под каждый конкретный входной файл и содержать полный словарь. :)

[CodeMaster]

Шынни, велика вероятность потери данных. Да и не ко всем типам данных подходит.


Любой набор данных можно упаковать в один байт (версия пакера)

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

[Black Cat / Era CG]

Ну имхо несерьезное восприятие данной темы вполне естественно.
Вы ставите проблему, опираясь на два сомнительных предмета:

идеальное сжатие без потери данных
Можно говорить о максимальном сжатии. Об идеальном сжатии - вряд ли.

оптимальным значением коэффициент/время
Оптимальное для чего? Оптимальность - это в корне относительное понятие, крайне зависящее от конкретных задач и условий.

И далее вы предлагаете сравнить гипотетическое идеальное с относительным. Как?

[CodeMaster]

Можно говорить о максимальном сжатии. Об идеальном сжатии - вряд ли.

Это всё софистика, думатцо 99,99% понятно, что речь идёт о минимальном размере набора служебные данные + словарь + сжатые данные.


И далее вы предлагаете сравнить гипотетическое идеальное с относительным. Как?

Ответ в первом посте.


примерно

Т.е. максимальное теоретически возможное (a.k.a. идеальное) сжатие для данного набора данных и данного алгоритма равно, например, 51%, то в оптимальном для 90% случаев сжатии оно составляет например ~60% или может ~52%, интересно понять соотношение этих величин.

[shurik-ua]

Если оцифровать белый шум с любой разрядностью - то

максимальное теоретически возможное (a.k.a. идеальное) сжатие для данного набора данных
равно 0%.

[SfS]

Математически доказано, что для любого алгоритма Z сжатия данных можно подобрать два набора данных D1 и D2, таких, что:

1. Алгоритм Z для набора данных D1 будет самым эффективным из всех алгоритмов.
2. Алгоритм Z для набора данных D2 будет неэффективным (т.е. выходной файл данных будет по размеру больше входного).

То есть, если на минутку стать омерзительным философом-интеллегентом, о можно мрачно сказать "Ах, в этом мире нет ничего идеального!" и пойти пить водку:)

[nlo_j77]

Вообще... - если брать в рассчёт теорию... - любой массив данных (включая бесконечный), можно упаковать (множественными проходами) в 2кб (учитывая, что данные 8-миразрядные!!)
эти два кб упакованных данных будут содержать 4 равных части - 1 словарь, 2 перекрестный словарь, 3 распаковщик и 4 сами упакованные данные :)
При каждом проходе распаковки, оба словаря обновляются, распаковщик остаётся без изменений.
Однако... - при множественной распаковке.... - чем больше объём данных, тем больше времени на распаковку (бесконечный объём данных будет распаковываться бесконечно) :)

P.S. Похоже на ахинею, но могу обосновать :)

P.P.S Про белый шум - добавляем к разрядности один пустой бит.... и всё замечательно пакуется! :)

[NEO SPECTRUMAN]

идеальное сжатие без потери данных?
ну идеального быть не может
для каждого типа файла/конкретного файла идеальным будет свое сжатие


Вообще...
но как ни старайся в один бит
больше чем 1 бит данных ты не запихнешь...

самое оптимальное не жать каждый файл по отдельности
а жать все вместе
оптимальное в нахождении максимально похожих участков

мне интересно почему до сих пор нету пакера с готовым встроенным словарем так мегабайт на 1000

[CodeMaster]

для каждого типа файла/конкретного файла идеальным будет свое сжатие

Та это всё понятно. Вот например берём мы Войну и Мир в txt пакуем алгоритмом PPM (будем считать, что он лучший для текста) на выходе мы получим единственно возможный файл с упакованными данными минимального размера независимо от вычислительных возможностей? Другими словами, если нам дан конкретный набор данных и известен его тип, можно математически высчитать его минимальный размер в упакованном виде?


P.S. Похоже на ахинею, но могу обосновать

Ну вот на ВиМ и обоснуй, упакуй в 2 КБ, текст книги ведь не бесконечный ;-)

[nlo_j77]

но как ни старайся в один бит
больше чем 1 бит данных ты не запихнешь...

Одного бита вполне хватит для маркера изменённых данных.


Ну вот на ВиМ и обоснуй, упакуй в 2 КБ, текст книги ведь не бесконечный ;-)

Чтобы упаковать, надо не теоретически доказать, а написать пакер... - за него мне платить точно никто не будет (да и не нужен он никому, ибо больно медленно будет паковать/распаковывать)... - мне работа пока важнее :)

[CodeMaster]

Чтобы упаковать, надо не теоретически доказать, а написать пакер...

Мне пакер не нужен, мне теоретическое обоснование гораздо интереснее.


да и не нужен он никому, ибо больно медленно будет паковать/распаковывать

Это всё относительно.

[nlo_j77]

Ну смотри - допустим мы преобразуем 8-ми битные данные в 7-ми и добавляем один бит маркера - дальше некоторые байты изменяем (допустим меняем на 0) и помечаем маркером в итоге получается пакующаяся последовательность (до этого ищем что и как изменить чтобы последовательность паковалась), пакуем и получаем опять последовательность (в теории упакованную процентов на 5-10, опять преобразуем данные в 7 бит с добавлением маркера... - в итоге получим нулевую последовательность с двумя словарями распаковки и данными, которые при паковке-преобразовании не будут менять своего размера - который, чисто в теории равен около 512 байт

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

P.S. немного поясню - у нас непакующаяся последовательность 512 байт, а мы пакуем 513 - после, как минимум 512 проходов, её раздует до намного большего размера, а потом ещё за 512 проходов она упакуется в 512 байт (немного грубо, но смысл передаёт)

[NEO SPECTRUMAN]

чисто в теории равен около 512 байт
8 битами как ни старайся можно описать 256 разнообразных уникальных файлов
как ни старайся ты не упакуешь больше
это же относится ко всему остальному
в один бит не вместишь 2Кб рандомных значений...

[Spectramine]

Та это всё понятно. Вот например берём мы Войну и Мир в txt пакуем алгоритмом PPM (будем считать, что он лучший для текста) на выходе мы получим единственно возможный файл с упакованными данными минимального размера независимо от вычислительных возможностей? Другими словами, если нам дан конкретный набор данных и известен его тип, можно математически высчитать его минимальный размер в упакованном виде?



Ну вот на ВиМ и обоснуй, упакуй в 2 КБ, текст книги ведь не бесконечный ;-)

Существует такое понятие, как информационная энтропия. Энтропия сообщения определяет предел сжатия. Так что насчет "всё можно упаковать в 2 кб" - это из области вечных двигателей.

[CodeMaster]

Так что насчет "всё можно упаковать в 2 кб" - это из области вечных двигателей.

Это не ко мне обращение.


Существует такое понятие, как информационная энтропия. Энтропия сообщения определяет предел сжатия.

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

[Spectramine]

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

Насколько я понимаю, энтропия сообщения определяется зависимостями символов сообщения. Чем более глубоко и разнообразно вычисляются зависимости символов друг от друга, тем более точно рассчитывается энтропия.

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

[HardWareMan]

Вы слышали про вавилонскую библиотеку (http://libraryofbabel.info/)? К сожалению, только английский текст, но есть ЛЮБОЙ! Не верите? Проверьте сами.

[CodeMaster]

Насколько я понимаю, энтропия сообщения определяется зависимостями символов сообщения.
Вроде нет. Она определяется вероятностью повторов.


Чем более глубоко и разнообразно вычисляются зависимости символов друг от друга
Не знаю как с зависимостью, но количество повторов в данных, вроде бы, вычисляется однозначно.


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


Вы слышали про вавилонскую библиотеку?
А как это относится к данной теме?

[NEO SPECTRUMAN]

К сожалению, только английский текст, но есть ЛЮБОЙ! Не верите? Проверьте сами.
в принципе можно ужать фаил в одну хеш суму 2К
а потом бруталфорсом перебирать все возможные варианты файла

так же можно сохранить указатель какой по счету файл с такой хеш суммой соответствует исходному

только этот файл должен быть с контролем ошибок

в итоге после перебирания всех возможных комбинаций файла
получется несколько десятков\сотен\тысяч\итд осмысленных файлов которые будут проходить контроль ошибок
и один из них будет соответствовать тому что мы запаковали

но это из разряда первую половину вечности файл пакуем
вторую распаковываем....

- - - Добавлено - - -


только английский текст, но есть ЛЮБОЙ! Не верите? Проверьте сами.
вот только путь к нужной книге будет занимать больше места чем сама книга...:v2_tong2:

- - - Добавлено - - -


Вы слышали про вавилонскую библиотеку?
я думал о таком только для картинок небольшого разрешения
но размеры и сложность обработки сразу.... ...что все это...

[CodeMaster]

один из них будет соответствовать тому что мы запаковали

Даже не поднимая вопрос, как компьютер будет проверять осмысленность данных (пусть даже текста, ибо не факт, что ему можно будеть объяснить, что "Сильмариллион" это осмысленный текст), как компьютер узнает, какой именно текст мы запаковали?

[NEO SPECTRUMAN]

Даже не поднимая вопрос, как компьютер будет проверять осмысленность данных (пусть даже текста, ибо не факт, что ему можно будеть объяснить, что "Сильмариллион" это осмысленный текст), как компьютер узнает, какой именно текст мы запаковали?
дык кодирование с контролем ошибок
контрольные суммы на каждые 256 байт например
номер файла с такой же хеш суммой по счету (скорей всего будет гигантских размеров)
ИИ (в далеком будещем например)


а так вероятность того что под эту же хеш суму
попадет какойто другой текст
без орфографических ошибок
лишних запятых
без непечатаемых символов итд
и содержащий осмысленный текст
наверное не так сильно высока

- - - Добавлено - - -


Даже не поднимая вопрос, как компьютер будет проверять осмысленность данных
проблема не так проверить осмысленность данных
а перебрать все возможные комбинации байтов файла (ну или не все можно и как то оптимизировать)

при самых простых контрольных суммах на это уйдет неимоверное количество времени

но оно хорошо дружит с многопоточностью!!!

- - - Добавлено - - -


какой именно текст мы запаковали?
наверное придется перебирать ручками
а оно ли это :v2_tong:
наверное это не сильно далеко уходит от "библиотеки" которую упомянул HardWareMan

понадобится еще целая куча места чтобы описать как отличить нужный файл

[Spectramine]

Вроде нет. Она определяется вероятностью повторов.
Энтропия вычисляется на основании вероятностей/частот символов. Простая энтропия - независимыми вероятностями символов, условная - вероятностями с учётом предшествующих символов.

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

Повторы - это повторяющиеся цепочки символов, я так понимаю? Жмутся не только повторяющиеся цепочки, но и отдельные символы с разной частотой появления. Cуществуют и другие специфические "артефакты" входного потока, поддающиеся сжатию.


Это и есть перебор: добавили словарь одного размера, посчитали энтропию, добавили второй, опять посчитали и т.д. пока не нашли идеальный размер словаря для конкретных данных.
Можно просмотреть весь поток/файл полностью, выявить все повторяющиеся цепочки, построить словарь - расширение алфавита, размером с количество входных символов + количество выделенных повторяющихся цепочек. Далее считаем энтропию. Никакого перебора.

[CodeMaster]

наверное придется перебирать ручками

Тогда уж сжимать книгу в код ISBN, а при распаковке брать её с полки и сканировать ручным сканером и распознавать OCR...

Думацо можно уже прекращать постить тут всякий бред.

[NEO SPECTRUMAN]

Думацо можно уже прекращать постить тут всякий бред.
на основе этого бреда
мну вспомнил
один свой старый алгоритм по сжатию (с нимоверно долгой распаковкой)
и внезапно почти придумал еще один новый (который может даже будет что то жать но явно не в 2к любой файл...)

[CodeMaster]

Повторы - это повторяющиеся цепочки символов, я так понимаю?
Повторы это повторы, хоть символы, хоть цепочки которые идут подряд.


Например, для текста важна зависимость вероятности текущего символа от предыдущего
Какие зависимости для энтропийного сжатия?


Можно просмотреть весь поток/файл полностью, выявить все повторяющиеся цепочки, построить словарь - расширение алфавита, размером с количество входных символов + количество выделенных повторяющихся цепочек. Далее считаем энтропию. Никакого перебора.

Чего так архиваторы не делают?

[Spectramine]

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



Какие зависимости для энтропийного сжатия? Для сжатия с фиксированными частотами символов, зависимостью можно считать общую таблицу частот символов. По оси X - номер символа, по оси Y - его частота. Зависимость, заданная таблично, плюс сумма частот символов =1, то есть частоты взаимозависимы.
Также для энтропийного сжатия используются зависимости частот символов от N-го количества предыдущих символов (условная энтропия).



Чего так архиваторы не делают? Если размер буфера >= размера файла, они так и делают. В остальном - видимо, ограничения на объем используемой памяти/время архивации поджимают.

[NEO SPECTRUMAN]

А где нибудь применяется упаковка с потерями
а потом отдельная упаковка разницы с оригиналом?

так чтоб в итоге получалось без потерь

[CodeMaster]

Если размер буфера >= размера файла, они так и делают.
Появится время, проверю на практике.


так чтоб в итоге получалось без потерь
Практически уверен, что коэффициент сжатия будет меньше, а время больше.

[NEO SPECTRUMAN]

Практически уверен, что коэффициент сжатия будет меньше, а время больше.
разница для изображений\звука будет +\- несколько цифер нет не будет
можно будет вообще срезать часть битов оставив знак и 2-4 бита на разницу
в придачу эти данные тоже можно будет запаковать


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

- - - Добавлено - - -

взял png картинку 375кб
ужал жипиэгом в 28кб
разница запихнутая в png 300кб

если жо положить Jpg и разницу в bmp в архив
получается 215 кб

оригинал в bmp пожатый 7z-ипом, как и ожидалось, занимает 220кб
при этом сам png практически не жмется 373кб

выгодней хранить пакованные bmp-щки

[Reobne]

NEO SPECTRUMAN, Попробуй ещё сжать ту-же картинку, Jpg-ом на максимальном качестве. Это подразумевает без потерь.

[NEO SPECTRUMAN]

Это подразумевает без потерь.
АГАЩАС без потерь...

[Reobne]

Когда экспериментировал, у меня получилось на максимальном сжатии 10% пикселей получили +-1. И ни одного пикселя не получили +-2 и более. И эта разница, после zip, в 5 раз меньше чем jpg.
Картинка картинке рознь.

[NEO SPECTRUMAN]

И ни одного пикселя не получили +-2 и более.
плавные градиенты наверное лучше пожмуться


Картинка картинке рознь.
ну до

[Barmaley_m]

Насколько я понимаю, стоит задача сжать один конкретный набор данных таким образом, чтобы размер депакера + размер запакованных данных были минимальными.

В таком случае теория знает эту задачу под названием "Колмогоровская сложность (https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BB%D0%BC%D0%BE%D0%B3%D0%BE%D1%80%D 0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D1%81%D0%BB%D0 %BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C)". Грубо говоря, колмогоровская сложность - это минимальная длина программы, которая выводит на экран заданную строку. При этом под "строкой" можно понимать распакованные данные, а под "выводом на экран" - процесс распаковки. Колмогоровская сложность зависит от того, на каком компьютере работает программа, но для компьютеров и языков общего назначения различия невелики.

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

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

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

Если бы алгоритм расчета колмогоровской сложности существовал - то были бы возможны следующие чудеса. Например: мы берем последовательно числа 0, 1, 2, 3 и т.д. Шифруем эти числа каким-нибудь неизвестным науке шифром, ключ не запоминаем. Получаем абракадабру на несколько гигабайт. И скармливаем её программе расчета колмогоровской сложности (которая, как мы на минуту представили, существует). Так вот, при этом программа расчета колмогоровской сложности "увидела бы", что та абракадабра, которую мы ей скормили, является на самом деле зашифрованным текстом; нашла бы алгоритм шифрования и ключ. И оформила бы вывод этой абракадабры на экран самым коротким образом - "синтезировав" программу, фактически повторяющую процесс шифрования.