Alternative zu RLE Kompression
Verfasst: 22.05.2022, 12:35
Ich hab Daten mit einer relativ geringen Entropie in einem 1D Array, sieht in etwa wie folgt aus:
[0]: 0xFFFFFFFF
[1]: 0xFFFFFFFF
[2]: 0x0
[3]: 0xFF000000
[4]: 0x0
[5]: 0x0
...
Die Daten enthalten häufig Wiederholungen, außerdem gibt es häufig Bereiche, in denen sich 0 wiederholt. RLE bietet sich hier meiner Meinung nach perfekt an.
Nun zur Problemstellung:
Meine Daten können teilweise gigantisch sein, und im schlechtesten Fall bis zu 256mb an Speicherplatz einnehmen. Es handelt sich hier um eine kompilierte Regel Tabelle für Cellular Automata (will ich nur als grobe Orientierung erwähnt haben).
Durch die häufige Wiederholung und Ähnlichkeit der Daten, bietet sich also definitiv eine Kompression an. Das Problem an RLE Kompression ist allerdings, dass man die gesamten Daten dekomprimieren muss, um darauf zuzugreifen.
Da diese Tabelle in einer laufenden Cellular Automata Simulation verwendet wird, muss die Dekomprimierung sehr schnell sein, da jede einzelne Zelle auf die Tabelle zugreift, und dabei dekomprimieren muss.
Was ich brauche/suche:
- Eine Möglichkeit, schnell zur Laufzeit auf komprimierte Daten zuzugreifen
- Die Daten lediglich partiell zu dekomprimieren
- Einen (fertigen?) Algorithmus, welcher sich hauptsächlich an Dekompressionszeit, anstatt Kompressionszeit orientiert
Das wichtigste ist, dass ich den Index in die Tabelle bereits weis. Ich muss lediglich eine Möglichkeit haben, mit diesem Index einen einzelnen Wert möglichst schnell aus der Tabelle auszulesen, ohne dabei die ganze Tabelle zu dekomprimieren (da mich ja nur ein einziger Wert darin interessiert).
Meine bisherigen Idee:
- Meine Daten in Blöcke aufteilen, und diese Blöcke individuell mit RLE komprimieren
Gibt es da was fertiges, oder hat jemand eine Idee für so einen Algorithmus?
[0]: 0xFFFFFFFF
[1]: 0xFFFFFFFF
[2]: 0x0
[3]: 0xFF000000
[4]: 0x0
[5]: 0x0
...
Die Daten enthalten häufig Wiederholungen, außerdem gibt es häufig Bereiche, in denen sich 0 wiederholt. RLE bietet sich hier meiner Meinung nach perfekt an.
Nun zur Problemstellung:
Meine Daten können teilweise gigantisch sein, und im schlechtesten Fall bis zu 256mb an Speicherplatz einnehmen. Es handelt sich hier um eine kompilierte Regel Tabelle für Cellular Automata (will ich nur als grobe Orientierung erwähnt haben).
Durch die häufige Wiederholung und Ähnlichkeit der Daten, bietet sich also definitiv eine Kompression an. Das Problem an RLE Kompression ist allerdings, dass man die gesamten Daten dekomprimieren muss, um darauf zuzugreifen.
Da diese Tabelle in einer laufenden Cellular Automata Simulation verwendet wird, muss die Dekomprimierung sehr schnell sein, da jede einzelne Zelle auf die Tabelle zugreift, und dabei dekomprimieren muss.
Was ich brauche/suche:
- Eine Möglichkeit, schnell zur Laufzeit auf komprimierte Daten zuzugreifen
- Die Daten lediglich partiell zu dekomprimieren
- Einen (fertigen?) Algorithmus, welcher sich hauptsächlich an Dekompressionszeit, anstatt Kompressionszeit orientiert
Das wichtigste ist, dass ich den Index in die Tabelle bereits weis. Ich muss lediglich eine Möglichkeit haben, mit diesem Index einen einzelnen Wert möglichst schnell aus der Tabelle auszulesen, ohne dabei die ganze Tabelle zu dekomprimieren (da mich ja nur ein einziger Wert darin interessiert).
Meine bisherigen Idee:
- Meine Daten in Blöcke aufteilen, und diese Blöcke individuell mit RLE komprimieren
Gibt es da was fertiges, oder hat jemand eine Idee für so einen Algorithmus?