Alternative zu RLE Kompression

[x1m4]

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?

[xq]

Meine Daten können teilweise gigantisch sein, und im schlechtesten Fall bis zu 256mb an Speicherplatz einnehmen.

Warum genau benötigst du die Kompression? Bist du auf einem resourceneingeschränkten System oder ist das einfach ein Bauchgefühl, was sagt "256 Megabyte sind irgendwie viel"?

Weil die einfachste Lösung wäre hier im Falle Bauchgefühl einfach, nicht zu komprimieren. 256mb sind jetzt nicht unbedingt wenig, aber definitiv auch nicht viel Daten auf einem modernen PC-System.

Falls die Kompression aber auf jeden Fall notwendig ist:
Welche Zugriffspatterns hast du? Komplett wild verteilt? Wenn ein Zugriff auf X passiert, ist ein Zugriff auf X+-N wahrscheinlich? Macht es ggf. Sinn, die Daten anders anzuordnen?

[x1m4]

Bei mir gibt es bis zu 256 verschiedene Zell Arten. Jede Art von Zelle hat solch eine eigene (potenziell riesige) Tabelle zugewiesen, in welcher im Voraus berechnete Regeln drin stehen.

Die Anzahl der Nachbaren um eine Zelle gibt den Tabellen Index an. Der Wert in der Tabelle gibt mir dann das entsprechende Ergebnis für das Verhalten der Zelle zurück. Der Zugriff ist dadurch relativ ungeordnet.

Der genaue Algorithmus, um den Tabellen Index zu bekommen ist:
- Erstelle Indizierungs Variable (unsigned 32-bit mit 0 initialisiert)
- Geh mit Schleife durch jede Nachbar Zelle. Wenn Nachbar Zelle aktiv, dann setz mit dem Schleifen Index das jeweile bit in der Indizierungs Variable auf 1

Dadurch kann man sich schnell anhand der Nachbaren einen Index in die Tabelle bauen. In 2D CA wären es 8 Nachbarn, mein CA ist allerdings 3D mit 26 Nachbarn, was 2^26 mögliche Kombinationen ergibt, und dadurch die Tabelle so aufbläht.

[Mirror]

Wie wäre es wenn Du die Nachbarkombinationen in Gruppen einteilst? Also wenn nur links ein Nachbar ist, dann ist das ähnlich als wenn Du nur rechts einen Nachbarn hast. Du könntest für rechts die Daten aus links auslesen und dann nur spiegeln. Das würde die Tabelle schon schrumpfen lassen. Du müsstest dann allerdings alle Kombinationen durchgehen. Du könntest auch noch Rotationen verwenden ( neben den Spiegelungen ).

[marcgfx]

0xFFFFFFFF ??? Weiss? RGBA? Kannst du das nicht einfach als PNG speichern? 256 Arten von Zellen also wäre ja auch GIF denkbar oder eben PNG mit Palette.

edit: ok das mit den Zellen habe ich nicht geschnallt. Dennoch sehen die Daten für mich wie RGBA aus und PNG32 sollte dafür recht gut geeignet sein.

[x1m4]

0xFFFFFFFF ??? Weiss? RGBA? Kannst du das nicht einfach als PNG speichern? 256 Arten von Zellen also wäre ja auch GIF denkbar oder eben PNG mit Palette.

Die Zahlen sind nur als Platzhalter da, eigentlich sind das "zufällige" 26-bit große Zahlen.

PNG Kompression zu verwenden hatte ich mir auch schon überlegt, da PNG lossless ist. Allerdings weiß ich nicht, ob PNG beim dekomprimieren auch Random Access Zugriffe effizient unterstützt, was bei meinem Fall ja das Hauptkriterium ist. Die Kompression muss nicht maximal effizient sein, und die Zeit, welche die Kompression beansprucht, ist auch relativ egal.

Bei mir kommt es hauptsächlich auf die Geschwindigkeit bei der Dekompression an.

[x1m4]

Eine weitere Idee: Mit RLE anstatt die Wiederholungen einer Zahl, den relativen Index im Speicher bis wohin wiederholt wird schreiben. Das erlaubt, frei im komprimierten Speicher, und nicht von 0 aus dekomprimieren zu müssen.

