Betrachten wir den trivialen Ansatz, der in vielen Fällen optimal sein kann:

Es würde speichern:

• Die Anzahl der Elemente im Bereich (mit 31 Bit, da die Listen in Java auf 2^31 - 1 Elemente begrenzt sind).
• Es folgt für jeden Index ein Bit, das anzeigt, ob das Element im Set vorhanden ist oder nicht.

Dies ist die Implementierung, die die erste Version des fraktalen Bildkompressors hatte, um die Daten aus den Splits und Merges der Triangulationen zu speichern.

Obwohl es nicht optimal war, da die Iterationen der Splits fortschritten, verringerte sich die Anzahl der zu speichernden Elemente und wurde zu einem sehr kleinen Prozentsatz des Gesamtvolumens, in diesem Fall kann die triviale Kodierung wesentlich verbessert werden.

Nun ist das Ziel, diese triviale Kodierung zu verbessern, um zu sehen, ob eine komprimiertere Kodierung in Bezug auf die Anzahl der verwendeten Bits erhalten werden kann.

Erstes Konzept : Wenn die Anzahl der Elemente im Set viel kleiner ist als die Größe des Bereichs, können wir die vorhandenen Indizes speichern.

In diesem Fall wäre die Verwendung:

• 31 Bit für die Anzahl der Elemente im Bereich.
• 31 Bit für die Anzahl der im Set vorhandenen Elemente.
• 31 Bit * die Anzahl der Elemente, die im Set vorhanden sind.

Zweiter Ansatz . Wir verbessern die Anzahl der Bits pro gespeichertem Element:

• 31 Bit für die Anzahl der Elemente im Bereich. Die Anzahl der Bits des größten Elements im Bereich ( numBitsElem ) würde berechnet werden.
• 5 Bits zu speichern numBitsElem ........................................................................................................Wenn also die Anzahl der Elemente im Bereich 1023 wäre, würde eine 10 in diesen 5 Bits gespeichert werden.
• numBitsElem Bits, um die Anzahl der Elemente im Set zu speichern.
• numBitsElem Bits * die Anzahl der Elemente, die im Set vorhanden sind.

Nach und nach nähern wir uns einer besseren Kodierung...

Dritte Annäherung . Wir erkennen, dass, wenn wir den Satz in aufsteigender Reihenfolge sortieren, die Deltas (Differenzen zwischen aufeinander folgenden Elementen) wahrscheinlich mit weniger Bits codiert werden können als ein absolutes Element des Bereichs:

• 31 Bit für die Anzahl der Elemente im Bereich.
• Wir berechnen das kleinste numBitsElem, um ein Element zu kodieren.Wir berechnen auch die Liste der Deltas (Liste der Unterschiede zwischen den aufeinander folgenden Elementen der sortierten Liste der Elemente im Set).Und schließlich berechnen wir auch numBitsDelta
• 5 Bits zu speichern numBitsElem ........................................................................................................
• 5 Bits zu speichern numBitsDelta ........................................................................................................
• numBitsElem Bits, um die Anzahl der Elemente im Set zu speichern.
• numBitsDelta Bits * die Anzahl der Elemente im Set.

Nun, es scheint, dass wir bereits die optimale Kodierung erreichen, richtig?...

Machen wir weiter...

Vierte Annäherung . Wir konzentrieren uns auf die Tatsache, dass es eine viel größere Anzahl von kleineren Deltas, und vielleicht nur ein paar viel größere, die brechen die ` numBitsDelta == Einzelnachweise ==

Unter diesen Bedingungen könnten wir eine ` numOptimumBitsDelta ‚ kleiner als das Maximum numMaxBitsDelta `, die wiederum kleiner oder gleich ist ` numBitsElem == Einzelnachweise ==

Aber wie kodieren wir ein Delta-Element, das ` übersteigt numOptimumBitsDelta - Nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein, nein.

Nun... da Deltas niemals 0 sein werden (es gibt keine wiederholten Elemente in einem Set), können wir den Wert 0 verwenden, um anzuzeigen, dass es ein besonderer Wert ist.

Und dass 0 würde von dem Wert des Deltas gefolgt werden, aber kodiert dieses Mal mit ` numMaxBitsDelta == Einzelnachweise ==Die Gesamtzahl der Bits kann wie folgt berechnet werden:

• 31 Bit für die Anzahl der Elemente im Bereich. Wir berechnen die kleinsten numBitsElem um ein Element kodieren zu können. Wir berechnen auch die Liste der Deltas (Liste der Unterschiede zwischen den aufeinander folgenden Elementen der geordneten Liste der Elemente im Set).
• 31 Bit, um die Anzahl der Elemente im Set zu speichern.
• 5 Bits zu speichern numOptimumBitsDelta ........................................................................................................
• 5 Bits zu speichern numMaxBitsDelta ........................................................................................................
• numOptimumBitsDelta Bits * die Anzahl der Elemente im Set.
• numMaxBitsDelta Bits * die Anzahl der Deltas, die überschreiten numOptimumBitsDelta ........................................................................................................

