Inkrementalni komprese

[mhi]

Resim 2 problemy (na sobe nezavisle, ale svym zpusobem podobne):

- kazdy den stahuji z internetu nejaka data, jedna se o plaintext HTML stranku, kde je dlouhatanska tabulka, ktera se ale meni nejen na konci, ale vyjimecne i uprostred. Potreboval bych tyto z 90% shodne HTML soubory nejak "pribalit" postupne za sebe, takova idealni predstava je  dolepeni do .tar.gz, ktery by si umel vzit stav pred ukoncenim komprese (zapis tar traileru) a umel  tam dolepit ten novy soubor s tim, ze by se asi vyuzil stav kompresoru "z minula". Bylo by to vlastne ekvivalentni reseni vse prekomprimovat znovu, coz je taky asi pruchozi (treba po mesicich), ale nelibi se mi to, protoze dalsi bod

- podobne mam hromadu ruznych PDFek, ktera prichazi nova a nova, je v nich nekolik typu obsahu. Problem je, ze takove PDFko ma treba 300kB, je v nich nekolik typu textu/tabulek, ktere se porad dokola opakuji, obcas to prochazi "rucnim" zpracovanim (ruzne typy exportu/tisk do PDF, apod.). Text samotny nejde bohuzel rozumne vypreparovat, ne bez ztraty informace. V PDFku jsou casto zbytecne obrazky, jsou tam pribalene fonty, apod. No a tohle bych potreboval taky nejak inkrementalne stavet za sebe, aby se vyuzila informace z historickych souboru. Napadlo mne pouzit (udelat?) nastroj, ktery rozbali PDFkove objekty do plaintextu, aby to slo lip komprimovat externe, a hlavne treba ty opakujici se objekty by komprese  vzala z minula.

Prosim jen o hotova minimalisticka reseni (tzn. ne instalace nejakeho molochu), naprogramovat si to nejak asi umim, nebo si umim koupit velky disk a rychlejsi pocitac.

[Reklama]

[BoneFlute]

Pokud jsem to dobře pochopil...
Jeden zip/rar soubor, otevřít a přidat nové pdf? Jak se to bude chovat? Očekával bych, že se využije slovník toho zipu. Nebo ne?

Druhá možnost: vytvořit si virtuální komprimovaný FS?

[alex6bbc]

kdyz se v ruznych souborech objevuji stejne kusy textu/binarnich dat, tak bych pouzil huffmanovo kodovani.
velke bloky, ktere se casto opakuji se zakoduji pomoci mensiho poctu bajtu.

vzdy bych zpracoval nejake mnozstvi dat, vygeneroval mapovani pro huffmana a zakodoval podle toho data.
mapovani a zakodovane soubory bych ukladal postupne do jednoho souboru a la tar, a postupne bych si ukladal offsety a delky na mapovani, na data a na dalsi bloky, ktere se do souboru pridaji v budoucnu.

v budoucnu by bylo mozno znova vytvorit mapu pro huffmana a zase ji ulozit na aktualni konec souboru s novymi zakodovanymi daty a indexy/offsety by se updatovaly.

[alex6bbc]

kdybys to jednoduse ukladal do gitu, tak by to mohlo fungovat ne?
mam dojem, ze taky uklada jen diffy a i binarni data tam jde vlozit.

[vcunat]

git pokud vím ukládá soubory tak jak jsou (nejprve).  A jednou za čas udělá packy, tedy znovu kompresi, asi vždy všeho dohromady, když už se odhodlá.  Snad by to i mohlo amortizovaně fungovat slušně, jen s binárními soubory si jistý nejsem.

[Reklama]

[alex6bbc]

git pokud vím ukládá soubory tak jak jsou (nejprve).  A jednou za čas udělá packy, tedy znovu kompresi, asi vždy všeho dohromady, když už se odhodlá.  Snad by to i mohlo amortizovaně fungovat slušně, jen s binárními soubory si jistý nejsem.

