Ich habe eine Datei mit bestellten Binärzahlen von bis 2 n - 1 :
0000000000
0000000001
0000000010
0000000011
0000000100
...
1111111111
7z hat diese Datei nicht sehr effizient komprimiert (für n = 20 wurden 22 MB auf 300 kB komprimiert).
Gibt es Algorithmen, die sehr einfache Datenstrukturen erkennen und Dateien auf mehrere Bytes komprimieren können? Ich möchte auch wissen, auf welchem Gebiet der CS- oder Informationstheorie solche intelligenten Algorithmen studiert werden. "AI" wäre zu weit gefasst, bitte schlagen Sie konkretere Keywords vor.
Der Begriff der Symmetrie sollte eine grundlegende Rolle bei der Datenkomprimierung spielen, aber Suchanfragen nach "Symmetrie bei der Datenkomprimierung" und "Gruppentheorie bei der Datenkomprimierung" geben überraschenderweise fast nichts Relevantes zurück.
information-theory
data-compression
DSblizzard
quelle
quelle
Antworten:
Dies scheint ein klarer Anwendungsfall für die Delta-Komprimierung zu sein . Wenn a priori bekannt ist, ist dies trivial: Speichern Sie die erste Zahl wörtlich, und speichern Sie für jede nächste Zahl nur die Differenz zur vorherigen. In deinem Fall wird dies gebenn
Im Gegensatz zu DWs "Alles oder Nichts" -Vorschlag kann die Delta-Komprimierung mit Lauflängencodierung tatsächlich sinnvolle Komprimierungsverhältnisse für einige einfache Inhalte der realen Welt wie Audio mit niedriger Auflösung ergeben. (Es ist daher für Audio-Komprimierung mit geringer Qualität, sehr geringer Latenz und geringer Leistung geeignet.)
quelle
Natürlich gibt es Algorithmen. Hier ist mein Algorithmus:
Wenn nicht, schreibe ein 1-Bit aus und schreibe dann die 7z-Komprimierung der Datei aus.
Dies ist äußerst effizient für Dateien dieser bestimmten Struktur.
Der Punkt ist: Es gibt kein kostenloses Mittagessen bei der Datenkomprimierung. Möglicherweise können Sie einen Komprimierungsalgorithmus erstellen, der einen Dateityp gut komprimiert. Wenn Sie jedoch von vornherein etwas über die Art der zu komprimierenden Dateien wissen, können Sie den Algorithmus für diesen bestimmten Dateityp optimieren.
Der Bereich ist "Datenkomprimierung". Sehen Sie sich unser Datenkomprimierungs- Tag an und lesen Sie Lehrbücher zur Datenkomprimierung.
quelle
Alles, was eine BWT (Burrows-Wheeler-Transformation) verwendet, sollte in der Lage sein, dies ziemlich gut zu komprimieren.
Mein schneller Python-Test:
(Zahlen hier sind 'first_compressor second_compressor time_taken bytes_out')
(BWT von hier genommen )
Dies ist immer noch "nicht nur ein paar Bytes", aber dennoch viel besser als nur gzip allein. BWT + bz2 verringert sich beispielsweise für eine 16-Bit-Eingabe von 1114111 auf 237 Byte.
Leider sind BWTs für viele Anwendungen viel zu langsam und speicherhungrig. Vor allem, da dies eine naive Implementierung in Python ist - auf meinem Computer ist vor 2 ** 20 kein RAM mehr verfügbar.
Mit Pypy konnte ich die volle 2 ** 20-Eingabe ausführen und komprimierte sie mit einer BWT gefolgt von bz2 auf 2611 Bytes. Aber es dauerte mehr als 3 Minuten und erreichte einen Spitzenwert von über 4 GB RAM ...
Auch leider ist dieser Ansatz immer noch O (2 ^ n) Ausgangsraum, so scheint es - zumindest aus Kurvenanpassung 1..20.
quelle
eval
indem Sie:for first in (bwt_c, nothing, lzma, zlib, gzip, bz2):
undfOut = first.compress(inputData)
.4 times block size
Arbeitsspeicher (z. B. ~ 4 MB) und einer Geschwindigkeit von>10 MB/s
(ich bin der Autor einer solchen bwt-Bibliothek / Komprimierungsalgorithmus) ausgeführt wird, die für viele Anwendungen durchaus verwendbar ist. Beachten Sie, dass auch mit gzip sehr gute komprimierbare Ergebnisse erzielt werden. Vielen Dank für Ihre Mitteilung. Mir sind keine Forschungsergebnisse zur zweimaligen Verwendung von bwt bekannt.PNG-Codierung macht genau das, was Sie wollen. Es funktioniert auch mit realen Daten, nicht nur mit extrem organisierten Daten.
In PNG wird jede Zeile mit einem Filter codiert, von dem 4 angegeben werden. Eine davon ist "Codiere dieses Pixel als die Differenz zwischen seinem Wert und dem Wert des darüber liegenden Pixels". Nach dem Filtern werden die Daten mit DEFLATE komprimiert.
Diese Filterung ist ein spezielles Beispiel für die Delta-Codierung, die von leftaroundabout in seiner Antwort erwähnt wurde. Statt sie jedoch mit Run Length Encoding zu verfolgen, wird der leistungsfähigere DEFLATE-Algorithmus verwendet. Es erreicht das gleiche Ziel, nur DEFLATE kann eine größere Anzahl von Eingaben verarbeiten und bietet dennoch die gewünschten Komprimierungsverhältnisse.
Ein weiteres Tool, das häufig in wissenschaftlichen Daten verwendet wird, bei denen einfaches Filtern + DEFLATE nicht so effektiv ist, ist die RICE-Codierung. In RICE nehmen Sie einen Werteblock und geben zuerst alle höchstwertigen Bits und dann alle zweithöchstwertigen Bits bis hinunter zu den niedrigstwertigen Bits aus. Sie komprimieren dann das Ergebnis. Für Ihre Daten ist dies nicht so effektiv wie die PNG-Filterung (da Ihre Daten perfekt für die PNG-Filterung geeignet sind), aber für viele wissenschaftliche Daten führt dies tendenziell zu guten Ergebnissen. Bei vielen wissenschaftlichen Daten ändert sich das höchstwertige Bit tendenziell langsam, während das niedrigste fast zufällig ist. Dadurch werden die hoch vorhersagbaren Daten von den hoch entropischen Daten getrennt.
quelle
Jeder praktische Algorithmus, der nach bestimmten Strukturen sucht, würde sich nur auf die Strukturen beschränken, die fest darin codiert sind. Sie könnten 7z patchen, um diese bestimmte Sequenz zu erkennen, aber wie oft wird diese bestimmte Struktur im wirklichen Leben vorkommen? Nicht oft genug, um die für die Überprüfung der Eingaben für diese Eingabe erforderliche Zeit zu beanspruchen.
Abgesehen von den praktischen Aspekten kann man sich den perfekten Kompressor als einen Algorithmus vorstellen, der versucht, das kürzeste Programm zu konstruieren, das eine bestimmte Ausgabe erzeugt. Natürlich gibt es dafür keine praktischen Möglichkeiten. Selbst wenn Sie eine Brute-Force-Aufzählung aller möglichen Programme durchgeführt und überprüft haben, ob sie die gewünschte Ausgabe liefern ( keine völlig verrückte Idee ), stoßen Sie auf das Problem "Anhalten" , was bedeutet, dass Sie Testläufe nach einer bestimmten Anzahl abbrechen müssen von Ausführungsschritten, bevor Sie wissen, ob dieses Programm definitiv nicht die gewünschte Ausgabe erzeugen kann.
Der Suchbaum für einen solchen Brute-Force-Ansatz wächst exponentiell mit der Programmlänge und ist nicht für alle, sondern nur für die einfachsten Programme (etwa 5-7 Anweisungen lang) praktisch.
quelle
Das Kompressionsverhältnis hängt vollständig vom angestrebten Dekomprimierer ab. Wenn der Dekomprimierer 4-Byte-Folgenummern nicht kompakter als 4 Byte pro Nummer dekodieren kann, sind Sie SOL.
Es gibt verschiedene Dinge, die das Codieren von fortlaufenden Nummern ermöglichen würden. Zum Beispiel eine Differenzkodierung. Sie nehmen jeweils n Bytes und nehmen dann die Differenz oder das xor der Bits und komprimieren dann das Ergebnis. Dies fügt hier 4 Optionen hinzu, um für jede Byteanzahl zu versuchen: identity
a'[i] = a[i]
; Unterschieda'[i] = a[i-1]-a[i]
; umgekehrte Differenza'[i] = a[i]-a[i-1]
; und das xora'[i] = a[i]^a[i-1]
. Das bedeutet, dass 2 Bits hinzugefügt werden, um die Methoden auszuwählen, und eine Byteanzahl für 3 von 4 Optionen.Es sind jedoch nicht alle Daten eine Folge von Datensätzen fester Länge. Die differenzielle Codierung macht dafür keinen Sinn (es sei denn, der Kompressor kann empirisch nachweisen, dass er für ein Datenbit funktioniert).
quelle