Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 42
Это все фигня, вот у Алексея Бабушкина алгоритм сжимает с 2Гб в 2Кб.
А самое главное, он поделился своим секретом. Надо данные перевести в HEX, а потом DEC. А когда получите большое число, надо прибавить нолик в начало, и найти такое число, которое при деление на что-то, получит такое же число :) Обычно на это, у Алексея уходило около 2х часов, но он пообещал исправить алгоритм.
Взято со страницы ВК: vk.com/mefistofell
А самое главное, он поделился своим секретом. Надо данные перевести в HEX, а потом DEC. А когда получите большое число, надо прибавить нолик в начало, и найти такое число, которое при деление на что-то, получит такое же число :) Обычно на это, у Алексея уходило около 2х часов, но он пообещал исправить алгоритм.
Взято со страницы ВК: vk.com/mefistofell
Изначально хотел в топик добавить про Бабушкина, а потом думаю — зачем, всё равно появится в первом комментарии. :)
Когда в соответствующем топике шло обсуждение, я по-быстрому набросал программку, представляющую длинную десятичную дробь в виде максимально короткой обыкновенной (и, думаю, не я один — многие хотя бы попробовали поиграться с подборщиком дробей).
По результатам «исследования» хотел даже написать статью на Хабр, но потом решил, что пользы от такой статьи ноль. Но, если кратко, результат таков.
За некоторыми исключениями, в общем случае в обыкновенной дроби получается ровно столько же цифр, сколько и в десятичной, например:
Значительный выигрыш можно получить при сжатии периодических дробей вида 0.X(Y)n с повторяющимся «хвостом», а также в некоторых частных случаях, довольно редких:
Причём от длины дроби этот самый выигрыш никак не зависит (последний пример особенно показателен, когда дробь с громаднейшим количеством повторений даёт выигрыш в 1 цифру). Если посмотреть статистику распределения «выигрышных» дробей на числовой оси, получается довольно удручающая картина: видно, что некоторое сжатие возможно всего в 2.7% случаев, причём эти счастливые случаи распределены весьма равномерно, и из них подавляющее большинство даёт выигрыш всего 1 цифру (по-видимому, это связано с тем, что у обыкновенных дробей нет ограничений по точности — переводя их в десятичные, можно вычислить сколь угодно много знаков после запятой).
Переход к восьмеричной системе счисления никак не поменял общей картины (а переделывать библиотеку BigNumber под двоичные и шестнадцатеричные числа мне было откровенно лень).
В итоге, даже очень хитро извратившись (например, нарезав файл на кусочки небольшой длины и переведя в дробь каждый кусочек), получим крайне ничтожный выигрыш, который нацело съедают два факта:
Тем не менее, на основе этой «идеи» возможно написать алгоритм, по эффективности сжатия близкий к RLE.
По результатам «исследования» хотел даже написать статью на Хабр, но потом решил, что пользы от такой статьи ноль. Но, если кратко, результат таков.
За некоторыми исключениями, в общем случае в обыкновенной дроби получается ровно столько же цифр, сколько и в десятичной, например:
0.55 = 5/9
0.123 = 8/65
0.1235=11/89
1513748957234095723948572348957234589
23759823495723489572349572358973248977 =
6451435714817374103222462663515810501 / 42618927557217687537475866931148217146
Значительный выигрыш можно получить при сжатии периодических дробей вида 0.X(Y)n с повторяющимся «хвостом», а также в некоторых частных случаях, довольно редких:
0.55555555555 = 5/9
1234567 = 10/81
111111111111111111166666666666688888888888888888
888555555555555555555559999999999977777777777666
666666666666888888888888888999999999966677777555
554444444466666669000000000004444444444444433333 =
40794740312874221278684064243002291903427193257
006746411080848729199282910340405775349993739573 / 367152662815867991324580246779013200935991442325
290302640364562363935155639050137213967980478817
Причём от длины дроби этот самый выигрыш никак не зависит (последний пример особенно показателен, когда дробь с громаднейшим количеством повторений даёт выигрыш в 1 цифру). Если посмотреть статистику распределения «выигрышных» дробей на числовой оси, получается довольно удручающая картина: видно, что некоторое сжатие возможно всего в 2.7% случаев, причём эти счастливые случаи распределены весьма равномерно, и из них подавляющее большинство даёт выигрыш всего 1 цифру (по-видимому, это связано с тем, что у обыкновенных дробей нет ограничений по точности — переводя их в десятичные, можно вычислить сколь угодно много знаков после запятой).
Переход к восьмеричной системе счисления никак не поменял общей картины (а переделывать библиотеку BigNumber под двоичные и шестнадцатеричные числа мне было откровенно лень).
В итоге, даже очень хитро извратившись (например, нарезав файл на кусочки небольшой длины и переведя в дробь каждый кусочек), получим крайне ничтожный выигрыш, который нацело съедают два факта:
- Необходимо хранить длину каждого кусочка, иначе мы просто не поймём, сколько знаков после запятой нужно вычислять при распаковке
- Коль размеры чисел в обыкновенной дроби различны, нам как-то нужно указывать их длины (или позицию символа дроби "/" в строке)
Тем не менее, на основе этой «идеи» возможно написать алгоритм, по эффективности сжатия близкий к RLE.
Насколько я знаю существует оптимальный способ представления дробей! И намного красивее и не зависит от системы исчесления.
Непрерывная дробь (цепная дробь). Доказано, что частичные дроби дают наилучшее приближение в виде простых дробей для иррациональных чисел. + Квадратные корни представимы в виде периодической цепной дроби, что позволяет существенно сжать информацию.
В общем, если есть необходимость записать огромную в дробь в компактной записи используйте ряд коэфициентов цепной дроби.
Существует хорошая книга Арнольда по этому поводу www.mccme.ru/mmmf-lectures/books/books/book.14.pdf.
Непрерывная дробь (цепная дробь). Доказано, что частичные дроби дают наилучшее приближение в виде простых дробей для иррациональных чисел. + Квадратные корни представимы в виде периодической цепной дроби, что позволяет существенно сжать информацию.
В общем, если есть необходимость записать огромную в дробь в компактной записи используйте ряд коэфициентов цепной дроби.
Существует хорошая книга Арнольда по этому поводу www.mccme.ru/mmmf-lectures/books/books/book.14.pdf.
Есть арифметическое кодирование, которое в результате некоторых преобразований превращает любую последовательность данных в некую рациональную дробь (возможно, довольно длинную). Дальше мы приближаем нашу дробь двоичной дробью и получаем выходной файл.
Арифметическое сжатие – самое эффективное сжатие (даже теоретически – доказано, что лучше нельзя), не учитывающее последовательности символом (все символы сжимаются независимо).
Арифметическое сжатие – самое эффективное сжатие (даже теоретически – доказано, что лучше нельзя), не учитывающее последовательности символом (все символы сжимаются независимо).
Интереса ради запаковал тестовые файлы с помощью PPMd (есть в 7zip):
В этой категории от алгоритма тоже толку мало.
Canterbury:
Zopfli - 669,993
PPMd - 574,757
enwik8:
Zopfli - 34,995,756
PPMd - 22,506,231
В этой категории от алгоритма тоже толку мало.
Вы забываете об обратной совместимости. ppmd не распакуется как любой зип.
Алгоритм интересен тем, что в браузере уже есть его реализация, чего не скажешь о PPM.
Google ничего не стоит в один момент добавить в Chrome и на свои CDN новый алгоритм. Они проделывали это тысячу раз начиная с транспортного уровня (quic), заканчивая webm, webp, spdy, NaCl, dart, и т. д. Стандарт HTTP предусматривает поле Accept-Encoding, которое сейчас обычно «gzip, deflate» и никто не запрещает сделать «ppmd, gzip, deflate». Тысячи сайтов, которые в хроме дают на четверть меньше трафика для скриптов — чем не конкурентное преимущество? Вопрос не в том, что нет реализации, а в том, что нет алгоритма-кандидата, который бы обеспечивал хорошее соотношение затрат на распаковку и степени сжатия. Что PPMd, что LZMA(2), оба расжимаются значительно медленнее gzip. Остаются вариации PPM? Появление новых алгоритмов в Accept-Encoding это только вопрос времени.
Не совсем корректно сравнивать контекстно-независимый алгоритм deflate и контекстно-зависимый PPMd на текстовых данных.
Я понимаю, что все хотят использовать zopfli на стороне сервера и сжимать html, js и сss.
Нужно бы на бинарных данных проверить (любят на Firefox тестировать, кажется).
Я понимаю, что все хотят использовать zopfli на стороне сервера и сжимать html, js и сss.
Нужно бы на бинарных данных проверить (любят на Firefox тестировать, кажется).
Статику хорошо будет жать, а вот на лету со 100 кратным увеличением нагрузки — как-то сомнительно.
Некая компрессия в браузере смысл имеет, но, все же, жать даже gzip-9 стандартные динамические (т.к. сжатие будет происходить на каждый запрос) страницы сайта — уже барство, ибо загрузка сервера выше и дольше, а скорость загрузки при этом у клиента меняется в сравнении с gzip-5 не сильно.
На этом фоне заторомозить сжатие страницы еще во много раз — идея очень редко нужная, ибо уж очень нечастая задача ее оправдывает.
gzip_static, соглашусь, более вероятный кандидат для использования нового алгоритма. Другое дело, что, если при сжатии «обычным» и новым алгоритмами (и учитывая их разницу во времени работы) разница в кол-ве пакетов для передачи того же файла будет или очень небольшой, или ее вообще не будет, то смысла возиться нет вообще — а, судя по тестам, так оно почти со всеми страницами и будет.
На этом фоне заторомозить сжатие страницы еще во много раз — идея очень редко нужная, ибо уж очень нечастая задача ее оправдывает.
gzip_static, соглашусь, более вероятный кандидат для использования нового алгоритма. Другое дело, что, если при сжатии «обычным» и новым алгоритмами (и учитывая их разницу во времени работы) разница в кол-ве пакетов для передачи того же файла будет или очень небольшой, или ее вообще не будет, то смысла возиться нет вообще — а, судя по тестам, так оно почти со всеми страницами и будет.
так себе результаты
на jquery-1.8.3-min разница в 120 байт (7z gz ultra против -i1000)
на 40kb css файле на 60% состоящем из base64 разница 300 байт
даже для gzip_static, я бы не стал возиться
на jquery-1.8.3-min разница в 120 байт (7z gz ultra против -i1000)
на 40kb css файле на 60% состоящем из base64 разница 300 байт
даже для gzip_static, я бы не стал возиться
Deflate-алгоритмы сжатия не являются лидерами по качеству / скорости / ресурсоемкости
Хотя хорошая интегральная характеристика по этим трем компонентам и привела к повсеместному распространению
Хотя хорошая интегральная характеристика по этим трем компонентам и привела к повсеместному распространению
… а так же популярность формата zip в досовские времена
между прочим, архиваторы pkzip/pkunzip в «ранние досовские времена» использовали другие методы сжатия.
ru.wikipedia.org/wiki/Pkzip
Deflate появился только в 93-ем году, к тому времени «зипование» уже было популярным явлением
(Ой, щас буду вспоминать White Bear BBS — держите меня семеро!)
Были всякие ARJ / LHA / PKARC / HA и ACB
ru.wikipedia.org/wiki/Pkzip
Deflate появился только в 93-ем году, к тому времени «зипование» уже было популярным явлением
(Ой, щас буду вспоминать White Bear BBS — держите меня семеро!)
Были всякие ARJ / LHA / PKARC / HA и ACB
Не сыпьте соль на рану… ARJ… моя преееелесть… ^^
Из перечисленных вами только HA резко выделялся во времена BBS. Ой, как же тяжело он на моем 286 он распаковывался… Но вся литература обычно как раз сисопами и жалась в HA. Как сейчас помню: скачал «Лабиринт отражений», и пару минут наблюдал «HA 0.99 © Harri Hirvola»
Картинка смешная — четыре символа заменяются на шесть, что как бы намекает на то что это не сжатие совсем, а наоборот символов стало на 33% больше.
Для Джавовских JAR и Андройдовских APK отлично подойдет же!
Мне одному кажется, что результаты в сравнении с ресурсоемкостью алгоритма настолько сомнительны, что так и остался бы алгоритм никому не известным, если бы не имя Google?
Кстати, на основе этого Zopfli можно написать улучшенный вариант PNGOUT/OptiPNG! Вот и профит от него для Web-а будет.
(ошибся уровнем, комментарий адресовался Lorents
FAIL
13:~# wget https://zopfli.googlecode.com/files/zopfli-1.0.0.zip
13:~# unzip zopfli-1.0.0.zip
13:~# zip -9 -r test.zip zopfli-1.0.0
13:~# ls -l zopfli-1.0.0.zip test.zip
-rw-r--r-- 1 root root 57822 Май 27 16:07 test.zip
-rw-r--r-- 1 root root 57873 Апр 25 20:11 zopfli-1.0.0.zip
Забавно, что все еще имеет смысл накатить поверх deflopt'ом
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Новый алгоритм Zopfli улучшает сжатие zlib на 3-8%