ну идеального быть не можетСообщение от CodeMaster
для каждого типа файла/конкретного файла идеальным будет свое сжатие
но как ни старайся в один бит
больше чем 1 бит данных ты не запихнешь...
самое оптимальное не жать каждый файл по отдельности
а жать все вместе
оптимальное в нахождении максимально похожих участков
мне интересно почему до сих пор нету пакера с готовым встроенным словарем так мегабайт на 1000
С любовью к вам, Yandex.Direct
Размещение рекламы на форуме способствует его дальнейшему развитию
Та это всё понятно. Вот например берём мы Войну и Мир в txt пакуем алгоритмом PPM (будем считать, что он лучший для текста) на выходе мы получим единственно возможный файл с упакованными данными минимального размера независимо от вычислительных возможностей? Другими словами, если нам дан конкретный набор данных и известен его тип, можно математически высчитать его минимальный размер в упакованном виде?
Ну вот на ВиМ и обоснуй, упакуй в 2 КБ, текст книги ведь не бесконечный ;-)
Последний раз редактировалось CodeMaster; 13.08.2017 в 22:13.
"Во времена всеобщей лжи говорить правду - это экстремизм" - афоризм.
Одного бита вполне хватит для маркера изменённых данных.
Чтобы упаковать, надо не теоретически доказать, а написать пакер... - за него мне платить точно никто не будет (да и не нужен он никому, ибо больно медленно будет паковать/распаковывать)... - мне работа пока важнее
Мне пакер не нужен, мне теоретическое обоснование гораздо интереснее.
Это всё относительно.
"Во времена всеобщей лжи говорить правду - это экстремизм" - афоризм.
Ну смотри - допустим мы преобразуем 8-ми битные данные в 7-ми и добавляем один бит маркера - дальше некоторые байты изменяем (допустим меняем на 0) и помечаем маркером в итоге получается пакующаяся последовательность (до этого ищем что и как изменить чтобы последовательность паковалась), пакуем и получаем опять последовательность (в теории упакованную процентов на 5-10, опять преобразуем данные в 7 бит с добавлением маркера... - в итоге получим нулевую последовательность с двумя словарями распаковки и данными, которые при паковке-преобразовании не будут менять своего размера - который, чисто в теории равен около 512 байт
Но процесс упаковки-распаковки, может с таким алгоритмом занять несколько лет, если не десятков лет.
Причём, как мы в своё время считали есть оптимальный размер файла, который будет паковаться за наименьшее время... - всё что больше, или меньше этой длины, будет паковаться дольше. (всё это относится исключительно к изначально непакующимся разнородным данным)
P.S. немного поясню - у нас непакующаяся последовательность 512 байт, а мы пакуем 513 - после, как минимум 512 проходов, её раздует до намного большего размера, а потом ещё за 512 проходов она упакуется в 512 байт (немного грубо, но смысл передаёт)
Последний раз редактировалось nlo_j77; 14.08.2017 в 22:43.
8 битами как ни старайся можно описать 256 разнообразных уникальных файлов
как ни старайся ты не упакуешь больше
это же относится ко всему остальному
в один бит не вместишь 2Кб рандомных значений...
Существует такое понятие, как информационная энтропия. Энтропия сообщения определяет предел сжатия. Так что насчет "всё можно упаковать в 2 кб" - это из области вечных двигателей.
Это не ко мне обращение.
Мне интересен не предел как таковой, а математическое обоснование этого предела. Насколько я понял, вот как раз для энтропийных алгоритмов сжатия можно математически высчитать максимальный коэф сжатия, а для словарных нет, там только методом перебора можно подобрать максимальное сжатие.
"Во времена всеобщей лжи говорить правду - это экстремизм" - афоризм.
Насколько я понимаю, энтропия сообщения определяется зависимостями символов сообщения. Чем более глубоко и разнообразно вычисляются зависимости символов друг от друга, тем более точно рассчитывается энтропия.
Словарные методы сжатия кодируют преобразованный алфавит входного потока, дополненный символами повторяющихся цепочек (либо символами длин и смещений). Добавьте эти символы к входному алфавиту, рассчитывайте энтропию с учетом этих символов и - вуаля, можно вычислить энтропию для словарных методов сжатия.
Последний раз редактировалось Spectramine; 15.08.2017 в 13:25.
Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)
Ваши права
Ответить с цитированием
