Komprese Base64 a komprese textu?

15.2.2020 13:37 | Přečteno: 2762× | Softwarové inženýrství | poslední úprava: 16.2.2020 12:55

Některé formáty chceme mít textové, protože obsahují převážně textová data, ale občas do nich potřebujeme vložit třeba obrázek nebo jinou binární přílohu, což se typicky řeší pomocí Base64 (případně hexadecimálního řetězce).¹ Tento textový formát pak chceme někdy zase komprimovat… Textové části se komprimují obvykle dobře, ale na částech s Base64 daty si většina kompresních algoritmů si na nich vyláme zuby a uloží data velmi neefektivně (výrazně hůře, než by mohly při zachování bezztrátovosti).

Existuje nějaký algoritmus, který by v textu dokázal detekovat Base64 nebo hex části a u nich efektivně komprimovat původní binární data a jen si poznamenat, že se výsledek při dekompresi má převést zase zpět na Base64 či hex? Ano, můžou tam být nějaké mezery či zalomení řádků, což přináší nejednoznačnost, ale jinak je to bezztrátový převod, který lze provádět neomezeně sem a tam. Stačilo by podporovat jen jednu nebo několik málo variant (např. Base64 bez zalomení a mezer nebo Base64 se zalomením na x. sloupci) a ke komprimovaným datům si ji poznamenat.

Někdy by se taky hodila polo-ruční komprese pomocí předem definovaného slovníku – když se nám v textu často opakují určité řetězce, mohli bychom si je na začátku nebo v průběhu textu pomocí nějakých příkazů (uvozených např. zpětným lomítkem) přidat do slovníku a pak je opakovaně používat (zase nějakým příkazem se zpětným lomítkem). V podstatě by šlo o velmi jednoduchý jazyk, který umožňuje pouze definovat proměnné a pak na ně odkazovat. Vše, co není \příkazem, se bere jako doslovná hodnota a při dekompresi/dekódování se posílá rovnou na výstup. Při kompresi bychom museli algoritmu sami poskytnout slovník často používaných řetězců (případně by se je algoritmus mohl pokusit najít sám, ale to znamená více-průchodové zpracování). Výhoda by byla v tom, že by to byl pořád lidsky čitelný text a i tu dekompresi by mohl snadno provést ručně člověk v průběhu čtení. Taky by to mohlo sloužit jako předzpracování pro nějaký obecný kompresní algoritmus a ve výsledku by to přineslo lepší kompresní poměr.

Existuje něco takového? Moc se mi nechce věřit, že bych byl první, kdo na tuhle úlohu narazil. (vím, že např. zstd umožňuje natrénovat si vlastní slovník a uložit si ho do souboru, ale to není úplně to, co hledám)

_{[1] ano, svým způsobem je to prasárna a binární formáty tímto problémem netrpí, do nich se prostě vloží atribut/uzel binárního typu a máme hotovo; nicméně realita je taková, že textové formáty s vloženým Base64 se používají a těžko s tím něco naděláme – je potřeba se s tím naučit žít a efektivně pracovat}

       

Komentáře

[Bedňa]

Otestoval som to a nejak čierne to s tou kompresiou nevidím.

curl -sb -H https://investorplace.com/wp-content/uploads/2014/05/DuckDuckGo-Logo.jpg | wc -c 116027

curl -sb -H https://investorplace.com/wp-content/uploads/2014/05/DuckDuckGo-Logo.jpg | base64 | wc -c 156740

curl -sb -H https://investorplace.com/wp-content/uploads/2014/05/DuckDuckGo-Logo.jpg | base64 | gzip -f | wc -c 100488

[DaBler]

Asi máte problém s pochopením psaného textu. Zkuste: curl -sb -H https://investorplace.com/wp-content/uploads/2014/05/DuckDuckGo-Logo.jpg | gzip -f | wc -c 97931

[Bedňa]

Toto chápem, je tam problém do 5% nárastu objemu "base64" dát. Otázka ale je, "stojí to za komplikácie s vývojom nejakého nového komprimovacieho jazyka?"

[Matlák]

Řekl bych že nestojí.Daň v podobě 5% nárůstu dat je IMHO daní za to že to právě není komplikované. U nekompresovaných PCM dat je to například 10%, ale u JPEG,MP3 a MP4 souborů je to zpravidla pod 3%. Kdybych dostal takový soubor (typicky by nejspíš vypadl z nějaké aplikace která to mimochodem používá a neočekává že to někdo bude muset analyzovat), zjistil že na to potřebuju kdovíjaký nástroj který nemám nainstalovaný a po rozbalení zjistil že je to jenom o 5% menší s tím že jsem si nainstaloval další balík jenom kvůli tomu, tak bych nad tím celkem kroutil hlavou. A kdybych ten balík neměl (a případně to musel zreverzovat) tak bych už nejspíš zuřil. Ale možná nám Franta předvede nějaký případ kdy je to mnohem horší..?

[xkucf03]

Ale možná nám Franta předvede nějaký případ kdy je to mnohem horší..?

Viz níže, může to být třetina, což už docela rozdíl je.

Co se týče těch opakujících řetězců, přemýšlím např. nad logy nebo nad nějakými výpisy, do kterých jsou vložená na každém řádku (nebo často) nějaká data, která mají svoji hlavičku nebo jinou opakující se část.

Já právě nevím, jestli se to vyplatí – proto tahle diskuse. Nejradši bych, kdyby se ukázalo, že tohle už někdo vyřešil a algoritmus a nástroj pro efektivní kompresi opakujících se textů a Base64 už existuje :-)

