Определённого конкретного набора данных, если единственным критерием будет коэффициент сжатия? Если да, то каково (примерно) различие идеального с оптимальным значением коэффициент/время?
Вид для печати
Определённого конкретного набора данных, если единственным критерием будет коэффициент сжатия? Если да, то каково (примерно) различие идеального с оптимальным значением коэффициент/время?
Да, существует. Любой набор данных можно упаковать в один байт (версия пакера), при условии что упаковщик/распаковщик будут модифицироваться под каждый конкретный входной файл и содержать полный словарь. :)
Шынни, велика вероятность потери данных. Да и не ко всем типам данных подходит.
Очень маленькое количество данных можно так упаковать. Понятно, что 2 байтами гораздо больше, но так же понятно, что и вопрос был не об этом.Цитата:
Сообщение от Bedazzle
Ну имхо несерьезное восприятие данной темы вполне естественно.
Вы ставите проблему, опираясь на два сомнительных предмета:
Можно говорить о максимальном сжатии. Об идеальном сжатии - вряд ли.Цитата:
идеальное сжатие без потери данных
Оптимальное для чего? Оптимальность - это в корне относительное понятие, крайне зависящее от конкретных задач и условий.Цитата:
оптимальным значением коэффициент/время
И далее вы предлагаете сравнить гипотетическое идеальное с относительным. Как?
Это всё софистика, думатцо 99,99% понятно, что речь идёт о минимальном размере набора служебные данные + словарь + сжатые данные.Цитата:
Сообщение от Black Cat / Era CG
Ответ в первом посте.Цитата:
Сообщение от Black Cat / Era CG
Т.е. максимальное теоретически возможное (a.k.a. идеальное) сжатие для данного набора данных и данного алгоритма равно, например, 51%, то в оптимальном для 90% случаев сжатии оно составляет например ~60% или может ~52%, интересно понять соотношение этих величин.Цитата:
Сообщение от CodeMaster
Если оцифровать белый шум с любой разрядностью - то
равно 0%.Цитата:
Сообщение от CodeMaster
Математически доказано, что для любого алгоритма Z сжатия данных можно подобрать два набора данных D1 и D2, таких, что:
1. Алгоритм Z для набора данных D1 будет самым эффективным из всех алгоритмов.
2. Алгоритм Z для набора данных D2 будет неэффективным (т.е. выходной файл данных будет по размеру больше входного).
То есть, если на минутку стать омерзительным философом-интеллегентом, о можно мрачно сказать "Ах, в этом мире нет ничего идеального!" и пойти пить водку:)
Вообще... - если брать в рассчёт теорию... - любой массив данных (включая бесконечный), можно упаковать (множественными проходами) в 2кб (учитывая, что данные 8-миразрядные!!)
эти два кб упакованных данных будут содержать 4 равных части - 1 словарь, 2 перекрестный словарь, 3 распаковщик и 4 сами упакованные данные :)
При каждом проходе распаковки, оба словаря обновляются, распаковщик остаётся без изменений.
Однако... - при множественной распаковке.... - чем больше объём данных, тем больше времени на распаковку (бесконечный объём данных будет распаковываться бесконечно) :)
P.S. Похоже на ахинею, но могу обосновать :)
P.P.S Про белый шум - добавляем к разрядности один пустой бит.... и всё замечательно пакуется! :)
ну идеального быть не можетЦитата:
Сообщение от CodeMaster
для каждого типа файла/конкретного файла идеальным будет свое сжатие
но как ни старайся в один битЦитата:
Сообщение от nlo_j77
больше чем 1 бит данных ты не запихнешь...
самое оптимальное не жать каждый файл по отдельности
а жать все вместе
оптимальное в нахождении максимально похожих участков
мне интересно почему до сих пор нету пакера с готовым встроенным словарем так мегабайт на 1000
Та это всё понятно. Вот например берём мы Войну и Мир в txt пакуем алгоритмом PPM (будем считать, что он лучший для текста) на выходе мы получим единственно возможный файл с упакованными данными минимального размера независимо от вычислительных возможностей? Другими словами, если нам дан конкретный набор данных и известен его тип, можно математически высчитать его минимальный размер в упакованном виде?Цитата:
Сообщение от NEO SPECTRUMAN
Ну вот на ВиМ и обоснуй, упакуй в 2 КБ, текст книги ведь не бесконечный ;-)Цитата:
Сообщение от nlo_j77
Одного бита вполне хватит для маркера изменённых данных.Цитата:
Сообщение от NEO SPECTRUMAN
Чтобы упаковать, надо не теоретически доказать, а написать пакер... - за него мне платить точно никто не будет (да и не нужен он никому, ибо больно медленно будет паковать/распаковывать)... - мне работа пока важнее :)Цитата:
Сообщение от CodeMaster
Мне пакер не нужен, мне теоретическое обоснование гораздо интереснее.Цитата:
Сообщение от nlo_j77
Это всё относительно.Цитата:
Сообщение от nlo_j77
Ну смотри - допустим мы преобразуем 8-ми битные данные в 7-ми и добавляем один бит маркера - дальше некоторые байты изменяем (допустим меняем на 0) и помечаем маркером в итоге получается пакующаяся последовательность (до этого ищем что и как изменить чтобы последовательность паковалась), пакуем и получаем опять последовательность (в теории упакованную процентов на 5-10, опять преобразуем данные в 7 бит с добавлением маркера... - в итоге получим нулевую последовательность с двумя словарями распаковки и данными, которые при паковке-преобразовании не будут менять своего размера - который, чисто в теории равен около 512 байт
Но процесс упаковки-распаковки, может с таким алгоритмом занять несколько лет, если не десятков лет.
Причём, как мы в своё время считали есть оптимальный размер файла, который будет паковаться за наименьшее время... - всё что больше, или меньше этой длины, будет паковаться дольше. (всё это относится исключительно к изначально непакующимся разнородным данным)
P.S. немного поясню - у нас непакующаяся последовательность 512 байт, а мы пакуем 513 - после, как минимум 512 проходов, её раздует до намного большего размера, а потом ещё за 512 проходов она упакуется в 512 байт (немного грубо, но смысл передаёт)
8 битами как ни старайся можно описать 256 разнообразных уникальных файловЦитата:
Сообщение от nlo_j77
как ни старайся ты не упакуешь больше
это же относится ко всему остальному
в один бит не вместишь 2Кб рандомных значений...
Существует такое понятие, как информационная энтропия. Энтропия сообщения определяет предел сжатия. Так что насчет "всё можно упаковать в 2 кб" - это из области вечных двигателей.Цитата:
Сообщение от CodeMaster
Это не ко мне обращение.Цитата:
Сообщение от weiv
Мне интересен не предел как таковой, а математическое обоснование этого предела. Насколько я понял, вот как раз для энтропийных алгоритмов сжатия можно математически высчитать максимальный коэф сжатия, а для словарных нет, там только методом перебора можно подобрать максимальное сжатие.Цитата:
Сообщение от weiv
Насколько я понимаю, энтропия сообщения определяется зависимостями символов сообщения. Чем более глубоко и разнообразно вычисляются зависимости символов друг от друга, тем более точно рассчитывается энтропия.Цитата:
Сообщение от CodeMaster
Словарные методы сжатия кодируют преобразованный алфавит входного потока, дополненный символами повторяющихся цепочек (либо символами длин и смещений). Добавьте эти символы к входному алфавиту, рассчитывайте энтропию с учетом этих символов и - вуаля, можно вычислить энтропию для словарных методов сжатия.
Вы слышали про вавилонскую библиотеку? К сожалению, только английский текст, но есть ЛЮБОЙ! Не верите? Проверьте сами.
Вроде нет. Она определяется вероятностью повторов.Цитата:
Сообщение от weiv
Не знаю как с зависимостью, но количество повторов в данных, вроде бы, вычисляется однозначно.Цитата:
Сообщение от weiv
Это и есть перебор: добавили словарь одного размера, посчитали энтропию, добавили второй, опять посчитали и т.д. пока не нашли идеальный размер словаря для конкретных данных.Цитата:
Сообщение от weiv
А как это относится к данной теме?Цитата:
Сообщение от HardWareMan
в принципе можно ужать фаил в одну хеш суму 2КЦитата:
Сообщение от HardWareMan
а потом бруталфорсом перебирать все возможные варианты файла
так же можно сохранить указатель какой по счету файл с такой хеш суммой соответствует исходному
только этот файл должен быть с контролем ошибок
в итоге после перебирания всех возможных комбинаций файла
получется несколько десятков\сотен\тысяч\итд осмысленных файлов которые будут проходить контроль ошибок
и один из них будет соответствовать тому что мы запаковали
но это из разряда первую половину вечности файл пакуем
вторую распаковываем....
- - - Добавлено - - -
вот только путь к нужной книге будет занимать больше места чем сама книга...:v2_tong2:Цитата:
Сообщение от HardWareMan
- - - Добавлено - - -
я думал о таком только для картинок небольшого разрешенияЦитата:
Сообщение от HardWareMan
но размеры и сложность обработки сразу.... ...что все это...
Даже не поднимая вопрос, как компьютер будет проверять осмысленность данных (пусть даже текста, ибо не факт, что ему можно будеть объяснить, что "Сильмариллион" это осмысленный текст), как компьютер узнает, какой именно текст мы запаковали?Цитата:
Сообщение от NEO SPECTRUMAN
дык кодирование с контролем ошибокЦитата:
Сообщение от CodeMaster
контрольные суммы на каждые 256 байт например
номер файла с такой же хеш суммой по счету (скорей всего будет гигантских размеров)
ИИ (в далеком будещем например)
а так вероятность того что под эту же хеш суму
попадет какойто другой текст
без орфографических ошибок
лишних запятых
без непечатаемых символов итд
и содержащий осмысленный текст
наверное не так сильно высока
- - - Добавлено - - -
проблема не так проверить осмысленность данныхЦитата:
Сообщение от NEO SPECTRUMAN
а перебрать все возможные комбинации байтов файла (ну или не все можно и как то оптимизировать)
при самых простых контрольных суммах на это уйдет неимоверное количество времени
но оно хорошо дружит с многопоточностью!!!
- - - Добавлено - - -
наверное придется перебирать ручкамиЦитата:
Сообщение от CodeMaster
а оно ли это :v2_tong:
наверное это не сильно далеко уходит от "библиотеки" которую упомянул HardWareMan
понадобится еще целая куча места чтобы описать как отличить нужный файл
Энтропия вычисляется на основании вероятностей/частот символов. Простая энтропия - независимыми вероятностями символов, условная - вероятностями с учётом предшествующих символов.Цитата:
Сообщение от CodeMaster
Зависимости символов возможны очень разные, и они определяют их вероятности появления, чем больше выявлено зависимостей, тем точнее вычисляются вероятности появления символов. Например, для текста важна зависимость вероятности текущего символа от предыдущего, а для экрана спектрума - зависимость вероятности текущего байта не только от предыдущего, но и от байта, отстоящего на 256 байт назад.
Повторы - это повторяющиеся цепочки символов, я так понимаю? Жмутся не только повторяющиеся цепочки, но и отдельные символы с разной частотой появления. Cуществуют и другие специфические "артефакты" входного потока, поддающиеся сжатию.
Можно просмотреть весь поток/файл полностью, выявить все повторяющиеся цепочки, построить словарь - расширение алфавита, размером с количество входных символов + количество выделенных повторяющихся цепочек. Далее считаем энтропию. Никакого перебора.Цитата:
Это и есть перебор: добавили словарь одного размера, посчитали энтропию, добавили второй, опять посчитали и т.д. пока не нашли идеальный размер словаря для конкретных данных.
Тогда уж сжимать книгу в код ISBN, а при распаковке брать её с полки и сканировать ручным сканером и распознавать OCR...Цитата:
Сообщение от NEO SPECTRUMAN
Думацо можно уже прекращать постить тут всякий бред.
на основе этого бредаЦитата:
Сообщение от CodeMaster
мну вспомнил
один свой старый алгоритм по сжатию (с нимоверно долгой распаковкой)
и внезапно почти придумал еще один новый (который может даже будет что то жать но явно не в 2к любой файл...)
Повторы это повторы, хоть символы, хоть цепочки которые идут подряд.Цитата:
Сообщение от weiv
Какие зависимости для энтропийного сжатия?Цитата:
Сообщение от weiv
Чего так архиваторы не делают?Цитата:
Сообщение от weiv
А, понятно, о каких повторах идет речь. Количество этих повторов действительно можно вычислить однозначно, но к вычислению энтропии они имеют отдаленное отношение. Для вычисления безусловной энтропии "повторы" вообще не используются, для условной они - редкий частный случай зависимости вероятности очередного символа от предыдущих.Цитата:
Повторы это повторы, хоть символы, хоть цепочки которые идут подряд.
Для сжатия с фиксированными частотами символов, зависимостью можно считать общую таблицу частот символов. По оси X - номер символа, по оси Y - его частота. Зависимость, заданная таблично, плюс сумма частот символов =1, то есть частоты взаимозависимы.Цитата:
Какие зависимости для энтропийного сжатия?
Также для энтропийного сжатия используются зависимости частот символов от N-го количества предыдущих символов (условная энтропия).
Если размер буфера >= размера файла, они так и делают. В остальном - видимо, ограничения на объем используемой памяти/время архивации поджимают.Цитата:
Чего так архиваторы не делают?
А где нибудь применяется упаковка с потерями
а потом отдельная упаковка разницы с оригиналом?
так чтоб в итоге получалось без потерь
Появится время, проверю на практике.Цитата:
Сообщение от weiv
Практически уверен, что коэффициент сжатия будет меньше, а время больше.Цитата:
Сообщение от NEO SPECTRUMAN
Цитата:
Сообщение от CodeMaster
разница для изображений\звука будет +\- несколько цифернет не будет
можно будет вообще срезать часть битов оставив знак и 2-4 бита на разницу
в придачу эти данные тоже можно будет запаковать
мне кажетсо должно быть среднее между сжатием с потерями и сжатием без потерьЦитата:
Сообщение от CodeMaster
а время должно увеличится не так значительно
сжатие с потерями, как по мне, требует больше ресурсов чем сжатие без потерь
- - - Добавлено - - -
взял png картинку 375кб
ужал жипиэгом в 28кб
разница запихнутая в png 300кб
если жо положить Jpg и разницу в bmp в архив
получается 215 кб
оригинал в bmp пожатый 7z-ипом, как и ожидалось, занимает 220кб
при этом сам png практически не жмется 373кб
выгодней хранить пакованные bmp-щки
NEO SPECTRUMAN, Попробуй ещё сжать ту-же картинку, Jpg-ом на максимальном качестве. Это подразумевает без потерь.
АГАЩАС без потерь...Цитата:
Сообщение от Reobne
Когда экспериментировал, у меня получилось на максимальном сжатии 10% пикселей получили +-1. И ни одного пикселя не получили +-2 и более. И эта разница, после zip, в 5 раз меньше чем jpg.
Картинка картинке рознь.
плавные градиенты наверное лучше пожмутьсяЦитата:
Сообщение от Reobne
ну доЦитата:
Сообщение от Reobne
Насколько я понимаю, стоит задача сжать один конкретный набор данных таким образом, чтобы размер депакера + размер запакованных данных были минимальными.
В таком случае теория знает эту задачу под названием "Колмогоровская сложность". Грубо говоря, колмогоровская сложность - это минимальная длина программы, которая выводит на экран заданную строку. При этом под "строкой" можно понимать распакованные данные, а под "выводом на экран" - процесс распаковки. Колмогоровская сложность зависит от того, на каком компьютере работает программа, но для компьютеров и языков общего назначения различия невелики.
К сожалению, в теории доказывается, что колмогоровская сложность невычислима. Не существует алгоритма, который мог бы по заданной строке рассчитать ее колмогоровскую сложность.
Следствие - не существует алгоритма, который бы по заданной строке нашел бы программу минимальной длины, которая выводит эту строку на экран. В самом деле, если бы такой алгоритм существовал - то можно было бы тупо измерить длину получившейся программы и тем самым вычислить колмогоровскую сложность, что противоречит п. 1.
Также невозможно проверить, является ли заданная программа минимальной для вывода на экран некоторой строки.
Если бы алгоритм расчета колмогоровской сложности существовал - то были бы возможны следующие чудеса. Например: мы берем последовательно числа 0, 1, 2, 3 и т.д. Шифруем эти числа каким-нибудь неизвестным науке шифром, ключ не запоминаем. Получаем абракадабру на несколько гигабайт. И скармливаем её программе расчета колмогоровской сложности (которая, как мы на минуту представили, существует). Так вот, при этом программа расчета колмогоровской сложности "увидела бы", что та абракадабра, которую мы ей скормили, является на самом деле зашифрованным текстом; нашла бы алгоритм шифрования и ключ. И оформила бы вывод этой абракадабры на экран самым коротким образом - "синтезировав" программу, фактически повторяющую процесс шифрования.