Zusätzlich macht es wahrscheinlich noch Sinn, eine Sprung Tabelle mit Meta Informationen wie z.B Speicher Regionen mit zu geben, um den initialen Index im Speicher, von dem aus dekomprimiert werden soll, schneller zu finden. Ich schätze mal, mit einer vernünftigen Implementierung könnte man die Dekomprimierung auf lediglich 3-4 Lese Operationen reduzieren.

Wahrscheinlich würde mit dem Prinzip es auch Sinn machen, den Speicher dann rückwärts auszulesen.

Eine weitere Möglichkeit wäre noch, bei der Kompression die Daten in Blöcke aufzuteilen. Damit könnte man dann ein Laufzeit Cache System einbauen, sodass bereits dekomprimierte Region direkt aus dem Cache gezogen werden können. Das Zugriffsmuster meiner Tabelle ist mir leider noch nicht ganz klar, da könnte man dann evtl. mit ZigZag oder Morton Encoding das Speicherlayout noch zusätzlich optimieren.

[marcgfx]

Wenn das Dekomprimieren schnell genug ist, braucht du kein Random Access?
In einere ersten Fassung kannst du eigentlich komplett ohne Kompression arbeiten. Damit hättest du schon eine Referenzwert für die Geschwindigkeit und wie viel dich die Kompression dann kostet.

In Blöcke aufteilen bringt womöglich schon was, weil du nur einen Teil dekomprimieren musst. Die Aufteilung in Blöcke wäre mit PNG möglich. Du hättest damit visuelles Feedback. Ich habe PNG selbst schon so missbraucht und doofe Fehler kann man sehen. Zusätzlich musst du nichts selber schreiben um PNG zu laden/speichern, bzw. du findest dazu auch Code online.

[xq]

Du könntest auch noch Rotationen verwenden ( neben den Spiegelungen ).

Name ist Programm! *grins*

Aber das klingt, als hättest du es sowieso mit absurd großen Datenmengen (ich nehme mal an, es geht um dein Voxel-Programm) zu tun, da tun die 256MB LUT imho auch nicht mehr weh und ich würde die Daten wie schon initial gesagt einfach unkomprimiert rumliegen lassen.

Mir ist spontan auch keine passende Kompression bekannt, PNG ist ja auch nur deflate, aber in sinnvoll gespeichert (da 2D-Grafiken ja "Signale" sind, kann man eben die tiefen Oktaven zuerst komprimieren und bekommt damit eine progressive dekompression des Signals mit niedriger Qualität und dann steigend).

Das Konzept ist ja aber bei dir nicht anwendbar. DXT/S3TC wäre ein Kompressionsverfahren, welches direct access erlaubt, dafür eben lossy ist. Was auch gehen könnte, wäre, dass du einzelne blöcke komprimierst statt den gesamten Stream und dir ne Index-Tabelle bereit stellst, welche den Index in den Stream angibt. Aber ich glaube, wir haben hier schon ein Problem auf rein theoretischer Seite, da ja Kompression versucht, die Daten so klein zu machen, wie nur möglich, während Indexierung erzwingt, dass Elemente die selbe Größe haben

[Schrompf]

Ich kenne jetzt nicht exakt die Natur der Daten, aber aus der Kalten würde ich ein blockbasiertes Kompressionsverfahrung empfehlen. Du nimmst eine Zeile, oder einen 4x4x4-Block oder was auch immer geeignet ist, und komprimierst die einzeln. Die einfachste Kompression wäre dann: "sind alle Werte gleich oder gibt's Unterschiede?" Die nächste wäre "Ich komme mit weniger Bits pro Wert aus, indem ich ne Palette voranstelle". Oder "RLE pro Teilsegment". Oder hierarchisch "Pro 4x4x4-Segment gibt ein Bit an, ob da was Genaueres drin steht oder ob das Teilsegment komplett leer ist."

Die Problemstellung klingt wie "Sparse Voxel Tree" und dazu gibt's ja nun schon einige etablierte Herangehensweisen.

[edit] und das Ganze könnte durchaus sogar schneller sein als vorher trotz der komplexen Dekompression, weil Random Access in einer 256MB-Tabelle quasi garantierter Cache Miss ist.

[Jonathan]

