The OpenNET Project / Index page

[ новости /+++ | форум | wiki | теги | ]



"Facebook открыл реализацию алгоритма сжатия Zstandard"
Вариант для распечатки  
Пред. тема | След. тема 
Форум Разговоры, обсуждение новостей
Изначальное сообщение [ Отслеживать ]

"Facebook открыл реализацию алгоритма сжатия Zstandard"  +/
Сообщение от opennews (??), 01-Сен-16, 11:42 
Facebook опубликовал (https://code.facebook.com/posts/1658392934479273/smaller-and.../) библиотеку и инструментарий для работы с новым эффективным алгоритмом сжатия данных Zstandard (http://www.zstd.net/), по сравнению с zlib/Deflate демонстрирующим в 3-5  раз более высокую скорость сжатия и в два раза более быструю распаковку, при уровне сжатия выше на 10-15%. Zstandard подходит для организации сжатия в режиме реального времени и может рассматриваться как оптимальный компромисс, между быстрым но неэффективым lz4 и медленным но хорошо сжимающим xz. Код написан на языке Си  и распространяется (https://github.com/facebook/zstd) под лицензией BSD.


В Zstandard задействован метод кодирования конечного состояния энтропии (Finite State Entropy (https://github.com/Cyan4973/FiniteStateEntropy)), в котором для кодирования энтропии применяется теория  асимметричных численных систем (http://arxiv.org/abs/1311.2540) (Asymmetric Numeral Systems (http://www.ezcodesample.com/abs/abs_article.html)). Эффективность и скорость сжатия в Zstandard очень близка к предложенному Google алгоритму brotli (https://www.opennet.ru/opennews/art.shtml?num=43006), но Zstandard почти в три раза быстрее при распаковке. По скорости сжатия и распаковки Zstandard  заметно отстаёт от Snappy (330 и 940 MB/s против 480 и 1600 MB/s), но опережает его по уровню сжатия почти на 30%.

Особенностью Zstandard является возможность тренировки для повышения эффективности сжатия мелких наборов данных. Алгоритм можно оптимизировать для определённого типа данных, сформировав словарь на основе предварительно предоставленных примеров. Словарь загружается до сжатия или распаковки и позволяет существенно повысить степень сжатия для типовых данных. Например, использование словаря, размером 64 Кб позволяет увеличить уровень сжатия с 2.8 до 6.9  при упаковке данных о 1000 пользователях GitHub (846 Кб со словарём сжимаеться  в 122 Кб, а без в 300 Кб).


В отличие от zlib в Zstandard также предоставлены гибкие средства для использования доступных аппаратных возможностей - под окно сжатия можно выделить несколько Mб памяти (в zlib используется 32 Кб), поддерживается распараллеливание операций на многоядерных CPU. Кроме того, Zstandard предоставляет более широкий диапазон для  варьирования параметрами упаковки - на выбор предоставляется 22 уровня сжатия (1 - важна скорость, 22 - важен размер), позволяющих увеличить степень сжатия за счёт снижения скорости или, наоборот, повысить скорость ценой эффективности сжатия. В будущем число уровней сжатия планируется увеличить, также будут предоставлены типовые словари для увеличения эффективности сжатия  JSON, HTML и типовых сетевых протоколов.


URL: https://code.facebook.com/posts/1658392934479273/smaller-and.../
Новость: http://www.opennet.ru/opennews/art.shtml?num=45058

Ответить | Правка | Cообщить модератору

Оглавление

Сообщения по теме [Сортировка по времени | RSS]


1. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +1 +/
Сообщение от Аноним (-), 01-Сен-16, 11:42 
Кто-нибудь пояснит, при чём здесь Facebook? До этого я думал, что автором Zstd является автор алгоритма LZ4 и открыт он был ещё в начале прошлого года, если не раньше: https://www.opennet.ru/opennews/art.shtml?num=41534
Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

2. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +/
Сообщение от Аноним (-), 01-Сен-16, 11:46 
Микрософт вон атом изобрёл, а пейспук — сабж. Всё ок.
Ответить | Правка | ^ к родителю #1 | Наверх | Cообщить модератору

3. "Facebook открыл реализацию алгоритма сжатия Zstandard"  –1 +/
Сообщение от commiethebeastie (ok), 01-Сен-16, 11:50 
Билл ГейТс изобрел интернеты.
Ответить | Правка | ^ к родителю #2 | Наверх | Cообщить модератору

10. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +2 +/
Сообщение от ано (?), 01-Сен-16, 13:13 
Ты лжешь! Интернеты изобрел Стиви Жопс из Эйпол
Ответить | Правка | ^ к родителю #3 | Наверх | Cообщить модератору

32. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +2 +/
Сообщение от Sluggard (ok), 01-Сен-16, 20:49 
Не-не-не. Они изобрели скруглённые углы.
Ответить | Правка | ^ к родителю #10 | Наверх | Cообщить модератору

37. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +/
Сообщение от Аноним (-), 01-Сен-16, 21:35 
Вы все не правы. Интернеты изобрели в ЦРУ.
Ответить | Правка | ^ к родителю #32 | Наверх | Cообщить модератору

41. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +1 +/
Сообщение от Yurisemail (??), 02-Сен-16, 09:42 
Вы нас плавно подводите к тому, что Фэйсбук проект ЦРУ? ;)
Ответить | Правка | ^ к родителю #37 | Наверх | Cообщить модератору

51. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +/
Сообщение от Аноним (-), 03-Сен-16, 16:39 
> Не-не-не. Они изобрели скруглённые углы.

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

Ответить | Правка | ^ к родителю #32 | Наверх | Cообщить модератору

52. "Facebook открыл реализацию алгоритма сжатия Zstandard"  –1 +/
Сообщение от Sluggard (ok), 03-Сен-16, 16:45 
> Вы будете ржать, но автор сабжа учился на маркетолога. Но в какой-то
> момент решил что труба шатал углы закруглять. И занялся сжатием. Преуспев
> в этом получше многих других.

Бывает, что такого. И анестезиологи вон ядро пишут. У меня приятель филолог писал под Symbian сперва на Python, потом на C++.

Ответить | Правка | ^ к родителю #51 | Наверх | Cообщить модератору

6. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +/
Сообщение от anonymous (??), 01-Сен-16, 12:26 
Автору хочется кушать, приходится работать на дядю
Ответить | Правка | ^ к родителю #1 | Наверх | Cообщить модератору

8. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +10 +/
Сообщение от Crazy Alex (ok), 01-Сен-16, 12:50 
Ужас-то какой.

Вообще-то работа на дядю в IT в большинстве случаев на порядок комфортнее и спокойнее работы на себя. И не факт, что в минус по деньгам. Работая на себя слишком много профессий совмещать приходится.

Ответить | Правка | ^ к родителю #6 | Наверх | Cообщить модератору

30. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +/
Сообщение от Аноним (-), 01-Сен-16, 20:34 
А в чем работа на дядю состоит? Чувак что так пилил свой алгоритм что эдак. Дядя заинтересовался в этом результате и нанял чувака чтобы тот мог делать то что делает фултайм. Результвт доступен что дяде, что чуваку, что нам с вами.

В последних ревизиях годный кстати алгоритм. Жмет лучше zlib и при том распаковывается быстрее. Именно с zstd яппл собезьянничал свой алгоритм.

Ответить | Правка | ^ к родителю #6 | Наверх | Cообщить модератору

11. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +1 +/
Сообщение от Аноним (-), 01-Сен-16, 13:33 
Так он работает в Facebook
Ответить | Правка | ^ к родителю #1 | Наверх | Cообщить модератору

39. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +/
Сообщение от Аноним (-), 02-Сен-16, 02:56 
Был в Оранжевом филиале французской компании.
FB больше платит.
Ответить | Правка | ^ к родителю #11 | Наверх | Cообщить модератору

12. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +/
Сообщение от Аноним84701 (?), 01-Сен-16, 13:45 
> Кто-нибудь пояснит, при чём здесь Facebook? До этого я думал, что автором
> Zstd является автор алгоритма LZ4 и открыт он был ещё в
> начале прошлого года, если не раньше: https://www.opennet.ru/opennews/art.shtml?num=41534

Поясняю: автору не только новые алгоритмы изобретать, но иногда в процессе изобретательства и кушать  хочется,  да и ночевать скорее всего предпочитает в теплой постельке, под крышей ;)


Ответить | Правка | ^ к родителю #1 | Наверх | Cообщить модератору

38. "Facebook открыл реализацию алгоритма сжатия Zstandard"  –1 +/
Сообщение от Аноним (-), 01-Сен-16, 21:40 
Кушать, крыша и тёплая постелька несовместимы с понятиями Настоящей Свободы.

Ответить | Правка | ^ к родителю #12 | Наверх | Cообщить модератору

13. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +/
Сообщение от Andrey Mitrofanov (?), 01-Сен-16, 14:04 
> Кто-нибудь пояснит, при чём здесь Facebook? До этого я думал, что автором
> Zstd является автор алгоритма LZ4 и открыт он был ещё в
> начале прошлого года, если не раньше: https://www.opennet.ru/opennews/art.shtml?num=41534

Ср.:

25.01.2015 09:47  Автор LZ4 представил новый быстрый и эффективный алгоритм сжатия ZSTD

Ян Колле (Yann Collet), автор эталонной реализации алгоритма LZ4, представил новый [...]

и

https://code.facebook.com/posts/1658392934479273/smaller-and...
17 hours agoData · Performance · Storage
Smaller and faster data compression with Zstandard
Yann Collet Chip Turner

People are creating, sharing, and storing [...]


Выводы?

Ответить | Правка | ^ к родителю #1 | Наверх | Cообщить модератору

21. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +/
Сообщение от ктонибудь (?), 01-Сен-16, 17:33 
> Кто-нибудь пояснит, при чём здесь Facebook?

объясняем: мордокнижка платит афттару zstandard зарплату. Чтобы он мог заниматься своей метафи...зачеркнуто, математикой, с девяти до восьми с перерывом на обед, а не стоять в очереди за бесплатным.

> До этого я думал, что автором Zstd является автор алгоритма LZ4 и открыт он был ещё в

если не полениться, побороть страх и сомнения и открыть таки ссылку - то ты увидишь, что фейсбучная статья подписана (в том числе) пресловутым автором алгоритма.

И то что опубликовано сейчас - работающий как они выразились "ready to production" код, а не proof of concept, который был "в начале прошлого года".

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

Теперь прикинем, как это будет внутри какой-нибудь rasp pi, где нет branch prediction (и любой branchless код просто длиннее и медленнее нормального), дорогая 64битная арифметика, где нет лишних ядер, лишней памяти - а заодно оценим количество менее вырожденных случаев (когда тот же opennet ротейтит логи, ага). Ну или даже фейсбук - который под сжатие своих релейшн графов может выделить целую ферму специально-сжимающих серверов, но графов у него нифига не один, поэтому совершенно наплевать, будут шестнадцать ядер жевать шестнадцать графов поочередно тредами, или параллельно - каждый своим ядром.

И задумаемся - а почему, собственно, гениальный математик даже не подумал в эту сторону?

Ну и вишенка на тортике - изящно вынести специфический(!) словарь в ../ и почему-то проигнорировать тот факт, что его размер вообще-то сопоставим со сжатым результатом. Неотъемлемой частью которого он, на самом-то деле, является.

Поневоле закрадываются сомнения - там все остальное-то нормально сделано?

Ответить | Правка | ^ к родителю #1 | Наверх | Cообщить модератору

23. "Facebook открыл реализацию алгоритма сжатия Zstandard"  –1 +/
Сообщение от qwerty (??), 01-Сен-16, 18:34 
>- изящно вынести специфический(!) словарь в ../

если данных терабайтами и при этом вариабельность 100k словаря за год  0%,
то почему бы и нет?

Ответить | Правка | ^ к родителю #21 | Наверх | Cообщить модератору

47. "Facebook открыл реализацию алгоритма сжатия Zstandard"  –1 +/
Сообщение от . (?), 02-Сен-16, 14:42 
>> - изящно вынести специфический(!) словарь в ../
> если данных терабайтами и при этом вариабельность 100k словаря за год  0%,

вы совсем читать не умеете? Ну ладно первоисточник ниасилить (это ж надо было весь этот булшит не просто прочесть по диагонали, но и проверить подозрительный момент) - но слово _специфический_ вами тоже не понято?

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


Ответить | Правка | ^ к родителю #23 | Наверх | Cообщить модератору

36. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +6 +/
Сообщение от Аноним (-), 01-Сен-16, 21:05 
> Теперь прикинем, как это будет внутри какой-нибудь rasp pi, где нет branch
> prediction (и любой branchless код просто длиннее и медленнее нормального), дорогая
> 64битная арифметика, где нет лишних ядер, лишней памяти -

Я сравнивал разные LZ-образные на одноядерном ARMv7. Это несколько отличается от x86.

1) LZ4: по прежнему в лидерах скорости сжатия/распаковки. Может догнаться до скорости memcpy(), а на хорошо сжимаемых данных даже обогнать memcpy (вероятно, разгрузив read исходных данных из оперативы по сравнению с memcpy). Ratio как обычно скромный. А он сильно жать в принципе не может. Не для этого он.

