Welche Alternativen gibt es zu einem Bit-Array?

StackOverflow https://stackoverflow.com/questions/36106

Frage

Ich habe eine Anwendung zum Abrufen von Informationen, die Bit-Arrays in der Größenordnung von 10 Millionen Bits erstellt.Die Anzahl der „gesetzten“ Bits im Array variiert stark, von „vollständig gelöscht“ bis „vollständig gesetzt“.Derzeit verwende ich ein einfaches Bit-Array (java.util.BitSet), sodass jedes meiner Bit-Arrays mehrere Megabyte benötigt.

Mein Plan ist es, die Kardinalität des ersten zu untersuchen N Bits und treffen Sie dann eine Entscheidung darüber, welche Datenstruktur für den Rest verwendet werden soll.Offensichtlich eignen sich einige Datenstrukturen besser für Arrays mit sehr spärlichen Bits, andere dagegen, wenn etwa die Hälfte der Bits gesetzt ist (wenn die meisten Bits gesetzt sind, kann ich die Negation verwenden, um sie als spärlich besetzte Menge von Nullen zu behandeln).

  • Welche Strukturen könnten in jedem Extrem gut sein?
  • Gibt es welche in der Mitte?

Hier ein paar Einschränkungen bzw. Hinweise:

  1. Die Bits werden nur einmal und in Indexreihenfolge gesetzt.
  2. Ich brauche 100 % Genauigkeit, daher ist so etwas wie ein Bloom-Filter nicht gut genug.
  3. Nachdem der Satz erstellt wurde, muss ich in der Lage sein, die „gesetzten“ Bits effizient zu durchlaufen.
  4. Die Bits sind zufällig verteilt, sodass Algorithmen zur Lauflängenkodierung wahrscheinlich nicht viel besser sind als eine einfache Liste von Bitindizes.
  5. Ich versuche, die Speichernutzung zu optimieren, aber die Geschwindigkeit bleibt bestehen manche Gewicht.

Etwas mit einer Open-Source-Java-Implementierung ist hilfreich, aber nicht unbedingt notwendig.Mich interessieren mehr die Grundlagen.

War es hilfreich?

Lösung

Es sei denn, die Daten sind wirklich zufällig Und hat eine symmetrische 1/0-Verteilung, dann wird dies einfach zu einem verlustfreien Datenkomprimierungsproblem und ist sehr analog zur CCITT-Gruppe-3-Komprimierung, die für Schwarzweiß verwendet wird (d. h.:Binär) FAX-Bilder.CCITT-Gruppe 3 verwendet ein Huffman-Codierungsschema.Im Fall von FAX verwenden sie einen festen Satz von Huffman-Codes, aber für einen bestimmten Datensatz können Sie für jeden Datensatz einen bestimmten Satz von Codes generieren, um das erreichte Komprimierungsverhältnis zu verbessern.Solange Sie, wie Sie angedeutet haben, nur nacheinander auf die Bits zugreifen müssen, ist dies ein ziemlich effizienter Ansatz.Der wahlfreie Zugriff würde einige zusätzliche Herausforderungen mit sich bringen, aber Sie könnten wahrscheinlich einen binären Suchbaumindex für verschiedene Offsetpunkte im Array generieren, der es Ihnen ermöglichen würde, in die Nähe der gewünschten Position zu gelangen und von dort aus hineinzugehen.

Notiz:Das Huffman-Schema funktioniert auch dann noch gut, wenn die Daten zufällig sind, solange die 1/0-Verteilung nicht vollkommen gleichmäßig ist.Das heißt, je weniger gleichmäßig die Verteilung ist, desto besser ist das Komprimierungsverhältnis.

Wenn schließlich die Bits wirklich zufällig mit einer gleichmäßigen Verteilung sind, dann, nun ja, entsprechend Herr.Claude Shannon, werden Sie es mit keinem Schema in nennenswertem Umfang komprimieren können.

Andere Tipps

Ich würde dringend die Verwendung einer Bereichskodierung anstelle der Huffman-Kodierung in Betracht ziehen.Im Allgemeinen kann die Bereichskodierung Asymmetrie effektiver ausnutzen als die Huffman-Kodierung, aber das gilt insbesondere dann, wenn die Alphabetgröße so klein ist.Wenn das „native Alphabet“ einfach aus Nullen und Einsen besteht, kann Huffman tatsächlich nur durch die Kombination dieser Symbole eine Komprimierung erreichen – und genau das wird durch die Bereichskodierung effektiver erreicht.

