Jiný uživatel chce zapsat nová data na pevný disk, ale nemá k tomu dostatek volného místa. Také nechci nic mazat, protože „všechno je velmi důležité a nezbytné“. A co s tím máme dělat?
Nikdo tento problém nemá. Na našich pevných discích jsou terabajty informací a toto množství nemá tendenci klesat. Ale jak je to jedinečné? Všechny soubory jsou nakonec jen sady bitů určité délky a nový se s největší pravděpodobností příliš neliší od toho, který je již uložen.
Je jasné, že vyhledávání informací již uložených na pevném disku je, když ne selhání, tak alespoň ne efektivní úkol. Na druhou stranu, pokud je rozdíl malý, můžete ho trochu upravit...
TL;DR - druhý pokus mluvit o podivné metodě optimalizace dat pomocí souborů JPEG, nyní ve srozumitelnější podobě.
O kouscích a rozdílech
Pokud vezmete dva zcela náhodné kusy dat, pak se v průměru polovina bitů, které obsahují, shoduje. Z možných rozložení pro každý pár ('00, 01, 10, 11′) má přesně polovina stejné hodnoty, vše je zde jednoduché.
Ale samozřejmě, když vezmeme jen dva soubory a přiložíme jeden k druhému, pak o jeden z nich přijdeme. Pokud změny uložíme, jednoduše je znovu objevíme , který bez nás dokonale existuje, i když se obvykle nepoužívá ke stejným účelům. Můžeme zkusit vložit menší sekvenci do větší, ale i tak riskujeme ztrátu kritických segmentů dat, pokud je použijeme neuváženě se vším.
Mezi čím a čím tedy lze rozdíl odstranit? No, to znamená, že nový soubor zapsaný uživatelem je jen posloupnost bitů, se kterou sami nemůžeme nic dělat. Pak už jen stačí najít na pevném disku takové bity, aby se daly vyměnit, aniž byste museli rozdíl ukládat, abyste jejich ztrátu přežili bez vážnějších následků. A má smysl měnit nejen soubor na samotném FS, ale i některé méně citlivé informace v něm. Ale který a jak?
Způsoby montáže
Na pomoc přicházejí ztrátové komprimované soubory. Všechny tyto jpegy, mp3 a další, i když jsou ztrátovou kompresí, obsahují spoustu bitů, které jsou k dispozici pro bezpečnou úpravu. Je možné použít pokročilé techniky, které neznatelně upravují své komponenty v různých fázích kódování. Počkejte. Pokročilé techniky... nepostřehnutelné úpravy... jeden kousek do druhého... je to skoro jako !
Skutečně, vkládání jedné informace do druhé připomíná její metody jako nic jiného. Imponuje mi také nepostřehnutelnost změn provedených lidskými smysly. Tam, kde se cesty rozcházejí, je tajemství: naším úkolem je, aby uživatel zadal na svůj pevný disk další informace, jen mu to uškodí. Zase zapomene.
Proto, i když je můžeme použít, musíme provést určité úpravy. A pak je řeknu a ukážu na příkladu jedné z existujících metod a běžného formátu souboru.
O šakalech
Pokud to opravdu zmáčknete, je to ta nejstlačitelnější věc na světě. Mluvíme samozřejmě o souborech JPEG. Nejen, že existuje spousta nástrojů a existujících metod pro vkládání dat do něj, ale je to nejoblíbenější grafický formát na této planetě.
Abyste se však nevěnovali chovu psů, musíte v souborech tohoto formátu omezit pole působnosti. Nikdo nemá rád jednobarevné čtverce, které se objevují kvůli nadměrné kompresi, takže se musíte omezit na práci s již komprimovaným souborem, vyhnout se překódování. Přesněji řečeno s celočíselnými koeficienty, které zůstávají po operacích odpovědných za ztrátu dat - DCT a kvantování, což je perfektně zobrazeno v kódovacím schématu (díky wiki Národní knihovny Bauman):
Existuje mnoho možných metod pro optimalizaci souborů jpeg. Existuje bezeztrátová optimalizace (jpegtran), existuje optimalizace ““, které ve skutečnosti přispívají něčím jiným, ale nás nezajímají. Koneckonců, pokud je uživatel připraven vložit jednu informaci do druhé, aby zvýšil volné místo na disku, pak buď své obrázky optimalizoval už dávno, nebo to nechce dělat vůbec ze strachu ze ztráty kvality.
F5
Těmto podmínkám vyhovuje celá rodina algoritmů, se kterými se můžete seznámit . Nejpokročilejší z nich je algoritmus Andreas Westfeld, pracující s koeficienty jasové složky, protože lidské oko je na její změny nejméně citlivé. Navíc používá techniku vkládání založenou na maticovém kódování, která umožňuje provádět méně změn při vkládání stejného množství informací, čím větší je velikost použitého kontejneru.
Samotné změny se scvrkají na snížení absolutní hodnoty koeficientů o jedničku za určitých podmínek (tedy ne vždy), což umožňuje pomocí F5 optimalizovat ukládání dat na pevný disk. Jde o to, že koeficient po takové změně bude s největší pravděpodobností zabírat méně bitů po Huffmanově kódování kvůli statistickému rozložení hodnot v JPEG a nové nuly přinesou zisk při jejich kódování pomocí RLE.
Potřebné úpravy se scvrkají na odstranění části zodpovědné za utajení (přeuspořádání hesla), což šetří zdroje a čas provádění, a přidání mechanismu pro práci s mnoha soubory namísto jednoho najednou. Čtenář se pravděpodobně nebude zajímat o proces změny podrobněji, takže přejděme k popisu implementace.
High-tech
Abych demonstroval, jak tento přístup funguje, implementoval jsem metodu v čistém C a provedl řadu optimalizací jak z hlediska rychlosti provádění, tak paměti (nedokážete si představit, kolik tyto obrázky váží bez komprese, dokonce i před DCT). Multiplatformní dosažená pomocí kombinace knihoven , и , za což jim děkujeme. To vše dává dohromady 'make', takže uživatelé Windows si chtějí nainstalovat nějaký Cygwin pro sebe pro vyzkoušení, nebo si s Visual Studiem a knihovnami poradit sami.
Implementace je dostupná ve formě konzolové utility a knihovny. Zájemci se o používání druhého mohou dozvědět více v readme v úložišti na Githubu, odkaz připojím na konci příspěvku.
Jak používat?
Opatrně. Obrázky použité pro balení se vybírají vyhledáváním pomocí regulárního výrazu v daném kořenovém adresáři. Po dokončení lze soubory v rámci jeho hranic libovolně přesouvat, přejmenovávat a kopírovat, měnit soubory a operační systémy atd. Měli byste však být maximálně opatrní a žádným způsobem neměnit okamžitý obsah. Ztráta hodnoty byť jen jednoho bitu může znemožnit obnovu informací.
Po dokončení nástroj zanechá speciální archivní soubor obsahující všechny informace potřebné pro rozbalení, včetně údajů o použitých obrázcích. Sám o sobě váží asi pár kilobajtů a nemá zásadní vliv na obsazené místo na disku.
Možnou kapacitu můžete analyzovat pomocí parametru '-a': './f5ar -a [složka hledání] [regulární výraz kompatibilní s Perlem]'. Balení se provádí příkazem './f5ar -p [složka hledání] [regulární výraz kompatibilní s Perlem] [sbalený soubor] [název archivu]' a rozbalování pomocí './f5ar -u [soubor archivu] [název obnoveného souboru ]' .
Ukázka práce
Abych ukázal účinnost metody, nahrál jsem kolekci 225 zcela bezplatných fotografií psů ze služby a našel v dokumentech velké pdf 45 metrů druhého svazku Knuta.
Pořadí je celkem jednoduché:
$ du -sh knuth.pdf dogs/
44M knuth.pdf
633M dogs/
$ ./f5ar -p dogs/ .*jpg knuth.pdf dogs.f5ar
Reading compressing file... ok
Initializing the archive... ok
Analysing library capacity... done in 17.0s
Detected somewhat guaranteed capacity of 48439359 bytes
Detected possible capacity of upto 102618787 bytes
Compressing... done in 39.4s
Saving the archive... ok
$ ./f5ar -u dogs/dogs.f5ar knuth_unpacked.pdf
Initializing the archive... ok
Reading the archive file... ok
Filling the archive with files... done in 1.4s
Decompressing... done in 21.0s
Writing extracted data... ok
$ sha1sum knuth.pdf knuth_unpacked.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth_unpacked.pdf
$ du -sh dogs/
551M dogs/Screenshoty pro fanoušky
Rozbalený soubor lze a měl by stále číst:
Jak vidíte, z původních 633 + 36 == 669 MB dat na pevném disku jsme došli k příjemnějším 551. Takto radikální rozdíl se vysvětluje poklesem hodnot koeficientů, který ovlivňuje jejich následná bezeztrátová komprese: zmenšením jednoho po druhém lze snadno „odříznout pár bajtů z výsledného souboru. Stále se však jedná o ztrátu dat, i když extrémně malou, se kterou se budete muset smířit.
Naštěstí jsou pro oko absolutně neviditelné. Pod spoilerem (protože habrastorage neumí zpracovat velké soubory) může čtenář vyhodnotit rozdíl jak okem, tak i jejich intenzitu, získanou odečtením hodnot změněné komponenty od originálu: , , (čím matnější barva, tím menší rozdíl v bloku).
Místo závěru
Když vezmeme v úvahu všechny tyto potíže, nákup pevného disku nebo nahrání všeho do cloudu se může zdát jako mnohem jednodušší řešení problému. Ale i když nyní žijeme v tak nádherné době, neexistuje žádná záruka, že zítra bude stále možné jít online a všechna svá data navíc někam nahrát. Nebo jděte do obchodu a kupte si další tisíc terabajtový pevný disk. Vždy ale můžete využít stávající domy.
->
Zdroj: www.habr.com