2) Zstd: в отличие от x86 где zstd заметно быстрее zlib, на ARM zstd примерно как zlib. Ну может капельку быстрее иногда. Но жмет все-равно значительно лучше zlib'а. Профит по любому.

3) Brotli. Это уже тяжеловес. По скорости на ARM уже несколько сливает zlib. Но жмет кардинально плотнее и на верхних уровнях приближается к LZMA. Распаковываясь в ТРИ РАЗА быстрее чем LZMA на том же проце. Тоже вполне приятный tradeoff. Нагло жульничает на вебне используя встроенный словарь на добрых 120 кило.

Ответить | Правка | ^ к родителю #21 | Наверх | Cообщить модератору

48. "Facebook открыл реализацию алгоритма сжатия Zstandard"  –1 +/
Сообщение от . (?), 02-Сен-16, 15:05 
> Я сравнивал разные LZ-образные на одноядерном ARMv7. Это несколько отличается от x86.

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

> проце. Тоже вполне приятный tradeoff. Нагло жульничает на вебне используя встроенный
> словарь на добрых 120 кило.

ну это не нагло. Нагло это в исходной статье - сперва пообучать алгоритм, потом отложить словарик, потом _эти_же_ данные (не какие-то похожие, а именно те) сжать. (причем оно таки делало zlib чуть ли не в восемь раз даже с учетом словаря, совершенно неясно, зачем понадобилось такое мелкое жульничество. Возможно, ларчик откроется, если засечь время обучения- вызов time там тоже скромно опущен ;) Если словарь является частью программы, ничего плохого в этом я не вижу (как, собственно, и в специфическом словаре, упакованном вместе с данными, кто-то из ранних досовских архиваторов именно так и работал...аццки долго ;)

