Bibliothèque C pour la compression d’entiers positifs séquentiels

J’ai le problème très commun de créer un index pour un tableau de chaînes dans le disque. En bref, je dois stocker la position de chaque chaîne dans la représentation sur disque. Par exemple, une solution très naïve serait un tableau d’index comme suit:

uint64 idx [] = {0, 20, 500, 1024, …, 103434};

Ce qui dit que la première corde est à la position 0, la deuxième à la position 20, la troisième à la position 500 et la nième à la position 103434.

Les positions sont toujours des entiers non négatifs de 64 bits dans un ordre séquentiel. Bien que les chiffres puissent varier d’une différence à l’autre, dans la pratique, je m’attends à ce que la différence typique se situe dans la fourchette de 2 ^ 8 à 2 ^ 20. Je m’attends à ce que cet index soit mémorisé en mémoire et que les positions soient accessibles de manière aléatoire (en supposant une dissortingbution uniforme).

Je pensais écrire mon propre code pour un codage delta bloc ou un codage plus sophistiqué, mais il y a tellement de compromis entre la vitesse et l’espace de codage / décodage que je préférerais obtenir une bibliothèque de travail comme sharepoint départ. et peut-être même se contenter de quelque chose sans aucune personnalisation.

Des allusions? Une bibliothèque c serait l’idéal, mais une bibliothèque c ++ me permettrait également de lancer des tests de performance initiaux.

Quelques détails supplémentaires si vous suivez encore. Ceci sera utilisé pour construire une bibliothèque similaire à cdb ( http://cr.yp.to/cdb/cdbmake.html ) au-dessus de la bibliothèque cmph ( http://cmph.sf.net ). En bref, il s’agit d’une carte associative en lecture seule basée sur un disque volumineux 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 comporte des millions de centaines de valeurs, une taille moyenne dans les plages de quelques kilo-octets et une valeur maximale de 2 ^ 31.

Pour mémoire, si je ne trouve pas une bibliothèque prête à être utilisée, j’ai l’intention d’implémenter le codage delta dans des blocs de 64 entiers avec les octets initiaux spécifiant le décalage de bloc jusqu’à présent. Les blocs eux-mêmes seraient indexés avec un arbre, me donnant le temps d’access O (log (n / 64)). Il y a beaucoup trop d’autres options et je préférerais ne pas en discuter. Je suis vraiment impatient, prêt à utiliser du code plutôt que des idées sur la manière de mettre en œuvre l’encodage. Je serai heureux de partager avec tout le monde ce que j’ai fait une fois que je l’ai fait fonctionner.

J’apprécie votre aide et laissez-moi savoir si vous avez des doutes.

J’utilise fastbit (Kesheng Wu LBL.GOV), il semble que vous ayez besoin de quelque chose de bon, de rapide et de MAINTENANT, donc fastbit est une amélioration hautement compétente de la BBC d’Oracle (code bitmap aligné sur octets, berkeleydb). C’est facile à installer et très bon en général.

Cependant, avec plus de temps, vous pouvez envisager une solution de code gris , elle semble optimale pour vos besoins.

Daniel Lemire a un certain nombre de bibliothèques pour C / ++ / Java publiées sur code.google , j’ai lu certains de ses articles et ils sont assez sympas, plusieurs avancées sur fastbit et des approches alternatives pour la réorganisation des colonnes avec du gris permuté. les codes.

Presque oublié, je suis aussi tombé sur le Cabinet de Tokyo , bien que je ne pense pas que cela conviendra bien à mon projet actuel, je peux l’envisager davantage si je l’avais su auparavant;), il a un degré élevé d’interopérabilité,

Tokyo Cabinet est écrit en langage C et fourni en tant qu’API de C, Perl, Ruby, Java et Lua. Tokyo Cabinet est disponible sur les plates-formes dotées d’une API conforme à C99 et POSIX.

Comme vous avez parlé de CDB, le test de performance de TC comporte un mode TC (plusieurs contraintes opérationnelles de prise en charge de TC pour des performances variables) dans lequel il surpassait CDB de 10 fois pour les performances de lecture et 2 fois pour les écritures.

En ce qui concerne vos exigences en matière d’encodage delta, je suis assez confiant en bsdiff et en sa capacité à surpasser tout système de correction de contenu file.exe, il peut également comporter des interfaces de base pour vos besoins généraux.

Courgette, la nouvelle application de compression binary de Google, vaut peut-être la peine d’être vérifiée, au cas où vous auriez manqué le communiqué de presse, des différences 10 fois inférieures à celles de bsdiff dans le seul cas de test que j’ai vu publié.

Vous avez deux exigences contradictoires:

  1. Vous souhaitez compresser de très petits éléments (8 octets chacun).
  2. Vous avez besoin d’un access aléatoire efficace pour chaque élément.