Bin leider kein Experte auf dem Gebiet, aber das Problem klingt nicht sonderlich exotisch, es sollte also einen etablierten und sehr gut geeigneten Algorithmus dafür geben, d.h. ich würde danach suchen anstatt selber irgendwas zusammen zu frickeln.

Vielleicht reicht ja für den Anfang ein Überblick über die wichtigsten Methoden: https://en.wikipedia.org/wiki/Lossless_compression

Lossless + schnelle Dekompression erscheint mir relativ machbar. Random Access könnte da schon schwieriger werden, allerdings könnte ich mir vorstellen, dass man einige Algorithmen auch mit einer Look-Up-Table verwenden kann. RLE sollte ja ansich Blöcke von Daten unabhängig voneinander komprimieren, man weiß halt bloß nicht, wo der passende Block anfängt. Aber das kann man sich ja merken. Natürlich muss man dann wieder abwägen, wie klein man die Blöcke haben will, man will ja nicht dass das Wörterbuch größer als die eigentlichen Daten ist. Ähnliche Dinge sind möglicherweise auch bei anderen Algorithmen möglich.

[x1m4]

*aufräum* meine Antwort drunter wurde irgendwie doppelt abgeschickt

[x1m4]

Danke für das Feedback!

Ich glaub ich muss näher erläutern, um was für eine Art Daten es sich hier handelt, da mein Fall hier doch eher exotisch ist.
Bei meinem Voxel Engine Thema sieht man im letzten Post, dass ich an einem System zum Bauen von Schaltungen arbeite. Eine Schaltung sieht z.B. so aus:


Eine Schaltung besteht erstmal aus einer 32^3 großen Welt, welche Input Pins (blau) und Output Pins (Grün) hat - was quasi das IO Prinzip modelliert. Die Input Pins geben Informationen aus einer darüber liegenden Welt als Stromsignal in das Modul hinein. Die Output Pins geben ein Stromsignal in die darüber liegende Welt hinaus. So eine Schaltung kann später in eine normale Welt platziert werden, und nimmt dort genau 1 Voxel an Platz ein.

Die Schaltung im Screenshot oben macht z.B. folgendes: Wenn ein Stromsignal von z.B. Links kommt, dann wird nach Rechts Strom ausgegeben.

Mit diesen Schaltungen kann man Voxel Welten quasi Leben verpassen. Hiermit lassen sich auch so Dinge wie herunterfallender Sand und viele weitere Dinge "visuell programmieren".

Da diese Schaltungen später in einer Welt platziert werden können (als 1 Voxel), wäre es unfassbar langsam, wenn man diese Schaltungen in Echtzeit ausführen würden. Da meine Welten momentan bis zu 256^3 groß sind, könnte (und soll) man theoretisch jeden einzelnen Voxel eine Schaltung in Echtzeit ausführen lassen.
Um das möglich zu machen, konvertiere ich die Schaltungen in eine Regeltabelle, anstatt sie in Echtzeit zu berechnen. Ich gehe alle möglichen Zustände der Input Pins (entweder 0 oder 1 pro Pin) durch, führe die Simulation aus, und hole mir am Ende die Zustände der Output Pins (ebenfalls entweder 0 oder 1 pro Pin). Daraus ergibt sich eine riesige Tabelle an vorab berechneten Regeln, wobei der Index in die Tabelle anhand der Input Bits, und der jeweilige Wert in der Tabelle durch die Output Bits gegeben ist.

So eine generierte Tabelle hab ich mal in ein PNG konvertiert, und war über die Kompression überrascht. Von 256kb auf 5kb!!1 Das hat mir ein bisschen zu denken gegeben, und mir gesagt, dass es hier anscheinend viele redundante Daten bzw. Muster gibt.

Hier ein PNG von einer einfachen Schaltung. Man erkennt sofort, dass es hier von Mustern nur so wimmelt.


Ich hab die Regel Tabelle zur Analyse mal in eine text basierte binär Tabelle umgewandelt. Hier ein Beispiel, wie die Daten von so einer Tabelle aussehen (32-bit pro Zeile, in 4x 8-bit Pasche zerlegt).

Ich war überrascht, wie wenige Kombination es auf 8-bit Ebene gibt. Im Fall dieser Daten waren es glaub ich nur rund 40 verschiedene 8-bit Zahlen. Die Komplexität besteht hier also in der Anordnung dieser 8-bit Zahlen, und nicht in den Zahlen selbst.

