Neuanordnen von Daten (Satz von Zeichenfolgen), um die Komprimierung zu optimieren?

12

Gibt es Algorithmen zum Neuordnen von Daten, um die Komprimierung zu optimieren? Ich verstehe, dass dies spezifisch für die Daten und den Komprimierungsalgorithmus ist, aber gibt es ein Wort für dieses Thema? Wo kann ich in diesem Bereich recherchieren?

Insbesondere habe ich eine JSON-Liste mit 1,5 Millionen Zeichenfolgen, und ich möchte die Zeichenfolgen neu anordnen, damit die GZIP-Komprimierung (für HTTP) optimiert wird. Das Sortieren der Zeichenfolgen funktioniert ziemlich gut, aber ich weiß nicht wirklich, ob das optimal ist.

optimization permutations Jayen
quelle
1
Das optimale Neuordnen von Zeichenfolgen für die GZIP-Komprimierung (LZ77 mit einem kleinen Schiebefenster) klingt nach einem NP-harten Problem. Sie können wahrscheinlich eine Reduzierung des kürzesten allgemeinen Superstring-Problems finden.
Jouni Sirén
@ JouniSirén Ich denke, der längste gemeinsame Teilstring ist ein besserer Ansatz, da der kürzeste gemeinsame Teilstring mich darauf beschränkt, den gemeinsamen Teil hintereinander zu haben, oder? Es macht mir nichts aus, NP-schwer zu sein, solange es handhabbar ist (wie es einen Tag dauert, um auf einer modernen Maschine zu laufen).
Jayen

Antworten:

6

Dies ist eine Ergänzung zur Antwort von Navin Goyal.

Da eine JSON-Datei als Baumdatenstruktur betrachtet werden kann, können Sie die XBW-Transformation für Bäume verwenden, eine Erweiterung der Burrows-Wheeler-Transformation für Zeichenfolgen.

Hiroki Yanagisawa
quelle
1
Dank dafür. Ich habe nur eine JSON-Liste / ein JSON-Array, keine JSON-Objekte, daher sehe ich nicht, wie es als Baum angesehen werden kann. Ich könnte die Strings in einen Trie umwandeln, aber dann sehe ich nicht, wie das mit der XBW-Transformation zusammenhängt.
Jayen
4

Burrows - Wheeler-Transformation ist ein bekannter Komprimierungsalgorithmus, bei dem die Zeichen in der zu komprimierenden Zeichenfolge neu angeordnet werden.

Navin Goyal
quelle
1
Vielen Dank dafür, aber ich bin mir nicht sicher, wie ich diese Informationen verwenden kann. Ich möchte die zu komprimierenden Zeichenfolgen in der Liste neu anordnen, aber es ist mir egal, ob ich die ursprüngliche Reihenfolge wiederherstellen kann.
Jayen
1

Um die gzip-Komprimierung zu verbessern, möchten Sie, dass "ähnliche" Zeichenfolgen in der Liste angezeigt werden. Es gibt eine Reihe von Möglichkeiten, eine solche Ähnlichkeit zu definieren. Lassen Sie mich ein vernünftiges beschreiben, das in der Praxis gut funktioniert. Denken Sie daran, dass die Blockgröße von gzip 64 KB beträgt. Somit werden Ihre Daten in Blöcke von 64 KB aufgeteilt und jeder Block wird unabhängig komprimiert. Um die Komprimierung zu optimieren, müsste man die Anzahl der unterschiedlichen k-mere (Teilzeichenfolgen der Größe k) in jedem Block minimieren. Die Motivation ist, dass alle diese Teilzeichenfolgen durch einen Bezeichner ersetzt werden.

Während das obige Problem theoretisch schwierig ist (es ist eine Variante der Hypergraph-Partitionierung), existieren schnelle praktische Algorithmen. Ich würde LSH-ähnliches Clustering empfehlen , das mit einem einzigen Durchlauf über Ihre Daten implementiert werden kann. Beachten Sie, dass (alphabetische) Sortierung eine andere Möglichkeit ist, ähnliche Zeichenfolgen zu "gruppieren". Spezielle Clustering-Algorithmen können jedoch eine bessere Leistung erbringen.

Eine Alternative ist die Verwendung von zstd , das (i) schneller ist, (ii) höhere Komprimierungsverhältnisse erzielt und (iii) die Blockgröße nicht einschränkt (und daher Zeichenfolgen unabhängig von der Eingabereihenfolge gleich gut komprimiert).

Sergey Pupyrev
quelle
0

Ich habe vor einiger Zeit einen Algorithmus gesehen, der vielleicht nützlich sein kann. Es verwendet einen Algorithmus zum Bearbeiten der Entfernung, um die Entfernung zwischen den einzelnen Wörtern zu berechnen. Auf diese Weise wird ein Diagramm erstellt, in dem jedes Kantengewicht diesem Abstand entspricht. Schließlich erhält es eine Anweisung, einen Pfad auszuwählen, der die niedrigste Summe von Gewichten aufweist. Vielleicht kann es gzip verbessern.

Rafael Ribeiro
quelle
das klingt nicht nachvollziehbar, aber wenn jemand es versucht, posten Sie bitte einen Kommentar mit Ihren Ergebnissen
Jayen
Ich werde versuchen es zu testen. Ich bin neugierig auf dieses Problem. Abgesehen davon, warum denkst du, ist es nicht nachvollziehbar?
Rafael Ribeiro
Soweit ich weiß, ist der Bearbeitungsabstand O (nm), wobei n und m die Anzahl der Buchstaben im Zeichenfolgenpaar sind und Sie dies für jedes Zeichenfolgenpaar O (s ^ 2) tun müssen. Wenn also n = m, das ist O (s ^ 2 * n ^ 2), was für mich für 1,5 Millionen Saiten unlösbar klingt.
Jayen
Oh, ich habe mich nicht so sehr um die Komplexität gekümmert, weil ich dachte, Ihr Problem besteht darin, nur die Binärgröße zu verringern. Also wird diese Operation öfter vorkommen, oder?
Rafael Ribeiro
Ich habe hier gesucht und vielleicht können die Kosten für die Bearbeitung mithilfe von Levenshtein-Automaten gesenkt werden
Rafael Ribeiro