Ответить | Правка | ^ к родителю #36 | Наверх | Cообщить модератору

53. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +/
Сообщение от Аноним (-), 03-Сен-16, 17:11 
> спасибо, это как раз то, чего не сделали авторы - что и
> вызывает у меня удивление. Скудоумием они явно не могли страдать, значит
> - намеренная и осознаваемая подмена понятий.

Больше похоже на то что они так просто не умеют.

> Причем совсем непонятно, чего ради - на первый взгляд и честный анализ
> должен был дать достаточно достойные результаты.

ARM вообще забавные штуки. Там соотношения скорости проца vs скорость оперативы другие и в целом соотношения привычные на х86 могут ощутимо перекоситься. Хотя общая идея остается.

Кроме того сильно роялит какие именно были данные. Некоторые виды данных сильно лучше сжимаются если сделать (обратимый) препроцессинг, а при распаковке - вернуть как было. Если грамотно выбрать тестовый набор данных - можно выпятить почти любой алгоритм и задвинуть остальных. Единственная проблема: в других случаях цифры могут быть гораздо менее красивые. Поэтому самый надежный способ - пустить ряд алгоритмов на своих данных и посмотреть что получится. Иногда бывает даже такой "парадокс" что gzip -3 может сжать и лучше и быстрее чем gzip -9. Это касается и многих других алгоритмов, хоть и по разным причинам.

