En anvÀndare vill spara nya data pÄ sin hÄrddisk, men det finns inte tillrÀckligt med ledigt utrymme för det. Att radera nÄgot kÀnns inte bra, eftersom "allting Àr vÀldigt viktigt och nödvÀndigt". Vad ska vi göra med detta?
Detta problem pÄverkar fler Àn bara honom. VÄra hÄrddiskar huserar terabyte av information, och denna mÀngd tycks inte minska. Men hur unik Àr den? I slutÀndan Àr ju alla filer bara bitar med en viss lÀngd, och den nya skiljer sig förmodligen inte mycket frÄn den som redan lagras.
Det Àr uppenbart att söka efter redan lagrad information pÄ hÄrddisken Àr en uppgift som, om den inte Àr dömd att misslyckas, i alla fall Àr minst sagt ineffektiv. à andra sidan, om skillnaden Àr liten, kan man kanske justera lite...
TL;DR â en andra försök att berĂ€tta om en mĂ€rklig metod för dataoptimering med hjĂ€lp av JPEG-filer, denna gĂ„ng i en mer begriplig form.
Om bitar och skillnader
Om vi tar tvĂ„ helt slumpmĂ€ssiga bitar av data, sĂ„ överensstĂ€mmer i genomsnitt hĂ€lften av de innehĂ„llna bitarna. Och det Ă€r sant, bland möjliga kombinationer för varje par (â00, 01, 10, 11âČ) har exakt hĂ€lften samma vĂ€rden, det Ă€r enkelt.
Men förstÄs, om vi bara tar tvÄ filer och justerar en till den andra, sÄ förlorar vi en av dem. Om vi istÀllet sparar Àndringarna, sÄ Äteruppuppfinner vi , som redan existerar utan vÄr hjÀlp, Àven om det vanligtvis inte anvÀnds pÄ samma sÀtt. Man kan försöka infoga en mindre sekvens i en större, men Àven dÄ riskerar vi att förlora kritiska datasegment vid omdömeslöst anvÀndande av allt och alla.
Mellan vilka element kan vi dĂ„ eliminera skillnad? SĂ„ledes, den nya fil som anvĂ€ndaren skriver â bara en sekvens av bitar, med vilken vi i sig sjĂ€lva inte kan göra nĂ„got. DĂ„ mĂ„ste vi helt enkelt hitta sĂ„dana bitar pĂ„ hĂ„rddisken att de kan Ă€ndras utan att behöva lagra skillnaden, sĂ„ att vi kan överleva deras förlust utan allvarliga konsekvenser. Dessutom finns det anledning att inte bara Ă€ndra sjĂ€lva filen pĂ„ FS, utan nĂ„gon mindre kĂ€nslig information inuti den. Men vilken och hur?
Justeringstekniker
HÀr kommer filer med förlustkomprimering till hjÀlp. Alla dessa jpeg, mp3 och andra Àr visserligen kompression med förlust, men innehÄller fortfarande mÀngder av bitar som kan modifieras pÄ ett sÀkert sÀtt. Man kan anvÀnda avancerade tekniker som omÀrkligt modifierar deras komponenter pÄ olika kodningsstÀllen. VÀnta. Avancerade tekniker⊠omÀrklig modifiering⊠vissa bitar till andra⊠det hÀr Àr nÀstan som !
Och verkligen, att inkorporera en information i en annan pĂ„minner verkligen om dess metoder. Det Ă€r ocksĂ„ imponerande hur omĂ€rkliga förĂ€ndringar Ă€r för det mĂ€nskliga sinnet. DĂ€r vĂ€garna skiljs â det Ă€r vad gĂ€ller sekretessen: vĂ„r uppgift handlar om att lĂ„ta anvĂ€ndaren lĂ€gga till ytterligare information pĂ„ sin hĂ„rddisk, vilket bara skadar honom. Han kommer att glömma det.
DÀrför, Àven om vi kan anvÀnda dem, behöver vi göra vissa modifieringar. Och senare kommer jag att berÀtta om och visa dem med ett exempel pÄ en av de befintliga metoderna och ett vanligt filformat.
Om schakal
Om man ska komprimera, sÄ bör man komprimera det mest komprimerade i vÀrlden. Det handlar sÄklart om JPEG-filer. Dessutom finns det en uppsjö av verktyg och befintliga metoder för att inkorporera data i dem, och de Àr det mest populÀra grafiska formatet pÄ denna planet.
Trots det, för att inte hĂ„lla pĂ„ med hunduppfödning, mĂ„ste man begrĂ€nsa sitt arbetsomrĂ„de till filer av detta format. Ingen gillar enfĂ€rgade fyrkanter som dyker upp pĂ„ grund av överdriven komprimering, sĂ„ man bör begrĂ€nsa sig till att arbeta med filen som redan Ă€r komprimerad, och undvika omkodning. NĂ€rmare bestĂ€mt â med heltalskoefficienter som förblir efter operationerna ansvariga för dataförlust â DCT och kvantisering, vilket tydligt visas i kodningsschemat (tack till Bauman National Library Wiki):
Det finns mĂ„nga möjliga metoder för att optimera jpeg-filer. Det finns förlustlös optimering (jpegtran), det finns optimering ââ, som faktiskt ger en hel del, men de angĂ„r oss inte. För om anvĂ€ndaren Ă€r villig att inkorporera en information i en annan för att öka det lediga utrymmet pĂ„ hĂ„rddisken, sĂ„ har han antingen redan optimerat sina bilder, eller sĂ„ vill han helt enkelt inte göra det av rĂ€dsla för kvalitetsförlust.
F5
Ett helt familj av algoritmer passar in i sÄdana villkor, som man kan bekanta sig med . Den mest avancerade av dem Àr algoritmen av Andreas Westfeldt, som arbetar med ljusstyrkekomponentens koefficienter, eftersom det mÀnskliga ögat Àr minst kÀnsligt för förÀndringar i den. Dessutom anvÀnder den en inbÀddningsteknik baserad pÄ matris-kodning, vilket gör att man kan göra fÀrre förÀndringar nÀr man bÀddar in samma mÀngd information ju större storlek den anvÀnda behÄllaren har.
SjÀlva förÀndringarna bestÄr i att minska det absoluta vÀrdet pÄ koefficienterna med ett enhet under vissa förhÄllanden (det vill sÀga, inte alltid), vilket möjliggör anvÀndning av F5 för att optimera datalagring pÄ hÄrddisken. Det beror pÄ att koefficienten efter en sÄdan förÀndring sannolikt kommer att ta upp fÀrre bitar efter att Huffman-kodning har genomförts pÄ grund av det statistiska vÀrdesfördelningen i JPEG, och de nya nollorna kommer att ge fördelar vid kodning med hjÀlp av RLE.
NödvÀndiga modifieringar handlar om att ta bort den del som ansvarar för sekretess (lösenordsswap), vilket sparar resurser och exekveringstid, och att lÀgga till en mekanism för att hantera flera filer istÀllet för en i taget. Processen av förÀndringen kommer nog inte att intressera lÀsaren sÄ mycket, dÀrför gÄr vi vidare till beskrivningen av implementationen.
Högteknologi
För att demonstrera arbetet med en sĂ„dan metod har jag implementerat den i ren C och genomfört en rad optimeringar bĂ„de vad gĂ€ller exekveringshastighet och minne (du kan inte förestĂ€lla dig hur mycket dessa bilder vĂ€ger utan komprimering, Ă€ven till DCT). Plattformoberoende har uppnĂ„tts genom att anvĂ€nda en kombination av bibliotek , och , för vilket jag vill tacka dem. Allt detta byggs med âmakeâ, sĂ„ Windows-anvĂ€ndare som vill göra en bedömning bör installera Cygwin, eller pĂ„ annat sĂ€tt ta itu med Visual Studio och biblioteken sjĂ€lva.
Implementation Àr tillgÀnglig i form av ett kommandoradsverktyg och ett bibliotek. Mer information om anvÀndningen av det sistnÀmnda kan den intresserade lÀsa i readme-filen i git-repot, vars lÀnk jag kommer att bifoga i slutet av inlÀgget.
Hur man anvÀnder?
Var försiktig. De bilder som anvÀnds för packning vÀljs genom att söka med reguljÀra uttryck i den angivna rotmappen. Efter avslutat arbete kan filer flyttas, byta namn och kopieras inom dess grÀnser, samt Àndra fil- och operativsystem etc. Dock Àr det viktigt att vara mycket försiktig och inte Àndra det faktiska innehÄllet. Förlust av vÀrde, Àven en enda bit, kan leda till att informationen inte gÄr att ÄterstÀlla.
Efter att programmet har körts skapar det en speciell arkivfil som innehÄller all nödvÀndig information för uppackning, inklusive data om de anvÀnda bilderna. SjÀlv vÀger den runt ett par kilobyte och har ingen betydande pÄverkan pÄ det upptagna diskutrymmet.
Möjlig kapacitet kan analyseras med flaggan â-aâ: â. /f5ar -a [sökmapp] [Perl-kompatibelt reguljĂ€rt uttryck]â. Packning görs med kommandot â. /f5ar -p [sökmapp] [Perl-kompatibelt reguljĂ€rt uttryck] [packad fil] [arkivnamn]â, och uppackning sker med â. /f5ar -u [arkivfil] [Ă„terstĂ€llt filnamn]â.
Demonstration av arbetet
För att visa metodens effektivitet har jag laddat upp en samling av 225 helt gratis hundbilder frÄn tjÀnsten och hittade en stor pdf pÄ 45 meter av den andra volymen i dokumenten Knuth.
Sekvensen Àr ganska enkel:
$ du -sh knuth.pdf dogs/
44M knuth.pdf
633M dogs/
$ ./f5ar -p dogs/ .*jpg knuth.pdf dogs.f5ar
LĂ€ser komprimeringsfil... ok
Initierar arkivet... ok
Analyserar bibliotekskapacitet... klart pÄ 17,0 sekunder
UpptÀckte nÄgot garanterad kapacitet pÄ 48439359 byte
UpptÀckte möjlig kapacitet upp till 102618787 byte
Komprimerar... klart pÄ 39,4 sekunder
Sparar arkivet... ok
$ ./f5ar -u dogs/dogs.f5ar knuth_unpacked.pdf
Initierar arkivet... ok
LĂ€ser arkivfilen... ok
Fyller arkivet med filer... klart pÄ 1,4 sekunder
Dekomprimerar... klart pÄ 21,0 sekunder
Skriver den extraherade datan... ok
$ sha1sum knuth.pdf knuth_unpacked.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth_unpacked.pdf
$ du -sh dogs/
551M dogs/SkÀrmdumpar för entusiaster
Den uppackade filen gÄr fortfarande att lÀsa:
Som syns har vi frĂ„n de ursprungliga 633 + 36 == 669 megabyte data pĂ„ hĂ„rddisken kommit ner till mer behagliga 551. Denna radikala skillnad förklaras av den minskning av vĂ€rdena i koefficienterna som pĂ„verkar deras efterföljande förlustfria komprimering: en minskning med bara ett enhet kan utan problem âskĂ€raâ nĂ„gra byte frĂ„n den slutgiltiga filen. ĂndĂ„ innebĂ€r detta dataförlust, Ă€ven om den Ă€r mycket liten, som vi mĂ„ste acceptera.
Lyckligtvis Àr de helt osynliga för ögat. Under spoilern (eftersom habrastorage inte klarar av stora filer) kan lÀsaren uppskatta skillnaden bÄde visuellt och deras intensitet, erhÄllen genom att subtrahera vÀrdena för den Àndrade komponenten frÄn den ursprungliga: , , (ju svagare fÀrg, desto mindre skillnad i blocket).
Avslutande
Med tanke pÄ alla dessa komplikationer kan det verka mycket enklare att köpa en hÄrddisk eller ladda upp allt till molnet. Men Àven om vi nu lever i en fantastisk tid finns det inga garantier för att vi imorgon fortfarande kan gÄ online och ladda upp alla vÄra överflödiga data. Eller att vi kan gÄ till affÀren och köpa en ny hÄrddisk pÄ en terabyte. Men man kan alltid anvÀnda det som redan ligger hemma.
->
KĂ€lla: habr.com
