How to become an author
Search
Write a publication
Pull to refresh

Comments 42

Это все фигня, вот у Алексея Бабушкина алгоритм сжимает с 2Гб в 2Кб.
А самое главное, он поделился своим секретом. Надо данные перевести в HEX, а потом DEC. А когда получите большое число, надо прибавить нолик в начало, и найти такое число, которое при деление на что-то, получит такое же число :) Обычно на это, у Алексея уходило около 2х часов, но он пообещал исправить алгоритм.
Взято со страницы ВК: vk.com/mefistofell
Total votes 69: ↑14 and ↓55-41
Изначально хотел в топик добавить про Бабушкина, а потом думаю — зачем, всё равно появится в первом комментарии. :)
Total votes 63: ↑63 and ↓0+63
Когда в соответствующем топике шло обсуждение, я по-быстрому набросал программку, представляющую длинную десятичную дробь в виде максимально короткой обыкновенной (и, думаю, не я один — многие хотя бы попробовали поиграться с подборщиком дробей).
По результатам «исследования» хотел даже написать статью на Хабр, но потом решил, что пользы от такой статьи ноль. Но, если кратко, результат таков.
За некоторыми исключениями, в общем случае в обыкновенной дроби получается ровно столько же цифр, сколько и в десятичной, например:
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.
Total votes 30: ↑30 and ↓0+30
Насколько я знаю существует оптимальный способ представления дробей! И намного красивее и не зависит от системы исчесления.
Непрерывная дробь (цепная дробь). Доказано, что частичные дроби дают наилучшее приближение в виде простых дробей для иррациональных чисел. + Квадратные корни представимы в виде периодической цепной дроби, что позволяет существенно сжать информацию.
В общем, если есть необходимость записать огромную в дробь в компактной записи используйте ряд коэфициентов цепной дроби.

Существует хорошая книга Арнольда по этому поводу www.mccme.ru/mmmf-lectures/books/books/book.14.pdf.
Total votes 2: ↑2 and ↓0+2
Есть арифметическое кодирование, которое в результате некоторых преобразований превращает любую последовательность данных в некую рациональную дробь (возможно, довольно длинную). Дальше мы приближаем нашу дробь двоичной дробью и получаем выходной файл.

Арифметическое сжатие – самое эффективное сжатие (даже теоретически – доказано, что лучше нельзя), не учитывающее последовательности символом (все символы сжимаются независимо).
This comment wasn’t rated yet0
Судя по времени работы и использованию эвристики, алгоритм скорее надо сравнивать с PPM, PAQ и подобным семейством.
Total votes 4: ↑4 and ↓0+4
Интереса ради запаковал тестовые файлы с помощью PPMd (есть в 7zip):
Canterbury:
    Zopfli - 669,993
    PPMd   - 574,757
enwik8:
    Zopfli - 34,995,756
    PPMd   - 22,506,231

В этой категории от алгоритма тоже толку мало.
Total votes 5: ↑5 and ↓0+5
Вы забываете об обратной совместимости. ppmd не распакуется как любой зип.
Total votes 4: ↑4 and ↓0+4
Достаточно подключить Zopfli на сервере.

Как я понял, получается не простой *zip, а все-таки собственный формат.
Если это не так, то да, зачитываем в плюс алгоритма. Вот только относительная степень сжатия все равно столь мала, что он имеет смысл только на десятках и сотнях гигабит, imo.
Total votes 4: ↑2 and ↓20
на сервере для сжатия, распаковывает его просто браузер
Total votes 3: ↑3 and ↓0+3
Алгоритм интересен тем, что в браузере уже есть его реализация, чего не скажешь о PPM.
Total votes 5: ↑5 and ↓0+5
Google ничего не стоит в один момент добавить в Chrome и на свои CDN новый алгоритм. Они проделывали это тысячу раз начиная с транспортного уровня (quic), заканчивая webm, webp, spdy, NaCl, dart, и т. д. Стандарт HTTP предусматривает поле Accept-Encoding, которое сейчас обычно «gzip, deflate» и никто не запрещает сделать «ppmd, gzip, deflate». Тысячи сайтов, которые в хроме дают на четверть меньше трафика для скриптов — чем не конкурентное преимущество? Вопрос не в том, что нет реализации, а в том, что нет алгоритма-кандидата, который бы обеспечивал хорошее соотношение затрат на распаковку и степени сжатия. Что PPMd, что LZMA(2), оба расжимаются значительно медленнее gzip. Остаются вариации PPM? Появление новых алгоритмов в Accept-Encoding это только вопрос времени.
Total votes 6: ↑5 and ↓1+4
Они уже добавляли bzip2 (убрали) и sdch (добавили, но никто не использует). Это ещё не факт, что будут пользоваться.
Total votes 3: ↑3 and ↓0+3
Не совсем корректно сравнивать контекстно-независимый алгоритм deflate и контекстно-зависимый PPMd на текстовых данных.
Я понимаю, что все хотят использовать zopfli на стороне сервера и сжимать html, js и сss.