> каждый пятый файл вообще не cможет потом распаковать.

Ну это врядли. Мордокнига думаю мощно потестирует в продакшне. Да и до этого алгоритм народ немало гонял. Это впрочем вообще не архиватор а библа сжатия. Поверх которой можно запилить в том числе и архиватор.

>> проце. Тоже вполне приятный tradeoff. Нагло жульничает на вебне используя встроенный
>> словарь на добрых 120 кило.
> ну это не нагло. Нагло это в исходной статье - сперва пообучать алгоритм, потом
> отложить словарик, потом _эти_же_ данные (не какие-то похожие, а именно те) сжать.

Так гугл именно это и сделал: погонял brotli на своей выборке вебни. Сдампил наиболее удачный словарь. Вшил его прямо в библу (более +120 кил к весу либы). И теперь оно на вебне накручивает себе ratio только в путь. Точно так же его может накрутить и сабж, это ровно настолько же (не)честно. Проблема этого метода в том что если данные не похожи на то что в словаре, профита не наступает и цифры гораздо более скромные.

> (причем оно таки делало zlib чуть ли не в восемь раз даже с учетом словаря,
> совершенно неясно, зачем понадобилось такое мелкое жульничество.

Это не столько жульничество, сколько showcase себя любимого с демонстрацией того что можно получить за пределами zlib. Ну да, автор маркетолог-недоучка, поэтому умеет себя показать с выгодной стороны :). Но в целом он предпринял усилия для оптимизации алгоритма и доведения до ума и в целом tradeoff удачный вышел.

> Возможно, ларчик откроется, если засечь время обучения-

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

Словарь - это такая оптимизация если характер данных известен. Если это не так то он лишь раздувает либу и ничего не привносит.  По этой причине прошаренные compression contest меряют размер "код для распаковки + сжатые данные". Иначе кто-то снесет половину данных в код и выиграет, "распаковав". Ну это такой совсем частный случай словаря, одноразовый :)

