___ tag123c ___ C ist eine universelle Computerprogrammiersprache, die für Betriebssysteme, Bibliotheken, Spiele und andere Hochleistungsanwendungen verwendet wird. Dieses Tag sollte bei allgemeinen Fragen zur C-Sprache verwendet werden, wie in der Norm ISO 9899: 2011 definiert. Fügen Sie ggf. ein versionsspezifisches Tag wie c99 oder c90 für Fragen zu älteren Sprachstandards hinzu. C unterscheidet sich von C ++ und es sollte nicht mit dem C ++ - Tag kombiniert werden, wenn ein rationaler Grund fehlt.
___ qstnhdr ___ Was ist die effizienteste Bitvektor-Komprimierungsmethode für meinen Anwendungsfall?
___ tag123compression ___ Der Name, der dem Prozess zum Codieren von Daten gegeben wird, sodass er im Vergleich zur ursprünglichen Darstellung eine geringere Anzahl von Bits verwendet.
___ tag123bitmap ___ Der allgemeinere Ausdruck "Pixmap" bezieht sich auf eine Karte von Pixeln, in denen jeder mehr als zwei Farben speichern kann und somit mehr als ein Bit pro Pixel verwendet. Oft wird dafür auch Bitmap verwendet. In einigen Zusammenhängen impliziert der Begriff Bitmap ein Bit pro Pixel, während Pixmap für Bilder mit mehreren Bits pro Pixel verwendet wird.
___ answer4769050 ___
Ich arbeite an einem Projekt in Computerbiologie und ich muss einen Index von Orten speichern, die sich zwischen vielen Sequenzen unterscheiden. Momentan verwende ich einen B + -Baum für diesen Zweck, aber ich denke, dass die Verwendung eines Bitmap-Index für einen solchen Anwendungsfall viel schneller wäre: Nur eine kleine Anzahl von Orten unterscheidet sich zwischen zwei Sequenzen, durchschnittlich 1%, und sie sind nahezu gleichmäßig entlang der Sequenz verteilt; Es scheint also so, als ob es viel Platz für die Bitmap-Indexkomprimierung gibt.
Mein Problem ist, dass ich keine Komprimierungsmethode finden kann, die effizient ist:
- erlaubt schnelles individuelles Bit-Setzen / Unscharfschalten
- erlaubt effiziente Bereichsabfragen über die Bitmap
- erlaubt möglicherweise das schnelle XOR-ing / AND-ing von zwei Indizes
Thx im Voraus für Ihre Vorschläge.
Sie könnten eine einfache Baumdatenstruktur wie folgt verwenden:
%Vor%
Jeder Knoten repräsentiert eine Unteranordnung der großen Bitanordnung, die (2 ^ n) * Größe von (langen) Bits ist, n & gt; = 0. Leaf-Knoten speichern eine rohe Bitmaske in 'Maske', wenn sie sich am unteren Ende des Baums befinden, andernfalls speichern sie 0 in 'Maske'. Auf diese Weise kann ein Blattknoten mit einem 'Masken'-Wert von 0 eine (2 ^ n) * Größe eines (langen) leeren Bereichs im Bit-Array darstellen, so dass Sparse-Bit-Arrays effizient gespeichert werden können.
leftChild und rightChild sind in allen Blattknoten natürlich null. Jeder andere Knoten verfügt über einen Zeiger leftChild und rightChild, und jeder Knoten, der kein Blattknoten ist, hat mindestens einen untergeordneten Knoten mit Maske, in dem Bits festgelegt sind.
Um ein Bit in einem bestimmten Index zu finden:
%Vor%
Wenn Sie die Idee verstehen, sollten Sie den Baum konstruieren und den Rest der Algorithmen entwickeln. Ich habe den Code nicht wirklich getestet, da dies keine vollständige Lösung ist, einige Tippfehler oder ähnliches bleiben. Und ich bin kein Bitmap-Index-Experte, es könnte (wahrscheinlich) ein vorgefertigtes Paket geben, das das besser macht, aber diese Lösung ist einfach und sollte relativ effizient sein. 1% ist vielleicht noch nicht sparsam genug, um dies im Vergleich zu nur einem einfachen Bit-Array zu verbessern (unter der Annahme, dass Longs jeweils 64 Bits speichern, dauert es nicht mehr als 2 Longs, mehr als ein Bit im Durchschnitt zu haben), aber wenn Sparsity erhöht sich darüber hinaus die Raum- und Zeiteinsparungen zeigen.
___ tag123indexing ___ Indizierung von Datenstrukturen ist eine allgemeine Technik, um die Geschwindigkeit von Datensuchen zu verbessern.
___ tag123bitmanipulation ___ Die Manipulation einzelner Bits. Verwendete Operatoren können bitweise UND, ODER, XOR, NICHT, Linksverschiebung und Rechtsverschiebung enthalten.
___