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

[CodeMaster]

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

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

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

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

[Advertiser]

[nlo_j77]

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

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

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

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

[CodeMaster]

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

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

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

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

[Spectramine]

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



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

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

[CodeMaster]

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

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

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

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

[HardWareMan]

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

[CodeMaster]

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

Вроде нет. Она определяется вероятностью повторов.

Чем более глубоко и разнообразно вычисляются зависимости символов друг от друга

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

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

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

Вы слышали про вавилонскую библиотеку?

А как это относится к данной теме?

[Spectramine]

Вроде нет. Она определяется вероятностью повторов.

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

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

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

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

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

[CodeMaster]

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

Повторы это повторы, хоть символы, хоть цепочки которые идут подряд.

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

Какие зависимости для энтропийного сжатия?

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

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

[Spectramine]

Повторы это повторы, хоть символы, хоть цепочки которые идут подряд.

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

Какие зависимости для энтропийного сжатия?

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

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

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