Ich habe eine Information Retrieval-Anwendung, die Bit-Arrays in der Größenordnung von 10s Millionen Bits erstellt. Die Anzahl der "gesetzten" Bits in dem Array variiert stark, von allen klaren bis zu allen gesetzten. Derzeit verwende ich ein geradliniges Bit-Array ( java.util.BitSet ), so dass jedes meiner Bit-Arrays mehrere Megabytes benötigt.
Mein Plan ist es, die Kardinalität der ersten N Bits zu betrachten und dann eine Entscheidung darüber zu treffen, welche Datenstruktur für den Rest verwendet werden soll. Offensichtlich sind einige Datenstrukturen für sehr spärliche Bit-Arrays und andere, wenn ungefähr die Hälfte der Bits gesetzt ist (wenn die meisten Bits gesetzt sind, kann ich die Negation verwenden, um sie als eine spärliche Menge von Nullen zu behandeln).
Hier sind ein paar Einschränkungen oder Hinweise:
Etwas mit einer Open-Source-Java-Implementierung ist hilfreich, aber nicht unbedingt notwendig. Ich interessiere mich mehr für die Grundlagen.
Wenn die Daten nicht wirklich zufällig sind und eine symmetrische 1/0-Verteilung haben, wird dies einfach zu einem verlustfreien Datenkomprimierungsproblem und ist der CCITT-Gruppenkomprimierung 3 sehr ähnlich verwendet für schwarz-weiß (dh: binäre) FAX-Bilder. CCITT-Gruppe 3 verwendet ein Huffman-Codierschema. Im Fall von FAX verwenden sie einen festen Satz von Huffman-Codes, aber für einen gegebenen Datensatz können Sie einen spezifischen Satz von Codes für jeden Datensatz erzeugen, um das erreichte Kompressionsverhältnis zu verbessern. Solange Sie nur sequentiell auf die Bits zugreifen müssen, wie Sie es angedeutet haben, wird dies ein ziemlich effizienter Ansatz sein. Zufälliger Zugriff würde einige zusätzliche Herausforderungen erzeugen, aber Sie könnten wahrscheinlich einen binären Suchbaum-Index für verschiedene Offset-Punkte im Array generieren, der es Ihnen ermöglicht, sich der gewünschten Position zu nähern und von dort aus zu laufen.
Hinweis : Das Huffman-Schema funktioniert auch dann gut, wenn die Daten zufällig sind, solange die 1/0-Verteilung nicht perfekt gleichmäßig ist. Das heißt, je weniger gleichmäßig die Verteilung ist, desto besser ist das Kompressionsverhältnis.
Schließlich, wenn die Bits wirklich zufällig mit einer geraden Verteilung sind, dann, nun, nach Mr. Claude Shannon , du wirst nicht in der Lage sein, es mit irgendeinem Schema zu komprimieren.
Ich würde stark darüber nachdenken, eine Bereichscodierung anstelle der Huffman-Codierung zu verwenden. Im Allgemeinen kann die Entfernungscodierung die Asymmetrie effektiver ausnützen als die Huffman-Codierung, aber dies ist insbesondere dann der Fall, wenn die Alphabetgröße so klein ist. In der Tat, wenn das "native Alphabet" einfach 0s und 1s ist, ist der einzige Weg, wie Huffman überhaupt Kompression bekommen kann, die Kombination dieser Symbole - was genau die Entfernungscodierung ist, effektiver.
Vielleicht zu spät für Sie, aber es gibt eine sehr schnelle und speichereffiziente Bibliothek für Sparse-Bit-Arrays (verlustfrei) und andere Datentypen, die auf Versuchen basieren. Schau dir Judy-Arrays
anDanke für die Antworten. Dies ist, was ich für die dynamische Auswahl der richtigen Methode versuchen werde:
Ich sammle alle ersten N Treffer in einem konventionellen Bit-Array und wähle eine von drei Methoden, basierend auf der Symmetrie dieses Samples.
Die Grenzen zwischen den asymmetrischen, moderaten und symmetrischen Regionen hängen von der Zeit ab, die die verschiedenen Algorithmen benötigen, die gegen den benötigten Raum ausgewogen sind, wobei der relative Wert von Zeit gegen Raum ein einstellbarer Parameter wäre. Der Platz, der für die Huffman-Codierung benötigt wird, ist eine Funktion der Symmetrie, und ich werde das beim Testen profilieren. Außerdem werde ich alle drei Methoden testen, um die Zeitanforderungen meiner Implementierung zu bestimmen.
Es ist möglich (und eigentlich hoffe ich), dass die Methode der mittleren Komprimierung immer besser ist als die Liste oder das Bit-Array oder beides. Vielleicht kann ich dies fördern, indem ich eine Reihe von 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 Kompressionsgedanke:
Wenn das Bit-Array nicht verrückt ist, können Sie versuchen, die Burrows-Wheeler-Transformation anzuwenden, bevor Sie eine verwenden Wiederholungscodierung, wie Huffman. Eine naive Implementierung würde O (n ^ 2) Speicher während der (De-) Komprimierung und O (n ^ 2 log n) Zeit für die Dekomprimierung benötigen - es gibt fast sicher auch Shortcuts. Aber wenn Ihre Daten überhaupt eine sequenzielle Struktur aufweisen, sollte dies der Huffman-Codierung wirklich helfen.
Sie können diese Idee auch auf jeweils einen Block anwenden, um die Verwendung von Zeit / Speicher praktischer zu gestalten. Wenn Sie zu einem bestimmten Zeitpunkt einen Block verwenden, können Sie immer den größten Teil der Datenstruktur komprimieren, wenn Sie sequenziell lesen / schreiben.
Schneller kombinatorischer Beweis, dass Sie nicht viel Platz sparen können:
Angenommen, Sie haben eine beliebige Teilmenge von n / 2 Bits, die auf 1 von insgesamt n Bits gesetzt sind. Sie haben (n wählen n / 2) Möglichkeiten. Mit der Stirling-Formel beträgt diese ungefähr 2 ^ n / sqrt (n) * sqrt (2 / pi). Wenn jede Möglichkeit gleich wahrscheinlich ist, gibt es keine Möglichkeit, kürzeren Darstellungen eine wahrscheinliche Auswahl zu geben. Also brauchen wir log_2 (n wähle n / 2) Bits, was ungefähr n - (1/2) log (n) Bits ist.
Das ist keine sehr gute Ersparnis an Speicher. Wenn Sie beispielsweise mit n = 2 ^ 20 (1 Megabyte) arbeiten, können Sie nur etwa 10 Bit speichern. Es ist es einfach nicht wert.
Nachdem all das gesagt wurde, 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.
Tags und Links data-structures information-retrieval