Neben der Kompression, die ich nun wahrscheinlich mit Dictionary und großen Mustern lösen muss, ist bei meinen Daten vor allem die Dekompression wichtig. Hier ist es wichtig zu wissen, dass ich jeweils lediglich nur auf EINEN einzigen Wert in der Tabelle zugreifen muss. Ich hab leider keinen Algorithmus o.ä. gefunden, der hier für meinen Fall greift. Kompression von großen relativ redundanten 1D Daten, und schneller Zugriff auf einzelne komprimierte Datenpunkte.

Wenn beim simulieren einer Welt auf einen Voxel mit einer zugewiesenen Schaltung gestoßen wird, dann bilde ich mir anhand der Nachbaren dieses Voxels den Tabellen Index für die Regeltabelle. Darüber kann ich mir sehr schnell das Ergebnis der Schaltung holen, ohne irgendwas groß berechnen zu müssen. Der Prozess hier muss extrem schnell sein, da wie gesagt jeder Voxel in meiner Welt theoretisch so eine Schaltung beinhalten und "ausführen" kann.

Für 2^16 große Schaltungen in großen Welten funktioniert die Simulation auch schon bestens, nur bei größeren Schaltungen frisst es einfach viel zu viel Speicher.

Meine aktuelle Idee ist, wie oben schon angedeutet, ein Dictionary aus den 8-bit Mustern zu bauen, und über große Distanzen Muster zu erkennen. Diese Mustern würden mit Offset und Länge in eine Tabelle gespeichert werden, und der Zugriff z.B. mit einem BSP Baum optimiert werden.

Edit:

Ich kenne jetzt nicht exakt die Natur der Daten, aber aus der Kalten würde ich ein blockbasiertes Kompressionsverfahrung empfehlen.

Block basiert wie bei den BC Textur-Kompressions Varianten klang auch für mich als erstes am interessantesten, allerdings scheint meine Art der Daten doch eher ungeeignet dafür. Meine Daten sind 1D und es gibt keinen konkreten Zusammenhang zwischen Nachbarn, zudem sind meine Daten sehr redundant und wiederholen sich über große Bereiche.

RLE sollte ja ansich Blöcke von Daten unabhängig voneinander komprimieren, man weiß halt bloß nicht, wo der passende Block anfängt.

Ich glaub der Titel von meinem Post passt auch nur noch teilweise zu meinem momentanen Kenntnisstand. Ich brauch irgendwie schon was in Richtung RLE, allerdings nicht ein klassisches RLE über eine Varietät von 1, sondern über sehr große Bereiche. Außerdem müsste das RLE, statt der Anzahl der Wiederholungen, die jeweiligen Offsets im Speicher hinterlegen, damit bei der Dekomprimierung dann schnell und dynamisch an die entsprechenden Stellen im Speicher gesprungen werden kann, und das RLE nicht von Punkt 0 dekomprimiert werden muss.

Bin leider kein Experte auf dem Gebiet

Bin auch absolut neu im Thema Kompression, so in der Tiefe musste ich mich noch nie mit beschäftigen^^

[NytroX]

Wenn ich es richtig verstanden habe, dann hast du also viele Inputs/Indices, aber der Lookup führt oft zu dem gleichen Ergebnis, d.h. von den 4 8-Bit-Werten sind viele davon oft gleich. Ich denke mal ein Dictionary-basierter Algorithmus wäre dann vermutlich sinnvoll.

LZ4 würde ich mir mal anschauen, das ist ein Dictionary-basierter Algorithmus ohne Entropie-Encoding/Huffman, die Dekompression ist sehr schnell. Vielleicht ist sowas ähnliches hilfreich. (Deflate, der ja in png benutzt wird, ist ja quasi ähnlich (LZ77) aber zusätzlich mit Huffman-Encoding)
http://fastcompression.blogspot.com/201 ... ained.html

Für die Datenstruktur selbst fällt mir spontan der Radix Tree ein; vielleicht in einer abgewandelten Form für dich relevant.
Vielleicht kannst du damit die Daten effizienter hinterlegen und daraus dann die Tabelle generieren.
https://en.wikipedia.org/wiki/Radix_tree

