Drugi korisnik želi upisati novi dio podataka na tvrdi disk, ali nema dovoljno slobodnog prostora da to učini. Takođe ne želim ništa da brišem, jer je „sve veoma važno i neophodno“. I šta da radimo s tim?
Niko nema ovaj problem. Na našim čvrstim diskovima ima terabajta informacija i ta količina se ne smanjuje. Ali koliko je to jedinstveno? Na kraju, sve datoteke su samo skupovi bitova određene dužine i, najvjerovatnije, novi se ne razlikuje mnogo od onog koji je već pohranjen.
Jasno je da je traženje informacija koje su već pohranjene na tvrdom disku, ako ne neuspješan, onda barem ne efikasan zadatak. S druge strane, ako je razlika mala, onda je možete malo prilagoditi...
TL;DR - drugi pokušaj da se govori o čudnoj metodi optimizacije podataka pomoću JPEG fajlova, sada u razumljivijem obliku.
O bitovima i razlikama
Ako uzmete dva potpuno nasumična podatka, tada se u prosjeku polovina bitova koji sadrže poklapa. Zaista, među mogućim rasporedima za svaki par ('00, 01, 10, 11′), tačno polovina ima iste vrijednosti, ovdje je sve jednostavno.
Ali naravno, ako samo uzmemo dva fajla i jedan uklopimo u drugi, onda ćemo izgubiti jedan od njih. Ako sačuvamo promjene, jednostavno ćemo ponovo izmisliti , koji savršeno dobro postoji i bez nas, iako se obično ne koristi u iste svrhe. Možemo pokušati da ugradimo manji niz u veći, ali čak i tako riskiramo gubitak kritičnih segmenata podataka ako ga nesmotreno koristimo sa svime.
Između čega i čega se onda razlika može eliminisati? Dakle, nova datoteka koju je napisao korisnik je samo niz bitova, s kojima ne možemo ništa učiniti sami. Tada samo trebate pronaći takve bitove na tvrdom disku da se mogu mijenjati bez pohranjivanja razlike, tako da možete preživjeti njihov gubitak bez ozbiljnih posljedica. I ima smisla promijeniti ne samo datoteku na samom FS-u, već i neke manje osjetljive informacije unutar njega. Ali koji i kako?
Metode ugradnje
Komprimirani fajlovi sa gubitkom dolaze u pomoć. Svi ovi jpegovi, mp3 i drugi, iako sa kompresijom sa gubitkom, sadrže gomilu bitova koji se mogu sigurno promijeniti. Moguće je koristiti napredne tehnike koje neprimjetno modificiraju svoje komponente u različitim fazama kodiranja. Čekaj. Napredne tehnike... neprimjetna modifikacija... jedan dio u drugi... to je skoro kao !
Zaista, ugrađivanje jedne informacije u drugu podsjeća na njene metode kao ništa drugo. Impresioniran sam i neprimjetnošću promjena u ljudskim čulima. Gdje se putevi razilaze je u tajnosti: naš zadatak se svodi na to da korisnik unese dodatne informacije na svoj hard disk; to će mu samo naštetiti. Opet će zaboraviti.
Stoga, iako ih možemo koristiti, moramo napraviti neke modifikacije. A onda ću ih ispričati i pokazati koristeći primjer jedne od postojećih metoda i uobičajenog formata datoteke.
O šakalima
Ako ga stvarno stisnete, to je najkompresivnija stvar na svijetu. Naravno, govorimo o JPEG fajlovima. Ne samo da postoji mnoštvo alata i postojećih metoda za ugrađivanje podataka u njega, već je to najpopularniji grafički format na ovoj planeti.
Međutim, kako se ne biste bavili uzgojem pasa, morate ograničiti svoje polje aktivnosti u datotekama ovog formata. Niko ne voli jednobojne kvadrate koji se pojavljuju zbog pretjerane kompresije, pa se morate ograničiti na rad s već komprimiranim fajlom, izbjegavanje kodiranja. Tačnije, sa cjelobrojnim koeficijentima, koji ostaju nakon operacija odgovornih za gubitak podataka - DCT i kvantizacije, što je savršeno prikazano u šemi kodiranja (zahvaljujući wikiju Bauman National Library):
Postoji mnogo mogućih metoda za optimizaciju jpeg datoteka. Postoji optimizacija bez gubitaka (jpegtran), postoji optimizacija "“, koji zapravo doprinose nečemu drugom, ali nas nije briga za njih. Uostalom, ako je korisnik spreman ugraditi jednu informaciju u drugu kako bi povećao slobodan prostor na disku, tada je ili optimizirao svoje slike odavno, ili to uopće ne želi učiniti iz straha od gubitka kvalitete.
F5
Čitava porodica algoritama odgovara ovim uslovima, sa kojima se možete upoznati . Najnapredniji od njih je algoritam Andreas Westfeld, radeći s koeficijentima komponente svjetline, budući da je ljudsko oko najmanje osjetljivo na njene promjene. Štaviše, koristi tehniku ugrađivanja zasnovanu na matričnom kodiranju, što omogućava da se napravi manje promjena kada se ugrađuje ista količina informacija, što je veća veličina spremnika koji se koristi.
Same promjene se svode na smanjenje apsolutne vrijednosti koeficijenata za jedan pod određenim uvjetima (to jest, ne uvijek), što vam omogućava da koristite F5 za optimizaciju skladištenja podataka na vašem tvrdom disku. Činjenica je da će koeficijent nakon takve promjene najvjerovatnije zauzeti manje bitova nakon Huffmanovog kodiranja zbog statističke distribucije vrijednosti u JPEG-u, a nove nule će dati dobitak prilikom njihovog kodiranja pomoću RLE-a.
Neophodne modifikacije se svode na eliminisanje dela odgovornog za tajnost (preuređenje lozinke), čime se štedi resurse i vreme izvršavanja, i dodavanje mehanizma za rad sa više fajlova umesto jednog po jednog. Malo je vjerovatno da će čitaoca zanimati detaljniji proces promjene, pa prijeđimo na opis implementacije.
Visoka tehnologija
Da bih demonstrirao kako ovaj pristup funkcionira, implementirao sam metodu u čistom C-u i izvršio brojne optimizacije kako u pogledu brzine izvršavanja tako i memorije (ne možete zamisliti koliko ove slike teže bez kompresije, čak i prije DCT-a). Cross-platform je postignut kombinacijom biblioteka , и , na čemu im se zahvaljujemo. Sve ovo sastavlja 'make', tako da korisnici Windowsa žele sami da instaliraju Cygwin za procjenu, ili se sami bave Visual Studio-om i bibliotekama.
Implementacija je dostupna u obliku konzolnog uslužnog programa i biblioteke. Zainteresovani mogu saznati više o korištenju potonjeg u readme-u u spremištu na Github-u, link na koji ću priložiti na kraju posta.
Kako koristiti?
Pažljivo. Slike koje se koriste za pakovanje biraju se pretragom pomoću regularnog izraza u datom korijenskom direktoriju. Po završetku, fajlovi se mogu premještati, preimenovati i kopirati po želji unutar svojih granica, mijenjati datoteke i operativne sisteme, itd. Međutim, trebali biste biti izuzetno oprezni i ne mijenjati trenutni sadržaj ni na koji način. Gubitak vrijednosti čak i jednog bita može onemogućiti oporavak informacija.
Po završetku, uslužni program ostavlja posebnu arhivsku datoteku koja sadrži sve informacije potrebne za raspakivanje, uključujući podatke o korištenim slikama. Sam po sebi, teži oko par kilobajta i nema značajniji uticaj na zauzeti prostor na disku.
Možete analizirati mogući kapacitet koristeći '-a' zastavicu: './f5ar -a [fascikla za pretraživanje] [Perl-kompatibilni regularni izraz]'. Pakovanje se vrši naredbom './f5ar -p [fascikla za pretragu] [Regularni izraz kompatibilan sa Perlom] [upakovana datoteka] [ime arhive]', a raspakivanje pomoću './f5ar -u [arhivska datoteka] [obnovljeni naziv datoteke ]' .
Demonstracija rada
Da pokažem efikasnost metode, postavio sam kolekciju od 225 apsolutno besplatnih fotografija pasa iz servisa i pronašao u dokumentima veliki pdf od 45 metara drugog toma Knuta.
Slijed je prilično jednostavan:
$ 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/Snimci ekrana za fanove
Raspakovani fajl se može i još uvek treba čitati:
Kao što vidite, od originalnih 633 + 36 == 669 megabajta podataka na tvrdom disku, došli smo do ugodnijih 551. Ovako radikalna razlika se objašnjava smanjenjem vrijednosti koeficijenata, što utiče na njihov naknadna kompresija bez gubitaka: smanjenje jednog po jednog može lako „odsjeći par bajtova iz konačne datoteke. Međutim, ovo je i dalje gubitak podataka, iako izuzetno mali, s kojim ćete morati da se pomirite.
Na sreću, oni su apsolutno nevidljivi za oko. Ispod spojlera (budući da habrastorage ne može da obrađuje velike datoteke), čitalac može procijeniti razliku i na oko i njihov intenzitet, dobiven oduzimanjem vrijednosti promijenjene komponente od originala: , , (što je tamnija boja, to je manja razlika u bloku).
Umjesto zaključka
Uzimajući u obzir sve ove poteškoće, kupovina hard diska ili otpremanje svega u oblak može izgledati kao mnogo jednostavnije rješenje problema. Ali iako sada živimo u tako divnom vremenu, nema garancija da će sutra i dalje biti moguće otići na internet i negdje učitati sve svoje dodatne podatke. Ili idite u prodavnicu i kupite sebi još jedan hard disk od hiljadu terabajta. Ali uvijek možete koristiti postojeće kuće.
->
izvor: www.habr.com