kazdopadne by pak mohl autor porovnat svoje reseni s gitem co se tyka velikosti dat, rychlosti atd.

[RDa]

Koupil bych vetsi a pripadne rychlejsi disk.

Pokud chces vymyslet neco, tak z popisu problemu me prijde ze hodlas vyuzit korelaci mezi souborama, takze pak bych se zameril na tooly co umi udelat binarni diff. Ale delat to efektivne znamena (filesize^2) operaci, takze to bude trvat (nastesti mas male soubory). A muzes pak pouzit nejaky komprimovany FS, kde se ten bindiff ulozi a zkomprimuje jen sam o sobe.

Dalsi varianta je jet nejakou dobu uncompressed a az pak veci sbalit. Typicky to pouzivam na logy - jeden den = 24 logu = jeden gz na konci dne. Ty to muzes delat treba mesicne do archivu treba.

[mhi]

Mily alex6bbc, dekuji za odpoved, ale odpovidate skutecne to na co jsem se ptal? Jednak nechci nic programovat, a pak git (pominu-li ze neresi muj problem) bych za moloch uz povazoval. Myslel jsem nejakou utilitu typu tarxzappend file.tar.xz novysoubor.html

A pak huffmanovo kodovani obvykle neresi ty opakujici se bloky o delkach ktere se mi vyskytuji, to se dela trosku jinak, viz treba bzip2.

Jestli neco budu programovat, tak to bude tool, ktery bude hledat ty opakujici se bloky a v nejakem binarnim formatu si ulozi "knihovnu referenci" a pak data kombinovana s referencemi.

[alex6bbc]

Mily alex6bbc, dekuji za odpoved, ale odpovidate skutecne to na co jsem se ptal? Jednak nechci nic programovat, a pak git (pominu-li ze neresi muj problem) bych za moloch uz povazoval. Myslel jsem nejakou utilitu typu tarxzappend file.tar.xz novysoubor.html

A pak huffmanovo kodovani obvykle neresi ty opakujici se bloky o delkach ktere se mi vyskytuji, to se dela trosku jinak, viz treba bzip2.

Jestli neco budu programovat, tak to bude tool, ktery bude hledat ty opakujici se bloky a v nejakem binarnim formatu si ulozi "knihovnu referenci" a pak data kombinovana s referencemi.

aha ok.
ja to napsal, jak bych si to udelal, kdybych to potreboval.
opakujici se bloky muzou byt jakkoli velke a pokud se opakuji tak si to primo rika o to je mapovat na kratsi kod.
ale to by si clovek musel sam naprgat podle svych potreb.

[CPU]

Ohledně toho HTML: To je vzorová úloha pro DB ne?
Krajně, při záchvatu lenosti, tak zvolit šikovně velikost bloku a použít souborový systém s deduplikací.

Ad FS s deduplikací:
Mám velmi špatné zkušenosti, papírově to vypadá hezky, ale ve skutečnosti ....úspora několik % na běžných datech.
Ale právě ty textové soubory mohou být skvělý způsob, jak deduplikací ušetřit hrozně moc místa.

Deduplikace, při vhodně zvoleném bloku, by mohla uspořit hrozně moc místa a přitom by to zůstalo transparentní.
Nicméně se jí musí někdy trochu pomoct, třeba hlavičku obsahující datum dát do extra souboru.

[crown]

Jeste bych doplnil file system s deduplikaci + na nem zapnout on the fly kompresi. Pro textove/html soubory urcite.

Jinak ty PDF jsou imho uz komprimovane interne, takze dalsi komprese uz tolik neprinese.

[mhi]

Netusim jak na takovou ulohu vyuzit databazi.

Nevim jak by filesystem resil kdyz mi nekdo prida radek do tabulky nebo zmeni

<tr><td>aa<td>bb<td>cc

za

<tr><td>aa<td>qqq<td>cc

(dojde k posunu o byte a zmene uprostred, je to jen priklad- zde treba myslim zmenu cele vety v tabulce)

