Ein weiterer Benutzer möchte neue Daten auf der Festplatte speichern, hat jedoch nicht genügend freien Speicherplatz dafür. Er möchte auch nichts löschen, da 'alles sehr wichtig und notwendig' ist. Was können wir also tun?
Ein solches Problem hat nicht nur er. Auf unseren Festplatten lagern Terabytes an Informationen, und diese Menge nimmt nicht ab. Aber wie einzigartig sind diese Informationen? Schließlich sind alle Dateien nur Bitmuster einer bestimmten Länge, und wahrscheinlich unterscheiden sich neue Dateien nicht wesentlich von denen, die bereits gespeichert sind.
Es ist klar, dass das Suchen nach bereits gespeicherten Informationen auf der Festplatte, wenn nicht misslungen, so doch zumindest ineffektiv ist. Andererseits, wenn der Unterschied gering ist, könnte man sie ein wenig anpassen...
TL;DR – ein zweiter Versuch, über eine seltsame Methode der Datenoptimierung mit JPEG-Dateien zu berichten, diesmal in verständlicherer Form.
Über Bits und Unterschiede
Wenn man zwei vollkommen zufällige Datenstücke betrachtet, stimmen im Durchschnitt die Hälfte der enthaltenen Bits überein. Das ist richtig, denn unter den möglichen Kombinationen für jedes Paar ('00, 01, 10, 11') haben genau die Hälfte übereinstimmende Werte, das ist ganz einfach.
Natürlich, wenn wir einfach zwei Dateien nehmen und eine an die andere anpassen, verlieren wir eine von ihnen. Wenn wir jedoch die Änderungen speichern, erfinden wir das Rad einfach neu. , die auch ohne unser Zutun hervorragend funktioniert, auch wenn sie normalerweise nicht zu solchen Zwecken verwendet wird. Man könnte versuchen, eine kleinere Sequenz in eine größere einzufügen, aber selbst dann riskieren wir den Verlust kritischer Datensegmente bei unüberlegtem Einsatz in allen möglichen Kontexten.
Wie lassen sich die Unterschiede dann beseitigen? Das heißt, die vom Benutzer erstellte Datei ist einfach eine Folge von Bits, mit denen wir für sich genommen nichts anfangen können. Daher müssen wir auf der Festplatte nach Bits suchen, die so verändert werden können, dass wir die Differenz nicht speichern müssen und den Verlust ohne schwerwiegende Folgen überstehen können. Zudem macht es Sinn, nicht nur die Datei im Dateisystem zu ändern, sondern auch weniger sensible Informationen innerhalb dieser. Aber welche und wie?
Anpassungsmethoden
Hier kommen verlustbehaftete komprimierte Dateien ins Spiel. All diese JPEG-, MP3- und anderen Formate sind zwar verlustbehaftet komprimiert, enthalten jedoch eine Menge Bits, die sicher verändert werden können. Es können fortgeschrittene Techniken verwendet werden, die ihre Komponenten an verschiedenen Codierungsstellen unauffällig modifizieren. Moment mal. Fortgeschrittene Techniken… unauffällige Modifikation… einige Bits in andere… das ist ja fast schon !
Es ist in der Tat so, dass das Einfügen einer Information in eine andere nichts anderes ist als die Methoden, die dabei verwendet werden. Auch die Unsichtbarkeit der vorgenommenen Veränderungen für die menschlichen Sinne ist beeindruckend. Wo die Wege auseinandergehen, ist die Geheimhaltung: unsere Aufgabe besteht darin, zusätzliche Informationen auf die Festplatte des Nutzers zu übertragen, was ihm nur schadet. Er wird es sogar vergessen.
Daher, auch wenn wir sie verwenden können, müssen einige Änderungen vorgenommen werden. Ich werde dies weiter erläutern und anhand eines der bestehenden Methoden und eines verbreiteten Dateiformats zeigen.
Über Schakale
Wenn man schon komprimieren möchte, dann das komprimierbarste der Welt. Die Rede ist natürlich von JPEG-Dateien. Es gibt nicht nur eine Menge Werkzeuge und bestehender Methoden zum Einfügen von Daten darin, sondern es ist auch das beliebteste Grafikformat auf diesem Planeten.
Dennoch, um nicht das ganze Feld zu besetzen, muss man seinen Arbeitsbereich auf Dateien dieses Formats einschränken. Niemand mag die einfarbigen Kästchen, die durch übermäßige Kompression entstehen, daher sollte man sich darauf beschränken, mit bereits komprimierten Dateien zu arbeiten, und eine Neukodierung vermeiden. Genauer gesagt — mit Ganzzahlkoeffizienten, die nach Operationen, die für Datenverluste verantwortlich sind — DKP und Quantisierung, erhalten bleiben, wie es in der Codierungsschema schön dargestellt ist (Danke an die Wikipedia der Nationalbibliothek Bauman):
Es gibt viele mögliche Methoden zur Optimierung von JPEG-Dateien. Es gibt verlustfreie Optimierung (jpegtran) und es gibt die Optimierung „“, die tatsächlich noch einige Änderungen vornimmt, aber das beschäftigt uns nicht. Denn wenn der Benutzer bereit ist, Informationen in andere einzubetten, um den freien Speicherplatz auf der Festplatte zu erhöhen, dann hat er seine Bilder entweder schon optimiert oder möchte das überhaupt nicht tun, aus Angst vor Qualitätsverlust.
F5
Unter solchen Bedingungen passt eine ganze Familie von Algorithmen, mit denen man sich vertraut machen kann . Der fortschrittlichste von ihnen ist der Algorithmus verfasst von Andreas Westfeld, der mit Helligkeitskoeffizienten arbeitet, da das menschliche Auge am wenigsten empfindlich auf deren Veränderungen reagiert. Darüber hinaus nutzt er eine Einbettungsmethode, die auf der Kodierung einer Matrix basiert. Dadurch können bei der Einbettung derselben Informationsmenge umso weniger Veränderungen vorgenommen werden, je größer der verwendete Container ist.
Die Änderungen führen dazu, dass der absolute Wert der Koeffizienten unter bestimmten Bedingungen (also nicht immer) um eins verringert wird, was die Nutzung von F5 zur Optimierung der Datenspeicherung auf der Festplatte ermöglicht. Der Grund dafür ist, dass der Koeffizient nach dieser Änderung wahrscheinlich weniger Bits nach der Huffman-Kodierung belegen wird, aufgrund der statistischen Verteilung der Werte im JPEG, während neue Nullen Vorteile bei deren Kodierung mit RLE bieten.
Die erforderlichen Anpassungen beziehen sich auf die Beseitigung des Teils, der für die Geheimhaltung (Passwort-Mischung) verantwortlich ist, um Ressourcen und Ausführungszeit zu sparen. Zudem wird ein Mechanismus zum Umgang mit mehreren Dateien anstelle von einer einzelnen hinzugefügt. Der Prozess der Änderungen wird für den Leser wahrscheinlich nicht von Interesse sein, daher kommen wir zur Beschreibung der Umsetzung.
Hohe Technologie
Um die Funktionsweise dieses Ansatzes zu demonstrieren, habe ich eine Methode in reinem C implementiert und eine Reihe von Optimierungen sowohl hinsichtlich der Ausführungsgeschwindigkeit als auch des Speicherverbrauchs durchgeführt (Sie werden nicht glauben, wie viel diese Bilder ohne Kompression selbst im DCT-Format wiegen). Die Plattformunabhängigkeit wird durch die Kombination von Bibliotheken erreicht , und , wofür ich ihnen danke. Alles wird mit ‘make’ zusammengestellt, sodass Windows-Benutzer, die eine Bewertung vornehmen möchten, Cygwin installieren oder sich selbstständig mit Visual Studio und den Bibliotheken auseinandersetzen müssen.
Die Implementierung ist in Form eines Konsolenprogramms und einer Bibliothek verfügbar. Weitere Informationen zur Nutzung letzterer finden Interessierte im README im GitHub-Repository, dessen Link ich am Ende des Beitrags anfügen werde.
Wie verwendet man das?
Seien Sie vorsichtig. Die für die Verpackung verwendeten Bilder werden durch eine reguläre Ausdruckssuche im angegebenen Stammverzeichnis ausgewählt. Nach Abschluss können die Dateien nach Belieben innerhalb dieses Verzeichnisses verschoben, umbenannt und kopiert werden, sowie die Dateisysteme und Betriebssysteme geändert werden. Es ist jedoch äußerst wichtig, darauf zu achten, den unmittelbaren Inhalt nicht zu verändern. Der Verlust eines einzelnen Bits kann zu einem vollständigen Verlust der Informationen führen.
Nach Abschluss der Arbeit hinterlässt das Tool eine spezielle Archivdatei, die alle notwendigen Informationen für die Entpackung enthält, einschließlich der Daten über die verwendeten Bilder. Diese Datei hat selbst ein Gewicht von nur wenigen Kilobyte und hat keinen nennenswerten Einfluss auf den belegten Speicherplatz.
Sie können die mögliche Kapazität mit dem Flag ‘-a’ analysieren: ‘./f5ar -a [Suchordner] [Perl-kompatibler regulärer Ausdruck]’. Die Verpackung erfolgt mit dem Befehl ‘./f5ar -p [Suchordner] [Perl-kompatibler regulärer Ausdruck] [zu verpackende Datei] [Archivname]’, und die Entpackung erfolgt mit ‘./f5ar -u [Archivdatei] [name der wiederhergestellten Datei]’.
Demonstration der Funktionsweise
Um die Effektivität der Methode zu zeigen, habe ich eine Sammlung von 225 völlig kostenlosen Hundebildern von einem Dienst hochgeladen und fand in den Dokumenten eine große PDF-Datei von 45 Metern des zweiten Bandes von Knuth.
Die Reihenfolge ist recht einfach:
$ du -sh knuth.pdf dogs/
44M knuth.pdf
633M dogs/
$ ./f5ar -p dogs/ .*jpg knuth.pdf dogs.f5ar
Lese komprimierte Datei... ok
Initialisiere das Archiv... ok
Analysiere die Bibliothekskapazität... in 17,0s abgeschlossen
Erkannte ziemlich garantierte Kapazität von 48439359 Bytes
Erkannte mögliche Kapazität von bis zu 102618787 Bytes
Kompresse... abgeschlossen in 39,4s
Speichere das Archiv... ok
$ ./f5ar -u dogs/dogs.f5ar knuth_unpacked.pdf
Initialisiere das Archiv... ok
Lese die Archivdatei... ok
Fülle das Archiv mit Dateien... in 1,4s abgeschlossen
Dekomprimiere... abgeschlossen in 21,0s
Schreibe extrahierte Daten... ok
$ sha1sum knuth.pdf knuth_unpacked.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth.pdf
5bd1f496d2e45e382f33959eae5ab15da12cd666 knuth_unpacked.pdf
$ du -sh dogs/
551M dogs/Screenshots für Enthusiasten
Die entpackte Datei kann und sollte weiterhin gelesen werden:
Wie man sieht, sind wir von den ursprünglichen 633 + 36 == 669 Megabyte auf angenehme 551 Megabyte auf der Festplatte gekommen. Dieser radikale Unterschied lässt sich durch die Reduzierung der Koeffizienten erklären, die sich auf die anschließende verlustfreie Kompression auswirken: Eine einzige Einheit weniger kann leicht ein paar Byte aus der finalen Datei herauskürzen. Dennoch handelt es sich hierbei um einen Datenverlust, wenn auch einen sehr geringen, mit dem man leben muss.
Glücklicherweise sind diese Verluste für das Auge absolut nicht sichtbar. In einem Spoiler (da habrastorage keine großen Dateien verarbeiten kann) kann der Leser den Unterschied sowohl visuell als auch durch die Intensität bewerten, die sich aus der Subtraktion der Werte der veränderten Komponente vom Original ergibt: , , (je blasser die Farbe, desto geringer der Unterschied im Block).
Abschließend
Angesichts all dieser Komplikationen scheint es viel einfacher zu sein, eine Festplatte zu kaufen oder alles in die Cloud zu laden. Auch wenn wir jetzt in einer wunderbaren Zeit leben, gibt es keine Garantie, dass wir morgen noch ins Internet gehen und all unsere überschüssigen Daten irgendwo hochladen können. Oder dass wir in ein Geschäft gehen und uns eine weitere Festplatte mit tausend Terabyte kaufen können. Aber die bereits vorhandenen Festplatten zu nutzen, ist immer eine Option.
->
Quelle: habr.com
