Iný používateľ chce zapísať nový údaj na pevný disk, ale nemá na to dostatok voľného miesta. Tiež nechcem nič mazať, pretože „všetko je veľmi dôležité a potrebné“. A čo s tým máme robiť?
Nikto nemá tento problém. Na našich pevných diskoch sú terabajty informácií a toto množstvo nemá tendenciu klesať. Ale aké je to jedinečné? Nakoniec sú všetky súbory iba sady bitov určitej dĺžky a s najväčšou pravdepodobnosťou sa nový súbor príliš nelíši od toho, ktorý je už uložený.
Je jasné, že vyhľadávanie informácií už uložených na pevnom disku je, ak nie zlyhanie, tak aspoň nie efektívna úloha. Na druhej strane, ak je rozdiel malý, môžete ho trochu upraviť...
TL;DR - druhý pokus hovoriť o podivnej metóde optimalizácie dát pomocou súborov JPEG, teraz v zrozumiteľnejšej forme.
O kúskoch a rozdieloch
Ak vezmete dva úplne náhodné údaje, potom sa v priemere polovica bitov, ktoré obsahujú, zhoduje. V skutočnosti medzi možnými rozloženiami pre každý pár ('00, 01, 10, 11′) má presne polovica rovnaké hodnoty, tu je všetko jednoduché.
Ale samozrejme, ak vezmeme len dva súbory a prispôsobíme jeden druhému, potom jeden z nich stratíme. Ak zmeny uložíme, jednoducho ich znova vymyslíme , ktorý úplne dobre existuje aj bez nás, hoci sa zvyčajne nepoužíva na rovnaké účely. Môžeme sa pokúsiť vložiť menšiu sekvenciu do väčšej, ale aj tak riskujeme stratu kritických segmentov údajov, ak ich použijeme neuvážene so všetkým.
Medzi čím a čím sa potom dá odstrániť rozdiel? To znamená, že nový súbor napísaný používateľom je len postupnosť bitov, s ktorými nemôžeme sami nič urobiť. Potom už len treba nájsť na pevnom disku také bity, aby sa dali vymeniť bez toho, aby ste museli rozdiel ukladať, aby ste ich stratu prežili bez vážnejších následkov. A má zmysel meniť nielen súbor na samotnom FS, ale aj niektoré menej citlivé informácie v ňom. Ale ktorý a ako?
Spôsoby montáže
Na pomoc prichádzajú stratové komprimované súbory. Všetky tieto jpegy, mp3 a iné, hoci sú stratové kompresie, obsahujú kopu bitov, ktoré sa dajú bezpečne zmeniť. Je možné použiť pokročilé techniky, ktoré nepozorovane upravujú ich komponenty v rôznych fázach kódovania. počkaj. Pokročilé techniky... nepostrehnuteľná modifikácia... jeden kúsok do druhého... je to skoro ako !
Skutočne, vkladanie jednej informácie do druhej pripomína jej metódy ako nič iné. Imponuje mi aj nepostrehnuteľnosť zmien vykonaných na ľudských zmysloch. Tam, kde sa cesty rozchádzajú, je v tajnosti: našou úlohou je, aby používateľ zadal ďalšie informácie na svoj pevný disk, čo mu len uškodí. Opäť zabudne.
Preto, aj keď ich môžeme použiť, musíme urobiť nejaké úpravy. A potom ich poviem a ukážem na príklade jednej z existujúcich metód a bežného formátu súboru.
O šakaloch
Ak ho naozaj stlačíte, je to tá najstlačiteľnejšia vec na svete. Hovoríme samozrejme o súboroch JPEG. Nielenže existuje veľa nástrojov a existujúcich metód na vkladanie údajov do neho, ale je to najobľúbenejší grafický formát na tejto planéte.
Aby ste sa však nevenovali chovu psov, musíte v súboroch tohto formátu obmedziť pole pôsobnosti. Nikto nemá rád monochromatické štvorce, ktoré sa objavujú v dôsledku nadmernej kompresie, takže sa musíte obmedziť na prácu s už komprimovaným súborom, vyhýbanie sa prekódovaniu. Presnejšie, s celočíselnými koeficientmi, ktoré zostávajú po operáciách zodpovedných za stratu dát - DCT a kvantizácia, ktorá je dokonale zobrazená v schéme kódovania (vďaka wiki Národnej knižnice Bauman):
Existuje mnoho možných metód na optimalizáciu súborov jpeg. Existuje bezstratová optimalizácia (jpegtran), existuje optimalizácia ““, ktoré v skutočnosti prispievajú niečím iným, ale nestaráme sa o ne. Koniec koncov, ak je používateľ pripravený vložiť jednu informáciu do druhej, aby zväčšil voľné miesto na disku, potom buď optimalizoval svoje obrázky už dávno, alebo to nechce robiť vôbec zo strachu zo straty kvality.
F5
Týmto podmienkam vyhovuje celá rodina algoritmov, s ktorými sa môžete zoznámiť . Najpokročilejší z nich je algoritmus od Andreasa Westfelda, pracujúceho s koeficientmi jasovej zložky, keďže ľudské oko je najmenej citlivé na jej zmeny. Okrem toho využíva techniku vkladania založenú na maticovom kódovaní, ktorá umožňuje vykonať menej zmien pri vkladaní rovnakého množstva informácií, čím väčšia je veľkosť použitého kontajnera.
Samotné zmeny sa zredukujú na zníženie absolútnej hodnoty koeficientov za určitých podmienok (teda nie vždy), čo umožňuje pomocou F5 optimalizovať ukladanie dát na pevnom disku. Ide o to, že koeficient po takejto zmene bude s najväčšou pravdepodobnosťou zaberať menej bitov po Huffmanovom kódovaní v dôsledku štatistického rozloženia hodnôt v JPEG a nové nuly prinesú zisk pri ich kódovaní pomocou RLE.
Potrebné úpravy sa scvrkli na odstránenie časti zodpovednej za utajenie (zmena hesla), čo šetrí zdroje a čas vykonávania, a pridanie mechanizmu na prácu s mnohými súbormi namiesto jedného naraz. Čitateľ sa pravdepodobne nebude zaujímať o proces zmeny podrobnejšie, takže prejdime k popisu implementácie.
High-tech
Aby som demonštroval, ako tento prístup funguje, implementoval som metódu v čistom C a vykonal som niekoľko optimalizácií z hľadiska rýchlosti vykonávania a pamäte (neviete si predstaviť, koľko tieto obrázky vážia bez kompresie, dokonca aj pred DCT). Multiplatformové dosiahnuté pomocou kombinácie knižníc , и , za čo im ďakujeme. Toto všetko dáva dokopy 'make', takže užívatelia Windowsu si chcú nainštalovať nejaký Cygwin pre seba na vyhodnotenie, alebo si poradiť s Visual Studiom a knižnicami sami.
Implementácia je dostupná vo forme konzolovej utility a knižnice. Záujemcovia sa o používaní posledného môžu dozvedieť viac v readme v úložisku na Github, odkaz na ktorý pripojím na konci príspevku.
Ako používať?
Opatrne. Obrázky použité na balenie sa vyberajú vyhľadávaním pomocou regulárneho výrazu v danom koreňovom adresári. Po dokončení je možné súbory ľubovoľne presúvať, premenovávať a kopírovať v rámci jeho hraníc, meniť súbory a operačné systémy atď. Mali by ste však byť mimoriadne opatrní a žiadnym spôsobom nemeniť bezprostredný obsah. Strata hodnoty čo i len jedného bitu môže znemožniť obnovenie informácií.
Po dokončení nástroj zanechá špeciálny archívny súbor obsahujúci všetky informácie potrebné na rozbalenie vrátane údajov o použitých obrázkoch. Sama o sebe váži okolo pár kilobajtov a nemá zásadný vplyv na obsadené miesto na disku.
Možnú kapacitu môžete analyzovať pomocou príznaku '-a': './f5ar -a [priečinok vyhľadávania] [regulárny výraz kompatibilný s Perlom]'. Zbalenie sa vykoná príkazom './f5ar -p [vyhľadávací priečinok] [regulárny výraz kompatibilný s Perlom] [zbalený súbor] [názov archívu]' a rozbalenie pomocou './f5ar -u [archívny súbor] [názov obnoveného súboru ]' .
Ukážka práce
Aby som ukázal účinnosť metódy, odovzdal som zbierku 225 úplne bezplatných fotografií psov zo služby a našiel v dokumentoch veľké pdf 45 metrov druhého zväzku Knuta.
Postupnosť je celkom 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 pre fanúšikov
Rozbalený súbor je možné a mal by sa stále čítať:
Ako vidíte, z pôvodných 633 + 36 == 669 megabajtov dát na pevnom disku sme sa dostali k príjemnejším 551. Takýto radikálny rozdiel sa vysvetľuje poklesom hodnôt koeficientov, čo ovplyvňuje ich následná bezstratová kompresia: zmenšenie jedného po druhom môže ľahko „odrezať pár bajtov z výsledného súboru. Stále však ide o stratu dát, aj keď extrémne malú, s ktorou sa budete musieť zmieriť.
Našťastie sú pre oči absolútne neviditeľné. Pod spojlerom (keďže habrastorage nedokáže spracovať veľké súbory) môže čitateľ vyhodnotiť rozdiel okom aj ich intenzitu získanú odčítaním hodnôt zmeneného komponentu od originálu: , , (čím matnejšia farba, tým menší je rozdiel v bloku).
namiesto záveru
Ak vezmeme do úvahy všetky tieto ťažkosti, kúpa pevného disku alebo nahranie všetkého do cloudu sa môže zdať ako oveľa jednoduchšie riešenie problému. Ale aj keď teraz žijeme v takej nádhernej dobe, nie je zaručené, že zajtra bude stále možné ísť online a niekam nahrať všetky svoje údaje navyše. Alebo choďte do obchodu a kúpte si ďalší tisíc terabajtový pevný disk. Vždy však môžete použiť existujúce domy.
->
Zdroj: hab.com