En annan användare vill skriva en ny bit data till hårddisken, men han har inte tillräckligt med ledigt utrymme för att göra detta. Jag vill inte heller ta bort något, eftersom "allt är väldigt viktigt och nödvändigt." Och vad ska vi göra med det?
Ingen har det här problemet. Det finns terabyte med information på våra hårddiskar, och denna mängd tenderar inte att minska. Men hur unik är den? I slutändan är alla filer bara uppsättningar av bitar av en viss längd och troligen är den nya inte mycket annorlunda än den som redan är lagrad.
Det är uppenbart att sökning efter delar av information som redan finns lagrad på en hårddisk är, om inte ett misslyckande, så åtminstone inte en effektiv uppgift. Å andra sidan, om skillnaden är liten, så kan du justera den lite...
TL;DR - det andra försöket att prata om en konstig metod för att optimera data med JPEG-filer, nu i en mer förståelig form.
Om bitar och skillnader
Om du tar två helt slumpmässiga bitar av data, så sammanfaller i genomsnitt hälften av de bitar de innehåller. Faktiskt, bland de möjliga layouterna för varje par ('00, 01, 10, 11′), har exakt hälften samma värden, allt är enkelt här.
Men naturligtvis, om vi bara tar två filer och passar en till den andra, så kommer vi att förlora en av dem. Om vi sparar ändringarna kommer vi helt enkelt att återuppfinna , som existerar alldeles utmärkt utan oss, även om det vanligtvis inte används för samma ändamål. Vi kan försöka bädda in en mindre sekvens i en större, men trots det riskerar vi att förlora kritiska datasegment om vi använder den hänsynslöst med allt.
Mellan vad och vad kan då skillnaden elimineras? Tja, det vill säga, en ny fil skriven av användaren är bara en sekvens av bitar, som vi inte kan göra någonting med själv. Sedan behöver du bara hitta sådana bitar på hårddisken att de kan ändras utan att behöva lagra skillnaden, så att du kan överleva deras förlust utan allvarliga konsekvenser. Och det är vettigt att inte bara ändra filen på själva FS, utan lite mindre känslig information inuti den. Men vilken och hur?
Monteringsmetoder
Förlustiga komprimerade filer kommer till undsättning. Alla dessa jpeg-filer, mp3-filer och andra innehåller, även om komprimering med förlust, ett gäng bitar som säkert kan ändras. Det är möjligt att använda avancerade tekniker som omärkligt modifierar sina komponenter i olika stadier av kodningen. Vänta. Avancerade tekniker... omärklig modifiering... en bit in i en annan... det är nästan som !
Att bädda in en information i en annan påminner faktiskt om hennes metoder som inget annat. Jag är också imponerad av det omärkliga i de förändringar som gjorts i de mänskliga sinnena. Där vägarna skiljer sig är i hemlighet: vår uppgift handlar om att användaren anger ytterligare information på sin hårddisk, det kommer bara att skada honom. Han kommer att glömma igen.
Därför, även om vi kan använda dem, måste vi göra några ändringar. Och sedan kommer jag att berätta och visa dem med exemplet på en av de befintliga metoderna och ett vanligt filformat.
Om schakaler
Om du verkligen klämmer på det är det det mest komprimerbara i världen. Vi pratar naturligtvis om JPEG-filer. Det finns inte bara massor av verktyg och befintliga metoder för att bädda in data i det, utan det är det mest populära grafikformatet på denna planet.
Men för att inte delta i hunduppfödning måste du begränsa ditt verksamhetsområde i filer av detta format. Ingen gillar monokroma rutor som visas på grund av överdriven komprimering, så du måste begränsa dig till att arbeta med en redan komprimerad fil, undvika omkodning. Mer specifikt, med heltalskoefficienter, som kvarstår efter operationer som är ansvariga för dataförlust - DCT och kvantisering, som visas perfekt i kodningsschemat (tack vare wikin för Bauman National Library):
Det finns många möjliga metoder för att optimera jpeg-filer. Det finns förlustfri optimering (jpegtran), det finns optimering "", som faktiskt bidrar med något annat, men vi bryr oss inte om dem. När allt kommer omkring, om användaren är redo att bädda in en information i en annan för att öka ledigt diskutrymme, så har han antingen optimerat sina bilder för länge sedan, eller vill inte göra detta alls av rädsla för kvalitetsförlust.
F5
En hel familj av algoritmer passar dessa villkor, som du kan bekanta dig med . Den mest avancerade av dem är algoritmen av Andreas Westfeld, som arbetar med koefficienterna för ljusstyrkekomponenten, eftersom det mänskliga ögat är minst känsligt för dess förändringar. Dessutom använder den en inbäddningsteknik baserad på matriskodning, vilket gör det möjligt att göra färre ändringar när man bäddar in samma mängd information, ju större behållaren är.
Ändringarna i sig går ut på att reducera koefficienternas absoluta värde med en under vissa förhållanden (det vill säga inte alltid), vilket gör att du kan använda F5 för att optimera datalagringen på din hårddisk. Poängen är att koefficienten efter en sådan förändring sannolikt kommer att uppta färre bitar efter Huffman-kodning på grund av den statistiska fördelningen av värden i JPEG, och de nya nollorna kommer att ge en förstärkning när de kodas med RLE.
De nödvändiga ändringarna går ut på att eliminera den del som är ansvarig för sekretess (lösenordsomläggning), vilket sparar resurser och körtid, och att lägga till en mekanism för att arbeta med många filer istället för en åt gången. Det är osannolikt att läsaren är intresserad av förändringsprocessen mer i detalj, så låt oss gå vidare till en beskrivning av implementeringen.
Högteknologisk
För att demonstrera hur detta tillvägagångssätt fungerar implementerade jag metoden i ren C och genomförde ett antal 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 före DCT). Cross-platform uppnås med en kombination av bibliotek , и , vilket vi tackar dem för. Allt detta sammanställs av "make", så Windows-användare vill installera lite Cygwin för sig själva för utvärdering, eller hantera Visual Studio och bibliotek på egen hand.
Implementeringen är tillgänglig i form av ett konsolverktyg och bibliotek. Den som är intresserad kan ta reda på mer om att använda den senare i readme i arkivet på Github, länken som jag kommer att bifoga i slutet av inlägget.
Hur man använder
Försiktigt. Bilderna som används för paketering väljs genom att söka med ett reguljärt uttryck i den givna rotkatalogen. Efter färdigställandet kan filer flyttas, döpas om och kopieras efter behag inom dess gränser, ändra fil- och operativsystem etc. Du bör dock vara extremt försiktig och inte ändra det omedelbara innehållet på något sätt. Att förlora värdet på ens en bit kan göra det omöjligt att återställa information.
När det är färdigt lämnar verktyget en speciell arkivfil som innehåller all information som behövs för uppackning, inklusive data om bilderna som används. I sig själv väger den ungefär ett par kilobyte och har ingen betydande inverkan på det upptagna diskutrymmet.
Du kan analysera den möjliga kapaciteten genom att använda 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 med './f5ar -u [arkivfil] [återställt filnamn ]'.
Demonstration av arbete
För att visa metodens effektivitet laddade jag upp en samling av 225 helt gratis foton av hundar från tjänsten och hittade i dokumenten en stor pdf på 45 meter av den andra volymen Knuta.
Sekvensen är ganska 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ärmdumpar för fans
Den uppackade filen kan och bör fortfarande läsas:
Som du kan se, från de ursprungliga 633 + 36 == 669 megabyte data på hårddisken, kom vi till trevligare 551. En sådan radikal skillnad förklaras av minskningen av värdena på koefficienterna, vilket påverkar deras efterföljande förlustfri komprimering: att reducera en efter bara en kan enkelt " skära av ett par byte från den slutliga filen. Detta är dock fortfarande en dataförlust, om än en extremt liten sådan, som du kommer att behöva stå ut med.
Som tur är är de helt osynliga för ögat. Under spoilern (eftersom habrastorage inte kan hantera stora filer) kan läsaren utvärdera skillnaden både med ögat och deras intensitet, erhållen genom att subtrahera värdena för den ändrade komponenten från originalet: , , (ju mattare färg, desto mindre skillnad i blocket).
I stället för en slutsats
Med tanke på alla dessa svårigheter kan det verka som en mycket enklare lösning på problemet att köpa en hårddisk eller ladda upp allt till molnet. Men även om vi lever i en så underbar tid nu så finns det inga garantier för att det imorgon fortfarande kommer att vara möjligt att gå online och ladda upp all din extra data någonstans. Eller gå till butiken och köp dig ytterligare en tusen terabyte hårddisk. Men du kan alltid använda befintliga hus.
->
Källa: will.com