La deuxième condition est très susceptible d’imposer une longueur fixe pour chaque article.

Qu’est-ce que vous essayez de compresser? Si vous pensez à l’espace total d’index, vaut-il vraiment la peine de le sauver?

Si c’est le cas, vous pouvez essayer de réduire l’espace en deux et de le stocker dans deux tables. Les premiers magasins (valeur supérieure, indice de début, longueur, pointeur sur la deuxième table) et le second stockent (index, valeur inférieure).

Pour une recherche rapide, les index seraient implémentés en utilisant quelque chose comme B + Tree .

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é générait un enregistrement composé d’un numéro d’enregistrement (identifiant du document) et d’un numéro de mot (il aurait tout aussi bien pu stocker des décalages de mots) qui devaient être compressés autant que possible. J’ai utilisé une technique de compression delta qui tenait compte du fait qu’il y aurait plusieurs occurrences du même mot dans un document. Le numéro d’enregistrement n’a donc souvent pas besoin d’être répété. Et le mot delta delta correspondrait souvent à un ou deux octets. Voici le code que j’ai utilisé.

Comme il est en C ++, le code ne vous sera peut-être pas utile, mais peut constituer un bon sharepoint départ pour écrire des routines de compression.

Veuillez excuser la notation hongroise et les nombres magiques éparpillés dans le code. Comme je l’ai dit, j’ai écrit ceci il y a plusieurs années 🙂

IndexCompressor.h

// // index compressor class // #pragma once #include "File.h" const int IC_BUFFER_SIZE = 8192; // // index compressor // class IndexCompressor { private : File *m_pFile; WA_DWORD m_dwRecNo; WA_DWORD m_dwWordNo; WA_DWORD m_dwRecordCount; WA_DWORD m_dwHitCount; WA_BYTE m_byBuffer[IC_BUFFER_SIZE]; WA_DWORD m_dwBytes; bool m_bDebugDump; void FlushBuffer(void); public : IndexCompressor(void) { m_pFile = 0; m_bDebugDump = false; } ~IndexCompressor(void) {} void Attach(File& File) { m_pFile = &File; } void Begin(void); void Add(WA_DWORD dwRecNo, WA_DWORD dwWordNo); void End(void); WA_DWORD GetRecordCount(void) { return m_dwRecordCount; } WA_DWORD GetHitCount(void) { return m_dwHitCount; } void DebugDump(void) { m_bDebugDump = true; } }; 

IndexCompressor.cpp

 // // index compressor class // #include "stdafx.h" #include "IndexCompressor.h" void IndexCompressor::FlushBuffer(void) { ASSERT(m_pFile != 0); if (m_dwBytes > 0) { m_pFile->Write(m_byBuffer, m_dwBytes); m_dwBytes = 0; } } void IndexCompressor::Begin(void) { ASSERT(m_pFile != 0); m_dwRecNo = m_dwWordNo = m_dwRecordCount = m_dwHitCount = 0; m_dwBytes = 0; } void IndexCompressor::Add(WA_DWORD dwRecNo, WA_DWORD dwWordNo) { ASSERT(m_pFile != 0); WA_BYTE buffer[16]; int nbytes = 1; ASSERT(dwRecNo >= m_dwRecNo); if (dwRecNo != m_dwRecNo) m_dwWordNo = 0; if (m_dwRecordCount == 0 || dwRecNo != m_dwRecNo) ++m_dwRecordCount; ++m_dwHitCount; WA_DWORD dwRecNoDelta = dwRecNo - m_dwRecNo; WA_DWORD dwWordNoDelta = dwWordNo - m_dwWordNo; if (m_bDebugDump) { TRACE("%8X[%8X] %8X[%8X] : ", dwRecNo, dwRecNoDelta, dwWordNo, dwWordNoDelta); } // 1WWWWWWW if (dwRecNoDelta == 0 && dwWordNoDelta < 128) { buffer[0] = 0x80 | WA_BYTE(dwWordNoDelta); } // 01WWWWWW WWWWWWWW else if (dwRecNoDelta == 0 && dwWordNoDelta < 16384) { buffer[0] = 0x40 | WA_BYTE(dwWordNoDelta >> 8); buffer[1] = WA_BYTE(dwWordNoDelta & 0x00ff); nbytes += sizeof(WA_BYTE); } // 001RRRRR WWWWWWWW WWWWWWWW else if (dwRecNoDelta < 32 && dwWordNoDelta < 65536) { buffer[0] = 0x20 | WA_BYTE(dwRecNoDelta); WA_WORD *p = (WA_WORD *) (buffer+1); *p = WA_WORD(dwWordNoDelta); nbytes += sizeof(WA_WORD); } else { // 0001rrww buffer[0] = 0x10; // encode recno if (dwRecNoDelta < 256) { buffer[nbytes] = WA_BYTE(dwRecNoDelta); nbytes += sizeof(WA_BYTE); } else if (dwRecNoDelta < 65536) { buffer[0] |= 0x04; WA_WORD *p = (WA_WORD *) (buffer+nbytes); *p = WA_WORD(dwRecNoDelta); nbytes += sizeof(WA_WORD); } else { buffer[0] |= 0x08; WA_DWORD *p = (WA_DWORD *) (buffer+nbytes); *p = dwRecNoDelta; nbytes += sizeof(WA_DWORD); } // encode wordno if (dwWordNoDelta < 256) { buffer[nbytes] = WA_BYTE(dwWordNoDelta); nbytes += sizeof(WA_BYTE); } else if (dwWordNoDelta < 65536) { buffer[0] |= 0x01; WA_WORD *p = (WA_WORD *) (buffer+nbytes); *p = WA_WORD(dwWordNoDelta); nbytes += sizeof(WA_WORD); } else { buffer[0] |= 0x02; WA_DWORD *p = (WA_DWORD *) (buffer+nbytes); *p = dwWordNoDelta; nbytes += sizeof(WA_DWORD); } } // update current setting m_dwRecNo = dwRecNo; m_dwWordNo = dwWordNo; // add compressed data to buffer ASSERT(buffer[0] != 0); ASSERT(nbytes > 0 && nbytes < 10); if (m_dwBytes + nbytes > IC_BUFFER_SIZE) FlushBuffer(); CopyMemory(m_byBuffer + m_dwBytes, buffer, nbytes); m_dwBytes += nbytes; if (m_bDebugDump) { for (int i = 0; i < nbytes; ++i) TRACE("%02X ", buffer[i]); TRACE("\n"); } } void IndexCompressor::End(void) { FlushBuffer(); m_pFile->Write(WA_BYTE(0)); } 