[Alexander Kornrumpf]

https://ira.informatik.uni-freiburg.de/ ... n/2bdd.pdf

[x1m4]

Wow, also BDD sehen echt interessant und passend für meinen Fall aus. Auf große komprimierte Relations/Regel Tabellen möglichst schnell und ohne Dekomprimierung zugreifen, ist exakt das, was ich vom Prinzip her suche.

Danke für den Tipp, da les ich mich mal rein!

[Alexander Kornrumpf]

Ist schon ein bisschen nerd sniping (https://xkcd.com/356/) was du hier machst.

Ich habe mal ein bisschen damit raumgespielt, deine Datei hat 16 input bits (65536 Zeilen) aber 32 output bits. Ist da was beim hoch/runterladen schief gegangen? Es ist ja von vornherein klar, dass du manche Outputs gar nicht erreichen kannst, wenn du weniger Inputbits hast.

Ich bin mal die ersten Bits von hinten durchgegangen. Vorab: kann sein, dass ich hin und wieder (oder sogar überall) ein Inverses übersehen habe.

- das letzte bit ist immer 0 (das ist für die "kompression" natürlich der best case)
- das vorletzte bit entspricht dem vierten (0 indiziert) input bit. Sieht man auch ganz schön wenn man auf die ersten 32 Zeilen schaut. Das Muster wiederholt sich anscheinend.
- output bit 2 entspricht input bit 1 sieht man sofort wenn man es weiß :)
- output 3 ist immer 0
- output 4 ist input 12
- output 5 ist immer 0
- output 6 ist input 3
- output 7 ist immer 0

- output 8 ist immer 0
- output 9 ist immer 0
- output 10 ist input 9
- output 11 ist immer 0
- output 12 ist input 8
- output 13 ist immer 0
- output 14 ist input 7
- output 15 ist immer 0

Ich habe dann aufgehört weil ich nicht implementiert hatte die bits parallel zu analysieren und das programm deswegen 16 mal neustarten musste um obiges zu berichten.

Da du ja die "Schaltung" die das erzeugt hat vermutlich kennst, kannst du ja mal checken wie plausibel das ist. Dass die Kompressionsrate von "wir schreiben die Regeln einfach hin" bei so simplen Regeln nicht zu schlagen ist, ist ja eh klar.

[x1m4]

Ist schon ein bisschen nerd sniping (https://xkcd.com/356/) was du hier machst.

Dachte mir irgendwie schon, dass mein Kram vor allem für Leute aus der Elektro Technik interessant sein könnte^^

Ich habe mal ein bisschen damit raumgespielt, deine Datei hat 16 input bits (65536 Zeilen) aber 32 output bits. Ist da was beim hoch/runterladen schief gegangen? Es ist ja von vornherein klar, dass du manche Outputs gar nicht erreichen kannst, wenn du weniger Inputbits hast.

Bei der Schaltung in der Datei hab ich nur 16 Input Pins aktiviert, daher nur 2^16 Zeilen. Im Screenshot oben werden z.B. nur 4 Input Pins verwendet, die aktivierten Pins sind Lila eingefärbt. Die aktivierten Output Pins werden eigentlich auch Lila eingefärbt, der Screenshot ist aber schon ein paar Tage alt, da war das noch nicht eingebaut :)

Ingesamt können es bis zu 2^26 Input, und 2^26 Output Kombinationen geben, je nachdem, wieviele Pins jeweils aktiviert sind. Das manuelle aktivieren der Input Pins ist wichtig, da die Rechenzeit, um eine Schaltung in eine Regeltabelle zu kompilieren exponentiell mit der Anzahl der Input Pins steigt. Eine 2^16 große Schaltung kann je nach Größe der Welt und Komplexität der Schaltung ein paar Minuten kompilieren.

Danke für das Finden dieser Muster, sieht echt vielversprechend aus!

Es ist ja von vornherein klar, dass du manche Outputs gar nicht erreichen kannst, wenn du weniger Inputbits hast.

