J'ai un besoin spécial et les préoccupations les plus importantes sont les suivantes:
Voici mon "problème": J'ai besoin de stocker, en mémoire, un grand nombre de matrices de bits très clairsemés. Ces bitsets sont "ajoutés uniquement" et doivent être utilisés principalement pour les intersections. Par énorme, je veux dire aussi élevé que 200 000 bits de bits. P>
La plage doit être comprise entre [0 ... 16 000 000] pour chaque bitset. P>
J'ai rencontré des Testez avec des tableaux "seulement" 10 673 bits contenant des données réelles que j'ai et j'ai obtenu les résultats suivants: p> vu les chiffres concernés, j'ai évidemment besoin d'utiliser un peu compressé Les tableaux et ce n'est pas un problème: il restera facile à traiter avec constaté que les tableaux de bits sont "ajoutés uniquement". P> Les bits de bits de bits qui sont en groupe sont un peu groupés, mais pas totalement. Donc, vous aurez tendance à avoir plusieurs morceaux dans la même zone (mais généralement pas l'un après l'autre, ce qui rendait un peu pas génial pour les bits qui sont allumés). P> Ma question est de quel type de compression utilisera ? P> Maintenant, je ne sais pas si je devrais mettre ma première approche ici ou dans une réponse à ma propre question. P> Fondamentalement, j'ai imaginé un scénario "pire des cas" à l'aide d'un codage très muet: p> 1 bit: Si vous allumez, les 5 bits suivants déterminent le nombre de bits nécessaires pour calculer "Skip", si OFF, optimisation: Les 5 bits suivants déterminent le nombre de bits aussi être pris à la lettre (c'est-à-dire 'ON' ou 'OFF', sans sauter) [Cela ne serait pas basculé sur une fois déterminé à être plus efficace que l'autre représentation, alors quand il frappe, il doit toujours être une optimisation (taille-sage)] p) > li>
5 bits: combien de bits nous pouvons sauter avant le prochain bit sur P> LI>
x bits: skip p> li>
ul> Voici un exemple: un tableau de bits a 3 bits, le premier bit étant au 3 098 137, le second à 3 098 141 et le troisième à 3 098 143. P>
Worst case scenario:
108 913 290 bits needed for the 10 687 very sparse bit arrays
12.9 MB (13 295 KB)
6 Réponses :
Même si elles ne sont pas exactement ce que vous recherchez, il convient de vérifier Judy Arbres . Judy est une bibliothèque fortement optimisée pour les cartes commandées et une configuration est spécialement conçue comme un bitset plutôt que comme une carte. Je ne pense pas que l'intersection est l'une des opérations optimisées de manière nativement optimisée.
L'idée générale est d'utiliser un arbre avec un nombre fixe de bits d'adresses par niveau et de tirer parti de la portée de la portée de chaque niveau. Cela entraîne une mauvaise compression même dans le pire des cas et une performance de requête rapide aussi. Je crois qu'une opération d'intersection serait relativement simple et potentiellement très rapide.
En tout cas, c'est toujours une bonne idée de voler du meilleur!
YUP JUDY Les matrices sont super mais honnêtement, les maths derrière moi sont un peu trop compliqués pour moi :) et Afaict, il est seulement disponible en tant que 20kloc C-écrit Lib: - / Je refuse définitivement que roue :)
Zut, je voulais dire, je suis définitivement pas réinventer que roue :) évidemment :)
Pas besoin de réinventer leur roue, mais le principe de base semble être juste le genre de chose que vous recherchez: très clairsemé et facilement adaptable à écrire une fonction d'intersection rapide.
Je sais que je sais mais ... mais la mise en œuvre de Judy est une base de 20 000 lignes. C'est vraiment l'une des structures de données les plus difficiles à mettre en œuvre jamais écrites :)
Considérant que vous allez faire un tas de tests d'intersection de toute façon, vous devriez peut-être essayer de stocker tous les bitvecteurs en parallèle. Une liste d'entrée de 16 m de 16 m. Chaque entrée de cette liste contient une liste de laquelle des bitvectors d'entrée de 200K a une "1" à cet endroit. On dirait que vous vous attendez à avoir seulement environ 5 bits définis par vecteur d'entrée ou 1M entrées totales? Prenant une mise en oeuvre de la liste liée à l'homme de la paille pour le nombril et les godets, et un pire cas de non-intersections du tout (donc des godets de 1 m avec 1 élément chacun), vous pouviez tout stocker en 32 Mo.
Non Non, la liste que j'ai postée le montre, par exemple: "50% des bitvectors auront [entre 55 et] 67 bits" . Il y aura beaucoup plus de 1 M entrées totales. Avec 200K Bitvectors, je dirais qu'il y aurait, très grossièrement, un total de 100 millions de bits.
Je ne l'ai pas regardé de cette façon, mais maintenant que vous mentionnez de le faire "l'inverse", c'est une garantie que chacun des "étendue" (la gamme de 16 millions) sera utilisée quelques fois. La façon dont vous l'avez formulée, chaque entrée de la liste de 16 m aurait environ 4 à 8 bits.
Aha, je pensais que c'était un total, donc 55k / 10k = 5, mon erreur. Ainsi, aucune raison de faire de la matrice de 16 m rare, chaque entrée a besoin d'une place pour environ 8 identifiants de 18 bits (2 ^ 18> 200k), donc 288 Mo. Semblable à votre estimation.
Un autre problème est que j'ai besoin d'un moyen simple de trouver, par exemple, "tous les bits qui sont sur le tableau de bit numéro 190 834" . Je ne sais pas comment je pourrais faire cela rapidement si je devais analyser la liste d'entrée de 16 m.
Un peu similaire au pire cas que j'ai eu. Mais je suis sûr que ça va être assez plus bas une fois que je l'applique :) Parce que je pense que la commutation entre rle ( Skip 'x' bits ) et lecture-x-bits - comme -L'est-ce que fonctionnera bien sur mon jeu de données (à voir mais hey). Aussi je suis à peu près sûr que je n'aurai pas souvent besoin de 24 bits pour stocker le «Skip» (et évidemment, lorsque je progresse dans les données, de moins en moins de bits sera nécessaire pour le «sauter», alors j'ai vraiment pris un pire Scénario de cas-presque impossible :)
Vous pouvez utiliser un arbre binaire pour la matrice de bit. Dites, vous avez un tableau avec une plage de [m..n]. Stockez-la de manière:
Choisissez un certain nombre de codage pour [0 ... Taille de RAM], comme Fibonacci, Golomb ou Code Riz (vous pouvez choisir une représentation la plus appropriée après avoir profilé votre programme avec des données réelles). P >
Dans ce cas, si des limites sont courantes, les opérations d'intersection Un syndicat sont des récursions triviales: p>
Intersection: P>
Cet algorithme peut traiter avec des bits (si vous en avez besoin pour être le plus compact) et des octets / mots (si les opérations de bits sont si lentes). P>
Vous pouvez également ajouter des codages spécifiques pour Tableaux avec ensemble de bits, tous les tableaux de taille inférieure à une limite (8 éléments par exemple) pour diminuer le niveau de récursivité. P>
L'inconvénient est que sans que certains hacks ajoutent / suppression de l'élément à / de la matrice est une opération complexe. (comme complexe que les opérations d'intersection / union). p>
Par exemple, une matrice avec un seul jeu de bits 0xab doit être stocké dans une matrice de 0..0XFF comme (pseudocode pour): P>
010 00101 1 00100 010 000010011 000010010 2 5 1 4 2 19 18 (distance code explained)
+1, bonne réponse aussi. Je ne sais pas encore quelle route je vais aller, mais cela donne à la nourriture pour les pensées :)
Merci. De plus, je peux recommander de regarder à quel point divers algorithmes de compression sonore (MP2, AAC, etc.). Ils traitent avec des matrices rares (comme 0, 0, 0, 1, 0, -1, 1, 0, 0, 0, 0, 0, 0, 2, 0, 1, 0) lors de la compression des spectres haute fréquence.
Vous n'avez pas dit quel langage de programmation que vous souhaitez utiliser. On dirait que tu ne veux pas de Judy parce que c'est "C-seulement" ... Si vous utilisez c #, vous pouvez utiliser mon Compact Patricia Trie à la place. Est presque 4500 loc (commenté) et utilise des idées similaires à Judy, mais la taille et la vitesse de chaque trie ne sont pas idéales en raison des limitations de .NET. Il n'est pas optimisé pour calculer les intersections non plus, mais un tel algorithme pourrait être ajouté. L'article sur CP Traies n'apprécie pas ce point, mais il peut stocker des ensembles (des tableaux de bits clairsemés) beaucoup plus compact que les dictionnaires (les graphiques de l'article montrent la taille et la vitesse des dictionnaires, pas des ensembles).
Le meilleur cas est un groupe dense de bits. Avec une occupation de 50% (tous les autres jeux de bits), il nécessite moins de 8 bits par clé (moins de 4 bits par entier). (Correction: moins de 8 bits, pas plus.)
Si vous n'avez besoin que d'une représentation approximative des données, utilisez un Filtre de floraison .
Au fait, que voulez-vous dire par" ANNECENNE UNIQUEMENT "? Cela signifie-t-il que vous ajoutez uniquement des clés ou que chaque touche que vous ajoutez est supérieure aux touches que vous avez ajoutées avant?
Mise à jour : puisque vous ne devez ajouter que des clés plus importantes, vous devriez Probablement concevoir un algorithme spécial juste pour votre cas. IMO, lors de la conception d'un algorithme personnalisé, vous devez le rendre aussi simple que possible. Voici donc mon idée qui suppose que les clés de différents bitsets sont non corrélées (il n'ya donc aucun avantage à tenter de tenter de comprimer les données entre différents bitsets): Un bitset est représenté par un tableau trié de fentes 32 bits . Parce que c'est trié, vous pouvez utiliser la recherche binaire pour trouver des clés. Chaque emplacement consiste en un "préfixe" 24 bits et de 8 bits de "drapeaux". Chaque emplacement représente une région de 8 clés. Les "drapeaux" vous disent que les 8 clés de la région sont présentes dans le bitset et le "préfixe" vous indique quelle région dont nous parlons, en spécifiant des bits 3 à 26 de la clé. Par exemple, si les bits suivants sont "1" dans le bitset: ... puis le bitset est représenté par une matrice de 4 emplacements (16 octets): < / p> La première fente représente 1, 3, 4 (remarquez que les bits 1, 3 et 4 sont définis dans le nombre 0x15); La deuxième fente représente 1094 (136 * 8 + 6); La troisième emplacement représente 8001, 8002 et 8007; La quatrième emplacement représente 8009. Cela a-t-il un sens? Je ne sais pas si cela est aussi compact que votre idée. Mais je pense que vous aurez des requêtes plus rapides et des modifications plus rapides, et il sera assez facile à mettre en œuvre.
+1, belle réponse. Je ne sais pas encore beaucoup sur Patricia Trie (en plus du nom que j'ai déjà entendu), lira. Yup, par "ANNEZ UNIQUEMENT" Je veux dire que lorsque "l'étendue" (la plage) augmente, certains des tableaux de bits (typiquement 4 à 8) auront un peu réglé à la fin du bit déployer. Donc, je n'ai jamais "insert" un peu au milieu d'un tableau de bits. C'est donc vraiment un cas particulier que je pense que les choses facilitent les choses.
Je suppose que par "annexer uniquement", je veux dire que je n'aijoute que des clés et que la clé est également toujours supérieure à la clé que j'ai ajoutée auparavant.
J'aimerais pouvoir donner plus que +1, votre article a l'air excellent, la mise en œuvre de votre C # de "CPT". En fait, la langue que je suis après est probablement Java, mais je devra peut-être avoir un moyen facile de le porter à la fois c # et objectif - c ... Donc, je préfère avoir quelque chose de relativement facile. Mais votre Compact Patricia Trie a l'air incroyable. Une fois encore, mon cas est très spécial: la plupart de mes tableaux de bits n'ont même pas 0,5% de chaque jeu. C'est donc vraiment Super Sparse .
Impossible d'utiliser le filtre de floraison BTW, nécessite une représentation exacte des données.
Vous pourriez être intéressé par des diagrammes de décision binaire (BDD) et un diagramme de décision binaire plus précisément supprimé (ZBDD).
Ils sont utilisés pour représenter des ensembles de manière compressée. Contrairement aux autres formes comprimées, les opérations (telles que les intersections définies ou les insertions d'éléments - votre "annexe seulement"?) Travailler directement sur la forme compressée.
J'ai édité un peu ma question pour clarifier la "annexe que la chose". Fondamentalement, les tableaux de bits augmentent toujours (jusqu'à 16 000 000 bits maximum) et je ne modifie toujours que la fin de celui-ci, il est donc un peu facile de travailler directement sur la forme compressée.
Vous pouvez regarder dans des bitmaps compressés. Une stratégie commune consiste à utiliser le codage d'exécution aligné par des mots.
C ++ Mise en œuvre:
https://github.com/lemire/ewahboolarray
Mise en œuvre Java:
https://github.com/lemire/javaewah
Référence:
Daniel Lemire, Owen Kaser, Kamel Aouiche, le tri améliore les index bitmap alignés par mot. Ingénierie des données et des connaissances 69 (1), pages 3-28, 2010. http://arxiv.org/abs/0901.3751
Notez que les commentaires sur ré-inventer la roue peuvent être envoyés à / dev / null : Si seulement pour le Math / Défi derrière celui-ci, je veux mettre en œuvre cela moi-même. Et de toute façon, je serais très surpris de trouver une roue pouvant traiter de 200 000 "ANNEX-UNIQUEMENT" des tableaux de bit en mémoire :) Mais si vous en avez un, la mécanique derrière elle m'intéresse beaucoup :)
Il existe une limite théorique sur la densité de codage: avec une matrice d'éléments n, n dont le nombre minimum de bits à encoder serait -n * log2 (n / n) - (N-N) * log (n / n) *. Pour votre matrice dans laquelle 53153 sur 16M sont définis, cela serait de 514 kbits et pour 4992 bits set - 65 kbits. Et plus près de votre mémoire à cette limite, le codage plus complexe que vous devez choisir.
@Vovanium, je pense que vous avez laissé de côté le contexte nécessaire pour votre limite théorique (comme, une sorte d'hypothèse statistique sur la distribution des bits étant définie?)
J'ai pensé à une distribution de bits uniformes (i. Tous les 1 ont une probabilité constante p = n / n). La limite exacte pour N bits Ensemble de N est log2 [C (N, N)], qui n'est qu'un nombre de bits en nombre de combinaisons et est légèrement inférieur. Mais pour la grande n, cette formule est difficile à calculer.
"Structures de données succinctes" serait un mot clé pertinent pour toute personne intéressée par cette question