[Matlák]

Já bych spíš udělal, když už bych teda měl u velkých objemů dat které chodí zvenku takový problém, nástroj který projde takový mix a prostě rozbalí ta data, aplikuje na ně kompresi a změní hlavičky tak aby čtenář věděl že je to kompresované - a pak to zas zabalí zpět do base64. Pak by to bylo zpětně kompatibilní s nástroji co jsou na tohle zvyklé - prostě by místo log četly log.gz (pokud vím tak většina nástrojů co mám to automaticky dekompresuje při otvírání).

[xkucf03]

V případě dat, která už nejdou víc zkomprimovat (např. ten JPEG), je ten rozdíl minimální. Ale u dat, která by komprimovat šlo, se to zabalení do Base64 ukazuje jako dost velká překážka – algoritmus se přes něj nedostane k surovým datům a pracuje výrazně méně efektivně. Příklad:

 ╭──────────────────────────────┬─────────────────┬─────────────────────────────────────╮
 │ soubor              (string) │ bajtů (integer) │ % oproti nekomprimovanému (integer) │
 ├──────────────────────────────┼─────────────────┼─────────────────────────────────────┤
 │ ./DuckDuckGo-Logo.jpg        │          116027 │                                 100 │
 │ ./DuckDuckGo-Logo.jpg.b64    │          156740 │                                 135 │
 │ ./DuckDuckGo-Logo.jpg.b64.gz │          100488 │                                  87 │
 │ ./DuckDuckGo-Logo.jpg.gz     │           97931 │                                  84 │
 │ ./etc.xml                    │           48425 │                                 100 │
 │ ./etc.xml.b64                │           65418 │                                 135 │
 │ ./etc.xml.b64.gz             │            5735 │                                  12 │
 │ ./etc.xml.gz                 │            1955 │                                   4 │
 ╰──────────────────────────────┴─────────────────┴─────────────────────────────────────╯

A rozdíl 5 735 vs. 1 955 mi přijde už docela výrazný – komprimovaná data by mohla zabírat třetinu místa.

nového komprimovacieho jazyka?

Ten „jazyk“ se týká té druhé části, kde by šlo ručně definovat slovník (opakující se řetězce). Ten problém Base64 (či hex) je na tom nezávislý.

I když to by vlastně taky šlo řešit nějakým preprocesorem a postprocesorem – před kompresí by se mohla rozpoznaná Base64 data dekódovat a vložit v surové podobě a jen nějak označit, kde mají začátek a konec – pak by se to prohnalo libovolným generickým kompresním algoritmem, který by mohl pracovat efektivněji, díky tomu, že by měl přístup k těm surovým datům. A při dekompresi by se to nejdřív dekomprimovalo třeba gzipem nebo xz a pak prohnalo postprocesorem, který by na základě těch značek (začátků a konců) zase vyrobil Base64 text.

[Matlák]

já ti nevím, já bych prostě XML do textu zakódované v base64 nedával. Však XML je samo o sobě lidsky čitelný formát. U toho PCM (zvuku) je to 10% ale nenapadá mě prostě situace kdy bych někam ukládal nekompresovaná data typu pixmap nebo PCM nebo dokonce čitelná data (jako je XML) převedená do base64. I mailový klient to pozná a nechá to tak jak je, líp se to čte a problém s kompresí je vyřešen.

[Bedňa]

preprocesorem a postprocesorem

Jasne treba to riešiť klasickou unixovou fylozofiou. Rovnako ako Tar nevie komprimovať, ale používa sa na komprimovanie, pritom dáta len pripraví na komprimovanie.

Takéto riešenie mi príde až triviálne jednoduché. Identifikácia base64 nie je nijak zložitá. Samozrejme sa tam dajú riešiť aj nejaké iné botičky.

[Heron]

Jinak mě teda fascinuje, že jinde mluvíš o komplexitě jako o svatém grálu a tady navrhuješ extra speciální jazyk na řešení problému, který reálně asi nikoho netankuje. Tam, kde je potřeba ukládat velké množství dat už si to nějak vyřešili a tam, kde je potřeba jen přilepit přílohu, to zase tak moc nevadí. A jak píše Matlák, kdybych někde narazil na způsob ukládání dat, který s daty dělá kdo ví co jen pro ušetření pár % (počítáno od velikosti originálu), tak bych se velmi divil.

Mimochodem, volbou kompresního alg lze získat mnohem víc. Když jsem teď zkusil ten zkušební soubor (487MB base64) v gzipu, tak to má 67MB. Jen změnou na xz(27MB) jsem získal bez práce zmenšení na 39% velikosti gzipu. Ano, stále to nevysvětluje rozdíl proti komprimaci původního binárního souboru, ale v praxi by mi to stačilo. (Změna v konfigu z gz na xz.)

[xkucf03]

Jinak mě teda fascinuje, že jinde mluvíš o komplexitě jako o svatém grálu a tady navrhuješ extra speciální jazyk na řešení problému, který reálně asi nikoho netankuje.

Když se podíváš např. na HTML nebo e-mail (MIME), viz třeba komentář Dodatek III: Kódování, tak tam existuje řada různých kódování dat a několikanásobné obalování… historicky se na to nabalila spousta standardů – a to jde přitom jen o pouhé posílání e-mailů. Oproti tomu mi přijde jako dost malé zlo a naopak zjednodušení mít jeden univerzální standard třeba pro tu ruční slovníkovou kompresi textů. Implementace by byla celkem triviální a vzhledem k tomu, že by to bylo univerzální (šlo by to použít na logy, na XML, na e-maily atd.), tak by se ty náklady (komplexita) rozložily.

