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. All dies wird von „make“ zusammengestellt, sodass Windows-Benutzer Cygwin zur Evaluierung selbst installieren oder sich selbst mit Visual Studio und Bibliotheken befassen möchten.
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