Een andere gebruiker wil een nieuw stuk gegevens naar de harde schijf schrijven, maar heeft daarvoor niet voldoende vrije ruimte. Ik wil ook niets verwijderen, omdat “alles heel belangrijk en noodzakelijk is.” En wat moeten we ermee?
Niemand heeft dit probleem. Er staan terabytes aan informatie op onze harde schijven, en deze hoeveelheid neemt niet af. Maar hoe uniek is het? Uiteindelijk zijn alle bestanden slechts sets bits van een bepaalde lengte en hoogstwaarschijnlijk verschilt de nieuwe niet veel van degene die al is opgeslagen.
Het is duidelijk dat het zoeken naar stukjes informatie die al op een harde schijf zijn opgeslagen, zo niet een mislukking is, dan in ieder geval geen effectieve taak. Aan de andere kant, als het verschil klein is, kun je het een beetje aanpassen...
TL;DR - de tweede poging om te praten over een vreemde methode om gegevens te optimaliseren met behulp van JPEG-bestanden, nu in een begrijpelijker vorm.
Over bits en verschil
Als je twee volledig willekeurige stukjes data neemt, valt gemiddeld de helft van de bits die ze bevatten samen. Van de mogelijke lay-outs voor elk paar ('00, 01, 10, 11′) heeft precies de helft dezelfde waarden, alles is hier eenvoudig.
Maar als we slechts twee bestanden nemen en er één in de tweede passen, verliezen we er natuurlijk één. Als we de veranderingen opslaan, zullen we het gewoon opnieuw uitvinden , dat zonder ons prima bestaat, hoewel het meestal niet voor dezelfde doeleinden wordt gebruikt. We kunnen proberen een kleinere reeks in een grotere reeks in te bedden, maar toch lopen we het risico cruciale gegevenssegmenten kwijt te raken als we deze roekeloos bij alles gebruiken.
Tussen wat en wat kan het verschil dan worden geëlimineerd? Welnu, dat wil zeggen dat een nieuw bestand dat door de gebruiker is geschreven slechts een reeks bits is, waarmee we op zichzelf niets kunnen doen. Dan hoef je alleen maar zulke bits op de harde schijf te vinden dat ze kunnen worden gewijzigd zonder dat je het verschil hoeft op te slaan, zodat je het verlies ervan zonder ernstige gevolgen kunt overleven. En het is logisch om niet alleen het bestand op de FS zelf te wijzigen, maar ook wat minder gevoelige informatie daarin. Maar welke en hoe?
Montagemethoden
Gecomprimeerde bestanden met verlies komen te hulp. Al deze jpeg's, mp3's en andere bevatten, hoewel compressie met verlies, een aantal bits die veilig kunnen worden gewijzigd. Het is mogelijk om geavanceerde technieken te gebruiken die hun componenten onmerkbaar wijzigen in verschillende stadia van de codering. Wachten. Geavanceerde technieken... onmerkbare aanpassingen... het ene in het andere... het lijkt bijna !
Het inbedden van de ene informatie in de andere doet als geen ander denken aan haar methoden. Ik ben ook onder de indruk van de onmerkbaarheid van de veranderingen in de menselijke zintuigen. Waar de paden uiteenlopen, is het geheim: onze taak komt erop neer dat de gebruiker aanvullende informatie op zijn harde schijf invoert; het zal hem alleen maar schade berokkenen. Hij zal het weer vergeten.
Hoewel we ze kunnen gebruiken, moeten we daarom enkele wijzigingen aanbrengen. En dan zal ik ze vertellen en laten zien aan de hand van het voorbeeld van een van de bestaande methoden en een algemeen bestandsformaat.
Over jakhalzen
Als je er echt in knijpt, is het het meest samendrukbare ding ter wereld. We hebben het natuurlijk over JPEG-bestanden. Er zijn niet alleen talloze tools en bestaande methoden om gegevens erin in te sluiten, maar het is ook het populairste grafische formaat op deze planeet.
Om u echter niet bezig te houden met het fokken van honden, moet u uw werkterrein beperken in bestanden van dit formaat. Niemand houdt van monochrome vierkanten die verschijnen als gevolg van overmatige compressie, dus je moet jezelf beperken tot het werken met een reeds gecomprimeerd bestand. hercodering vermijden. Meer specifiek, met gehele coëfficiënten, die achterblijven na bewerkingen die verantwoordelijk zijn voor gegevensverlies - DCT en kwantisering, wat perfect wordt weergegeven in het coderingsschema (dankzij de wiki van de Bauman National Library):
Er zijn veel mogelijke methoden om jpeg-bestanden te optimaliseren. Er is verliesloze optimalisatie (jpegtran), er is optimalisatie "“, die eigenlijk iets anders bijdragen, maar ons daar niets van aantrekken. Als de gebruiker er immers klaar voor is om de ene informatie in de andere in te sluiten om de vrije schijfruimte te vergroten, dan heeft hij zijn afbeeldingen al lang geleden geoptimaliseerd, of wil hij dit helemaal niet doen uit angst voor kwaliteitsverlies.
F5
Een hele familie van algoritmen voldoet aan deze voorwaarden, waarmee u vertrouwd kunt raken . De meest geavanceerde daarvan is het algoritme door Andreas Westfeld, die werkt met de coëfficiënten van de helderheidscomponent, aangezien het menselijk oog het minst gevoelig is voor zijn veranderingen. Bovendien maakt het gebruik van een inbeddingstechniek gebaseerd op matrixcodering, waardoor het mogelijk is om minder wijzigingen aan te brengen bij het insluiten van dezelfde hoeveelheid informatie, naarmate de grootte van de gebruikte container groter is.
De veranderingen zelf komen neer op het verminderen van de absolute waarde van de coëfficiënten met één onder bepaalde omstandigheden (dat wil zeggen, niet altijd), waardoor u F5 kunt gebruiken om de gegevensopslag op uw harde schijf te optimaliseren. Het punt is dat de coëfficiënt na een dergelijke wijziging hoogstwaarschijnlijk minder bits zal innemen na Huffman-codering vanwege de statistische verdeling van waarden in JPEG, en dat de nieuwe nullen winst zullen opleveren bij het coderen ervan met behulp van RLE.
De noodzakelijke aanpassingen komen neer op het elimineren van het deel dat verantwoordelijk is voor geheimhouding (herschikking van wachtwoorden), wat middelen en uitvoeringstijd bespaart, en het toevoegen van een mechanisme om met veel bestanden te werken in plaats van met één tegelijk. Het is onwaarschijnlijk dat de lezer meer in detail geïnteresseerd is in het veranderingsproces, dus laten we verder gaan met een beschrijving van de implementatie.
Hoogwaardige technologie
Om te demonstreren hoe deze aanpak werkt, heb ik de methode in pure C geïmplementeerd en een aantal optimalisaties doorgevoerd, zowel qua uitvoeringssnelheid als qua geheugen (je kunt je niet voorstellen hoeveel deze afbeeldingen wegen zonder compressie, zelfs vóór DCT). Cross-platform bereikt met behulp van een combinatie van bibliotheken , и , waarvoor wij hen bedanken. Dit alles is samengesteld door 'make', dus Windows-gebruikers willen Cygwin voor zichzelf installeren ter evaluatie, of zelf met Visual Studio en bibliotheken aan de slag gaan.
De implementatie is beschikbaar in de vorm van een consolehulpprogramma en een bibliotheek. Geïnteresseerden kunnen meer te weten komen over het gebruik van dit laatste in het leesmij-bestand in de repository op Github, de link waaraan ik aan het einde van het bericht zal toevoegen.
Hoe te gebruiken?
Voorzichtig. De afbeeldingen die voor het verpakken worden gebruikt, worden geselecteerd door te zoeken met behulp van een reguliere expressie in de opgegeven hoofdmap. Na voltooiing kunnen bestanden naar believen binnen de grenzen ervan worden verplaatst, hernoemd en gekopieerd, bestanden en besturingssystemen worden gewijzigd, enz. U moet echter uiterst voorzichtig zijn en de directe inhoud op geen enkele manier wijzigen. Het verliezen van de waarde van zelfs maar één bit kan het onmogelijk maken om informatie te herstellen.
Na voltooiing laat het hulpprogramma een speciaal archiefbestand achter met alle informatie die nodig is voor het uitpakken, inclusief gegevens over de gebruikte afbeeldingen. Op zichzelf weegt het ongeveer een paar kilobytes en heeft het geen noemenswaardige invloed op de bezette schijfruimte.
U kunt de mogelijke capaciteit analyseren met behulp van de vlag '-a': './f5ar -a [zoekmap] [Perl-compatibele reguliere expressie]'. Inpakken gebeurt met het commando './f5ar -p [zoekmap] [Perl-compatibele reguliere expressie] [ingepakt bestand] [archiefnaam]', en uitpakken met './f5ar -u [archiefbestand] [herstelde bestandsnaam ]'.
Demonstratie van werk
Om de effectiviteit van de methode te laten zien, heb ik een verzameling van 225 absoluut gratis foto's van honden van de dienst geüpload en vond in de documenten een grote pdf van 45 meter van het tweede deel Knuta.
De volgorde is vrij eenvoudig:
$ 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/Screenshots voor fans
Het uitgepakte bestand kan en moet nog steeds worden gelezen:
Zoals je kunt zien, kwamen we van de oorspronkelijke 633 + 36 == 669 megabytes aan gegevens op de harde schijf tot aangenamere 551. Een dergelijk radicaal verschil wordt verklaard door de afname van de waarden van de coëfficiënten, wat hun effect beïnvloedt daaropvolgende verliesvrije compressie: door één met één te verkleinen, kunt u gemakkelijk “een paar bytes uit het uiteindelijke bestand afsnijden. Dit is echter nog steeds een gegevensverlies, zij het een uiterst klein verlies, dat u zult moeten verdragen.
Gelukkig zijn ze absoluut onzichtbaar voor het oog. Onder de spoiler (aangezien habrastorage geen grote bestanden kan verwerken), kan de lezer het verschil zowel op het oog als op hun intensiteit beoordelen, verkregen door de waarden van de gewijzigde component af te trekken van het origineel: , , (hoe doffer de kleur, hoe kleiner het verschil in het blok).
In plaats Output
Gezien al deze moeilijkheden lijkt het kopen van een harde schijf of het uploaden van alles naar de cloud misschien een veel eenvoudigere oplossing voor het probleem. Maar ook al leven we nu in zo’n prachtige tijd, er is geen garantie dat het morgen nog mogelijk is om online te gaan en al je extra gegevens ergens te uploaden. Of ga naar de winkel en koop nog een harde schijf van duizend terabyte. Maar je kunt altijd bestaande huizen gebruiken.
->
Bron: www.habr.com