|
Един от специалистите на Google през свободното си време разработил нов алгоритъм за компресия на данни наречен Zopfli, който е с 3,7-8,3% по-ефикасен от стандартната библиотека zlib, включена на максимално ниво на компресиране. Първоначално алгоритъмът е бил замислен като метод за компресия без загуби на WebP, но разбира се, той може да бъде използван и за компресиране на всякакви цифрови данни.
Новият алгоритъм е вариация на стандартните Deflate алгоритми и поради тази причина е съвместим с Deflate и gzip, а разархивирането на неговите данни вече се поддържа от всички съвременни браузъри. Достатъчно е Zopfli да бъде включен на сървъра. Например, той може да бъде използван в уеб-сървъра Nginx, без да се налагат промени в модула gzip.
Характерна черта на този алгоритъм е, че изисква около 100 пъти по-голям ресурс при архивиране, а разархивирането става със същата скорост, както и при другите алгоритми.
В статията Data compression using Zopfli.pdf авторът обяснява, чрез какви оптимизации е успял да постигне по-добро компресиране. Известно е, че Deflate използва комбинация от алгоритъма на Хъфман и алгоритъма LZ77. Първият кодира входните символи чрез кодове с променлива дължина, в зависимост от честотата на поява за всеки символ. Вторият използва принципа на "пълзящия прозорец" и работи с редове и препратки към тях, а не само с отделни символи. Deflate използва различни евристики за търсене на подходящи редове от символи, специфична хеш-таблица, както и оптимизация на данните преди кодирането, за да се разбере, кой от методите е по-подходящ за всеки конкретен случай. От нивото на компресия (от 1 до 9) зависи колко време и какви ресурси ще са необходими, за да се избере големината на редовете от символи, търсени в хеш-таблицата.
В статията е разяснено още, че се използват нови техники на компресиране, базирани на моделиране на ентропията и търсене на най-кратък път. |
|
