Új tömörítési algoritmust fejlesztett ki a Google

Google

A Zopfli után (amely egy deflate-kompatibilis tömörítő, a HUP-on is volt róla szó itt) a Google új tömörítési formátumot fejlesztett ki.

A formátum a mérések szerint 26%-kal hatékonyabb, mint a Zopfli, mégis körülbelül a deflate sebességével tömörít, és tömörítésben jobb, mint az LZMA vagy a bzip2. Részletek a Google Opensoure blogján. A Google nyílt forráskódú implementációt is közzétett, Apache 2.0 licenc alatt. Elérhető a GitHubon.

( trey | 2015. 09. 24., cs – 15:05 )

Akartam írni róla.

By Zoltan Szabadka, Software Engineer, Compression Team

--
trey @ gépház

( Breaknet | 2015. 09. 24., cs – 15:57 )

Vajon meddig lehet fokozni a tömörítési hatékonyságot? Mindig jönnek újabb és újabb algoritmusok, amelyek X százalékkal hatékonyabb tömörítést ígérnek, a WinRar is minden verziójánál leírja, hogy hány százalékkal lett hatékonyabb a tömörítés, ha összeszámolnánk, akkor már biztos vagy 1000%-nál tartanánk.

Jaja entropia, csak hanyad rendu? :)

Illetve gyakorlatban hogyan hatarozod meg.. mi egy adatstruktura entropiaja (pl. routing tabla), de akar azt is kerdezhetnem mi az entropiaja egy szovegfajlnak, ami az elso 1 millio primet tartalmazza. Mely algoritmus/szoftver tudja ezt meghatarozni?

Kb annyira hasznos az entropia a gyakorlatban, mint a Kolmogorov bonyolultsag.

Becsulni sem tudod :) Altalaban ezt ugy szoktak csinalni, hogy valasztanak egyet a szamos entropia meghatarozas kozul (pl legegyszerubb szovegnel a nulladrendu entropia) es az alapjan adnak neked egy 0-1 kozotti normalizalt erteket. Azonban azt tudni kell, hogy ez esetben peldaul a tomorithetoseg boven meghaladhatja a kapott entropiat (pl. blokk tomorites eseten). Ez pedig nem azert van, mert hu de kiraly tomoritot irtal, hanem mert mas a valos entropia, mint amit szamoltal.

Ezert irtam az elso 1 millio primes peldat. Nem talalsz olyan programot, ami minden bemenetre kepes akar csak nagysagrendileg helyes eredmenyt adni. Ugyanis a rendezettseg felismerese nem trivialis. Ha az lenne, akkor kepesek lennenk olyan optimalis tomoritot irni, amely elo tudna allitani azt a legrovidebb kitomorito kod+adat parost, ami vissza tudja allitani az adott bemenetet (es a kitomorito gyakorlatilag csak egy VM lenne). Ez a problema viszont baratok kozott is NP teljes (sot megkockaztatom hogy visszavezetheto a megallasi problemara es akkor algoritmikusan eldonthetetlen).

... így elsőre hirtelenjében pöpec :D ( pontosabban másodjára, miután a πfs.c -t át kellett nevezni pifs.c -re, meg átirkálni az autoconf-ot )

make all-recursive
make[1]: Entering directory `/tmp/pifs-master/pifs-master'
Making all in src
make[2]: Entering directory `/tmp/pifs-master/pifs-master/src'
gcc -std=gnu99 -DHAVE_CONFIG_H -I. -I.. -D_FILE_OFFSET_BITS=64 -I/usr/include/fuse -Wall -Werror -Wextra -Wno-unused-parameter -g -O2 -MT pifs.o -MD -MP -MF .deps/pifs.Tpo -c -o pifs.o pifs.c
cc1: warnings being treated as errors
pifs.c: In function ‘pifs_opendir’:
pifs.c:258: error: cast from pointer to integer of different size
pifs.c: In function ‘pifs_readdir’:
pifs.c:265: error: cast to pointer from integer of different size
pifs.c: In function ‘pifs_releasedir’:
pifs.c:290: error: cast to pointer from integer of different size
pifs.c: In function ‘pifs_fsyncdir’:
pifs.c:297: error: cast to pointer from integer of different size
make[2]: *** [pifs.o] Error 1
make[2]: Leaving directory `/tmp/pifs-master/pifs-master/src'
make[1]: *** [all-recursive] Error 1
make[1]: Leaving directory `/tmp/pifs-master/pifs-master'
make: *** [all] Error 2

-fs-
Az olyan tárgyakat, amik képesek az mc futtatására, munkaeszköznek nevezzük.
/usr/lib/libasound.so --gágágágá --lilaliba

( toMpEr | 2015. 09. 24., cs – 16:46 )

Saját mérés: 


Eredeti json:   1874.51KB
Zlib    0.074s  558.68KB
Gzip    0.130s  547.09KB
Deflate 0.125s  547.04KB
Bz2     0.291s  482.88KB
Brotli  7.856s  438.01KB
Decompress
Zlib    0.010s
Gzip    0.011s
Deflate 0.009s
Bz2     0.089s
Brotli  0.012s

--------
Vultr VPS: SSD + 768MB RAM, 5USD/hó (benchmark), 20USD kupon: SSDVPS

Lefordítottam a Brotli-t és összevetettem xz-vel.
Lerántottam a 4.2.1 kernel forrását. https://www.kernel.org/pub/linux/kernel/v4.x/linux-4.2.1.tar.xz
Kicsomagoltam (unxz) 602 MB lett a linux-4.2.1.tar. Majd becsomagoltam külön-külön mindkettővel:

Brotli - 87 MB 36 perc
xz - 82 MB 6 perc 23 másodperc

Szóval nálam nem fogja ez leváltani az xz-t.

Küldenél angol szövegmintát nekem? Szívesen összehasonlítom.

Addig is egy angol szöveg: https://tools.ietf.org/html/draft-alakuijala-brotli-01

html: 398926 byte
Brotli: 86088 byte és 1,39 másodperc alatt tömörítette
xz: 85524 byte és 0,24 másodperc alatt tömörítette

Ám legyen. Én eddig nem tudtam igazolni hogy jobb lenne, addig viszont fenntartással kezelem.
Sajnos marketing duma napjainkban olyan, aminek úgy be lehet dőlni, mint a Volkswagen-féle környezetbarát dízel autóknak. A hírt rögtön mindenki átveszi és adja átgondolás nélkül tovább.
Aztán valaki valós körülmények között is elkezdett mérni ...
http://24.hu/fn/gazdasag/2015/09/22/volkswagen-botrany-ezek-utan-mit-le…

Ha tömörítve utazik az adat, akkor még a tömörítési idővel együtt is gyorsulhat az átvitel. Tehát összességében kevesebb időt tökölhet a szerver a küldéssel.
(Jó példa ilyenre a BTRFS, ahol lzo tömörítéssel általában sokkal gyorsabb az írás és olvasás, mint tömörítés nélkül)

Frissítve Lzma-val (xz): 


Original        1874.51KB
Zlib    0.073s  558.68KB
Gzip    0.137s  547.09KB
Deflate 0.140s  547.04KB
Bz2     0.305s  482.88KB
Lzma    1.254s  455.77KB
Brotli  8.080s  438.01KB
Decompress
Zlib    0.010s
Gzip    0.011s
Deflate 0.009s
Bz2     0.095s
Lzma    0.057s
Brotli  0.012s

Ez alapján, a deflate-nél kb 20%-al kevesebb helyfoglalás és a gyors kitömörítési sebesség miatt hasznos ritkán frissülő anyagok kiszolgálásánál (pl archívumok).

--------
Vultr VPS: SSD + 768MB RAM, 5USD/hó (benchmark), 20USD kupon: SSDVPS

( krychek | 2015. 09. 24., cs – 19:03 )

Lemaradt a cikkből, hogy Brotlinak hívják ezt az algoritmust.

Rákerestem az imént erre a szóra. A képtalálatok között a Google 20 darab zsömlét meg a saját logójából egy példányt köpött ki.
Szóval Zsömi... Cool.

Szerk.:

Közben az angol kommentek olvasgatása közben felfedeztem, hogy valójában "Brötli" a helyes írásmód. Erre már csak zsömlék jöttek, semmi Google logó.

Szerk 2.:

Aztán meg azon kezdtem gondolkodni, hogy mi köze lehet a zsömlének a tömörítéshez, de asszem rájöttem. Az imént találtam egy antik darabot a konyhában. Tényleg baromi tömör.
---
Science for fun...

Müüsli - egérke
Hüüsli - házacska, kunyhó
Gipfeli - kifli (khm)
Sächli (krákogj a céhánál) - zacskó
Stempli - pecsét

És így tovább. Nem egyértelműen mindig kicsinyít, de legtöbbször igen. Gyerekbeszédben nagyon gyakori. Természetesen használják a -chen-t is. A vicces, amikor a kvízműsorban ki van írva a kérdésben, hogy Mäuschen, és felolvassa a műsorvezető műzliként.

( BandiG v | 2015. 09. 24., cs – 19:29 )

Valahol azt olvastam, hogy nem altalanos celu tomorito rendszer ez, hanem weboldalak kiszolgalasara optimalizalt. Espedig oly modon, hogy egy nagy, elore meghatarozott szotarat cipel magaval a tomorito es a kitomorito resz, a szotarban a weben leggyakoribb karaktersorok (gondolom HTML tagek, CSS, javasript kod-toredekek) es 5 nagy nyelv (angol, arab, ...) gyakori szavai-kifejezesei vannak.

( toMpEr | 2015. 09. 27., v – 19:25 )

Extra infó:
A jelenleg is eléggé támogatott Woff2 webfont formátum már ezt használja: "The compression algorithm used for both the compressed font data stream and extended metadata block is Brotli " - http://www.w3.org/TR/WOFF2/

+ Érkezik Firefox 44-be via

Edit: Ennek fenyeben kiprobaltam a tomoritesi szinteket es elegge meglepo eredmeny jott ki: 


Original Compress 1874.51KB Decompress
Zlib     0.069s   558.68KB 	0.011s
Gzip     0.132s   547.09KB 	0.011s
Deflate  0.131s   547.04KB 	0.009s
Bz2      0.299s   482.88KB 	0.098s
Lzma     1.372s   455.77KB 	0.057s
Bro/1    0.035s   506.78KB 	0.011s
Bro/2    0.046s   504.26KB 	0.010s
Bro/3    0.052s   502.25KB 	0.011s
Bro/4    0.059s   507.89KB 	0.010s
Bro/5    0.160s   527.18KB 	0.012s
Bro/6    0.221s   527.73KB 	0.012s
Bro/7    0.269s   527.06KB 	0.012s
Bro/8    0.305s   526.27KB 	0.012s
Bro/9    0.373s   525.81KB 	0.012s
Bro/10   8.111s   438.01KB 	0.012s
Bro/11   8.075s   438.01KB 	0.012s

Ez alapjan az 1-es szinten jelentosen gyorsabb es jobb tomoritest ad, mint a gzip. (ugyancsak erdekes, hogy valamiert a 4-9 szinting nem ad jobb tomoritest, mint az 1-es)

(az tesztadat 11ezer fajl sha256 hexdigestjet tartamlazo json file volt)

--------
Vultr VPS: SSD + 768MB RAM, 5USD/hó (benchmark), 20USD kupon: SSDVPS