Ein anderer Benutzer möchte neue Daten auf die Festplatte schreiben, hat aber nicht genĂŒgend freien Speicherplatz dafĂŒr. Ich möchte auch nichts löschen, denn âalles ist sehr wichtig und notwendig.â Und was sollen wir damit machen?
Niemand hat dieses Problem. Auf unseren Festplatten befinden sich Terabytes an Informationen, und diese Menge nimmt tendenziell nicht ab. Aber wie einzigartig ist es? Letztendlich sind alle Dateien nur SÀtze von Bits einer bestimmten LÀnge, und höchstwahrscheinlich unterscheidet sich die neue Datei nicht wesentlich von der bereits gespeicherten.
Es ist klar, dass die Suche nach Informationen, die bereits auf einer Festplatte gespeichert sind, wenn nicht fehlschlÀgt, so doch zumindest keine effektive Aufgabe ist. Wenn der Unterschied hingegen gering ist, können Sie ihn ein wenig anpassen ...
TL;DR â der zweite Versuch, ĂŒber eine seltsame Methode zur Datenoptimierung mithilfe von JPEG-Dateien zu sprechen, jetzt in einer verstĂ€ndlicheren Form.
Ăber Bits und Unterschiede
Nimmt man zwei völlig zufĂ€llige Daten, dann stimmen im Durchschnitt die HĂ€lfte der darin enthaltenen Bits ĂŒberein. TatsĂ€chlich hat von den möglichen Layouts fĂŒr jedes Paar ('00, 01, 10, 11âČ) genau die HĂ€lfte die gleichen Werte, hier ist alles einfach.
Aber wenn wir einfach zwei Dateien nehmen und eine an die zweite anpassen, verlieren wir natĂŒrlich eine davon. Wenn wir die Ănderungen speichern, werden wir einfach neu erfinden , das auch ohne uns vollkommen existiert, obwohl es normalerweise nicht fĂŒr die gleichen Zwecke verwendet wird. Wir können versuchen, eine kleinere Sequenz in eine gröĂere einzubetten, aber trotzdem riskieren wir den Verlust kritischer Datensegmente, wenn wir sie rĂŒcksichtslos mit allem verwenden.
Zwischen was und was kann dann der Unterschied beseitigt werden? Nun, das heiĂt, eine vom Benutzer geschriebene neue Datei ist nur eine Folge von Bits, mit der wir alleine nichts anfangen können. Dann mĂŒssen Sie nur noch solche Bits auf der Festplatte finden, dass sie geĂ€ndert werden können, ohne dass die Differenz gespeichert werden muss, sodass Sie deren Verlust ohne schwerwiegende Folgen ĂŒberstehen können. Und es ist sinnvoll, nicht nur die Datei auf dem FS selbst zu Ă€ndern, sondern auch einige weniger sensible Informationen darin. Aber welches und wie?
Anpassungsmethoden
Verlustbehaftete komprimierte Dateien helfen hier. Alle diese JPEGs, MP3s und andere Dateien enthalten trotz verlustbehafteter Komprimierung eine Reihe von Bits, die sicher geĂ€ndert werden können. Es ist möglich, fortschrittliche Techniken zu verwenden, die ihre Komponenten in verschiedenen Phasen der Kodierung unmerklich verĂ€ndern. Warten. Fortgeschrittene Techniken... unmerkliche Modifikation... ein StĂŒck ins andere... es ist fast so !
TatsÀchlich erinnert die Einbettung einer Information in eine andere wie nichts anderes an ihre Methoden. Mich beeindruckt auch die Unmerklichkeit der VerÀnderungen der menschlichen Sinne. Wo die Wege auseinandergehen, liegt in der Geheimhaltung: Unsere Aufgabe besteht darin, dass der Benutzer zusÀtzliche Informationen auf seine Festplatte eingibt; das wird ihm nur schaden. Er wird es wieder vergessen.
Obwohl wir sie verwenden können, mĂŒssen wir daher einige Ănderungen vornehmen. Und dann werde ich sie am Beispiel einer der vorhandenen Methoden und eines gĂ€ngigen Dateiformats erzĂ€hlen und zeigen.
Ăber Schakale
Wenn man es wirklich zusammendrĂŒckt, ist es das komprimierbarste Ding der Welt. Die Rede ist natĂŒrlich von JPEG-Dateien. Es gibt nicht nur unzĂ€hlige Tools und bestehende Methoden zum Einbetten von Daten, es ist auch das beliebteste Grafikformat auf diesem Planeten.
Um jedoch keine Hundezucht zu betreiben, mĂŒssen Sie Ihren TĂ€tigkeitsbereich auf Dateien dieses Formats beschrĂ€nken. Niemand mag monochrome Quadrate, die durch ĂŒbermĂ€Ăige Komprimierung entstehen. Daher mĂŒssen Sie sich darauf beschrĂ€nken, mit einer bereits komprimierten Datei zu arbeiten. Neukodierung vermeiden. Genauer gesagt mit ganzzahligen Koeffizienten, die nach Operationen verbleiben, die fĂŒr Datenverlust verantwortlich sind â DCT und Quantisierung, was im Kodierungsschema perfekt dargestellt wird (danke an das Wiki der Bauman National Library):
Es gibt viele mögliche Methoden zur Optimierung von JPEG-Dateien. Es gibt verlustfreie Optimierung (jpegtran), es gibt Optimierung "â, die eigentlich etwas anderes beitragen, uns aber egal sind. Denn wenn der Nutzer bereit ist, eine Information in eine andere einzubetten, um den freien Speicherplatz zu vergröĂern, dann hat er seine Bilder entweder schon vor langer Zeit optimiert oder möchte dies aus Angst vor QualitĂ€tsverlusten gar nicht mehr tun.
F5
FĂŒr diese Bedingungen gibt es eine ganze Familie von Algorithmen, mit denen Sie sich vertraut machen können . Der fortschrittlichste davon ist der Algorithmus von Andreas Westfeld, der mit den Koeffizienten der Helligkeitskomponente arbeitet, da das menschliche Auge am wenigsten empfindlich auf deren VerĂ€nderungen reagiert. DarĂŒber hinaus nutzt es eine auf Matrixkodierung basierende Einbettungstechnik, die es ermöglicht, bei der Einbettung der gleichen Informationsmenge weniger Ănderungen vorzunehmen, je gröĂer der verwendete Container ist.
Die Ănderungen selbst laufen darauf hinaus, den Absolutwert der Koeffizienten unter bestimmten Bedingungen (d. h. nicht immer) um eins zu reduzieren, wodurch Sie mit F5 die Datenspeicherung auf Ihrer Festplatte optimieren können. Der Punkt ist, dass der Koeffizient nach einer solchen Ănderung aufgrund der statistischen Werteverteilung in JPEG nach der Huffman-Kodierung höchstwahrscheinlich weniger Bits belegen wird und die neuen Nullen bei der Kodierung mit RLE einen Gewinn bringen.
Die notwendigen Ănderungen laufen darauf hinaus, den Teil zu eliminieren, der fĂŒr die Geheimhaltung verantwortlich ist (Neuordnung des Passworts), was Ressourcen und AusfĂŒhrungszeit spart, und einen Mechanismus hinzuzufĂŒgen, der es ermöglicht, mit vielen Dateien statt nur einer nach der anderen zu arbeiten. Der Ănderungsprozess im Detail wird den Leser wahrscheinlich nicht interessieren, daher kommen wir zur Beschreibung der Umsetzung.
Spitzentechnologie
Um zu demonstrieren, wie dieser Ansatz funktioniert, habe ich die Methode in reinem C implementiert und eine Reihe von Optimierungen sowohl hinsichtlich der AusfĂŒhrungsgeschwindigkeit als auch des Speichers durchgefĂŒhrt (Sie können sich nicht vorstellen, wie viel diese Bilder ohne Komprimierung, noch vor DCT, wiegen). PlattformĂŒbergreifend durch eine Kombination von Bibliotheken erreicht , Đž , wofĂŒr wir ihnen danken. Das Ganze wird mit âmakeâ kompiliert, sodass Benutzer Windows Zur Evaluierung möchten sie entweder Cygwin installieren oder sich selbststĂ€ndig mit Visual Studio und den zugehörigen Bibliotheken vertraut machen.
Die Implementierung ist in Form eines Konsolendienstprogramms und einer Bibliothek verfĂŒgbar. Mehr zur Nutzung von Letzterem erfahren Interessierte in der Readme-Datei im Repository auf Github, deren Link ich am Ende des Beitrags anfĂŒge.
Wie man verwendet?
SorgfĂ€ltig. Die zum Verpacken verwendeten Bilder werden durch Suche mithilfe eines regulĂ€ren Ausdrucks im angegebenen Stammverzeichnis ausgewĂ€hlt. Nach Abschluss können Dateien innerhalb ihrer Grenzen beliebig verschoben, umbenannt und kopiert, Dateien und Betriebssysteme geĂ€ndert werden usw. Sie sollten jedoch Ă€uĂerst vorsichtig sein und den unmittelbaren Inhalt in keiner Weise verĂ€ndern. Der Verlust auch nur eines Bits kann die Wiederherstellung von Informationen unmöglich machen.
Nach Abschluss hinterlĂ€sst das Dienstprogramm eine spezielle Archivdatei, die alle zum Entpacken erforderlichen Informationen enthĂ€lt, einschlieĂlich Daten zu den verwendeten Bildern. Es wiegt allein etwa ein paar Kilobyte und hat keinen wesentlichen Einfluss auf den belegten Speicherplatz.
Sie können die mögliche KapazitĂ€t mithilfe des Flags â-aâ analysieren: â./f5ar -a [Suchordner] [Perl-kompatibler regulĂ€rer Ausdruck]â. Das Packen erfolgt mit dem Befehl â./f5ar -p [Ordner durchsuchen] [Perl-kompatibler regulĂ€rer Ausdruck] [gepackte Datei] [Archivname]â, das Entpacken mit â./f5ar -u [Archivdatei] [Name der wiederhergestellten Dateiâ. ]' .
Demonstration der Arbeit
Um die Wirksamkeit der Methode zu zeigen, habe ich eine Sammlung von 225 absolut kostenlosen Fotos von Hunden aus dem Dienst hochgeladen und fand in den Dokumenten ein groĂes PDF von 45 Metern des zweiten Bandes Knuta.
Der Ablauf ist ganz einfach:
$ 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 fĂŒr Fans
Die entpackte Datei kann und soll weiterhin gelesen werden:
Wie Sie sehen, sind wir von den ursprĂŒnglichen 633 + 36 == 669 Megabyte Daten auf der Festplatte zu angenehmeren 551 gekommen. Ein so radikaler Unterschied erklĂ€rt sich aus der Abnahme der Koeffizientenwerte, die sich auf sie auswirkt AnschlieĂende verlustfreie Komprimierung: Durch die schrittweise Reduzierung können leicht âein paar Bytes aus der endgĂŒltigen Datei abgeschnitten werdenâ. Allerdings handelt es sich dennoch um einen, wenn auch Ă€uĂerst geringen, Datenverlust, den Sie in Kauf nehmen mĂŒssen.
Zum GlĂŒck sind sie fĂŒr das Auge absolut unsichtbar. Unter dem Spoiler (da Habrastorage keine groĂen Dateien verarbeiten kann) kann der Leser den Unterschied sowohl anhand des Auges als auch anhand seiner IntensitĂ€t beurteilen, die durch Subtrahieren der Werte der geĂ€nderten Komponente vom Original erhalten wird: , , (Je stumpfer die Farbe, desto geringer ist der Unterschied im Block).
Statt einer Schlussfolgerung
Angesichts all dieser Schwierigkeiten scheint der Kauf einer Festplatte oder das Hochladen alles in die Cloud eine viel einfachere Lösung des Problems zu sein. Aber auch wenn wir jetzt in einer so wunderbaren Zeit leben, gibt es keine Garantie dafĂŒr, dass es morgen noch möglich sein wird, online zu gehen und alle Ihre zusĂ€tzlichen Daten irgendwo hochzuladen. Oder gehen Sie in den Laden und kaufen Sie sich eine weitere Festplatte mit tausend Terabyte. Sie können aber jederzeit bestehende HĂ€user nutzen.
->
Source: habr.com
