En annen bruker ønsker å skrive et nytt stykke data til harddisken, men han har ikke nok ledig plass til å gjøre dette. Jeg vil heller ikke slette noe, siden "alt er veldig viktig og nødvendig." Og hva skal vi gjøre med det?
Ingen har dette problemet. Det er terabyte med informasjon på harddiskene våre, og denne mengden har ikke en tendens til å synke. Men hvor unikt er det? Til slutt er alle filer bare sett med biter av en viss lengde, og mest sannsynlig er den nye ikke mye forskjellig fra den som allerede er lagret.
Det er klart at det å søke etter deler av informasjon som allerede er lagret på en harddisk er, om ikke en feil, så i det minste ikke en effektiv oppgave. På den annen side, hvis forskjellen er liten, så kan du justere den litt...
TL;DR - det andre forsøket på å snakke om en merkelig metode for å optimalisere data ved å bruke JPEG-filer, nå i en mer forståelig form.
Om biter og forskjeller
Hvis du tar to helt tilfeldige biter med data, så faller i gjennomsnitt halvparten av bitene de inneholder sammen. Faktisk, blant de mulige oppsettene for hvert par ('00, 01, 10, 11′), har nøyaktig halvparten de samme verdiene, alt er enkelt her.
Men selvfølgelig, hvis vi bare tar to filer og tilpasser en til den andre, vil vi miste en av dem. Hvis vi lagrer endringene, vil vi ganske enkelt finne opp på nytt , som eksisterer utmerket uten oss, selv om den vanligvis ikke brukes til samme formål. Vi kan prøve å bygge inn en mindre sekvens i en større, men likevel risikerer vi å miste kritiske segmenter av data hvis vi bruker den hensynsløst med alt.
Mellom hva og hva kan da forskjellen elimineres? Vel, det vil si, en ny fil skrevet av brukeren er bare en sekvens av biter, som vi ikke kan gjøre noe med av seg selv. Da trenger du bare å finne slike biter på harddisken at de kan endres uten å måtte lagre differansen, slik at du kan overleve tapet deres uten alvorlige konsekvenser. Og det er fornuftig å endre ikke bare filen på selve FS, men litt mindre sensitiv informasjon i den. Men hvilken og hvordan?
Tilpasningsmetoder
Lossy komprimerte filer kommer til unnsetning. Alle disse jpeg-filene, mp3-ene og andre, selv om komprimering med tap, inneholder en haug med biter som trygt kan endres. Det er mulig å bruke avanserte teknikker som umerkelig modifiserer komponentene deres på forskjellige stadier av kodingen. Vente. Avanserte teknikker... umerkelig modifikasjon... en bit inn i en annen... det er nesten som !
Å bygge inn en informasjon i en annen minner faktisk om metodene hennes som ingenting annet. Jeg er også imponert over hvor umerkelig endringene som er gjort i de menneskelige sansene. Der veiene skiller seg er i hemmelighet: Vår oppgave kommer ned til at brukeren legger inn tilleggsinformasjon på harddisken sin; det vil bare skade ham. Han vil glemme igjen.
Derfor, selv om vi kan bruke dem, må vi gjøre noen modifikasjoner. Og så vil jeg fortelle og vise dem ved å bruke eksemplet på en av de eksisterende metodene og et vanlig filformat.
Om sjakaler
Hvis du virkelig klemmer det, er det den mest komprimerbare tingen i verden. Vi snakker selvfølgelig om JPEG-filer. Ikke bare er det tonnevis av verktøy og eksisterende metoder for å legge inn data i det, men det er det mest populære grafikkformatet på denne planeten.
For ikke å delta i hundeavl, må du imidlertid begrense aktivitetsfeltet ditt i filer med dette formatet. Ingen liker monokrome firkanter som vises på grunn av overdreven komprimering, så du må begrense deg til å jobbe med en allerede komprimert fil, unngå omkoding. Mer spesifikt, med heltallskoeffisienter, som forblir etter operasjoner som er ansvarlige for datatap - DCT og kvantisering, som vises perfekt i kodingsskjemaet (takket være wikien til Bauman National Library):
Det er mange mulige metoder for å optimalisere jpeg-filer. Det er tapsfri optimalisering (jpegtran), det er optimalisering "", som faktisk bidrar med noe annet, men vi bryr oss ikke om dem. Tross alt, hvis brukeren er klar til å legge inn en informasjon i en annen for å øke ledig diskplass, så har han enten optimalisert bildene sine for lenge siden, eller vil ikke gjøre dette i det hele tatt av frykt for tap av kvalitet.
F5
En hel familie av algoritmer passer til disse forholdene, som du kan gjøre deg kjent med . Den mest avanserte av dem er algoritmen av Andreas Westfeld, som arbeider med koeffisientene til lysstyrkekomponenten, siden det menneskelige øyet er minst følsomt for endringer. I tillegg bruker den en innbyggingsteknikk basert på matrisekoding, som gjør det mulig å gjøre færre endringer når du legger inn samme mengde informasjon, jo større størrelsen på beholderen er.
Selve endringene koker ned til å redusere den absolutte verdien av koeffisientene med én under visse forhold (det vil si ikke alltid), noe som lar deg bruke F5 for å optimalisere datalagring på harddisken. Poenget er at koeffisienten etter en slik endring mest sannsynlig vil oppta færre biter etter Huffman-koding på grunn av den statistiske fordelingen av verdier i JPEG, og de nye nullene vil gi en gevinst ved koding av dem ved hjelp av RLE.
De nødvendige modifikasjonene koker ned til å eliminere delen som er ansvarlig for hemmelighold (passordomorganisering), som sparer ressurser og utførelsestid, og legge til en mekanisme for å jobbe med mange filer i stedet for én om gangen. Leseren er neppe interessert i endringsprosessen mer detaljert, så la oss gå videre til en beskrivelse av implementeringen.
High tech
For å demonstrere hvordan denne tilnærmingen fungerer, implementerte jeg metoden i ren C og utførte en rekke optimaliseringer både når det gjelder utførelseshastighet og minne (du kan ikke forestille deg hvor mye disse bildene veier uten komprimering, selv før DCT). Kryssplattform oppnådd ved å bruke en kombinasjon av biblioteker , и , som vi takker dem for. Alt dette er satt sammen av 'make', så Windows-brukere ønsker å installere noen Cygwin for seg selv for evaluering, eller håndtere Visual Studio og biblioteker på egenhånd.
Implementeringen er tilgjengelig i form av et konsollverktøy og bibliotek. De som er interessert kan finne ut mer om bruk av sistnevnte i readme i repository på Github, lenken som jeg legger ved på slutten av innlegget.
Hvordan bruker du?
Forsiktig. Bildene som brukes til pakking velges ved å søke med et regulært uttrykk i den gitte rotkatalogen. Etter ferdigstillelse kan filer flyttes, gis nytt navn og kopieres etter eget ønske innenfor sine grenser, endre fil- og operativsystemer osv. Du bør imidlertid være ekstremt forsiktig og ikke endre det umiddelbare innholdet på noen måte. Å miste verdien av enda en bit kan gjøre det umulig å gjenopprette informasjon.
Ved ferdigstillelse etterlater verktøyet en spesiell arkivfil som inneholder all informasjon som er nødvendig for utpakking, inkludert data om bildene som brukes. I seg selv veier den omtrent et par kilobyte og har ingen betydelig innvirkning på den okkuperte diskplassen.
Du kan analysere den mulige kapasiteten ved å bruke '-a'-flagget: './f5ar -a [søkemappe] [Perl-kompatibelt regulært uttrykk]'. Pakking gjøres med kommandoen './f5ar -p [søk mappe] [Perl-kompatibelt regulært uttrykk] [pakket fil] [arkivnavn]', og utpakking med './f5ar -u [arkivfil] [gjenopprettet filnavn] ]'.
Demonstrasjon av arbeid
For å vise effektiviteten til metoden lastet jeg opp en samling av 225 helt gratis bilder av hunder fra tjenesten og fant i dokumentene en stor pdf på 45 meter av det andre bindet Knuta.
Rekkefølgen er ganske 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/Skjermbilder for fans
Den utpakkede filen kan og bør fortsatt leses:
Som du kan se, fra de originale 633 + 36 == 669 megabyte med data på harddisken, kom vi til en mer behagelig 551. En slik radikal forskjell forklares av reduksjonen i verdiene til koeffisientene, som påvirker deres påfølgende tapsfrie komprimering: å redusere én etter én kan enkelt " kutte av et par byte fra den endelige filen. Dette er imidlertid fortsatt et datatap, om enn ekstremt lite, som du må tåle.
Heldigvis er de helt usynlige for øyet. Under spoileren (siden habrastorage ikke kan håndtere store filer), kan leseren evaluere forskjellen både etter øye og deres intensitet, oppnådd ved å trekke verdiene til den endrede komponenten fra originalen: , , (jo mattere farge, jo mindre forskjell i blokken).
I stedet for en konklusjon
Med tanke på alle disse vanskelighetene, kan det å kjøpe en harddisk eller laste opp alt til skyen virke som en mye enklere løsning på problemet. Men selv om vi lever i en så fantastisk tid nå, er det ingen garantier for at det i morgen fortsatt vil være mulig å gå på nett og laste opp all ekstra data et sted. Eller gå til butikken og kjøp deg ytterligere en tusen terabyte harddisk. Men du kan alltid bruke eksisterende hus.
->
Kilde: www.habr.com