Jak jsem psal, nevím, jestli to za to stojí, ale přeci jen mít mít třeba dvě třetiny méně dat není úplně malý rozdíl.

Mimochodem, volbou kompresního alg lze získat mnohem víc. Když jsem teď zkusil ten zkušební soubor (487MB base64) v gzipu, tak to má 67MB. Jen změnou na xz(27MB) jsem získal bez práce zmenšení na 39% velikosti gzipu.

To je irelevantní – pokud by se nějaký ten preprocesor používal, tak po něm může následovat libovolný kompresní algoritmus – tzn. klidně ten xz nebo zstd. Např. ten soubor etc.xml.b64.xz by stále měl 2,35× víc než etc.xml.xz, takže i v případě lepšího algoritmu by ten preprocesor docela dost místa ušetřil.

[Heron]

Když se podíváš např. na HTML nebo e-mail (MIME)

Nic z toho nepovažuji za hodné následování. To, že ani v roce 2020 nemáme jednoduchý standard na posílání krátkých a převážně textových zpráv s omezenou velikostí a možností k tomu snadno připojit binární data (opět do velikostí malých MB), nepovažuji za něco, čím bychom se měli chlubit. Email je jedna z nejhorších služeb, kterou může admin spravovat (a těch vzájemných rozporů a nekompatibilit) je tam víc.

Oproti tomu mi přijde jako dost malé zlo a naopak zjednodušení mít jeden univerzální standard třeba pro tu ruční slovníkovou kompresi textů. Implementace by byla celkem triviální a vzhledem k tomu, že by to bylo univerzální (šlo by to použít na logy, na XML, na e-maily atd.), tak by se ty náklady (komplexita) rozložily.

Ale my máme alg., které skvěle komprimují text i binární data. Problém je právě v tom base64. Tady je to docela hezky vysvětleno. Base64 je obfuskace původních bitů, ztrácí se původní vzory. (Samotného mě překvapilo, že to fakt není výřez z ascii, ale kompletně jiná abeceda. Ale já s base64 nepracuju vlastně nikde, tak jsem nad tím nikdy nepřemýšlel.) Takže by se mohla použít compression friendly transformace, pokud by byla vůbec potřeba.

Mimochodem, právě jsem to zkusil na hexdumpu. Původní binární soubor těch 361MB, hex 722MB, xz toho hexu má 18MB. Ten alg poznal, že má polovinu bitů nulovou a tu větší velikost proti původním 14MB přičítám tomu, že xz tam vkládá hlavičky a padding (někde tady byla zprávička o novém archívním formátu, kde to borec rozebíral). To mi nepřijde vůbec špatné. Takže výběrem vhodné transformace se dá získat mnohem víc.

Jak jsem psal, nevím, jestli to za to stojí, ale přeci jen mít mít třeba dvě třetiny méně dat není úplně malý rozdíl.

Tak pokud to bude v řádu kB, tak to asi význam nemá. Nepředpokládám, že bys tím prohánět TB dat.

[xkucf03]

Nic z toho nepovažuji za hodné následování.

Však jsem to taky uváděl jako odstrašující příklad.

To, že ani v roce 2020 nemáme jednoduchý standard na posílání krátkých a převážně textových zpráv s omezenou velikostí a možností k tomu snadno připojit binární data (opět do velikostí malých MB), nepovažuji za něco, čím bychom se měli chlubit.

Souhlas.

Ale my máme alg., které skvěle komprimují text i binární data. Problém je právě v tom base64.

Jenže v reálném světě se Base64 vyskytuje bohužel dost často. Já z toho taky nejsem nadšený. A ano, asi by bylo lepší ta binární data zapisovat hexadeximálně, což je výrazně jednodušší na implementaci (čtení i zápis), dalo by se to líp komprimovat a ještě je to „lidsky čitelné“ (máš šanci z toho vykoukat určité známé sekvence, zatímco Base64 asi ručně nelouská nikdo)… i za cenu toho, že ta data budou v nekomprimované podobě delší. Nicméně dobrý kompresní algoritmus by si měl efektivně poradit s daty, která se běžně v realitě vyskytují, a ne jen s nějakými ideálními daty (hypotetický dokonalý formát ve vakuu).

To Base64 je dobré asi fakt jen v případě, kdy ta binární data chceš vytisknout na papír a chceš ho oproti hexadecimálnímu zápisu spotřebovat méně. I když k tomuto účelu se hodí spíš nějaký formát, který má zabudované kontrolní součty a samoopravné mechanismy.

Bohužel spousta lidí má panickou hrůzu z binárních formátů, až nábožensky uctívají formáty textové, a když do nich potřebují vložit binární data (jako že dříve či později potřebují), tak je tam narvou v Base64 a jakékoli úvahy nad efektivitou a úsporností odbudou tím, že data se dají dodatečně zkomprimovat obecným algoritmem a řešit nějak úspornost by byla předčasná optimalizace. (někdy ano, ale přijde mi chybné apriori tvrdit, že to můžu jakkoli zprasit a ono se to pak nějak samo zkomprimuje – nejlepší kompresní poměr mají podle mého data, která se vůbec nemusela zapsat)

[Heron]

