En anden bruger ønsker at skrive et nyt stykke data til harddisken, men han har ikke nok ledig plads til at gøre dette. Jeg ønsker heller ikke at slette noget, da "alt er meget vigtigt og nødvendigt." Og hvad skal vi gøre med det?
Ingen har dette problem. Der er terabyte af information på vores harddiske, og denne mængde har ikke en tendens til at falde. Men hvor unikt er det? I sidste ende er alle filer bare sæt af bits af en vis længde, og højst sandsynligt er den nye ikke meget anderledes end den, der allerede er gemt.
Det er klart, at søgning efter informationer, der allerede er gemt på en harddisk, er, hvis ikke en fejl, så i det mindste ikke en effektiv opgave. På den anden side, hvis forskellen er lille, så kan du justere den lidt...
TL;DR - det andet forsøg på at tale om en mærkelig metode til at optimere data ved hjælp af JPEG-filer, nu i en mere forståelig form.
Om bits og forskel
Hvis du tager to helt tilfældige stykker data, så falder i gennemsnit halvdelen af de bits, de indeholder, sammen. Faktisk, blandt de mulige layouts for hvert par ('00, 01, 10, 11′), har nøjagtig halvdelen de samme værdier, alt er enkelt her.
Men selvfølgelig, hvis vi bare tager to filer og tilpasser den ene til den anden, så mister vi en af dem. Hvis vi gemmer ændringerne, genopfinder vi simpelthen , som eksisterer udmærket uden os, selvom det normalt ikke bruges til samme formål. Vi kan prøve at indlejre en mindre sekvens i en større, men alligevel risikerer vi at miste kritiske segmenter af data, hvis vi bruger det hensynsløst med alt.
Mellem hvad og hvad kan forskellen så elimineres? Nå, det vil sige, en ny fil skrevet af brugeren er bare en sekvens af bits, som vi ikke kan gøre noget med af sig selv. Så mangler du bare at finde sådanne bits på harddisken, at de kan ændres uden at skulle gemme forskellen, så du kan overleve deres tab uden alvorlige konsekvenser. Og det giver mening at ændre ikke kun filen på selve FS, men nogle mindre følsomme oplysninger inde i den. Men hvilken og hvordan?
Tilpasningsmetoder
Lossy komprimerede filer kommer til undsætning. Alle disse jpeg'er, mp3'er og andre, selvom komprimering med tab, indeholder en masse bits, der sikkert kan ændres. Det er muligt at bruge avancerede teknikker, der umærkeligt ændrer deres komponenter på forskellige stadier af kodningen. Vente. Avancerede teknikker... umærkelig modifikation... en smule ind i en anden... det er næsten ligesom !
Indlejring af en information i en anden minder faktisk om hendes metoder som intet andet. Jeg er også imponeret over umærkeligheden af de ændringer, der er foretaget i de menneskelige sanser. Hvor stierne skilles er i hemmelighed: Vores opgave kommer ned til, at brugeren indtaster yderligere oplysninger på sin harddisk; det vil kun skade ham. Han vil glemme igen.
Derfor, selvom vi kan bruge dem, er vi nødt til at foretage nogle ændringer. Og så vil jeg fortælle og vise dem ved at bruge eksemplet på en af de eksisterende metoder og et almindeligt filformat.
Om sjakaler
Hvis du virkelig klemmer det, er det den mest komprimerbare ting i verden. Vi taler selvfølgelig om JPEG-filer. Ikke kun er der tonsvis af værktøjer og eksisterende metoder til at indlejre data i det, men det er det mest populære grafikformat på denne planet.
Men for ikke at deltage i hundeavl skal du begrænse dit aktivitetsområde i filer af dette format. Ingen kan lide monokrome firkanter, der vises på grund af overdreven komprimering, så du skal begrænse dig til at arbejde med en allerede komprimeret fil, undgå omkodning. Mere specifikt med heltalskoefficienter, som forbliver efter operationer, der er ansvarlige for datatab - DCT og kvantisering, som er perfekt vist i kodningsskemaet (takket være wikien fra Bauman National Library):
Der er mange mulige metoder til at optimere jpeg-filer. Der er tabsfri optimering (jpegtran), der er optimering "“, som faktisk bidrager med noget andet, men vi er ligeglade med dem. Når alt kommer til alt, hvis brugeren er klar til at indlejre en information i en anden for at øge ledig diskplads, så har han enten optimeret sine billeder for længe siden eller slet ikke ønsker at gøre dette af frygt for tab af kvalitet.
F5
En hel familie af algoritmer passer til disse forhold, som du kan sætte dig ind i . Den mest avancerede af dem er algoritmen af Andreas Westfeld, der arbejder med koefficienterne for lysstyrkekomponenten, da det menneskelige øje er det mindst følsomme over for dets ændringer. Desuden bruger den en indlejringsteknik baseret på matrixkodning, som gør det muligt at foretage færre ændringer ved indlejring af den samme mængde information, jo større størrelsen af den anvendte container er.
Ændringerne i sig selv bunder i at reducere den absolutte værdi af koefficienterne med én under visse forhold (det vil sige ikke altid), hvilket giver dig mulighed for at bruge F5 til at optimere datalagring på din harddisk. Pointen er, at koefficienten efter en sådan ændring højst sandsynligt vil optage færre bits efter Huffman-kodning på grund af den statistiske fordeling af værdier i JPEG, og de nye nuller vil give en forstærkning, når de kodes ved hjælp af RLE.
De nødvendige ændringer går ud på at fjerne den del, der er ansvarlig for hemmeligholdelse (omarrangering af adgangskode), hvilket sparer ressourcer og eksekveringstid, og tilføjelse af en mekanisme til at arbejde med mange filer i stedet for én ad gangen. Det er usandsynligt, at læseren er interesseret i forandringsprocessen mere detaljeret, så lad os gå videre til en beskrivelse af implementeringen.
High tech
For at demonstrere, hvordan denne tilgang virker, implementerede jeg metoden i ren C og gennemførte en række optimeringer både med hensyn til eksekveringshastighed og hukommelse (du kan ikke forestille dig, hvor meget disse billeder vejer uden komprimering, selv før DCT). Cross-platform opnået ved hjælp af en kombination af biblioteker , и , hvilket vi takker dem for. Alt dette er sat sammen af 'make', så Windows-brugere ønsker at installere nogle Cygwin for sig selv til evaluering, eller håndtere Visual Studio og biblioteker på egen hånd.
Implementeringen er tilgængelig i form af et konsolværktøj og et bibliotek. Interesserede kan finde ud af mere om at bruge sidstnævnte i readme i repository på Github, linket, som jeg vil vedhæfte i slutningen af indlægget.
Hvordan man bruger?
Forsigtigt. Billederne, der bruges til pakning, vælges ved at søge med et regulært udtryk i den givne rodmappe. Efter færdiggørelsen kan filer flyttes, omdøbes og kopieres efter behag inden for dets grænser, ændre fil- og operativsystemer osv. Du bør dog være yderst forsigtig og ikke ændre det umiddelbare indhold på nogen måde. At miste værdien af blot en bit kan gøre det umuligt at gendanne information.
Efter færdiggørelsen efterlader værktøjet en særlig arkivfil, der indeholder alle nødvendige oplysninger til udpakning, herunder data om de anvendte billeder. I sig selv vejer den omkring et par kilobyte og har ikke nogen væsentlig indflydelse på den optagede diskplads.
Du kan analysere den mulige kapacitet ved at bruge flaget '-a': './f5ar -a [søgemappe] [Perl-kompatibelt regulært udtryk]'. Pakning udføres med kommandoen './f5ar -p [søgemappe] [Perl-kompatibelt regulært udtryk] [pakket fil] [arkivnavn]', og udpakning med './f5ar -u [arkivfil] [gendannet filnavn] ]'.
Demonstration af arbejde
For at vise effektiviteten af metoden uploadede jeg en samling af 225 helt gratis billeder af hunde fra tjenesten og fandt i dokumenterne en stor pdf på 45 meter af andet bind Knuta.
Rækkefølgen er ret enkel:
$ 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/Skærmbilleder til fans
Den udpakkede fil kan og bør stadig læses:
Som du kan se, fra de originale 633 + 36 == 669 megabyte data på harddisken, kom vi til mere behagelige 551. En sådan radikal forskel forklares af faldet i værdierne af koefficienterne, hvilket påvirker deres efterfølgende tabsfri komprimering: at reducere én efter én kan nemt “ afskære et par bytes fra den endelige fil. Dette er dog stadig et datatab, omend et ekstremt lille et, som du bliver nødt til at affinde dig med.
Heldigvis er de helt usynlige for øjet. Under spoileren (da habrastorage ikke kan håndtere store filer), kan læseren evaluere forskellen både efter øje og deres intensitet, opnået ved at trække værdierne af den ændrede komponent fra originalen: , , (jo mat farve, jo mindre forskel på blokken).
I stedet for en konklusion
I betragtning af alle disse vanskeligheder kan det virke som en meget enklere løsning på problemet at købe en harddisk eller uploade alt til skyen. Men selvom vi lever i sådan en vidunderlig tid nu, er der ingen garantier for, at det i morgen stadig vil være muligt at gå online og uploade alle dine ekstra data et sted. Eller gå til butikken og køb dig endnu en tusind terabyte harddisk. Men du kan altid bruge eksisterende huse.
->
Kilde: www.habr.com