> специфическом словаре, упакованном вместе с данными, кто-то из ранних досовских
> архиваторов именно так и работал...аццки долго ;)

В общем случае внешний словарь имеет смысл только если есть достаточно большой набор однотипных данных, так что перенос некоторошо типового shared куска в либу или рядом себя окупит. Гугл ориентировался на вебню - ну и вынес в такой кусок типовые теги/слова/etc. Почему сабжу так должно юыть нельзя - хз :)

Ответить | Правка | ^ к родителю #48 | Наверх | Cообщить модератору

46. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +/
Сообщение от arisu (ok), 02-Сен-16, 10:14 
> Поневоле закрадываются сомнения - там все остальное-то нормально сделано?

нормально. просто подобные штуки хоть и не принято сейчас называть «пресс‐релизы», но по сути это именно пресс‐релиз. соответственно, рассказывается о плюсах, умалчивается о минусах и всё такое. потому что надо продать. кому непонятно, что именно продаётся — пусть спускается с небес.

Ответить | Правка | ^ к родителю #21 | Наверх | Cообщить модератору

54. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +/
Сообщение от Аноним (-), 03-Сен-16, 17:26 
Автор zstd должен был стать маркетологом. Но как-то случайно подсел на алгоритмы и програмизм. Это ему настолько вштырило что он послал карьеру маркетолога и занялся алгоритмами сжатия.

Так что он умеет преподнести себя в выгодном свете. Но соль не в том. Он упрямый чувак, хорошо разбирается в оптимизациях и поэтому смог догнаться до высот на которых сломали зубы многие матерые програмеры. Zstd не самый быстрый и не самый плотный. Зато он практичный и серьезно претендует на нишу zlib, который с точки зрения технологий мало ушел от эпохи DOSовых архиваторов. Zstd в той же нише, только лучше. И по скорости распаковки и по достижимой степени сжатия.

Ответить | Правка | ^ к родителю #46 | Наверх | Cообщить модератору

55. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +/
Сообщение от arisu (ok), 03-Сен-16, 17:30 
а я нигде не писал, что сабж плохой, если что. я просто немного потоптался на форме презентации.
Ответить | Правка | ^ к родителю #54 | Наверх | Cообщить модератору

59. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +/
Сообщение от Аноним (-), 03-Сен-16, 18:25 
> а я нигде не писал, что сабж плохой, если что. я просто
> немного потоптался на форме презентации.

Топтаться на презентации маркетолога занятие неблагодарное. Маркетологи это умеют. А то что одним маркетологом меньше и одним програмером больше - вообще фича :P.

Ответить | Правка | ^ к родителю #55 | Наверх | Cообщить модератору

4. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +2 +/
Сообщение от Сергей (??), 01-Сен-16, 11:51 
Читайте внимательней,  алгоритм и его реализация в виде кода...
Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

5. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +/
Сообщение от Аноним (-), 01-Сен-16, 12:08 
Реализация в виде кода была сделана автором LZ4 и было выпущено много версий. И только к последней версии под номером 1.0.0 примазался Facebook.
Ответить | Правка | ^ к родителю #4 | Наверх | Cообщить модератору

15. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +/
Сообщение от Andrey Mitrofanov (?), 01-Сен-16, 14:34 
> Реализация в виде кода была сделана автором LZ4 и было выпущено много
> версий. И только к последней версии под номером 1.0.0 примазался Facebook.

Эти гады ещё и перелицензировали код с-под GPLv2+ на MIT.  Караул!!

https://github.com/facebook/zstd/commit/0588ee66cc003ab781c7...
https://github.com/facebook/zstd/commit/4ded9e591cbed57c54fc...
https://github.com/facebook/zstd/commit/1c59c20903ecd2881c09...

И да, не забываем
https://github.com/facebook/zstd/search?q=facebook
отписывать контрибуции
https://github.com/facebook/zstd/commit/4ded9e591cbed57c54fc...

...https://github.com/Cyan4973/FiniteStateEntropy/search?q=Yann...
---https://github.com/facebook/zstd/search?q=Yann+Collet+Facebook

Ответить | Правка | ^ к родителю #5 | Наверх | Cообщить модератору

16. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +/
Сообщение от MMx (?), 01-Сен-16, 15:53 
А что это за КЛА?
Что за контрибуции?
Что за???
Ответить | Правка | ^ к родителю #15 | Наверх | Cообщить модератору

17. "Facebook открыл реализацию алгоритма сжатия Zstandard"  +/
Сообщение от MMx (?), 01-Сен-16, 15:55 
Это какой-та не опенсорц
Ответить | Правка | ^ к родителю #15 | Наверх | Cообщить модератору