Nicméně dobrý kompresní algoritmus by si měl efektivně poradit s daty, která se běžně v realitě vyskytují, a ne jen s nějakými ideálními daty

A on si neporadí? Podle mě si poradí velmi dobře. Pořád to dokáže zmenšit na 5% původní velikosti. A jen změna z gzipu na xz je pořádné zlepšení. (Tato změna přinese víc, než změna z base64 na base16.)

Já se ve své praxi mnohem častěji setkávám s tím, že komprimační alg si nelze vybrat buď vůbec, nebo jen z omezeného výběru. Konkrétně ten gzip se používá (asi z historických důvodů) velmi často a je to více méně default. Někde to změnit jde (napadá mě třeba pgBarman) někde ne (bacula - s velkou slávou tam přidali lzo, což je rychlejší, ale s horším poměrem). ZFS má "jen" gzip (gzip-9 používám pro jail s archivem emailů v mdboxu a je to skvělé), btrfs už má i zstd. Tj. by bylo velké zlepšení, kdyby se dalo na více místech nasadit stávající lepší komprimační alg, než se pokoušet cokoliv udělat s base64.

Bohužel spousta lidí má panickou hrůzu z binárních formátů

Ano, k jejich škodě.

nejlepší kompresní poměr mají podle mého data, která se vůbec nemusela zapsat

To každopádně

tak je tam narvou v Base64 a jakékoli úvahy nad efektivitou a úsporností odbudou tím, že data se dají dodatečně zkomprimovat obecným algoritmem a řešit nějak úspornost by byla předčasná optimalizace

Otázkou je, o jakou optimalizaci by se mělo jednat a proč ti jde zrovna o velikost. Proč zrovna tato metrika? Existují i jiná kritéria, než je velikost souboru. (Vzpomněl jsem si na přednášku od autora XFS z roku 2012, kde na každou druhou otázku reagoval stylem: storage is cheap.) V některých případech je přístup k datům mnohem podstatnější, než velikost souboru. Mimochodem, ten příklad, co zde uvádím je SQLite DB soubor s katalogem z LightRoomu. Ano, poprvé mě překvapilo, jak moc to jde zkomprimovat, ale vzhledem k tomu, že mám několik set GB rawů, tak mě ta velikost zase tak moc nezajímá. A nějak mě nenapadá příklad, kdy by i rozdíl 30% ve velikosti komprimovaného souboru, ovšem na malých datech (textový formát asi nebude mít desítky GB) byl nějak kritický.

[Bedňa]

Bohužel spousta lidí má panickou hrůzu z binárních formátů

Ano, k jejich škodě.

V oblasti komunikácie sa používa base64 ako WEB SAFE, aby sa do komunikácie nedostali riadiace znaky a podnes keď niekde použiješ NEbase64 dáta, tak pindajú minimálne do konzoly. Vždy sa to obhajovalo tým, že aby to nejak nezhadzovalo staré softvéry.

[Heron]

Tak to je velmi zajímavé, transformací by se s těmi daty (entropií) nemělo nic stát, prostě se jen nahradí symboly za jiné.

Zkoušel jsem to na LZMA (xz) na binárním souboru, co lze velmi snadno komprimovat:

Originál: 360MB, xz: 13.7MB (3.8%)
Base64: 487MB, xz: 26.6MB (5.5%)

Nemůže to být tím, že ty komprimátory vidí plain text a použijí na to algorimus, který se víc hodí pro text než pro obecná binární data?

[Bedňa]

Trochu som sa na to mrkol a problém zabalenia base64 je v že používa len rozsah tlačiteľných ASCII znakov, čím degraduje bitovú hĺbu bajtu. Takže idálne je ako som písal vyššie a písal to vlastne aj Franta si spraviť na to preprocesor a postprocesor.

[Heron]

No já na to teď taky čumím jak tele na nový vrata. Myslel jsem si (očekával bych), že base64 bude používat ascii symboly, které vzniknou jako kontinuální výřez z 7b ascii table. A ono ne, base64 si definuje vlastní abecedu ve vlastním pořadí nekompatibilní s ascii.

čím degraduje bitovú hĺbu bajtu

To by snad neměl být problém a je to základ pro komprimaci - předpoklad, že se nevyužívá (rovnoměrně) celá bitová šířka. Když bych z každého byte udělal 2x4, tak alg by měl poznat, že horní 4b jsou nulové. Ostatně i toto je běžný text, většina znaků je z poměrně malé oblasti ascii.

[.]

No ono to b64 samo o sobě se zkomprimuje pěkně. Akorát už ne tak pěkně jako původní text a problém je právě v tom jednom bitu navíc. Teda spíš v tom, že víme, že existuje nějaký původní text. A na té abecedě vůbec nesejde.

[xkucf03]

Problém je v tom, že opakující se stejná data po zakódování do Base64 mohou vypadat různě:

$ echo xxxx ahoj xxxxxxxxxxxxxxxxxxxxxxxxx ahoj xxxx | base64 
eHh4eCBhaG9qIHh4eHh4eHh4eHh4eHh4eHh4eHh4eHh4eHggYWhvaiB4eHh4Cg==

Slovo ahoj je tam dvakrát, ale to kompresní algoritmus nepozná, protože jednou se kóduje jako CBhaG9qI a jednou jako ggYWhvaiB4 (zhruba tam někde). Ale když budeme mít štěstí a zrovna to vyjde na správnou pozici, tak to bude v obou případech stejný řetězec a algoritmus to může zkomprimovat:

