Drugi korisnik želi zapisati novi podatak na tvrdi disk, ali nema dovoljno slobodnog prostora za to. Također ne želim ništa brisati, jer je "sve vrlo važno i potrebno." I što da radimo s tim?
Nitko nema ovaj problem. Na našim tvrdim diskovima ima terabajta informacija i ta količina nema tendenciju smanjenja. Ali koliko je jedinstven? Na kraju, sve su datoteke samo skupovi bitova određene duljine i najvjerojatnije se nova ne razlikuje puno od one koja je već pohranjena.
Jasno je da je traženje informacija koje su već pohranjene na tvrdom disku, ako ne neuspjeh, onda barem ne učinkovit 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 datoteka, sada u razumljivijem obliku.
O bitovima i razlikama
Ako uzmete dva potpuno nasumična dijela podataka, tada se u prosjeku polovica bitova koje sadrže podudara. Doista, među mogućim izgledima za svaki par ('00, 01, 10, 11′), točno polovica ima iste vrijednosti, ovdje je sve jednostavno.
Ali naravno, ako samo uzmemo dvije datoteke i smjestimo jednu u drugu, tada ćemo izgubiti jednu od njih. Ako spremimo promjene, jednostavno ćemo ponovno izmisliti , koji sasvim dobro postoji i bez nas, iako se obično ne koristi u iste svrhe. Možemo pokušati ugraditi manji niz u veći, ali čak i tako riskiramo gubitak kritičnih segmenata podataka ako ih nepromišljeno koristimo sa svime.
Između čega i čega se onda razlika može eliminirati? Pa, to jest, nova datoteka koju je napisao korisnik je samo niz bitova, s kojim ne možemo ništa učiniti sami. Zatim samo trebate pronaći takve bitove na tvrdom disku da ih je moguće mijenjati bez pohranjivanja razlike, tako da možete preživjeti njihov gubitak bez težih posljedica. I ima smisla mijenjati ne samo datoteku na samom FS-u, već i neke manje osjetljive podatke unutar njega. Ali koji i kako?
Metode ugradnje
Komprimirane datoteke s gubitkom dolaze u pomoć. Svi ti jpegovi, mp3sovi i ostali, iako kompresirani s gubitkom, sadrže hrpu bitova koji se mogu sigurno mijenjati. Moguće je koristiti napredne tehnike koje neprimjetno modificiraju svoje komponente u različitim fazama kodiranja. Čekati. Napredne tehnike... neprimjetna modifikacija... jedan zalogaj u drugi... gotovo kao !
Doista, umetanje jedne informacije u drugu podsjeća na njezine metode kao ništa drugo. Impresioniran sam i neprimjetnošću promjena u ljudskim osjetilima. Ono gdje se putevi razilaze je tajnovitost: naš zadatak se svodi na to da korisnik unese dodatne informacije na svoj tvrdi disk, a to će mu samo naštetiti. Opet će zaboraviti.
Stoga, iako ih možemo koristiti, moramo napraviti neke izmjene. A onda ću im reći i pokazati na primjeru jedne od postojećih metoda i zajedničkog formata datoteke.
O šakalima
Ako ga stvarno stisnete, to je najstisljivija stvar na svijetu. Naravno, govorimo o JPEG datotekama. 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 ovom planetu.
Međutim, kako se ne biste bavili uzgojem pasa, morate ograničiti svoje područje djelovanja u datotekama ovog formata. Nitko ne voli jednobojne kvadrate koji se pojavljuju zbog pretjerane kompresije, pa se morate ograničiti na rad s već komprimiranom datotekom, izbjegavanje rekodiranja. Točnije, s cjelobrojnim koeficijentima, koji ostaju nakon operacija odgovornih za gubitak podataka - DCT i kvantizacije, što je savršeno prikazano u shemi kodiranja (zahvaljujući wikiju Nacionalne knjižnice Bauman):
Postoji mnogo mogućih metoda za optimizaciju jpeg datoteka. Postoji optimizacija bez gubitaka (jpegtran), postoji optimizacija "“, koji zapravo doprinose još nečemu, ali mi za njih ne marimo. Uostalom, ako je korisnik spreman ugraditi jednu informaciju u drugu kako bi povećao slobodan prostor na disku, tada je ili optimizirao svoje slike davno ili to uopće ne želi učiniti zbog straha od gubitka kvalitete.
F5
Cijela obitelj algoritama odgovara ovim uvjetima, s kojima se možete upoznati . Najnapredniji od njih je algoritam Andreasa Westfelda, radeći s koeficijentima komponente svjetline, budući da je ljudsko oko najmanje osjetljivo na njezine promjene. Štoviše, koristi tehniku ugrađivanja koja se temelji na matričnom kodiranju, što omogućuje manje promjena prilikom ugrađivanja iste količine informacija, što je veća veličina korištenog spremnika.
Same promjene svode se na smanjenje apsolutne vrijednosti koeficijenata za jedan pod određenim uvjetima (to jest, ne uvijek), što vam omogućuje da koristite F5 za optimizaciju pohrane podataka na vašem tvrdom disku. Stvar je u tome da će koeficijent nakon takve promjene najvjerojatnije zauzimati manje bitova nakon Huffmanovog kodiranja zbog statističke distribucije vrijednosti u JPEG-u, a nove nule će dati dobitak kada ih kodirate pomoću RLE.
Potrebne izmjene svode se na eliminaciju dijela odgovornog za tajnost (preslagivanje lozinki), čime se štede resursi i vrijeme izvršenja, te dodavanje mehanizma za rad s više datoteka umjesto jedne po jedne. Malo je vjerojatno da će čitatelja detaljnije zanimati 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 proveo niz optimizacija u pogledu brzine izvršavanja i memorije (ne možete zamisliti koliko su te slike teške bez kompresije, čak i prije DCT-a). Višeplatformsko ostvareno korištenjem kombinacije knjižnica , и , na čemu im se zahvaljujemo. Sve to sastavlja 'make', tako da korisnici Windowsa žele sami instalirati neki Cygwin za procjenu ili se sami pozabaviti Visual Studiom i bibliotekama.
Implementacija je dostupna u obliku konzolnog uslužnog programa i biblioteke. Zainteresirani mogu saznati više o korištenju potonjeg u readmeu u repozitoriju na Githubu, čiju poveznicu ću priložiti na kraju posta.
Kako koristiti?
Pažljivo. Slike koje se koriste za pakiranje odabiru se pretraživanjem pomoću regularnog izraza u zadanom korijenskom direktoriju. Po završetku, datoteke se mogu po želji premještati, preimenovati i kopirati unutar svojih granica, mijenjati datoteke i operativne sustave itd. Međutim, trebali biste biti izuzetno oprezni i ni na koji način ne mijenjati trenutni sadržaj. Gubitak vrijednosti čak i jednog bita može onemogućiti oporavak informacija.
Nakon završetka, uslužni program ostavlja posebnu arhivsku datoteku koja sadrži sve podatke potrebne za raspakiranje, uključujući podatke o korištenim slikama. Sam po sebi teži oko par kilobajta i nema značajniji utjecaj na zauzet prostor na disku.
Možete analizirati mogući kapacitet pomoću oznake '-a': './f5ar -a [mapa za pretraživanje] [regularni izraz kompatibilan s Perlom]'. Pakiranje se vrši naredbom './f5ar -p [mapa za pretraživanje] [regularni izraz kompatibilan s Perlom] [pakirana datoteka] [naziv arhive]', a raspakiranje pomoću './f5ar -u [arhivska datoteka] [oporavljeni naziv datoteke ]' .
Demonstracija rada
Kako bih pokazao učinkovitost metode, učitao sam kolekciju od 225 potpuno besplatnih fotografija pasa iz usluge i pronašao u dokumentima veliki pdf od 45 metara drugog toma Knuta.
Redoslijed 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/Slike zaslona za obožavatelje
Raspakirana datoteka može se i treba čitati:
Kao što vidite, od izvornih 633 + 36 == 669 megabajta podataka na tvrdom disku, došli smo do ugodnijih 551. Takva radikalna razlika objašnjava se smanjenjem vrijednosti koeficijenata, što utječe na njihovu naknadno sažimanje bez gubitaka: smanjivanje jednog po jednog može lako “odrezati nekoliko bajtova iz konačne datoteke. Međutim, to je još uvijek gubitak podataka, iako iznimno mali, s kojim ćete se morati pomiriti.
Srećom, apsolutno su nevidljivi oku. Pod spojlerom (budući da habrastorage ne može obraditi velike datoteke), čitatelj može procijeniti razliku i očima i njihov intenzitet, dobiven oduzimanjem vrijednosti promijenjene komponente od izvorne: , , (što je boja tamnija, to je manja razlika u bloku).
Umjesto zaključka
Uzimajući u obzir sve te poteškoće, kupnja tvrdog diska ili upload svega u oblak može se činiti puno jednostavnijim rješenjem problema. Ali iako sada živimo u tako divnom vremenu, nema jamstava da će sutra još uvijek biti moguće otići na internet i negdje učitati sve svoje dodatne podatke. Ili otiđite u trgovinu i kupite si još jedan tvrdi disk od tisuću terabajta. Ali uvijek možete koristiti postojeće kuće.
->
Izvor: www.habr.com