Algorithmus Challenge

[negaH]

Hi Meisterschied,

Ich habe es gelösst allerdings ganz anders. Das lag hauptsächlich daran das meine obige Problemstellung garnicht das eigentliche Ziel richtig treffen kann. Sorry, dafür das du dich so lange reingekniet hast.

Ich bin im Grunde auf exakt die gleiche Lösung wie du gekommen, war aber am Anfang noch der Meinung die maximal beste Lösung finden zu können, bzw. das eine der gefundenen Lösungen (falls es mehrere gibt) immer das Maximum darstellt.

Allerdings, nur auf grund einer statistischen Tabelle die NICHT auch das tatsächliche sequentielle Auftreten der einzelnen Längen in den Bitmaps berücksichtigt, kann die gefundene Lösung garnicht die beste sein !!

Soll heisen: wird nur mit obiger Tabelle nach dem besten "Pfad" gesucht so beträfe die Lösung alle Bitmaps mit gleicher Längenstatistik im Durchschnittlichen. Es ist aber entscheidend, ausgehend von den realen sequentiellen Längenverteilungen in den Bitmaps, die maximal beste Komprimierung zu erreichen.
Dies kann nur funktionieren wenn man auch immer im Optimierungsverfahren die tatsächlichen Bitmapdaten berücksichtigt, und eben nicht nur eine Statistik.

Die Statistik und dein Algo. können aber dazu benutzt werden meinen derzeitigen Suchalgorithmus zu beschleunigen. D.h. über deinen Algo. kann man eine Vorabschätzung errechnen mit welchen Suchmustern der eigentliche Suchalgo. am besten beginnen soll.

Gut, meine derzeitige Lösung, könnte man als Brute Force Suche mit vorzeitigem Abbruch bezeichnen. D.h. als erstes wird obige Längentabelle ermittelt. Somit kennen wir die Gesamtmenge aller Elemente die für die späteren Kombinationen 3 aus x nötig sind.
Nachdem nun die obigen Daten erfasst wurden wird JEDE Kombination anhand einer Testkomprimierung der Daten durchgespielt. Es wird also die tatsächlich mögliche Komprimierungrate der Daten mit zu jeweils jeder möglichen Kombination ermittelt. Allerdings, übersteigt diese aktuell kummulierte Größe der bisher komprimierten Daten die Größe der aktuell besten Komprimierung wird die Testkomprimierung abgebrochen. Diese Abbruchsbedingung wird zur durchschnittlichen Komprimierungsgröße jedes einzelnen Zeichens ermittelt.

Dieses Verfahren erscheint im ersten Moment sehr un-optimial, aber leider kann es anders garnicht funktionieren. Denn wir müssen, um die MAXIMAL beste Komprimierung zu ermitteln tatsächlich mit den Life-Daten viele Testkomprimierungen durchführen.

Nungut, es zeigte sich das mein Mini-Huffman-RLE Verfahren die Fontdaten ca. 30-60% im Durchschnitt komprimiert, und teilweise sogar weit über 200%.

Dabei ist zu bemerken das die unkomprimierten Daten ja nur 2-16 Kb groß sind und diese Daten per simplen RLE mit 4 Bytes Lookuptable so "stark" zu komprimieren ist schon enorm. Auf alle Fälle ist diese Form der RLE Komprimeirung besser als die Windows Bitmap RLE Komprimierung oder die PNG RLE Komprimierung, das habe ich getestet. Viel wichtiger war aber der Punkt das meine Fontdaten sehr variable Farbtiefen besitzen können, also 1,2,4,8,16,32,64,128,256 Farbenfonts ermöglichen. Bei diesen Anforderungen sind die anderen RLE Verfahren einfach zu kompliziert und erbrachten zu schlechte Kompressionsraten. Desweiteren ist die Dekomprimierung bei meinem RLE enorm effizient und einfach auf Embedded Controllern umzusetzen. Man benötigt auch nur 4 Bytes an zusätzlicher Lokkuptabelle mehr, als bei unkomprimierten 1 zu 1 Bitmapfonts. In fact, die komprimierten Fonts werden durch die eingesparten Speicherzugriffe im Vergleich zu unkomprimierten Fonts sogar noch wesentlich schneller angezeigt. Statt für 32 gleichfarbige Pixel eines 4 Farbfontes 8 Bytes aus dem langsammen Flash zu lesen, werden bei komprimierten Fonts im Bestfall nur 0.5 Bytes aus dem externen Speicher gelesen. Die Durchschnittliche Kompressionsrate für die Fonts die ich benötige betrugt pro Zeichen 60%, also über die Hälfte der Datenmenge wurde eingespart.

Soweit erstmal meine erzielten Resultate.

Gruß Hagen