Vielleicht zu spät für Sie, aber es gibt eine sehr schnelle und speichereffiziente Bibliothek für spärliche Bit-Arrays (verlustfrei) und andere Datentypen, die auf Versuchen basieren.Ansehen Judy-Arrays

Danke für die Antworten.Folgendes werde ich versuchen, um dynamisch die richtige Methode auszuwählen:

Ich werde zuerst alles einsammeln N Treffer in einem herkömmlichen Bitarray und wählen Sie basierend auf der Symmetrie dieses Beispiels eine von drei Methoden aus.

  • Wenn die Probe stark asymmetrisch ist, speichere ich die Indizes einfach in den festgelegten Bits (oder vielleicht den Abstand zum nächsten Bit) in einer Liste.
  • Wenn die Probe sehr symmetrisch ist, werde ich weiterhin ein herkömmliches Bit -Array verwenden.
  • Wenn die Probe mäßig symmetrisch ist, verwende ich eine verlustfreie Komprimierungsmethode wie Huffman -Codierung vorgeschlagen von Inscitekjeff.

Die Grenzen zwischen den asymmetrischen, moderaten und symmetrischen Bereichen hängen von der Zeit ab, die die verschiedenen Algorithmen im Verhältnis zum benötigten Platz benötigen, wobei der relative Wert von Zeit gegenüber Raum ein einstellbarer Parameter wäre.Der für die Huffman-Codierung benötigte Platz ist eine Funktion der Symmetrie, und ich werde dies durch Tests profilieren.Außerdem werde ich alle drei Methoden testen, um den Zeitbedarf meiner Implementierung zu ermitteln.

Es ist möglich (und das hoffe ich tatsächlich), dass die mittlere Komprimierungsmethode immer besser ist als die Liste oder das Bit-Array oder beides.Vielleicht kann ich dies fördern, indem ich einen Satz Huffman-Codes wähle, die für höhere oder niedrigere Symmetrie angepasst sind.Dann kann ich das System vereinfachen und einfach zwei Methoden verwenden.

Noch ein Komprimierungsgedanke:

Wenn das Bit-Array nicht verrückt lang ist, können Sie versuchen, das anzuwenden Burrows-Wheeler-Transformation bevor Sie eine Wiederholungskodierung wie Huffman verwenden.Eine naive Implementierung würde O(n^2) Speicher während der (De-)Komprimierung und O(n^2 log n) Zeit zum Dekomprimieren beanspruchen – es gibt mit ziemlicher Sicherheit auch Abkürzungen.Wenn Ihre Daten jedoch überhaupt eine sequentielle Struktur haben, sollte dies der Huffman-Codierung wirklich helfen.

Sie können diese Idee auch jeweils auf einen Block anwenden, um die Zeit-/Speichernutzung praktischer zu gestalten.Wenn Sie jeweils nur einen Block verwenden, können Sie möglicherweise den Großteil der Datenstruktur immer komprimiert halten, wenn Sie nacheinander lesen/schreiben.

Eine einfache verlustfreie Komprimierung ist der richtige Weg.Um es durchsuchbar zu machen, müssen Sie relativ kleine Blöcke komprimieren und einen Index in einem Array der Blöcke erstellen.Dieser Index kann den Bit-Offset des Startbits in jedem Block enthalten.

Schneller kombinatorischer Beweis, dass man nicht wirklich viel Platz sparen kann:

Angenommen, Sie haben eine beliebige Teilmenge von n/2 Bits, die auf 1 von insgesamt n Bits gesetzt ist.Sie haben (n wählen Sie n/2) Möglichkeiten.Benutzen Stirlings Formel, das ist ungefähr 2^n / sqrt(n) * sqrt(2/pi).Wenn jede Möglichkeit gleich wahrscheinlich ist, gibt es keine Möglichkeit, wahrscheinlichere Entscheidungen in kürzeren Darstellungen darzustellen.Wir benötigen also log_2 (n wähle n/2) Bits, was etwa n - (1/2)log(n) Bits entspricht.

Das ist keine sehr gute Speicherersparnis.Wenn Sie beispielsweise mit n=2^20 (1 MB) arbeiten, können Sie nur etwa 10 Bits einsparen.Es lohnt sich einfach nicht.

Abgesehen davon scheint es auch sehr unwahrscheinlich, dass wirklich nützliche Daten wirklich zufällig sind.Falls Ihre Daten strukturierter sind, gibt es wahrscheinlich eine optimistischere Antwort.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top