$ echo xxxx ahoj xxxxxxxxxxxxxxxxxxxxxxxxxxx ahoj xxxx | base64 
eHh4eCBhaG9qIHh4eHh4eHh4eHh4eHh4eHh4eHh4eHh4eHh4eCBhaG9qIHh4eHgK

Oproti tomu u hexadecimálního kódování se stejná vstupní data kódují vždy na stejné výstupní hodnoty bez ohledu na pozici a sousední bajty, takže se to dá komprimovat mnohem lépe.

Viz také:

$ echo x$(seq 10) | base64 
eDEgMiAzIDQgNSA2IDcgOCA5IDEwCg==

$ echo $(seq 10) | base64 
MSAyIDMgNCA1IDYgNyA4IDkgMTAK

posunem vstupních dat o jediný bajt získáš v Base64 úplně jiný výstup – bez dekódování nelze poznat, že to jsou z 99 % shodná data. U hexadeximálního kódování by ti na začátek přibylo 78 a ten zbytek by zůstal stejný.

[petr_p]

Base64 kóduje vstupních 6 bitů na výstupních 8. Takže řetězec identických bajtů na vstupu (AAAAAAAA) se na výstupu projeví jako řetězec s periodou 4 bajty (ABCDABCDAX). Perioda dva bajty na vstupu (ABABABABABAB) se natáhne na 8 bajtů na výstupu. Teprve 3bajtová perioda se zkrátí na 4bajtovou. Jinak řečeno jakýkoliv vstup jehož délka a zarovnání nesedí na násobek 3 bajtů bude zdánlivě neúměrně zvyšovat entropii. Zdánlivě píšu proto, že kompresní algoritmy hledají společné podřetězce (slovníková metoda) nebo periodické vzory (Huffman). Transformace přes base64 tato opakující se slova a vzory skrývá do mnohem delších period. Takže kompresním algoritmům se zdá, že vstup má vysokou entropii a kompresi vzdají předčasně. Extrémní případ je jakékoliv iracionální číslo, které má periodu nekonečně dlouhou, tudíž jej nelze těmito dvěma metodami komprimovat.

[Heron]

Výhodnější je opačná strategie, nejdřív komprimace, potom base64:

Originál: 360MB, xz: 13.7MB, base64: 19.5MB

Což je pořád menší, než ten komprimovanej base64.

[xkucf03]

Jenže abys to mohl udělat, tak právě ten algoritmus/nástroj musí umět detekovat Base64 a vytáhnout z něj původní data, která pak zkomprimuje. Ručně to samozřejmě udělat můžeš, ale to znamená upravit každou aplikaci, která s těmi daty bude pracovat a změnit její logiku a práci s každým takovým polem obsahujícím binární data kódovaná v Base64.

Oproti tomu, kdyby existoval kompresní algoritmus s lepší podporou Base64 nebo opakujících se textů, tak by na jeho použití šlo upravit aplikace výrazně snadněji – už dneska to bývá modulární, lze přecházet např. z gzipu na xz nebo zstd, informace o použitém kompresním algoritmu bývá v nějaké hlavičce, v metadatech (formátu či protokolu) tzn. na přechod mezi kompresními algoritmy bývají aplikace celkem připravené a lze to provést relativně snadno (zatímco měnit logiku aplikace a přidávat do ní navíc krok typu: a po tom, co dekódujeme Base64 z tohoto pole, tak je ještě dekomprimujeme gzipem… a nebo taky ne, protože staré verze data nekomprimovaly… aha, takže tam vlastně musíme někam přidat další hlavičku, kterou řekneme, zda data uvnitř Base64 jsou komprimovaná nebo ne… je výrazně pracnější).

[Heron]

Jenže abys to mohl udělat, tak právě ten algoritmus/nástroj musí umět detekovat Base64

Mě to připadá jak rovnák na ohejbák.

Máme tady alg, které fungují docela dobře na obecná binární i textová data. Jedinej problém je base64, které to obfuskuje tak, že to ty alg zmate. Ale třeba base16 (hexdump) už takovej problém není.

Takže pokud se bavíme v obecné rovině a měl bych navrhnout textový formát i pro vkládání binárních dat, aby se to dobře komprimovalo, tak base64 není vhodné řešení.

nebo opakujících se textů

To přece nikdy nebyl problém. Však na tomto principu jsou založené všechny slovníkové alg. Na hledání co nejdelších a nejčastěji se opakujících řetězců.

na přechod mezi kompresními algoritmy bývají aplikace celkem připravené a lze to provést relativně snadno

No však. Proto jsem psal, že změnou alg lze dosáhnout mnohem lepších výsledků.

zatímco měnit logiku aplikace

No to jsem ale nikde nenavrhoval. Můj postoj je, že to nestojí za to řešit (ačkoliv je to teda velmi zajímavý problém), protože změna komprimačního alg přinese mnohem víc (i když ne tolik, jako nějaká ideální varianta). To je ale zcela běžné.

[xkucf03]

Takže pokud se bavíme v obecné rovině a měl bych navrhnout textový formát i pro vkládání binárních dat, aby se to dobře komprimovalo, tak base64 není vhodné řešení.

Já jsem se zabýval spíš trochu jinou úvahou: Máme spoustu dat v textových formátech s vnořeným Base64 (to je předpoklad, který nemůžeme jen tak změnit). Lze nějakou drobnou změnou zlepšit situaci?