Vous avez omis des informations critiques sur le nombre de chaînes que vous souhaitez indexer.

Mais étant donné que vous dites que vous vous attendez à ce que la longueur minimale d’une chaîne indexée soit de 256, le fait de stocker les index sous la forme 64% entraîne au maximum une surcharge de 3%. Si la longueur totale du fichier de chaîne est inférieure à 4 Go, vous pouvez utiliser des index 32 bits et générer une surcharge de 1,5%. Ces chiffres me suggèrent que si la compression est importante, il vaut mieux compresser les chaînes, pas les index . Pour ce problème, une variation sur LZ77 semble appropriée.

Si vous voulez essayer une idée déchaînée, mettez chaque chaîne dans un fichier séparé, extrayez-les toutes dans un fichier zip et voyez comment vous pouvez utiliser zziplib . Ce ne sera probablement pas génial, mais c’est presque zéro travail de votre part.

Plus de données sur le problème seraient les bienvenues:

  • Nombre de cordes
  • Longueur moyenne d’une chaîne
  • Longueur maximale d’une chaîne
  • Longueur médiane des cordes
  • Degré de compression du fichier de chaînes avec gzip
  • Si vous êtes autorisé à modifier l’ordre des chaînes pour améliorer la compression

MODIFIER

Le commentaire et la question révisée rendent le problème beaucoup plus clair. J’aime votre idée de regroupement. Je voudrais essayer un simple codage delta, regrouper les deltas et utiliser un code de longueur variable dans chaque groupe. Je ne transmettrais pas le code 64 en tant que groupe – je pense que vous voudrez probablement le déterminer de manière empirique.

Vous avez demandé des bibliothèques existantes. Pour le groupage et l’encodage delta, je doute que vous trouviez beaucoup Pour les codes entiers de longueur variable, je ne vois pas beaucoup de choses dans les bibliothèques C, mais vous pouvez trouver des codages de longueur variable en Perl et Python . Il existe une tonne de papiers et de brevets sur ce sujet, et je suppose que vous allez devoir finir par vous-même. Mais il existe quelques codes simples, et vous pouvez essayer UTF-8: il peut coder des entiers non signés jusqu’à 32 bits, et vous pouvez récupérer le code C de Plan 9 et, j’en suis sûr, de nombreuses autres sources.

Est-ce que vous utilisez Windows? Si c’est le cas, je vous recommande de créer le fichier mmap à l’aide de la solution naïve proposée à l’origine, puis de le compresser à l’aide de la compression NTLM . Le code de votre application ne sait jamais que le fichier est compressé et le système d’exploitation le compresse pour vous. Vous ne penserez peut-être pas que ce serait très performant ou obtenir une bonne compression, mais je pense que vous serez surpris si vous l’essayez.