Jinak ty HTML maji treba 2MB.

****

Bindiff by sel pouzit jen kdyby umel srovnavat proti vice souborum. Napadlo mne, ze bych mohl vzit podle data treba poslednich 100 souboru a hledat proti nim + pokud uz jsou "komprimovane" s referencemi, tak i v tech referencovanych souborech. Ono by to pak samo naslo co je cemu podobne, mozna by podle toho slo ty soubory i typove roztridit . Vlastne by to asi statisticky mohlo poznat "tohle PDF delal stejny clovek jako techto 50 dalsich".

****

PDF je obvykle komprimovane uvnitr, pridani jednoho znaku do textu zmeni cely deflate bitstream, takze pro zpracovani je potreba je dekomprimovat.

[CPU]

Netusim jak na takovou ulohu vyuzit databazi.

Já ano, ale ty chceš něco fakt simpl, jednoduché.
Tedy - proto - použij FS s deduplikací, což je v podstatě taky jednoduchá databáze :-)
Jen se postarej, abys hlavičky (často se mění, protože tam je datum a pod), měl jinde.
Rozsekneš soubor na hlavičku a obsah. Navíc to celé můžeš krásně komprimovat na úrovni FS, jak tu zaznělo = bude to malinké, možná se to vejde na SSD.

Výhoda souborové deduplikace je i v tom, že když se ti změní formát souboru, výstupního souboru, tak v nejhorším zapíšeše znova celé 2MB a začínáš deduplikovat znovu. U DB by ses musel zajímat o změnu obsahu.

Jak zpracovat PDFka netuším, ale nejspíš extrahovat, jak jsi správně uvedl.

Velikost sektoru si asi budeš muset určit, zeřejmě to bude umět deduplikaci jen na úrovni sektoru, nikoliv na úrovni výřezu.  Tj bla123456789 a alb123456789 budou komplet jiná data a zůstanou, tak jak jsou. Očekávám, že ti sektorová deduplikace bude fungovat jen pokud budou oba sektory 123456789. Ale mohu se plést. Na Widlích mi to chodilo dobře jen při shodě sektorů. Jak se to posunulo (třeba se na začátek souboru umístila 1), už to mělo s deduplikací problémy. Kdo ví, jak chytrá je deduplikace na Linuxu. Ať poradí.

[Vít Šesták (v6ak)]

Samotný gzip to umí celkem triviálně, jen si nejsem jist s efektivitou při malém množství přidaných dat: https://unix.stackexchange.com/questions/264980/how-to-append-a-line-in-a-zipped-file-without-unzipping

Je otázka, jestli s tím bude umět pracovat i tar. Mohl by.

[CPU]

Netusim jak na takovou ulohu vyuzit databazi.

K čemu by ti byly HTML dekorace? Ty si můžeš uložit do nějaké XSLT šablony třebas.
Takže jedna z možností je přežvýkat soubor a jeho řádky regexem, protože ukládání formátování je nadbytečná informace. Jednotlivé věty pak ukládáš do DB, takže ti nevadí, že někdo věty zpřeházel, navíc máš kompletní historii.
Výhody:
Může to být bezkonkurečně nejmenší, máš k dispozici všechny verze, můžeš provádět data mining atd.
Nevýhody:
Musíš se zajímat o formát, jak ti přestane fungovat Regex, musíš upravit import.
S vysokou pravděpodobností může vzniknout situace, kdy bys musel strukturu tabulek upravit.

Tak je to o tom, jak důležitá data to jsou, jestli je můžeš zpracovat a kolik na to máš času.
Málo času / nechuť / nedůležitost / neexistující přidaná hodnota / ....nenene... = použij FS s deduplikací

Nicméně - odebrat HTML dekorace může být decela chytré tak jako tak - třeba i pro to FS s deduplikací.
Mnoho z nich můžeš beztrestně odebrat, aniž by to snížilo čitelnost textu = redukce dat.