Pokud by nový¹ kompresní algoritmus lépe pracoval s Base64, tak by to podle mého nějaký přínos mělo. Tím neříkám, že se chystám něco takového vytvářet, jen mi to přišlo jako zajímavá úvaha a chtěl jsem vědět, jestli to už neexistuje.

_{[1] resp. on nemusí být úplně nový, může právě vzniknout složením nějakého stávajícího + preprocesoru}

[Heron]

Chápu. Podle testů stačí vyměnit gzip za xz (nebo možná i zstd, ale to jsem ještě netestovat a nikde nenasadil, tak o tom moc nevím). A tím je to v podstatě hotovo.

[Bherzet]

Někdy by se taky hodila polo-ruční komprese pomocí předem definovaného slovníku – když se nám v textu často opakují určité řetězce, mohli bychom si je na začátku nebo v průběhu textu pomocí nějakých příkazů (uvozených např. zpětným lomítkem) přidat do slovníku a pak je opakovaně používat (zase nějakým příkazem se zpětným lomítkem).

Takhle nějak fungovala komprese textu v dobách DOSu a netuším, k čemu by to dnes bylo. To je kompromis na úrovni „trošičku zkomprimovat, ale né moc, aby to zůstalo jako text“. HTML, které každý tag nahrazuje nějakou referencí (nejkratší tag má 3 bajty, referenci by asi bylo logické mít co nejkratší, tzn. pro tu použít to zpětné lomítko, např. \a, a definici např. \a:<a href="), bys fakt číst nechtěl. To už můžeš rovnou textové HTML nahradit binárním formátem a ušetřit dalších pár bajtů.

Jako úloha na procvičení nějakého jazyka nebo jen tak pro zábavu je to zajímavá a možná to někdy použiju, tak dík za nápad :) Praktické uplatnění mi ale přijde nulové.

[j]

IMO se na to blbe divas.

Base64 se pouziva z duvodu compatability, a samo o sobe veci zvetsuje - jednoduse proto, ze pouziva redukovanej pocet znaku, a tudiz jich pro vyjadreni tehoz musi byt vic.

Typickej priklad je mail, do kteryho kdyz vrazis prilohu, tak ten mail nebude mit velikost prilohy, ale spis tak priloha + 30%.

Ta priloha sama o sobe opet typicky uz nejakou kompresi prosla, protoze je to trebas obrazek, nebo dokument, takze dalsi komprese to spis jeste zvetsi nez naopak.

Mno a ve finale, pokud ti ta velikost vadi, tak podle vseho pouzivas nevhodnej format nebo nevhodnej protokol. Pouzivej takovej, kterej nepouziva base64. Easy.

[Semo]

Tak ma to inspirovao... a vychadza, ze ak clovek predpoklada buducu kompresiu, tak je vyhodnejsie konvertovat do hexdumpu, nez do base64. Pokial sa buduca kompresia neocakava, tak samozrejme naopak.

Prekvapivo velky efekt na odstranenie LF z base64 a hexdump. Pravdepodobne dojde k zredukovaniu pouzitej abecedy na 64 resp. 16 moznych znakov, co sa lepsie komprimuje, nez 65 a 17.

"text" je tato diskusia vykopirovana zbroseru cez clipboard.

# xxd -p <text >text.hex
# base64 <text >text.b64
# tr -d \\n <text.h >text.b64-nolf
# gzip <text.b64 >text.b64.gz
# xz <text.b64 >text.b64.xz
# ...

$ du -b text* | sort -n
12388   text.xz
12976   text.hex-nolf.xz
13089   text.gzip
15538   text.hex-nolf.gz
16088   text.hex.xz
17264   text.b64-nolf.xz
18383   text.hex.gz
19772   text.b64-nolf.gz
20084   text.b64.xz
21077   text.b64.gz
36502   text
48672   text.b64-nolf
49313   text.b64
73004   text.hex-nolf
74221   text.hex

Debaty, ci najprv kompresia a potom enkodovanie alebo naopak su uplne o hovne, pretoze enkodovanie sa nerobi preto, aby sme si uzili, ale pretoze prenosovy kanal (alebo ulozne medium) neznesie divoke znaky (s cim enkodovanie a potom kompresia nijak nepomoze).

Takze ak je to vedomy umysel, tak samorejme najskor komprimovat. Ak sa ale da cakat, ze nejaky matlak to bude chciet komprimovat po tom, co to bolo enkodovane, tak sa da uvazovat o vyhodnosti hexdumpu

[Josef Kufner]

Komprese po zakódování do base64 nastane pokud přenosový kanál použije kompresi. Například pokud vložím obrázek do CSS jako data URI (což se běžně používá například pro ikonky) a výsledný CSS soubor se přenese po HTTP se zapnutou gzip kompresí.

[xkucf03]

+1 Ono jde totiž o to, že to typicky není nějaký jeden „matlák“, který by si řekl: „vymyslím si vlastní formát, kde budou data nejdřív zabalená v Base64 a pak zkomprimovaná“. Ale je to víc lidí, kteří se navzájem moc nekoordinují a jeden balí data do Base64 a moc neřeší, kudy ta data potečou a jak. A druhý, který provozuje nějaký obecný komunikační kanál, kde zavedl obecnou kompresi, zase moc neřeší, jaká data tečou uvnitř, protože tam může být cokoli. A pak se to sejde a výsledkem je to, že se data nejdřív balí do Base64 a pak komprimují obecným algoritmem, který s takto kódovanými daty neumí efektivně pracovat.

[Matlák]