Нужно бы на бинарных данных проверить (любят на Firefox тестировать, кажется).
Total votes 1: ↑1 and ↓0+1
Тестовый набор Canterbury содержит в себе бинарные файлы. На нем тоже есть сравнение.
This comment wasn’t rated yet0
Я уже посмотрел – там один xls-файл бинарный. Но он составляет только треть архива. Остальное – чистые тексты.
This comment wasn’t rated yet0
Эмм… А ptt5, sum? Суммарно 56% выходит. Понятно, что мелкие архивы, но все же.
This comment wasn’t rated yet0
Значит, не заметил. Прошу прощения.
Всё равно zopfli выглядит какой-то тупиковой веткой.
Total votes 1: ↑1 and ↓0+1
Скорее не тупиковой веткой, а собственно тупиком, т.е. логичным (и возможно последним?) пределом развития deflate-подобных алгоритмов.
This comment wasn’t rated yet0
Статику хорошо будет жать, а вот на лету со 100 кратным увеличением нагрузки — как-то сомнительно.
Total votes 4: ↑4 and ↓0+4
Некая компрессия в браузере смысл имеет, но, все же, жать даже gzip-9 стандартные динамические (т.к. сжатие будет происходить на каждый запрос) страницы сайта — уже барство, ибо загрузка сервера выше и дольше, а скорость загрузки при этом у клиента меняется в сравнении с gzip-5 не сильно.

На этом фоне заторомозить сжатие страницы еще во много раз — идея очень редко нужная, ибо уж очень нечастая задача ее оправдывает.

gzip_static, соглашусь, более вероятный кандидат для использования нового алгоритма. Другое дело, что, если при сжатии «обычным» и новым алгоритмами (и учитывая их разницу во времени работы) разница в кол-ве пакетов для передачи того же файла будет или очень небольшой, или ее вообще не будет, то смысла возиться нет вообще — а, судя по тестам, так оно почти со всеми страницами и будет.
Total votes 2: ↑2 and ↓0+2
так себе результаты

на jquery-1.8.3-min разница в 120 байт (7z gz ultra против -i1000)
на 40kb css файле на 60% состоящем из base64 разница 300 байт

даже для gzip_static, я бы не стал возиться
Total votes 2: ↑2 and ↓0+2
Думаю, смысл использования от использования данного алгоритма сжатия будет лишь у проектов, у которых огромный трафик, например Google или Facebook.
This comment wasn’t rated yet0
Ещё для CDN для того же jQuery и т.п., типа ajax.googleapis.com. Там столько трафика, что даже 3% это уже дофига.
Total votes 7: ↑7 and ↓0+7
Больше % экономии можно добиться хорошей настройкой работы с TCP протоколом, например, отсылать ACK и FIN вместе с данными (TCP_CORK).
This comment wasn’t rated yet0
Deflate-алгоритмы сжатия не являются лидерами по качеству / скорости / ресурсоемкости
Хотя хорошая интегральная характеристика по этим трем компонентам и привела к повсеместному распространению
Total votes 3: ↑3 and ↓0+3
… а так же популярность формата zip в досовские времена
This comment wasn’t rated yet0
между прочим, архиваторы pkzip/pkunzip в «ранние досовские времена» использовали другие методы сжатия.
ru.wikipedia.org/wiki/Pkzip
Deflate появился только в 93-ем году, к тому времени «зипование» уже было популярным явлением
(Ой, щас буду вспоминать White Bear BBS — держите меня семеро!)
Были всякие ARJ / LHA / PKARC / HA и ACB
Total votes 3: ↑3 and ↓0+3
Не сыпьте соль на рану… ARJ… моя преееелесть… ^^
Total votes 2: ↑1 and ↓10
Из перечисленных вами только HA резко выделялся во времена BBS. Ой, как же тяжело он на моем 286 он распаковывался… Но вся литература обычно как раз сисопами и жалась в HA. Как сейчас помню: скачал «Лабиринт отражений», и пару минут наблюдал «HA 0.99 © Harri Hirvola»
Total votes 4: ↑3 and ↓1+2
ha — реализация ppm ;)
Total votes 1: ↑1 and ↓0+1
Картинка смешная — четыре символа заменяются на шесть, что как бы намекает на то что это не сжатие совсем, а наоборот символов стало на 33% больше.
Total votes 3: ↑0 and ↓3-3
А что короче между «лето» и [4,12]? :)
Там же образное отображение идеи, а не побайтный дамп.
Если взять подход RLE, то [4,12] превращается в 2 байта. При исходных 4 (ABCD).
This comment wasn’t rated yet0
Для Джавовских JAR и Андройдовских APK отлично подойдет же!
Total votes 3: ↑3 and ↓0+3
Мне одному кажется, что результаты в сравнении с ресурсоемкостью алгоритма настолько сомнительны, что так и остался бы алгоритм никому не известным, если бы не имя Google?
This comment wasn’t rated yet0
Кстати, на основе этого Zopfli можно написать улучшенный вариант PNGOUT/OptiPNG! Вот и профит от него для Web-а будет.
Total votes 2: ↑2 and ↓0+2
Прекрасный проект, и прекрасное применение данного алгоритма! Плюс вам в карму, и семь футов под килем!
This comment wasn’t rated yet0
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
This comment wasn’t rated yet0
Забавно, что все еще имеет смысл накатить поверх deflopt'ом
Total votes 1: ↑0 and ↓1-1
Sign up to leave a comment.

Articles

Show the best of all time

Your account

Sections

Information

Services

Support
© 2006–2024, Habr