Input Pins können mit mehreren Output Pins verbunden sein. Man kann tatsächlich so ziemlich jeden Unfug in so einer Welt machen, da man mit asynchronen Signalstärken arbeitet (geht bisschen in die Richtung von Minecraft's Redstone).

Hier mal ein Video (von vor ein paar Tagen), wo ich die Schaltung für ein selbst replizierendes System verwende. Der graue Block ist quasi die Schaltung die man am Anfang vom Video sieht, nur in eine Regeltabelle kompiliert und dann als einzelner Block in die Welt der Schaltung selbst platziert (Ja, ist ein bisschen Gehirnfick).

Das Prinzip der Schaltung hier ist, dass die 6 Würfel Nachbarn geprüft werden, ob dort ein Block steht. Wenn dort jeweils ein Block steht, dann kommt ein Stromsignal in den entsprechenden Input Pin rein.
Die Input Pins übergeben dann das Stromsignal an die Output Pins auf der gegenüberliegenden Seite.
Wenn ein Output Pin ein Strom Signal kriegt, dann wird an der Stelle ein Block erstellt. In dem Fall ist der erstellte Block das Modul selbst, wodurch sich diese Wände ziehen. Quasi ein einfaches Cellular Automata mit so einer Schaltung definiert.



Edit: Hier noch ein weiteres Video wo man sieht, wie sich die Signale ausbreiten. Die türkisenen Blöcke sind Signal Inverter, die an einer Seite ein Signal ausgeben, solange an den anderen Seiten kein Signal reinkommt:

[Alexander Kornrumpf]

Es ist ja von vornherein klar, dass du manche Outputs gar nicht erreichen kannst, wenn du weniger Inputbits hast.

Input Pins können mit mehreren Output Pins verbunden sein. Man kann tatsächlich so ziemlich jeden Unfug in so einer Welt machen, da man mit asynchronen Signalstärken arbeitet (geht bisschen in die Richtung von Minecraft's Redstone).

Ich meinte dass du in 2^16 Tabellenzellen nicht 2^32 verschiedene Outputs speichern kannst, d. h. es muss Output-Kombinationen geben, die nicht vorkommen. Natürlich kann jedes einzelne Bit (in Kombination mit anderen) beide Werte annehmen (auch wenn es im Beispiel nicht so ist), aber informationstheoretisch ist das eben keine zusätzliche Information.

Danke für das Finden dieser Muster, sieht echt vielversprechend aus!

Ich habe den Code jetzt nochmal angepasst, dass er alle output bits auch wirklich anschaut. Man muss dann nebeneinander halt 32 bdd aufbauen damit man die Daten nicht 32 mal parsen muss (wenn man es naiv bit für bit nacheinander machen würde). Jedenfalls, für dieses Beispiel das vollständige Ergebnis: Scheint aber ein Bug drinzusein, es kommt nicht dasselbe raus, wie ich oben gepostet hatte.

[Alexander Kornrumpf]

War ein trivialer Bug. Hier also der BDD für alle 32 output bit in GraphViz syntax.

Code: Alles auswählen

---0---
 digraph bdd {
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---1---
 digraph bdd {
n4 [label = 4];
n4 -> n18446744073709551615 [style=dotted];
n4 -> n18446744073709551614;
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---2---
 digraph bdd {
n1 [label = 1];
n1 -> n18446744073709551615 [style=dotted];
n1 -> n18446744073709551614;
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---3---
 digraph bdd {
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---4---
 digraph bdd {
n12 [label = 12];
n12 -> n18446744073709551615 [style=dotted];
n12 -> n18446744073709551614;
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---5---
 digraph bdd {
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---6---
 digraph bdd {
n3 [label = 3];
n3 -> n18446744073709551615 [style=dotted];
n3 -> n18446744073709551614;
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---7---
 digraph bdd {
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---8---
 digraph bdd {
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---9---
 digraph bdd {
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---10---
 digraph bdd {
n9 [label = 9];
n9 -> n18446744073709551615 [style=dotted];
n9 -> n18446744073709551614;
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---11---
 digraph bdd {
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---12---
 digraph bdd {
n8 [label = 8];
n8 -> n18446744073709551615 [style=dotted];
n8 -> n18446744073709551614;
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---13---
 digraph bdd {
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---14---
 digraph bdd {
n7 [label = 7];
n7 -> n18446744073709551615 [style=dotted];
n7 -> n18446744073709551614;
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---15---
 digraph bdd {
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---16---
 digraph bdd {
n6 [label = 6];
n6 -> n18446744073709551615 [style=dotted];
n6 -> n18446744073709551614;
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---17---
 digraph bdd {
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---18---
 digraph bdd {
n10 [label = 10];
n10 -> n18446744073709551615 [style=dotted];
n10 -> n18446744073709551614;
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---19---
 digraph bdd {
n14 [label = 14];
n14 -> n18446744073709551615 [style=dotted];
n14 -> n18446744073709551614;
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---20---
 digraph bdd {
n11 [label = 11];
n11 -> n18446744073709551615 [style=dotted];
n11 -> n18446744073709551614;
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---21---
 digraph bdd {
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---22---
 digraph bdd {
n2 [label = 2];
n2 -> n18446744073709551615 [style=dotted];
n2 -> n18446744073709551614;
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---23---
 digraph bdd {
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---24---
 digraph bdd {
n13 [label = 13];
n13 -> n18446744073709551615 [style=dotted];
n13 -> n18446744073709551614;
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---25---
 digraph bdd {
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---26---
 digraph bdd {
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---27---
 digraph bdd {
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---28---
 digraph bdd {
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---29---
 digraph bdd {
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---30---
 digraph bdd {
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}
---31---
 digraph bdd {
n18446744073709551615 [label="0"];
n18446744073709551614 [label="1"];
}

[x1m4]

Danke das sieht echt gut aus. Ich hab ein paar Minuten versucht, den Output Text zu verstehen (Von GraphViz hab ich noch nie gehört).

Die einzige mir ersichtliche Baumstruktur in den Daten, ergibt sich über z.B. "n2 [label = 2];" was aussieht wie ein Knotenpunkt. Die Zahlen n18446744073709551615 und n18446744073709551614 scheinen 0 und 1 darzustellen, oder täusche ich mich da?
Das muss ich mir echt in Ruhe mal anschauen, ist aber aufjedenfall sehr hilfreich zu wissen. Wenn ich es richtig verstehe, dann kann man sich mit diesem BDD mit ein paar wenigen traversals anhand der Input Bits die jeweiligen Output Bits holen.

Wie man so einen BDD für meine Daten generiert, ist mir noch ein Rätsel. Hast du den BDD mit GraphViz erstellt oder selbst generiert (wenn ja, wie?).

[Alexander Kornrumpf]

Man kann aus dem BDD auch den booleanschen Ausdruck generieren. Ich habe bei der Gelegenheit auch noch wallclock-time angezeigt um eine Idee zu bekommen, wie schnell die BDD generiert werden können (Antwort: überaschend schnell):

Code: Alles auswählen

cargo run --release
   Compiling decision v0.1.0 (T:\Projects\zfx\decision)
    Finished release [optimized] target(s) in 0.95s
     Running `target\release\decision.exe`
Elapsed Time: 0.14089951 Seconds
Const(false)
Terminal(4)
Terminal(1)
Const(false)
Terminal(12)
Const(false)
Terminal(3)
Const(false)
Const(false)
Const(false)
Terminal(9)
Const(false)
Terminal(8)
Const(false)
Terminal(7)
Const(false)
Terminal(6)
Const(false)
Terminal(10)
Terminal(14)
Terminal(11)
Const(false)
Terminal(2)
Const(false)
Terminal(13)
Const(false)
Const(false)
Const(false)
Const(false)
Const(false)
Const(false)
Const(false)

Das sind einfach die Ausdrücke für die 32-Bits in deinen Daten von hinten nach vorne.

Const(false) bedeutet, was man denken würde dass es bedeutet, Terminal(4) bedeutet die freie Variable mit dem Namen "4", das habe ich so gewählt, dass das eben der Index des input bit ist (LSB hat index 0)

Das ist jetzt immer noch menschenlesbar, tatsächlich bräuchtest du theoretisch weniger als 32 byte um die Information zu kodieren, die da steht, also die Kompression ist phantastisch.

Der Dekompressionsalgorithmus, wenn man das überhaupt so nennen will, sollte hoffentlich auch klar sein, man wendet halt für jedes Output Bit den entsprechenden Ausdruck auf den Input an.

Natürlich ist das jetzt eine zufällige Eigenschaft der Beispieldaten, dass die Ausdrücke alle so einfach sind. Worst case können die Ausdrücke exponentiell in der Zahl der Input Bits groß werden, was ja, wenn man mal drüber nachdenkt nur logisch ist, weil man halt worst case 2^{input bits} Bit an Information speichern muss. Genau das tut ja deine unkomprimierte Tabelle.

Mir an deiner Stelle würde das aber Hoffnung machen, dass du den Worst-Case eher nicht triffst (sofern das Beispiel einigermaßen repräsentativ war).

Zu der Frage, wie ich das gemacht habe poste ich mal den Code. Ich muss mich direkt entschuldigen, ich wollte wie im anderen Thread geschrieben mal was mit Rust machen, Rust ist an sich schon nahezu unlesbar, mMn, und ich bin wahrlich kein Experte für schönes Rust:

Code: Alles auswählen

use std::fs::File;
use std::io::{BufRead, BufReader};
use std::time::Instant;

use arr_macro::arr;

use boolean_expression::{BDDFunc, BDD};

fn parse_line(reader: &mut BufReader<File>, tree: &mut [BDD<u8>; 32]) -> [BDDFunc; 32] {
    let mut line = String::new();
    reader.read_line(&mut line).unwrap();
    let list: Vec<u8> = line
        .split_whitespace()
        .map(|s| u8::from_str_radix(s, 2).unwrap())
        .collect();

    let mut result: [BDDFunc; 32] = [0; 32];

    for block in 0..4 {
        for bit in 0..8 {
            let idx = block * 8 + bit;
            result[idx] = if (list[3 - block] >> bit) % 2 == 0 {
                tree[idx].constant(false)
            } else {
                tree[idx].constant(true)
            }
        }
    }

    result
}

fn parse(
    left: Option<[BDDFunc; 32]>,
    level: u8,
    reader: &mut BufReader<File>,
    tree: &mut [BDD<u8>; 32],
) -> [BDDFunc; 32] {
    let next = if level == 0 {
        parse_line(reader, tree)
    } else {
        parse(None, level - 1, reader, tree)
    };

    return match left {
        Some(func) => {
            let mut result: [BDDFunc; 32] = [0; 32];
            for idx in 0..32 {
                let term = tree[idx].terminal(level);
                result[idx] = tree[idx].ite(term, next[idx], func[idx]);
            }
            result
        }
        None => parse(Some(next), level, reader, tree),
    };
}

fn main() {
    let start = Instant::now();

    let binput = File::open("binary.txt").unwrap();
    let mut reader = BufReader::new(binput);

    let mut tree: [BDD<u8>; 32] = arr![BDD::new(); 32];

    let node = parse(None, 15, &mut reader, &mut tree);

    println!("Elapsed Time: {} Seconds", start.elapsed().as_secs_f32());

    for idx in 0..32 {
        //println!("----{}---- \n {}", idx, tree[idx].to_dot(node[idx]));
        println!("{:?}", tree[idx].to_expr(node[idx]));
    }
}

Das ist aller Wahrscheinlichkeit nach _nicht_ das was du machen willst, sondern du willst wahrscheinlich die Schaltung direkt in den BDD schieben, ohne den Umweg über die Wahrheitstabelle, die zu erzeugen, wie du schreibst, sehr kostspielig ist, und die du eigentlich nicht brauchst. Sieh es eher als Proof-of-Concept.

Die eigentliche Arbeit macht https://docs.rs/boolean_expression/late ... xpression/

Ich habe mir das nicht weiter angeschaut, aber es gibt auch (viele) C libraries, die im Grunde dasselbe tun, da hast du einiges an Auswahl.

[x1m4]

Hab's nun endlich geschafft, einen Baum zu generieren. Das ist der BDD für die binary.txt.

Für die Generierung benutz ich weiterhin die 4x 8bit Pasche. Der erste Layer im Baum gibt das jeweilige Pasch an (0-3).
Beim Iterieren, gibt "l" den Bit-Index vom Input an, mit dem dann in den Nodes entweder "0" oder "1" genommen wird.

Den Baum kann man wahrscheinlich noch bisschen weiter optimieren, ich denke das reicht mir so aber erstmal.

Danke nochmal für den ganzen Input. BDDs sind tatsächlich genau das, was ich hier gebraucht hab. Hat mir viel Zeit und Kopfschmerzen gespart^^