Integer CSV Kompressionsalgorithmus

Question

Ich habe Oberflächenforschung über die Existenz eines Algorithmus, der Komma getrennte Ganzzahlen komprimiert aber ich habe nichts relevantes gefunden.

Mein Ziel ist es, große Mengen an strukturierten Komma getrennten Ganzzahlen zu komprimieren, deren Wertebereiche bekannt sind. Gibt es einen bekannten Algorithmus, um so etwas zu tun? Wenn nicht, wo wäre ein guter Anfang, um über einige relevante Interessensgebiete zu lesen, die mich dazu bringen werden, einen solchen Algorithmus zu entwickeln? Natürlich muss der Algorithmus reversibel und verlustfähig sein, so dass ich die komprimierten Daten entpacken kann, um die csv-Werte abzurufen.

Die Datenstruktur ist ein Array aus drei Werten, die Domain der ersten Zahl ist von 0 bis 4, die zweite ist von 0 bis 6, die dritte ist von 0 bis n, wobei n keine große Zahl ist. Diese Struktur wird wiederholt, um Daten zu erzeugen, die sich in einem zweidimensionalen Array befinden.

Answer 1

Die Verwendung von Standardkomprimierungsalgorithmen wie gzip oder bzip2 auf strukturierten Daten führt nicht zu optimaler Komprimierungseffizienz, weshalb die Konstruktion eines fallspezifischen Algorithmus den Zweck erfüllte.

Die Datenstruktur wird unten mit einem Beispiel gezeigt.

// cell: a data structure, array of three numbers 
// digits[0]: { 0, 1, 2, 3, 4 } 
// digits[1]: { 0, 1, 2, 3 } 
// digits[2]: { 0, 1, 2, ..., n } n is not an absurdly large number 
// Below it is reused in a multi-dimensional array. 
var cells = [ 
    [ [3, 0, 1], [4, 2, 4], [3, 0, 2], [4, 1, 3] ], 
    [ [4, 2, 3], [3, 0, 3], [4, 3, 3], [1, 1, 0] ], 
    [ [3, 3, 0], [2, 3, 1], [2, 2, 5], [0, 2, 4] ], 
    [ [2, 1, 0], [3, 0, 0], [0, 2, 3], [1, 0, 0] ] 
]; 

I verschiedene Tests auf dieser Datenstruktur haben (mit Ausnahme der weißen Räume als string) unter Verwendung von Standard-Kompressionsalgorithmen:

• gz 171-88 Bytes komprimiert
• bzip2 von 171 komprimiert 87 Bytes
• deflate 171-76 Bytes komprimiert

Der Algorithmus I constru Die komprimierten Daten bis zu 33 Bytes arbeiten bis n = 192. So konnte ich fallweise meine Daten mit mehr als der doppelten Effizienz von Standard-Textkomprimierungsalgorithmen komprimieren.

Die Art und Weise, wie ich eine solche Komprimierung erreicht habe, besteht in der Abbildung der möglichen Werte aller verschiedenen Kombinationen, die Zellen für ganze Zahlen halten können. Wenn Sie ein solches Konzept untersuchen möchten, wird es als Kombinatorik in der Mathematik bezeichnet. Ich konvertierte dann die ganze Zahl der Basis 10 in eine höhere Basis für die String-Darstellung.

Da ich menschliche Verwendbarkeit anstrebe (der komprimierte Code wird getippt) verwende ich die Basis 62, die ich als {[0-9], [a-z], [A-Z]} von 0 bis 61 darstellte. Ich pufferte die Zellenlänge, wenn sie in Base62 in zwei Ziffern umgewandelt wurde. Dies ermöglichte 62 * 62 (3844) verschiedene Zellkombinationen.

Schließlich habe ich am Anfang der komprimierten Zeichenfolge, die die Anzahl der Spalten darstellt, eine 62-stellige Zahl hinzugefügt. Beim Dekomprimieren wird die y-Größe verwendet, um die x-Größe aus der Länge der Zeichenfolge abzuleiten. Somit können die Daten ohne Verlust von Daten korrekt dekomprimiert werden.

Die komprimierte Zeichenkette des obigen Beispiels sieht wie folgt aus:

var uncompressed = compress(cells); // "4n0w1H071c111h160i0B0O1s170308110" 

ich eine Erklärung meiner Methode zur Verfügung gestellt haben, mein Problem zu helfen, andere vor einem ähnlichen Problem zu lösen. Ich habe meinen Code aus unbekannten Gründen nicht zur Verfügung gestellt.

TL; DR

strukturierte Daten zu komprimieren:

1. Repräsentieren diskretes Objekt als eine ganze Zahl
2. Encode die Basis 10 Ganzzahl auf eine höhere Basis
3. Wiederholen für alle Objekte
4. Anzahl der Zeilen oder Spalten an die komprimierte Zeichenfolge anfügen

strukturierte Daten zu dekomprimieren:

1. die Zeilen oder Spalten gelesen, und die andere von der Stringlänge
2. umge die Schritte 1 und 2 in Kompression
3. Repeat für alle Objekte

Answer 2

Es sei denn, es gibt eine bestimmte Struktur zu Ihrer Liste, die Sie nicht preisgeben und die Komprimierung drastisch helfen könnte, standardmäßige verlustfreie Komprimierungsalgorithmen wie gzip oder bzip2 sollten eine Reihe von Zahlen gut behandeln.

Bibliotheken für solche allgemeinen Algorithmen sollten für fast alle Sprachen und Plattformen ubiquitär verfügbar sein.