Na druhou stranu když už se ten matlák najde tak většinou komprimuje už komprimovaná data (obrázky, dokumenty nebo jiná komprimovaná média) a ztráty jsou v jednotkách procent. Takže ta šílená, neřízená evoluce WWW dopadla vlastně celkem dobře

[Matlák]

Debaty, ci najprv kompresia a potom enkodovanie alebo naopak su uplne o hovne,...

Takze ak je to vedomy umysel, tak samorejme najskor komprimovat.

Je vidět že i ti co jsou nad hovna povznesení se v nich občas rádi pohrabou (někdy z nutnosti, někdy, jako tady, z inspirace). Já bych to bral tak že textová data se zpravidla do base64 nepřevádí, ani na webu, ani v mailech, a komprimují se jen jednou (při přenosu či uložení/archivaci). Zatímco média (zvuk/obrázky/video, případně rich-text dokumenty, spreadsheety atp..) se komprimují už na začátku a další komprimace výsledného mixu (kořeněného tím base64 enkódováním) přidá pár procent - což vlastně není extra problém.

Ten problém bych viděl v situaci kdy sedím na serveru na který mi chodí vagony naložené nekompresovanými textovými logy či XML převedeným do base64 - ale to si doufám vyjednám z protistranou (ať si to laskavě zkomprimuje než to zakóduje) a pokud ne, tak z nouze (pokud mě zabrané místo fakt pálí) to něčím prolítnu a zkomprimuju "před" převedením do base64...

[Sněhulák]

na částech s Base64/hex daty si většina kompresních algoritmů si na nich vyláme zuby

To je tím, že ty data, co převedeš do Base64 už jsou komprimované (jpg, png ...) a mají vysokou entropii. Proto komprese už jednou komprimovaného zpravidla vede na výstup větší než vstup. Teda, pokud ten první kompresní algoritmus za něco stál.

[xkucf03]

Ne, viz třeba #5. Pokud se algoritmus dostane k surovým datům, tak je dokáže zkomprimovat mnohem efektivněji než data obfuskovaná Base64.

Pokud šlo o už jednou komprimovaná data (JPEG atd.), tak je ten rozdíl poměrně malý, ale pokud je uvnitř toho Base64 něco dobře komprimovatelného, je ten rozdíl třeba 1:3. Tzn. mohl bys ušetřit 2/3 objemu, pokud bys data před kompresí vybalil z Base64 a jen si tam poznamenal (což zabere tak zhruba jeden bajt), že je po dekompresi máš zase do toho Base64 zakódovat (aby platilo data = dekomprese(komprese(data))).

[Sněhulák]

Jasný, nicméně nemyslím si, že by šlo vymyslet obecný algoritmus, který by to zvládal. Muselo by to být něco, co "rozumí" tomu formátu, co chceš komprimovat (např HTML s obrázkama). Max. nějakou heuristiku, ale to je škaredý. Taky tvůj příspěvek předpokládá, že ten obecný kompresní algoritmus bude vhodný na kompresi toho vybaleného druhu dat.

[Josef Kufner]

Otázkou je, jak často je v praxi použito base64 na něco dobře komprimovatelného. Hodně často jsou to už komprimovaná data, např. obrázky, kde už není kam komprimovat. V takových případech komprese celkem dobře kompenzuje nafouknutí vzniklé použitím base64. Pokud použiju base64 na náhodná data a následně to komprimuji, dostanu zpět přibližně původní velikost (rozdíl je v jednotkách procent).

[Martin Mareš]

Začnu od konce: metoda se slovníkem, kterou popisujete, je vlastně základní princip, na kterém stojí algoritmus LZ77, jenž je pradědečkem skoro všech dnešních kompresních algoritmů. Takže cokoliv, co zvládne Vaše slovníková metoda, udělá nejspíš LZ77 sám od sebe. Dokonce i inicializace slovníkem nějakých "dobře známých řetězců" pro konkrétní doménu použití je dost běžná technika.

Jinak dnešní kompresní programy jsou typicky kombinací nějaké slovníkové techniky (něco podobného LZ77) s nějakým statistickým kódováním (Huffman, aritmetické, markovovské apod.). To statistické kódování se na netriviálně dlouhých souborech samo naučí dobře aproximovat inverzi base64. Takže jediná podstatná ztráta bude v tom, že LZ77 nedostane řetězce vždycky hezky zarovnané na hranice bajtů a bude mít efektivně kratší kontext. Obojí mu trochu sníží efektivitu, ale jak je vidět na příkladu s JPEGovým obrázkem, efekt nemusí být velký. Pokus s XML možná ztrácí spíš proto, že je to malý soubor. Bylo by zajímavé zkusit to na nějakých větších textových souborech.

[Josef Kufner]

Zde je takový malý experiment s 19MB titulky (prosté spojení pár desítek textových souborů s pravidelnou strukturou):

Soubor	Velikost [B]	Poměr
		all.srt	all.srt.b64
all.srt	19516522	100,00 %	74,03 %
all.srt.gz	7893461	40,45 %	29,94 %
all.srt.xz	5320716	27,26 %	20,18 %
all.srt.b64	26364428	135,09 %	100,00 %
all.srt.b64.gz	10928386	56,00 %	41,45 %
all.srt.b64.xz	7242868	37,11 %	27,47 %

[Bystroushaak]

Lrzip si nevede úplně špatně:

-rw-rw-r-- 1 bystrousak bystrousak 482M úno 17 13:44 test_data.tar
-rw-rw-r-- 1 bystrousak bystrousak 651M úno 17 13:45 test_data.tar.base64
-rw-rw-r-- 1 bystrousak bystrousak 462M úno 17 13:45 test_data.tar.base64.lrz
-rw-rw-r-- 1 bystrousak bystrousak 445M úno 17 13:44 test_data.tar.lrz

[JS1]

IMHO hlavni potiz s kompresi base64 kodovani spociva v tom, ze bezne kompresni algoritmy kompresuji po bytech, takze pokud zakodujeme posloupnost bajtu do posloupnosti retezcu bitu jine delky nez 8, budou mit problemy.

Zkusil bych nejakou kompresi typu PPM, treba algoritmus PAQ, to je zalozene na predikci jednotlivych bitu, a tudiz nezavisle od velikosti bajtu (a obecne od vstupniho kodovani dat). Navic to umi zvolit jiny prediktivni model pro base64 a normalni text (content mixing). Nicmene protoze to funguje po bitech, je to sice nejspis schopne vyrovnat se s kodovanim jako base64, ale za cenu toho, ze je to celkove mnohem pomalejsi.

[petr_p]

ZPAQ jsem měřil a pořád tam byl asi 40% propad velikosti archivu. Na ZPAQu se mi ale líbí formát archivu, který je v podstatě programem popisující dekompresi, takže kompresní program lze rozvíjet bez ohledu na kompatibilitu.

[Josef Kufner]

To zní jako bezpečnostní díra.

[Kate]

Vypadá to, že používají nějaký custom jazyk pro popis komprese, takže by to nemuselo být tak hrozné.

[kujva]

Specialisti rozlustili byste tohle?

UKaj9NTj+ccE+dAb1JoOOqHtv6uRZYGWL8cX+/ZprWQapegrjA5p2eXHuPuF4I6gvXuh4GLliplcVNtlrBm9sZOoY/PDYiX8SEyvAL3v9LLvI9wRv+DqFrCSyLFw4qsuJ47rYvIjaE20+c5Gzwi6gW5us6IkMHWUSn4qX+rddxg6HgsdyYqK3Nl4X1VWjKahGChhmH0V+NIMK5Cr6FYe+w==

[jiwopene]

Náhodná data? Hodnoty bajtů jsou celkem rovnoměrně rozložené.

$ base64 -d|xxd -c 1|cut -d' ' -f2|sort|uniq -c
UKaj9NTj+ccE+dAb1JoOOqHtv6uRZYGWL8cX+/ZprWQapegrjA5p2eXHuPuF4I6gvXuh4GLliplcVNtlrBm9sZOoY/PDYiX8SEyvAL3v9LLvI9wRv+DqFrCSyLFw4qsuJ47rYvIjaE20+c5Gzwi6gW5us6IkMHWUSn4qX+rddxg6HgsdyYqK3Nl4X1VWjKahGChhmH0V+NIMK5Cr6FYe+w==
      3 ab
      1 ac
      1 ad
      1 af
      1 a0
      3 a1
      1 a2
      1 a3
      1 a5
      2 a6
      1 a8
      1 ba
      3 bd
      2 bf
      1 b0
      2 b1
      1 b2
      1 b3
      1 b4
      1 b8
      1 ce
      1 cf
      1 c3
      3 c7
      1 c8
      1 c9
      1 db
      2 dc
      1 dd
      1 d0
      1 d2
      2 d4
      2 d9
      2 ea
      1 eb
      1 ed
      2 ef
      3 e0
      1 e2
      1 e3
      2 e5
      2 e8
      3 fb
      1 fc
      1 f2
      1 f3
      2 f4
      1 f6
      1 f8
      3 f9
      1 0b
      1 0c
      2 0e
      1 00
      1 04
      1 08
      1 1a
      1 1b
      1 1d
      2 1e
      1 11
      1 15
      1 16
      1 17
      2 18
      1 19
      1 2a
      2 2b
      1 2e
      1 2f
      2 23
      1 24
      1 25
      1 27
      1 28
      2 3a
      1 30
      1 4a
      1 4c
      1 4d
      1 46
      1 48
      1 5c
      2 5f
      1 50
      1 54
      1 55
      2 56
      2 6e
      1 61
      3 62
      1 63
      1 64
      2 65
      1 68
      2 69
      1 7b
      1 7d
      1 7e
      1 70
      1 75
      1 77
      1 78
      3 8a
      2 8c
      2 8e
      2 81
      1 85
      1 9a
      1 90
      1 91
      1 92
      1 93
      1 94
      1 96
      1 98
      1 99

$ base64 -d|xxd -c 1|cut -d' ' -f2|sed 's/^.//'|sort|uniq -c
UKaj9NTj+ccE+dAb1JoOOqHtv6uRZYGWL8cX+/ZprWQapegrjA5p2eXHuPuF4I6gvXuh4GLliplcVNtlrBm9sZOoY/PDYiX8SEyvAL3v9LLvI9wRv+DqFrCSyLFw4qsuJ47rYvIjaE20+c5Gzwi6gW5us6IkMHWUSn4qX+rddxg6HgsdyYqK3Nl4X1VWjKahGChhmH0V+NIMK5Cr6FYe+w==
     12 a
     13 b
      9 c
      9 d
     11 e
      9 f
     11 0
     10 1
      9 2
      9 3
     10 4
     10 5
      8 6
      6 7
     14 8
     10 9

[DaBler]

že by tvůj ECDSA public key?