27. "Facebook открыл реализацию алгоритма сжатия Zstandard"  –1 +/
Сообщение от Аноним (-), 01-Сен-16, 20:27 
А так можно? MIT вроде не допускает перелицензирование?
Ответить | Правка | ^ к родителю #15 | Наверх | Cообщить модератору

31. "Facebook открыл реализацию алгоритма сжатия Zstandard"  –1 +/
Сообщение от Аноним (-), 01-Сен-16, 20:38 
> А так можно? MIT вроде не допускает перелицензирование?

В mit как и bsd - полтора условия. Поверх которых можно нашлепнуть любые другие без нарушения лицензии ;). Проприерасы вообще EULA всем в рожу тычут, и ничего, так можно. А GPL чем принципиально отличается от других лицензий? :)

Ответить | Правка | ^ к родителю #27 | Наверх | Cообщить модератору

43. "Facebook открыл реализацию алгоритма сжатия Zstandard"  –1 +/
Сообщение от Andrey Mitrofanov (?), 02-Сен-16, 09:48 
> А так можно? MIT вроде не допускает перелицензирование?

--Дядя Юра, Вы дурак?

Ответить | Правка | ^ к родителю #27 | Наверх | Cообщить модератору

50. "Facebook открыл реализацию алгоритма сжатия Zstandard"  –1 +/
Сообщение от lemon tree (?), 03-Сен-16, 00:19 
Может, автор продал свои исходники Фейсбуку?
Ответить | Правка | ^ к родителю #15 | Наверх | Cообщить модератору

7. "Facebook опубликовал реализацию алгоритма сжатия Zstandard 1..."  –1 +/
Сообщение от mmm (??), 01-Сен-16, 12:41 
А если туда ещё и lepton подмешать - на jpg-ах всех порвёт.
Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

9. "Facebook опубликовал реализацию алгоритма сжатия Zstandard 1..."  +/
Сообщение от Аноним (-), 01-Сен-16, 13:10 
А почему никто не обращает внимание на фрактальное сжатие? Патенты уже истекли.
Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

18. "Facebook опубликовал реализацию алгоритма сжатия Zstandard 1..."  +/
Сообщение от Аноним (-), 01-Сен-16, 16:06 
> А почему никто не обращает внимание на фрактальное сжатие? Патенты уже истекли.

две причины - оно сильно Ассиметрично. распаковка - весьма шустра а сжатие в десятки, порой сотни раз медленее.
а второе - там необычная математика и ... программисты - просто не осилят прикручивать либы(две компании, лицензировавшие у луравэйв/лизардтех уже после покупки остатков итератед оными в конце нулевых - так и не смогли купленные либы прикрутить к своему решению, несмотря на то что в Ф500 входят и опыт "абстрактной" разработки софта у них - был).


Ответить | Правка | ^ к родителю #9 | Наверх | Cообщить модератору

33. "Facebook опубликовал реализацию алгоритма сжатия Zstandard 1..."  –1 +/
Сообщение от Аноним (-), 01-Сен-16, 20:50 
> две причины - оно сильно Ассиметрично. распаковка - весьма шустра а сжатие
> в десятки, порой сотни раз медленее.

Обычный Lempel-Ziv к этому вполне склонен и у того же Zstd есть высокие уровни сжатия, где он жмет раз в 100 медленнее распаковки. Зато наилучшее сжатие в пределах выбранного формата данных. И если важен размер и совместимость с именно этим декомпрессором и можно подождать, то это вполне себе вариант.

Кстати если кому LZ4 нравится...

...раз! http://create.stephan-brumme.com/smallz4/
...два! https://github.com/encode84/lz4x/tree/master/src

Да-да. Это подарочки от спецов сжатия - "optimal parsing" для LZ4. Крайне несимметрично по скорости, с целью выжать наилучшее сжатие в пределах выбранного формата любой ценой (несколько проходов и скорость под стать). Актуально для pre-compressed данных. Ну там ядро Linux например сжимаетя 1 раз а декомпрессится при каждой загрузке. Один раз в жизни разработчику можно и подождать, а чуть более быстрая загрузка его систем - будет вообще всегда и везде.

Первый кстати еще и с годным описанием что такое optimal parsing. Если кому учебники по вещам типа LZ кажутся слишком простыми и скучными, это пример того как делают лучшие алгоритмы сейчас, выжимая максимум в пределах заданного формата.

Ответить | Правка | ^ к родителю #18 | Наверх | Cообщить модератору

