funkcionálně.cz

Přední český blog o funkcionálním programování, kde se o funkcionálním programování nepíše
««« »»»

diff a komprese

18. 9. 2016 — k47

Někdy se zkrátka daří.

Celé dny se ne­stane nic a pak přijde den, kdy zjis­tím, jak fun­guje uni­xová uti­lita diff a po­u­žiji těchto zna­lostí, abych kom­pri­mo­val 3x rych­leji a 70x lépe než cti­hodný gzip.

Ale začnu po­po­řadě.

Mám da­ta­set, který je tvořen JSON sou­bory. Ne­zá­leží kolik přesně jich je, jde o něco jako O(hodně) a v ka­ta­logu Dellu jsem ne­na­šel stroj, který by měl RAM tak ve­li­kou, že by se do ní všechno vešlo. Nejde jen o ná­hodné JSON sou­bory, ale log JSONů (stylem jeden JSON na řádek), které jsou si velice po­dobné. Záznam může mít něco mezi jedním a sto ki­lo­bajty s tím, že se od toho před­cho­zího liší jen změ­nami na ně­ko­lika málo mís­tech: Nějaké vnitřní vlast­nosti mohou být ak­tu­a­li­zo­vané, do pole může být přidán jeden nebo dva dílčí ob­jekty a jiný může chybět. Po­dob­nost je veliká a vět­ši­nou přa­sa­huje 99%.

Když je en­t­ro­pie celého da­ta­setu takto malá, kom­presní al­go­ritmy by měly zářit.

Bo­hu­žel tomu tak není a Gzip v nej­lep­ším pří­padě kom­pri­mo­val na čtvr­tinu. To mi dlou­hou dobu přišlo jako ne­u­spo­ko­jivý vý­sle­dek s při­hléd­nu­tím k ob­rov­ské re­pe­tici v datech. Dlouho jsem to nijak ne­ře­šil, pro­tože disky jsou velké a ne­stojí skoro nic. Ale data na­růs­tala a na­růs­tala, až do té míry, že jsem o zase začal pře­mýš­let o lepší kom­presi.

Na­padlo mě, že když jde o stringy, mohl bych ucho­vá­vat jen diffy mezi řádky v logu. To na první pohled vypadá jako jed­no­du­chý pro­blém, který se dá sfouk­nout za půl hodiny. Když jsem o tom ale začal pře­mýš­let, došlo mi, že to není tak jed­no­du­ché. Naivní al­go­ritmy můžou fun­go­vat v mnoha pří­pa­dech, ale dají se velice snadno zmást a pak ne­na­jdou nejmenší možný diff, ale ně­ja­kou mon­stro­zitu, která nic moc ne­u­šetří.

Po­tře­bo­val jsem něco zá­sa­do­vého, po­tře­bo­val jsem al­go­rit­mus.

Na­pa­dala mě pa­rafráze na Ka­pi­tána Willarda z Apo­ka­ly­psy:

Eve­ry­one gets eve­ry­thing he wants.
I wanted an al­go­ri­thm.
And for my sins, Wi­ki­pe­dia gave me one.
Brou­ght it up to me like room ser­vice.

Jak jsem velice rychle zjis­til, zá­kla­dem uni­xové uti­lity diff je al­go­rit­mus pro na­le­zení nejdelší spo­lečné pod­sek­vence (lon­gest common sub­sequence/LCS).

Když mám na­pří­klad dvě sek­vence/stringy:

A B D E I J K L X
B C D I J L M N

a správně je za­rov­nám

A B   D E I J K L     X
  B C D   I J   L M N

je vidět, že jejich LCS je

B D I J L

Když mám tuhle sek­venci, můžu snadno spo­čí­tat diff. Z prv­ního ře­tězce byly od­stra­něny znaky A E K X a do dru­hého při­dány C M N. Hotovo.

Řešení LCS se dá najít re­kur­zivně v ne­po­u­ži­telně po­ma­lém čase nebo přes dy­na­mické pro­gra­mo­vání s pomocí O(n2) extra pro­storu. Pa­mě­ťové nároky si­tu­aci kom­pli­kují, pro­tože LCS na úrovni znaků dvou stringů, které mají 100kB, by po­tře­bo­valo 40GB po­moc­nou matici. Z toho důvodu uti­lita diff nebere v potaz jed­not­livé znaky, ale celé řádky, kte­rých je mnohem méně. To dělá pro­blém lépe zvlád­nu­telný.

Já však neměl text, ale jed­no­řád­kové JSONy.

Chvíli jsem začal uva­žo­vat, že bych JSONy na­par­so­val a po­čí­tal jejich diffy na úrovni da­to­vých struk­tur. Ale pak jsem, nej­spíš pod vlivem ducha Ed­warda Kmetta, dostal nápad. Co kdy­bych string JSONu roz­dě­lil podle čárek a po­čí­tal diff na úrovni těchto seg­mentů. Velice snadno bych tak dostal bloky textu, které mají v JSONu struk­tu­rální význam bez toho, aniž bych ho musel par­so­vat.

Diff mezi těmito dvěma JSONy

{"a":1,"b":2,"c":3}
{"a":1,"b":47,"c":3}

by vy­pa­dal

- 7 6       // odstraní 6 znaků počínaje pozicí 7
+ 7 "b":47, // na pozici 7 vloží nový řetězec

To fun­guje, ale proto, že JSON ob­sa­huje hodně věcí od­dě­le­ných čárkou a al­go­rit­mus běží v pod­statě v kva­d­ra­tic­kém čase, není to tak rychlé, jak by to jen mohlo být. Pokud JSON ob­sa­huje vno­řené ob­jekty, můžu ho na­se­kat podle uza­ví­rací slo­žené zá­vorky }1 . Těch bývá méně a hle­dání LCS je pak rych­lejší.

Ok, teď tedy vím, jak udělat diff JSONů. Ale je to k něčemu dobré?

Místo vy­svět­lo­vání ukážu malou ta­bulku:

jsonlog            2926466947 B   originální soubor
jsonlog.gz          772794031 B   komprimováno gzipem
jsonlog.diffs        80895070 B   komprimováno jako série diffů
jsonlog.diffs.gz     12725864 B   diff + gzip

Jak je vidět, tak v tomto pří­padě je sa­motné pře­ve­dení na sérii diffů skoro 10x efek­tiv­nější než gzip a kom­bi­nace s gzipem vede ke 230x kom­presi, velice blízko ke sku­tečné in­for­mační hod­notě da­ta­setu.

Kdyby se někdo za­jí­mal, proč si gzip vede tak zle, tak se musím při­znat, že nevím. Moje teorie je, že nevidí, a tedy ani ne­do­káže využít, po­dob­nosti ve velkém mě­řítku a kom­pri­muje v malém pra­cov­ním okně. Moje do­mé­nové zna­losti v tomto pří­padě fun­gují lépe než obecný gzip2 . Uva­žo­val jsem také o xz. Ten kom­pri­muje o něco lépe, ale je straš­livě pomalý.

Sa­motné di­f­fo­vání je 3x rych­lejší než gzip a diffy se na mém stroji (v jednom vlákně) de­kom­pri­mují rych­lostí 336 MB/s, což je víc než rych­lost čtení/zápisu ro­tu­jí­cího disku. Vy­platí se tedy online de­kom­pri­mo­vat data než je číst z disku.

A to podle mě, stojí za tu námahu.


Zdro­jový kód je v tomto gistutomto re­po­zi­táři


Do­da­tek #1: Uka­zuje se, že zstd s ma­xi­mální úrovní kom­prese kom­pri­muje stejně dobře jako můj diff+gzip hack a de­kom­prese je velice rychlá.

Do­da­tek #2: Po chvíli tes­to­vání zstd vypadá jako ide­ální pro­gram na obec­nou kom­pri­maci. Úrovní kom­prese je velice blízko xz/lzma, ale pra­cuje mnohem rych­leji a dokáže data de­kom­pri­mo­vat rych­lostí přes 1GB za sekundu.


Po­známky:

  1. Pokud na to chcete jít o něco chytřeji a vy­hnout se slo­že­ným zá­vor­kám v ře­těz­cích, stačí udělat dvou­sta­vové par­so­vání: mimo string a ve stringu. Když jsem mimo string, zá­vorky beru v potaz, když jsem ve stringu, pře­ska­kuji je.
  2. Fun­guje to takhle dobře jen pokud je po­dob­nost mezi sou­se­dí­cími zá­znamy veliká. Když by můj da­ta­set byl tvořen zcela ná­hod­nými JSONy, di­f­fová kom­prese by ne­u­šet­řila skoro žádné místo, na­roz­díl do gzipua, který by stále do­ká­zal srazit ve­lo­kost na něco kolem jedné čtvr­tiny.
@kaja47, kaja47@k47.cz, deadbeef.k47.cz, starší články