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

[nlo_j77]

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

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

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

[Advertiser]

[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]

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

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

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