14. "Facebook опубликовал реализацию алгоритма сжатия Zstandard 1..."  +1 +/
Сообщение от Аноним (-), 01-Сен-16, 14:32 
> конечного состояния энтропии (Finite State Entropy)

МГИМО финишд?

Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

28. "Facebook опубликовал реализацию алгоритма сжатия Zstandard 1..."  +/
Сообщение от Аноним (-), 01-Сен-16, 20:32 
>> конечного состояния энтропии (Finite State Entropy)
> МГИМО финишд?

Аск

Ответить | Правка | ^ к родителю #14 | Наверх | Cообщить модератору

19. "Facebook опубликовал реализацию алгоритма сжатия Zstandard 1..."  +2 +/
Сообщение от Аноним (-), 01-Сен-16, 16:53 
Пеговый Дудочник
Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

22. "Facebook опубликовал реализацию алгоритма сжатия Zstandard 1..."  +1 +/
Сообщение от anonymous (??), 01-Сен-16, 18:27 
МПеговый дудочник
Ответить | Правка | ^ к родителю #19 | Наверх | Cообщить модератору

25. "Facebook опубликовал реализацию алгоритма сжатия Zstandard 1..."  –1 +/
Сообщение от Аноним (-), 01-Сен-16, 19:25 
Что ты несешь?
Ответить | Правка | ^ к родителю #22 | Наверх | Cообщить модератору

34. "Facebook опубликовал реализацию алгоритма сжатия Zstandard 1..."  –1 +/
Сообщение от Аноним. (?), 01-Сен-16, 20:54 
> МПеговый дудочник

MPEGLA'овый :)

Впрочем для MPEGLA тоже подарочек есть: https://aomedia.googlesource.com/aom - эта крутень дает довольно приличную картинку 1080P даже при ... 500 Кбит?! Вау. Эй, H.264 а попробуй так же? И чтоб не превратиться в блочную муть? :)

Ответить | Правка | ^ к родителю #22 | Наверх | Cообщить модератору

40. "Facebook опубликовал реализацию алгоритма сжатия Zstandard 1..."  +/
Сообщение от KBAKEP (ok), 02-Сен-16, 05:05 
Скорее уж H.265.
Ответить | Правка | ^ к родителю #34 | Наверх | Cообщить модератору

44. "Facebook опубликовал реализацию алгоритма сжатия Zstandard 1..."  +/
Сообщение от Аноним (-), 02-Сен-16, 09:52 
тогда уж AV1 и Daaala, Thor ;)
Theora-у ванильную - тоже вяло(но ощутимо)допиливают да и VP8, VP9 для "внутреннего использования" гугль юзает вовсю )
Ответить | Правка | ^ к родителю #40 | Наверх | Cообщить модератору

58. "Facebook опубликовал реализацию алгоритма сжатия Zstandard 1..."  +/
Сообщение от Аноним (-), 03-Сен-16, 18:24 
> тогда уж AV1 и Daaala, Thor ;)
> Theora-у ванильную - тоже вяло(но ощутимо)допиливают да и VP8, VP9 для "внутреннего
> использования" гугль юзает вовсю )

На VP8 почти забили. Из него сильно больше уже не выжмешь. VP9 достаточно активно пилят и фиксят. Daala частично внедрили в AV1, который в первом приближении смесь VP10 с Daala, может и из Thor чего-то выдрали. Основные коммитеры - из daala и vp10.

Ответить | Правка | ^ к родителю #44 | Наверх | Cообщить модератору

56. "Facebook опубликовал реализацию алгоритма сжатия Zstandard 1..."  +/
Сообщение от Аноним (-), 03-Сен-16, 18:20 
> Скорее уж H.265.

Наздоровье, гугл и ко задались целью его уделать. И уже уделывают существующие реализации. Они взяли лучшее из всех. В будущий VP10 заинтегрили части из Daala. Кодирование энтропии - новомодный FSE. Который на распаковку быстрый, есть надежды что несмотря на круть кодека он не будет тормозным в проигрывании, в отличие от.

Благодаря запчастям от Daala - артефакты неназойливые, поэтому фулхдец на 500 кбит и катит: сложно заметить где на..бка :). На...бка не похожа на мпеговские квадратики.

Алсо, в вебе H.265 не будет. Там ТРИ акулы мочатся за право лицензировать это. Поэтому за перспективы H.265 никто ломанного гроша не даст. Даже MS подписался в это - значит лиса хром и ишак будут уметь AV1 сразу как его сделают. И эта толпа таки анализирует патенты до того как вываливать "типа, стандарты". H.265 ну никак не конкурент AV1. Вокруг него нет такой task force, которые не только формат подгоняют но и референсный кодер-декодер сразу пишут под открытой лицензией.

