Effiziente Komprimierung einfacher Binärdaten

27

Ich habe eine Datei mit bestellten Binärzahlen von bis 2 n - 1 :02n1

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.

DSblizzard
quelle
11
Schauen Sie sich die Kolmogorov-Komplexität an, die in gewissem Sinne die optimale Komprimierung (bis zu einer additiven Konstante) ist. Leider ist Kolmogorov Komplexität nicht berechenbar ...
Yuval Filmus
12
Warum müssen Sie diese Daten komprimieren? Kannst du es nicht einfach jederzeit regenerieren, wenn du es brauchst? (Dies hängt eng mit dem von @YuvalFilmus erwähnten Kolmogorov-Komplexitätsansatz zusammen: Die Kolmogorov-Komplexität ist im Wesentlichen die Länge des kürzesten Programms, das die Ausgabe generiert.)
David Richerby
7
Ich habe einen solchen Algorithmus vor 20 Jahren in der High School geschrieben. Bei Ihrer Eingabe hätte es auf "wenige Bytes" komprimiert (ungefähr 3.500.000: 1 in einem optimalen Szenario). Daten sehen jedoch selten so aus, sodass ein solcher Algorithmus nicht praktikabel ist. Allgemeine Komprimierungsalgorithmen müssen sich mit komplexen Mustern befassen, nicht mit einfachen. Jeder kann einen Algorithmus zum Speichern linearer Daten schreiben, aber das Speichern interessanter Daten ist die Herausforderung.
Phyrfox
3
Wie ergibt n = 20 22 MB? Ich bekomme 4,2 MB, wenn ich 4-Byte-Ganzzahlen verwende
njzk2
3
@JiK oh, ok. Nun, das wäre ein erster Begriff der Komprimierung und würde nicht 8 Bits verwenden, um ein einzelnes Bit darzustellen.
njzk2

Antworten:

27

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

0
1
1
1
1
...

O(n)O(1)

nNn

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.)

links herum
quelle
44

Natürlich gibt es Algorithmen. Hier ist mein Algorithmus:

  1. 02n1nn

  2. 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 Tag an und lesen Sie Lehrbücher zur Datenkomprimierung.

DW
quelle
5
Die Aufgabe eines Kompressors ist es, gemeinsame Muster zu erkennen und auszunutzen. Es ist nicht so, dass dieses Muster ungewöhnlich oder undurchsichtig ist. Es ist also eine natürliche Frage, warum es nicht ausgenutzt wird. Ihm zu sagen, dass es einen Kompromiss gibt, oder ihm einen Algorithmus zu geben, der bei allem, außer bei diesem Muster, versagt, ist ein völliger Verlust.
Mehrdad
17
Sicher sieht für mich ungewöhnlich aus. Dies würde in realen Daten äußerst selten vorkommen, verglichen mit den Mustern, nach denen gute Kompressoren suchen.
Amalloy
17
@Mehrdad Es ist kein snarky cop-out: es ist der springende Punkt . Für jedes Muster X, das einfach generiert und einfach überprüft wird, gibt es einen Komprimierungsalgorithmus, der nach diesem Muster sucht und sich damit befasst. Das ist also die Antwort auf jede Frage im Sinne von "Gibt es einen Komprimierungsalgorithmus, der sich mit einem solchen X befasst?" Klar, es gibt immer einen Algorithmus, der nach etwas komplexeren Mustern sucht. Und es gibt eines, das nach etwas komplexeren Mustern sucht als dieses, ad infinitum . Ihr Einwand ist unbegründet.
David Richerby
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Gilles 'SO- hör auf böse zu sein'
Eine extreme Anwendung dieses Prinzips sind Bittorrent-Magnet-Links, bei denen beliebige Dateien oder Dateisammlungen beliebiger Größe einfach auf feste 160 Datenbits dargestellt (komprimiert) werden. Es besteht natürlich die Gefahr einer Hash-Kollision.
Slebetman
17

Alles, was eine BWT (Burrows-Wheeler-Transformation) verwendet, sollte in der Lage sein, dies ziemlich gut zu komprimieren.

Mein schneller Python-Test:

>>> import gzip
>>> import lzma
>>> import zlib
>>> import bz2
>>> import time
>>> dLen = 16
>>> inputData = '\n'.join('{:0{}b}'.format(x, dLen) for x in range(2**dLen))
>>> inputData[:100]
'0000000000000000\n0000000000000001\n0000000000000010\n0000000000000011\n0000000000000100\n000000000000010'
>>> inputData[-100:]
'111111111111010\n1111111111111011\n1111111111111100\n1111111111111101\n1111111111111110\n1111111111111111'
>>> def bwt(text):
    N = len(text)
    text2 = text * 2
    class K:
        def __init__(self, i):
            self.i = i
        def __lt__(a, b):
            i, j = a.i, b.i
            for k in range(N): # use `range()` in Python 3
                if text2[i+k] < text2[j+k]:
                    return True
                elif text2[i+k] > text2[j+k]:
                    return False
            return False # they're equal

    inorder = sorted(range(N), key=K)
    return "".join(text2[i+N-1] for i in inorder)

>>> class nothing:
    def compress(x):
        return x

>>> class bwt_c:
    def compress(x):
        return bwt(x.decode('latin_1')).encode('latin_1')

>>> for first in ('bwt_c', 'nothing', 'lzma', 'zlib', 'gzip', 'bz2'):
    fTime = -time.process_time()
    fOut = eval(first).compress(inputData)
    fTime += time.process_time()
    print(first, fTime)
    for second in ('nothing', 'lzma', 'zlib', 'gzip', 'bz2'):
        print(first, second, end=' ')
        sTime = -time.process_time()
        sOut = eval(second).compress(fOut)
        sTime += time.process_time()
        print(fTime + sTime, len(sOut))

bwt_c 53.76768319200005
bwt_c nothing 53.767727423000224 1114111
bwt_c lzma 53.83853460699993 2344
bwt_c zlib 53.7767307470001 5930
bwt_c gzip 53.782549449000044 4024
bwt_c bz2 54.15730512699997 237
nothing 6.357100005516259e-05
nothing nothing 0.0001084830000763759 1114111
nothing lzma 0.6671195740000258 27264
nothing zlib 0.05987233699988792 118206
nothing gzip 2.307255977000068 147743
nothing bz2 0.07741139000017938 187906
lzma 0.6767229399999906
lzma nothing 0.6767684639999061 27264
lzma lzma 0.6843232409999018 27324
lzma zlib 0.6774435929999072 27280
lzma gzip 0.6774431810001715 27292
lzma bz2 0.6821310499999527 27741
zlib 0.05984937799985346
zlib nothing 0.05989508399989063 118206
zlib lzma 0.09543156799986718 22800
zlib zlib 0.06264000899977873 24854
zlib gzip 0.0639041649999399 24611
zlib bz2 0.07275534999985211 21283
gzip 2.303239570000187
gzip nothing 2.303286251000145 147743
gzip lzma 2.309592880000082 1312
gzip zlib 2.3042639900002087 2088
gzip gzip 2.304663197000309 1996
gzip bz2 2.344431411000187 1670
bz2 0.07537686600016968
bz2 nothing 0.07542737000017041 187906
bz2 lzma 0.11371452700018381 22940
bz2 zlib 0.0785322910001014 24719
bz2 gzip 0.07945505000020603 24605
bz2 bz2 0.09332576600013454 27138

(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.

TLW
quelle
Sie könnten loswerden, evalindem Sie: for first in (bwt_c, nothing, lzma, zlib, gzip, bz2):und fOut = first.compress(inputData).
Kasperd
@kasperd - wie würde ich die Namen in diesem Fall ausdrucken? Persönlich ist es einfacher (und weniger fehleranfällig), eine Auswertung durchzuführen, als zu versuchen, die Namen und Referenzen synchron zu halten.
TLW
5
Erst bwt und dann bz2 komprimiert das extrem gut. Dies ist ein äußerst merkwürdiges Verhalten und wahrscheinlich auf dieses genaue Muster zurückzuführen. Beachten Sie, dass Sie das bwt zweimal ausführen (bz2 basiert auf dem BWT), was normalerweise zu einer schlechteren Komprimierung führt. Beachten Sie auch, dass bwt heutzutage normalerweise mit 4 times block sizeArbeitsspeicher (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.
Christoph
3
@Christoph - Ich weiß, dass bz2 auf BWT basiert ... Ich hatte tatsächlich angefangen, eine Antwort auf den Effekt von 'nur bz2 verwenden' zu schreiben, aber festgestellt, dass es nicht annähernd so komprimiert war, wie ich erwartet hatte, ging 'huh ', und beschlossen, zu sehen, ob meine eigene BWT besser machen würde. Nur ich brauchte einen Kompressor für die Ausgabe und ging 'kann auch verschiedene Kompressoren versuchen, um zu sehen, was passiert'.
TLW
1
@Christoph - Ich habe noch einmal nachgesehen. 2 Bwts dieser Daten erzeugen etwas, das für die RLE-Codierung extrem zugänglich ist. Wie in, wenn Sie die Anzahl der RLE - Paare , die für 0 zählen, 1, 2, ... verschachtelten BWTS auf einem 16-Bit - Eingang, erhalten Sie 622.591 1.081.343 83 ...
TLW
10

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.

0000000000       00000  most significant bits
0000000001       00000
0000000010  =>   00000
0000000011       00000
0000000100       00000
                 00000
                 00000
                 00001
                 00110
                 01010 least significant bits
Cort Ammon - Setzen Sie Monica wieder ein
quelle
5

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.

Roman Starkov
quelle
n
1
nnn+1n1
Nun, Werkzeuge wie Mathematica finden Funktionen für viele Sequenzen ...
Raphael
3

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]; Unterschied a'[i] = a[i-1]-a[i]; umgekehrte Differenz a'[i] = a[i]-a[i-1]; und das xor a'[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).

Ratschenfreak
quelle