Google zrychlí web. Vymyslel pro něj nový kompresní algoritmus Brotli

23. 9. 2015

Kompresní algoritmus Deflate kombinuje bezztrátové algoritmy využívající binární strom (Huffmanovo kódování) a slovníkové metody (LZ77). Využívá se u formátu ZIP, 7-zip nebo třeba PNG. Jeho implementace v knihovně zlib se používá i na webu – lze přes ně komprimovat stahované soubory PHP, CSS nebo JS. Deflate nicméně není ani příliš rychlý, ani efektivní.

Jak si vedou jednotlivé algoritmy v testu Canterbury

Google se jej už před dvěma lety snažil vylepšit, když vymyslel jeho kompatibilní alternativu Zopfli s účinnější kompresí. Včera však oznámil vytvoření úplně nového open source algoritmu Brotli. Opět využívá Huffmana a LZ77, k tomu pak ještě kontextové modelování druhého řádu.

Je prý efektivnější (tj. balí do menších souborů), přitom má rychlejší kompresi i dekompresi. To jsou vlastnosti klíčové pro web na horším připojení a se slabším hardwarem, typicky na mobilech. Google věří, že vývojáři zahrnou Brotli do svých prohlížečů co nejdříve. Sám ale o podpoře v Chromu nebo u svých webů zatím nemluví.

Vzor Canterbury | Vzorek 1285 HTML souborů v 93 jazycích

Firma ukázala výsledky prvních testů, kde se Brotli postavil proti algoritmům Deflate, Zopfli, LZMA, LZHAM a bzip2. Zkouška proběhla na šestijádrovým Xeonu E5-1650 (3,5 GHz s HT) u různých vzorků souborů: Canterbury corpus a 1285 HTML souborů v 93 jazycích.

V různých nastaveních u vzorku Canterbury dosáhl Brotli nejlepšího kompresního poměru (kolikrát se soubor zmenšil), nejrychlejší komprese i dekomprese. Brotli s kvalitou 9 dosáhl druhého nejlepšího poměru 3,965, účinnější byl jen LZMA v kvalitě 9 (4,24). Jenže oproti němu měl Brotli násobně rychlejší kompresi (17 oproti 3,9 MB/s) a především dekompresi (354,5 oproti 71,7 MB/s).

A při nastavení kvality 1 (nejméně úsporná) byl Brotli účinnější než Deflate s kvalitou 9 (poměr 3,381 oproti 3,371), přitom měl šestkrát rychlejší kompresi (98,3 oproti 15,5 MB/s) a jen nepatrně horší dekompresi (334 oproti 347,3 MB/s).