Ответить | Правка | ^ к родителю #40 | Наверх | Cообщить модератору

26. "Facebook опубликовал реализацию алгоритма сжатия Zstandard 1..."  +/
Сообщение от Аноним (-), 01-Сен-16, 20:24 
Использую в двух своих проектах. При равной скорости векторные изображения жмет на 40% сильнее zlib.
Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

35. "Facebook опубликовал реализацию алгоритма сжатия Zstandard 1..."  +/
Сообщение от Аноним (-), 01-Сен-16, 20:57 
> Использую в двух своих проектах. При равной скорости векторные изображения жмет на
> 40% сильнее zlib.

Да почти все жмет лучше чем zlib. Особенно если данных больше чем 32Кб. Все-таки 32 Кб окно без возможности увеличения - ловит мало совпадений. Ну и FSE как вторая стадия - это такой удачный компромисс где скорость побольше чем у хаффмана при том что степень сжатия на уровне арифметического кодиорования. Это Jarek Duda придумал свой ANS и потом пополам с спецами по сжатию прикрутили все это к реальным алгоритмам. Так появился FSE.

Ответить | Правка | ^ к родителю #26 | Наверх | Cообщить модератору

42. "Facebook опубликовал реализацию алгоритма сжатия Zstandard 1..."  +1 +/
Сообщение от Аноним (-), 02-Сен-16, 09:43 
А как это прикрутить к pifs?
Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

64. "Facebook опубликовал реализацию алгоритма сжатия Zstandard 1..."  +/
Сообщение от Аноним (64), 03-Янв-19, 14:34 
Месье долгожитель что пользуется pifs?
Ответить | Правка | ^ к родителю #42 | Наверх | Cообщить модератору

45. "Facebook опубликовал реализацию алгоритма сжатия..."  +2 +/
Сообщение от arisu (ok), 02-Сен-16, 10:10 
словари рулят. берёшь, значит, весь исходный файл, и засовываешь его в словарь. БУМ! всех порвал, мегасжатие, скорость потрясающая, памяти почти не требует.

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

Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

57. "Facebook опубликовал реализацию алгоритма сжатия..."  +/
Сообщение от Аноним (-), 03-Сен-16, 18:21 
> вообще, многопроходное сжатие — скучное читерство.

А в каком месте optimal parsing например - читерство?

Ответить | Правка | ^ к родителю #45 | Наверх | Cообщить модератору

60. "Facebook опубликовал реализацию алгоритма сжатия..."  +/
Сообщение от arisu (ok), 03-Сен-16, 18:54 
>> вообще, многопроходное сжатие — скучное читерство.
> А в каком месте optimal parsing например - читерство?

именно в том. читерство и есть, к тому же ещё и тормозное.

Ответить | Правка | ^ к родителю #57 | Наверх | Cообщить модератору

62. "Facebook опубликовал реализацию алгоритма сжатия..."  +/
Сообщение от нах (?), 05-Сен-16, 10:02 
> словари рулят. берёшь, значит, весь исходный файл, и засовываешь его в словарь

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

> вообще, многопроходное сжатие — скучное читерство.

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

Для данных которые "сжимаются один раз, распаковываются тыщу" нет ничего ужасного в том, что при сжатии тратится время на словарь. До тех пор, пока однопроходное сжатие не оказывается только на пару процентов хуже ;-)

В общем, совершенно загадочно, зачем им это понадобилось - когда и честное сравнение в их пользу.

Ответить | Правка | ^ к родителю #45 | Наверх | Cообщить модератору

63. "Facebook опубликовал реализацию алгоритма сжатия..."  +/
Сообщение от arisu (ok), 05-Сен-16, 10:37 
дык я не говорил, что оно всё плохо. я сказал, что оно скучное читерство. лично мне хватает zlib, который всё равно уже есть в любой системе, а нет — так разжиматель после deflate пишется в несколько килобайт. поэтому я интересуюсь остальным чисто с точки зрения: «а это интересно?» неа, неинтересно: и не ново, и не особо впечатляет, и к тому же для лучшего сжатия рекомендуют читерить. скука.

p.s. zlib, кстати, тоже умеет в `deflateSetDictionary()` и `inflateSetDictionary()`.

Ответить | Правка | ^ к родителю #62 | Наверх | Cообщить модератору

Архив | Удалить

Рекомендовать для помещения в FAQ | Индекс форумов | Темы | Пред. тема | След. тема




Спонсоры:
Слёрм
Inferno Solutions
Hosting by Ihor
Хостинг:

Закладки на сайте
Проследить за страницей
Created 1996-2019 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру