J'ai le problème très courant de créer un index pour une gamme de chaînes dans les disques. En bref, je dois stocker la position de chaque chaîne dans la représentation dans le disque. Par exemple, une solution très naïve serait un tableau d'index comme suit:
uint64 idx [] = {0, 20, 500, 1024, ..., 103434};
qui dit que la première chaîne est en position 0, la seconde à la position 20, la troisième à la position 500 et la nième en position 103434.
Les positions sont toujours non négatives 64 bits entiers dans l'ordre séquentiel. Bien que les chiffres puissent varier selon toute différence, je m'attends à ce que la différence typique soit à l'intérieur de la plage de 2 ^ 8 à 2 ^ 20. Je m'attends à ce que cet indice soit mpl'ed en mémoire et les positions seront accessibles au hasard (assumer la distribution uniforme).
Je pensais à écrire mon propre code pour faire une sorte de blocage de blocage de bloc de blocage ou autre codage plus sophistiqué, mais il y a tellement de compromis différents entre le codage / la vitesse de décodage et l'espace que je préférerais obtenir une bibliothèque de travail comme un point de départ et peut-être même se contenter de quelque chose sans aucune personnalisation.
Toute astuce? Une bibliothèque C serait idéale, mais un C ++ vous permettrait également de gérer quelques points de repère initiaux.
Quelques détails supplémentaires si vous suivez toujours. Ceci sera utilisé pour construire une bibliothèque similaire à CDB ( http://cr.yp.to/cdb /cdbmake.html ) Sur le dessus de la bibliothèque CMPH ( http://cmph.sf.net ) . En bref, il s'agit pour une grande carte associative basée sur un disque en lecture seule avec un petit index en mémoire.
Comme il s'agit d'une bibliothèque, je n'ai pas de contrôle sur l'entrée, mais le cas d'utilisation typique que je souhaite optimiser avoir des millions de centaines de valeurs, la taille moyenne de la valeur dans les quelques plages de kilo-octets et une valeur maximale à 2 ^ 31 .
Pour l'enregistrement, si je ne trouve pas une bibliothèque prête à être utilisée, j'ai l'intention d'implémenter le codage Delta en blocs de 64 entiers avec les octets initiaux spécifiant le décalage du bloc jusqu'à présent. Les blocs eux-mêmes seraient indexés avec un arbre, me donnant O (log (n / 64)) heure d'accès. Il y a beaucoup trop d'autres options et je préférerais ne pas les discuter. Je suis vraiment impatient d'utiliser le code plutôt que des idées sur la manière de mettre en œuvre le codage. Je serai heureux de partager avec tout le monde ce que j'ai fait une fois que je l'ai travaillé.
J'apprécie votre aide et laissez-moi savoir si vous avez des doutes.
6 Réponses :
Qu'est-ce que vous essayez exactement de compresser? Si vous envisagez de l'espace total de l'index, cela vaut-il vraiment la peine d'économiser l'espace?
Si oui, une chose que vous pourriez essayer est de couper l'espace en deux et rangez-la en deux tables. Premiers magasins (Ut Ut Ut, index de démarrage, longueur, pointeur sur la deuxième table) et la seconde stockerait (index, bassin uint).
Pour la recherche rapide, les indices seraient mis en œuvre à l'aide de quelque chose comme B + arbre . < / p>
Vous avez deux exigences conflictuelles:
La deuxième exigence est très susceptible d'imposer une longueur fixe pour chaque élément.
Bien que je ferai un accès aléatoire dans ces données, cela n'a pas nécessairement besoin d'être O (1). Par exemple, comprimer les nombres en blocs contenant 64 valeurs chacun et maintenir un arbre pour trouver quel bloc à décompresser peut me donner une compression significative et un accès suffisant pour le fasat. Comme je l'ai dit, la question concerne davantage de rechercher une bibliothèque avec des algorithmes de codage facilement disponibles tels que le codage Delta, Elias-gamma et probablement la pièce de bloc à jouer. Voir la question Stackoverflow.com/Questtions/523733/compress-sorteD-Entegers et en particulier le commentaire de Simmon pour une autre explication.
Je comprends. C'est est possible mais la maintenance de l'arborescence en mémoire elle-même est relativement coûteuse compte tenu de la petite taille d'éléments.
Vous avez omis des informations critiques sur le nombre de chaînes que vous avez l'intention d'indexer.
Mais étant donné que vous dites que vous vous attendez à ce que la longueur minimum d'une chaîne indexée soit 256, stockez les indices comme 64% les au plus 3% de surcharge. Si la longueur totale du fichier de chaîne est inférieure à 4 Go, vous pouvez utiliser des indices 32 bits et inciter 1,5% de frais généraux. Ces chiffres me suggèrent que si la compression est importante, Si vous voulez essayer une idée sauvage, placez chaque chaîne dans un fichier séparé, tirez-les dans un fichier zip et voyez comment vous pouvez faire avec Plus de données sur le problème seraient les bienvenues:
Le commentaire et la question révisée rend le problème beaucoup plus clair. J'aime votre idée de regroupement et j'essaierais un simple codage Delta, regroupez les Deltas et utilisez un code de longueur variable au sein de chaque groupe. Je ne serais pas filé en 64 comme la taille du groupe, je pense que vous voudrez probablement déterminer que empiriquement.
Vous avez demandé des bibliothèques existantes. Pour le groupement et le delta codant, je doute que vous trouverez beaucoup. Pour les codes d'entier de longueur variable, je ne vois pas beaucoup dans la voie des bibliothèques C, mais vous pouvez trouver des codages de longueur variable dans Perl et python . Il y a une tonne de papiers et de certains brevets sur ce sujet et je soupçonne que vous allez vous retrouver à faire de la vôtre. Mais il y a des codes simples là-bas et vous pourriez donner à l'UTF-8 un try-it-It peut coder les entiers non signés jusqu'à 32 bits, et vous pouvez saisir C code C de Plan 9 et je suis sûr de nombreuses autres sources. zzipplib . Cela ne sera probablement pas génial, mais il est presque nul le travail de votre part.
gzip
Edit
Bonjour Norman, le nombre de cordes est de l'ordre de plusieurs millions de millions et une longueur moyenne serait de 10 km. La longueur maximale est 2 ^ 31. L'ensemble complet des chaînes (les valeurs) ne correspond pas à la mémoire et ils ne peuvent pas être commandés. Plus sur le côté pratique, j'utilise cela pour construire une bibliothèque. Je n'ai donc pas vraiment de contrôle sur l'entrée. Ces chiffres représentent des cas d'utilisation que j'ai vus dans le passé (pages Web).
Yow! Ok, votre édition rend le problème beaucoup plus claire. Si vous trouvez une solution hors de l'étagère, je serai très impressionné. J'ai ajouté quelques liens avec ma réponse.
J'ai fait quelque chose de similaire il y a des années pour un moteur de recherche en texte intégral. Dans mon cas, chaque mot indexé a généré un enregistrement composé d'un numéro d'enregistrement (ID de document) et d'un numéro de texte (il pourrait tout aussi facilement avoir stocké des compensations de mot) qui devaient être comprimées autant que possible. J'ai utilisé une technique de compression Delta qui profitait du fait qu'il y aurait un certain nombre d'occurrences du même mot dans un document, le numéro d'enregistrement n'a donc pas besoin de répéter du tout. Et le mot offset delta conviendrait souvent dans un ou deux octets. Voici le code que j'ai utilisé.
Étant donné que c'est en C ++, le code peut ne pas vous être utile, mais peut être un bon point de départ pour écrire des routines de compressions.
Veuillez excuser la notation hongroise et les numéros de magie Spewn dans le code. Comme je l'ai dit, j'ai écrit cela il y a de nombreuses années: -)
J'utilise fastbit (kesheng wu lbl.gov), il semble que vous ayez besoin de quelque chose de bien, rapide Et maintenant, la Fastbit est donc une amélioration extrêmement concurrente sur la BBC d'Oracle (code bitmap aligné d'octets, BerkeleyDB). Il est facile de configurer et de très bon gernement.
Cependant, étant donné plus de temps, vous voudrez peut-être consulter un code gris Solution, il semble optimal à vos fonctions.
Daniel Lemire possède un certain nombre de bibliothèques pour C / ++ / Java publié sur code.google , j'ai lu sur certains de ses papiers et ils sont assez gentils, plusieurs avancées sur la fixation de la colonne et des approches alternatives pour la réchorquage des colonnes avec des codes gris permutés.
presque oublié, j'ai aussi rencontré Cabinet de Tokyo , bien que je ne pense pas que ce sera bien adapté à Mon projet actuel, je peux le considérer davantage si j'avais su plus loin;), il a un large degré d'interopérabilité,
Cabinet Tokyo est écrit dans le C
langue, et fournie comme API de C,
Perl, Ruby, Java et Lua. Tokyo
L'armoire est disponible sur les plates-formes
qui ont une API conforme à C99 et
POSIX.
Comme vous avez référence à CDB, le Benchmark TC dispose d'un mode TC (plusieurs contraintes opérationnelles de TC pour la variation de Perf) où elle a dépassé le CDB de 10 fois pour la lecture en lecture et 2 fois pour écrire.
En ce qui concerne votre exigence de codage Delta, je suis assez confiant dans BSDIff et c'est la capacité de sortir -Plus de tout système de correctif de contenu File.exe, il peut également avoir des interfaces fondamentales pour vos besoins généraux.
nouvelle application de compression binaire de Google, courgette peut valoir la peine Vérification, au cas où vous avez manqué le communiqué de presse, 10x Diff's Diff's's's de Bsdiff dans le cas d'essai que j'ai vu publié.
Salut randomnickname42, merci pour le pointeur. Ressemble à un candidat très prometteur. Pour l'enregistrement, j'ai également trouvé une bibliothèque similaire ici: code.google.com/p/lemurbitmapindex Je vais donner à la fois un essai.
On dirait qu'il est breveté. FreePatentsOnline.com/6831575.html . Pourrait avoir une importance.
codeforge.lbl.gov/projects/fastbit est un site Dev-site pour la Fastbit, LGPL, Je suppose que ne pas être BSD ou MS-PL peut être un problème, mais le L dans LGPL est un peu de comphert. ;)
Salut randomnickname42, merci pour la modification. Je développe exactement un concurrent réadien pour Tokyocabinet.
courez-vous sur Windows? Si tel est le cas, je recommande de créer le fichier MMAP à l'aide de la solution naïve que vous avez proposé à l'origine, puis de compresser le fichier à l'aide de compression NTLM . Votre code d'application ne connaît jamais le fichier est compressé et le système d'exploitation est la compression de fichier pour vous. Vous ne pensez peut-être pas que cela serait très performant ou obtenir une bonne compression, mais je pense que vous serez surpris si vous l'essayez.
Quelle est la condition d'accès? Aléatoire ? Séquentiel? D'abord durer seulement? Quelle est la taille de la valeur d'index (32, 48, 64bits)? Les valeurs d'indice devraient-elles être totalement aléatoires (distribution plates) ou pourraient-il y avoir des relations internes que nous pourrions utiliser?
Une autre question ... en regardant l'exemple, il semble que les valeurs d'indice sont en ordre croissant. Qu'est-ce que la valeur du delta?
L'accès doit être aléatoire. Assumer la distribution uniforme. Les entrées d'index sont des entiers de 64 bits. Leur Delta suit la même distribution de la taille des valeurs qu'ils indiquent: quelques kilo-octets.
Utiliseriez-vous la même structure de données sur le disque que dans la mémoire?
L'indice est censé être en mémoire (MmeAlled) pendant que les données (les chaînes) vivront sur disque. Considérons tout petit Endian si c'est une préoccupation.