Haben wir schon die optimale Codierung erreicht?

Fünfte Annäherung Nun, da wir das alles schon programmiert haben...Wir könnten über die komplementäre Situation nachdenken...Wäre es möglich, dass die Kodierung der Ergänzung des Sets mit dem gleichen Algorithmus zu mehr komprimierten Ergebnissen führen würde?

Die Ergänzung des Satzes wird als ein anderer Satz verstanden, der vom Original getrennt ist, dessen Verbindung mit dem ursprünglichen Satz der gesamte Bereich ist.

Das heißt, das komplementäre Set hätte alle Elemente des Bereichs fehlen im Original-Set, und keiner von denen im Original-Set.

Die Schönheit ist, dass aus einem Satz, es ist sehr einfach, die komplementäre Satz zu erhalten, und daher könnten wir die ursprüngliche Satz erhalten, nachdem die komplementäre kodiert.

Die offensichtliche Anwendung ist ein Satz, der alle Elemente des Bereichs außer einem, oder ein paar...

Nun... wenn wir nur die abwesenden lagern (das Komplementärset), könnte es in einer viel kleineren Größe gelagert werden, oder?

Die Kodierung in diesem Fall könnte so sein:

• 31 Bit für die Anzahl der Elemente im Bereich. Wir berechnen die kleinsten numBitsElem um ein Element zu kodieren. Wir berechnen auch die Liste der Deltas (Liste der Unterschiede zwischen den aufeinander folgenden Elementen der geordneten Liste der Elemente im Set).
• 1 Bit, um zu speichern, ob wir das Original-Set, oder die Ergänzung zu speichern.Das ist das Extra.
• 31 Bit, um die Anzahl der Elemente im Set zu speichern.
• 5 Bits zu speichern numOptimumBitsDelta ........................................................................................................
• 5 Bits zu speichern numMaxBitsDelta ........................................................................................................
• numOptimumBitsDelta Bits * die Anzahl der Elemente im Set.
• numMaxBitsDelta Bits * die Anzahl der Deltas, die überschreiten numOptimumBitsDelta , in den Positionen, wo sie erscheinen.

Nun... jetzt reden wir.

Also, da steckte ich fest... aber ich bin mir bewusst, dass wenn all diese Wunder getan werden können, was nicht durch die Suche nach anderen Mustern getan werden konnte, oder einfach mit einem verlustfreien Kompressor, wie Reißverschluss oder 7z...

Das muss warten, auf dem Backburner für das nächste Mal...

Der Decoder ist trivial... Sie müssen nur die Parameter des Bitstreams lesen und die notwendigen Aktionen anwenden, um den ursprünglichen Satz zu erhalten.

Ich werde mich auf den Encoder-Algorithmus konzentrieren und versuchen, die Anzahl der Operationen zu optimieren.

Die Idee ist es, die Anzahl der Bits, die es mit jeder Art von Codierung besetzen würde, vorzukalkulieren und das Optimum zu halten.

Da es keinen Sinn machen würde, Delta-Kodierung zu verwenden, wenn es am Ende mehr als die triviale Kodierung einbezieht.

Also berechnen wir, was die triviale Kodierung bedeuten würde.

Und auch... wir berechnen die optimalen Parameter der aufwendigeren Delta-Kodierung, die wir im vorherigen Abschnitt erklärt haben.

Dies würde durch die Berechnung der Anzahl der Bits erfolgen, die die Kodierung für die Parameterkombinationen belegt:

• numOptimumBitsDelta
• numMaxBitsDelta Das ist behoben.
• Verwenden Sie das Original oder Komplementär-Set.

Um eine übermäßige Rechenkomplexität bei der Suche nach optimalen Parametern zu vermeiden (die durch die Verwendung großer Bereiche benachteiligt werden könnten), tun wir folgendes:

Der komplementäre Satz wird nur einmal berechnet und gespeichert.

Die Delta-Listen des Original-Sets und des Komplementär-Sets werden nur einmal berechnet und gespeichert.

Um die Anzahl der Bits zu berechnen, die durch die verschiedenen Parameterkombinationen erzeugt werden:

Wir berechnen das Histogramm der Anzahl der Bits in den Delta-Listen nur einmal. Basierend auf diesem Histogramm ist die Berechnung der Gesamtzahl der Bits einfach und die Rechenkomplexität dieser Berechnungen ist viel geringer als wenn wir "simuliert" Element-für-Element-Kodierung.

Sobald die optimale Parameterkombination für die Delta-Kodierung erreicht ist, wird seine Größe mit der der trivialen Kodierung verglichen, und das Beste aus den beiden wird gewählt.