Un alt utilizator dorește să scrie o nouă bucată de date pe hard disk, dar nu are suficient spațiu liber pentru a face acest lucru. De asemenea, nu vreau să șterg nimic, deoarece „totul este foarte important și necesar”. Și ce ar trebui să facem cu el?
Nimeni nu are această problemă. Există terabytes de informații pe hard disk-urile noastre, iar această cantitate nu tinde să scadă. Dar cât de unic este? În cele din urmă, toate fișierele sunt doar seturi de biți de o anumită lungime și, cel mai probabil, cel nou nu este mult diferit de cel care este deja stocat.
Este clar că căutarea unor informații deja stocate pe un hard disk este, dacă nu un eșec, atunci cel puțin nu este o sarcină eficientă. Pe de altă parte, dacă diferența este mică, atunci o poți ajusta puțin...
TL;DR - a doua încercare de a vorbi despre o metodă ciudată de optimizare a datelor folosind fișiere JPEG, acum într-o formă mai ușor de înțeles.
Despre biți și diferență
Dacă luați două date complet aleatorii, atunci, în medie, jumătate din biții pe care îi conțin coincid. Într-adevăr, dintre layout-urile posibile pentru fiecare pereche (’00, 01, 10, 11′), exact jumătate au aceleași valori, totul este simplu aici.
Dar, desigur, dacă luăm doar două fișiere și potrivim unul la al doilea, atunci vom pierde unul dintre ele. Dacă salvăm modificările, pur și simplu ne vom reinventa , care există perfect fără noi, deși de obicei nu este folosit în aceleași scopuri. Putem încerca să încorporăm o secvență mai mică într-una mai mare, dar chiar și așa riscăm să pierdem segmente critice de date dacă o folosim cu nesăbuință cu orice.
Între ce și ce atunci poate fi eliminată diferența? Ei bine, adică un fișier nou scris de utilizator este doar o secvență de biți, cu care nu putem face nimic de la sine. Atunci trebuie doar să găsiți astfel de biți pe hard disk încât să poată fi modificați fără a fi nevoie să stocați diferența, astfel încât să puteți supraviețui pierderii lor fără consecințe grave. Și este logic să schimbați nu doar fișierul de pe FS în sine, ci și unele informații mai puțin sensibile din interiorul acestuia. Dar care și cum?
Metode de montare
Fișierele comprimate cu pierderi vin în ajutor. Toate aceste fișiere jpeg, mp3 și altele, deși cu pierderi de compresie, conțin o grămadă de biți care pot fi modificați în siguranță. Este posibil să se utilizeze tehnici avansate care își modifică imperceptibil componentele în diferite etape de codificare. Aștepta. Tehnici avansate... modificare imperceptibilă... un pic în altul... e aproape ca !
Într-adevăr, încorporarea unei informații în alta amintește de metodele ei ca nimic altceva. Sunt impresionat și de imperceptibilitatea schimbărilor aduse simțurilor umane. În cazul în care căile diverg, este în secret: sarcina noastră se reduce la introducerea de către utilizator a informațiilor suplimentare pe hard disk-ul său; nu va face decât să-i facă rău. Va uita din nou.
Prin urmare, deși le putem folosi, trebuie să facem câteva modificări. Și apoi le voi spune și le voi arăta folosind exemplul uneia dintre metodele existente și un format de fișier comun.
Despre șacali
Dacă îl strângi cu adevărat, este cel mai compresibil lucru din lume. Desigur, vorbim despre fișierele JPEG. Nu numai că există tone de instrumente și metode existente pentru încorporarea datelor în el, dar este cel mai popular format de grafică de pe această planetă.
Cu toate acestea, pentru a nu vă angaja în creșterea câinilor, trebuie să vă limitați domeniul de activitate în fișiere de acest format. Nimănui nu-i plac pătratele monocrome care apar din cauza compresiei excesive, așa că trebuie să te limitezi la a lucra cu un fișier deja comprimat, evitând recodificarea. Mai exact, cu coeficienți întregi, care rămân după operațiunile responsabile de pierderea datelor - DCT și cuantizare, care este perfect afișat în schema de codificare (mulțumită wiki-ului Bibliotecii Naționale Bauman):
Există multe metode posibile pentru optimizarea fișierelor jpeg. Există optimizare fără pierderi (jpegtran), există optimizare "„, care de fapt contribuie cu altceva, dar nu ne pasă de ele. La urma urmei, dacă utilizatorul este gata să încorporeze o informație în alta pentru a crește spațiul liber pe disc, atunci fie și-a optimizat imaginile cu mult timp în urmă, fie nu vrea deloc să facă acest lucru de teama pierderii calității.
F5
O întreagă familie de algoritmi se potrivește acestor condiții, cu care vă puteți familiariza . Cel mai avansat dintre ele este algoritmul de Andreas Westfeld, lucrând cu coeficienții componentei de luminozitate, deoarece ochiul uman este cel mai puțin sensibil la modificările sale. Mai mult, folosește o tehnică de încorporare bazată pe codificarea matricei, ceea ce face posibilă efectuarea mai puține modificări atunci când încorporează aceeași cantitate de informații, cu atât dimensiunea containerului utilizat este mai mare.
Modificările în sine se reduc la reducerea valorii absolute a coeficienților cu unul în anumite condiții (adică nu întotdeauna), ceea ce vă permite să utilizați F5 pentru a optimiza stocarea datelor pe hard disk. Cert este că coeficientul după o astfel de modificare va ocupa cel mai probabil mai puțini biți după codarea Huffman datorită distribuției statistice a valorilor în JPEG, iar noile zerouri vor oferi un câștig atunci când le codifică folosind RLE.
Modificările necesare se rezumă la eliminarea părții responsabile de secret (rearanjarea parolei), care economisește resurse și timp de execuție și adăugarea unui mecanism de lucru cu mai multe fișiere în loc de unul câte unul. Este puțin probabil ca cititorul să fie interesat de procesul de schimbare mai detaliat, așa că să trecem la o descriere a implementării.
High Tech
Pentru a demonstra cum funcționează această abordare, am implementat metoda în C pur și am realizat o serie de optimizări atât în ceea ce privește viteza de execuție, cât și memoria (nu vă puteți imagina cât cântăresc aceste imagini fără compresie, chiar înainte de DCT). Multi-platformă realizată folosind o combinație de biblioteci , и , pentru care le mulțumim. Toate acestea sunt adunate prin „make”, astfel încât utilizatorii Windows doresc să instaleze Cygwin pentru ei înșiși pentru evaluare sau să se ocupe de Visual Studio și biblioteci pe cont propriu.
Implementarea este disponibilă sub forma unui utilitar de consolă și bibliotecă. Cei interesați pot afla mai multe despre utilizarea acestuia din urmă în readme-ul din depozitul de pe Github, link-ul la care îl voi atașa la sfârșitul postării.
Cum se utilizează?
Cu grija. Imaginile utilizate pentru ambalare sunt selectate prin căutare folosind o expresie regulată în directorul rădăcină dat. După finalizare, fișierele pot fi mutate, redenumite și copiate după bunul plac în limitele sale, pot schimba fișierele și sistemele de operare etc. Cu toate acestea, ar trebui să fiți extrem de atenți și să nu modificați în niciun fel conținutul imediat. Pierderea valorii chiar și a unui bit poate face imposibilă recuperarea informațiilor.
La finalizare, utilitarul lasă un fișier de arhivă special care conține toate informațiile necesare pentru despachetare, inclusiv date despre imaginile utilizate. În sine, cântărește aproximativ câțiva kiloocteți și nu are niciun impact semnificativ asupra spațiului ocupat pe disc.
Puteți analiza capacitatea posibilă folosind indicatorul „-a”: „./f5ar -a [dosar de căutare] [expresie regulată compatibilă cu Perl]”. Ambalarea se face cu comanda „./f5ar -p [dosar de căutare] [expresie regulată compatibilă cu Perl] [fișier împachetat] [nume arhivă]”, iar despachetarea cu „./f5ar -u [fișier arhivă] [nume fișier recuperat ]' .
Demonstrație de muncă
Pentru a arăta eficacitatea metodei, am încărcat o colecție de 225 de fotografii absolut gratuite cu câini de la serviciu și a găsit în documente un pdf mare de 45 de metri al celui de-al doilea volum Knuta.
Secvența este destul de simplă:
$ 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/Capturi de ecran pentru fani
Fișierul dezambalat poate și ar trebui să fie citit:
După cum puteți vedea, din 633 + 36 == 669 megaocteți de date de pe hard disk, am ajuns la 551 mai plăcute. O astfel de diferență radicală se explică prin scăderea valorilor coeficienților, care le afectează compresie ulterioară fără pierderi: reducerea unul câte unul poate „taia cu ușurință câțiva octeți din fișierul final. Cu toate acestea, aceasta este încă o pierdere de date, deși extrem de mică, pe care va trebui să o suportați.
Din fericire, sunt absolut invizibili pentru ochi. Sub spoiler (deoarece habrastorage nu poate gestiona fișiere mari), cititorul poate evalua diferența atât în funcție de ochi, cât și de intensitatea acestora, obținută prin scăderea valorilor componentei modificate din original: , , (cu cât culoarea este mai tern, cu atât diferența de bloc este mai mică).
În loc de concluzie
Având în vedere toate aceste dificultăți, cumpărarea unui hard disk sau încărcarea totul în cloud poate părea o soluție mult mai simplă la problemă. Dar, chiar dacă trăim într-o perioadă atât de minunată acum, nu există garanții că mâine va fi în continuare posibil să intrați online și să încărcați toate datele suplimentare undeva. Sau mergi la magazin și cumpără-ți încă un hard disk de o mie de terabyte. Dar puteți folosi oricând casele existente.
->
Sursa: www.habr.com