permet de dire que j'ai de nombreux objets contenant des chaînes de longueur non triviale (environ 3-4kb). Les chaînes sont toutes différentes les unes des autres mais contiennent en même temps beaucoup de parties communes / de suivantes. En moyenne, peut-être 80-90% de toute chaîne individuelle est également contenue avec les autres. Existe-t-il un moyen facile d'exploiter automatiquement cette énorme redondance pour compresser les données?
Idéalement, la solution serait C ++ et transparente pour l'utilisateur (c'est-à-dire que je peux l'utiliser comme si j'étais accessible à une lecture régulière Const std STD :: String, mais à la lecture d'un stockage compressé).
4 Réponses :
algorithmique, Lempel-ZIV-WELCH Avec un dictionnaire pour tous les objets / chaînes pourrait être un bon départ.
Si beaucoup de chaînes sont créées de manière dynamique au fil du temps, ce dictionnaire deviendra gros. Donc, à la fin, il peut s'agir d'une idée plus simple et meilleure pour simplement compresser les cordes séparément.
Il y aura très peu de chaînes créées une fois que le lot initial a été chargé, alors je ne m'attendais pas à un problème là-bas ...
Si les parties communes des chaînes sont courantes car elles sont composées d'autres cordes, vous pourriez obtenir une certaine traction en utilisant le stlport Quand utiliser la corde:
Quand ne pas utiliser de corde:
corde classe, qui cherche tout le monde comme une STD :: String, mais utilise la représentation de l'arborescence de sous-chaîne avec une copie sur l'écriture qui les rend tous les deux très Espace efficace (des substrings communes sont partagés) et très bien à des insertions et de suppression (log (n))
Je pense que cela a plus que la copie sur l'écriture. Je pense que les données sont stockées dans un arbre de chaînes, pas dans une zone de mémoire contiguë.
Il s'agit d'une copie-écriture combinée à une capacité à préparer aux chaînes au même coût algorithmique que l'adjuvant.
Je pense que je suis adapté à votre deuxième cas: mes cordes ne sont pas contrôlées par moi et je les reçois d'une base de données.
Vous pouvez utiliser codage Huffman La mise en œuvre n'est pas difficile, il existe également des algorithmes zip dans les langues ( comme c # et java) et vous pouvez les utiliser.
Également si vous êtes sûr de 80-90%, créez un dictionnaire de tous les mots, puis pour chaque chaîne Stocker la position du mot dictionnaire, des moyens ont un tableau de grandes taille (10000 c'est-à-dire) et marquez la connexion position bits [i] à 1 Si un mots [i] existe dans la chaîne actuelle. Pensez que chaque longueur de mot est de 5 caractères, l'abréviation prend environ 1/5.
Comme @saeed mentionné, un simple codage de Huffman fonctionnera bien ici.
Il n'y a pas besoin dans le dictionnaire, si les mots communs sont connus Apriori (vous avez mentionné que c'est un HTML). Il suffit de précomputer une table Huffman à l'aide de données statistiques à partir de nombreux fichiers HTML (notez que vous pouvez encoder une balise entière par un seul symbole et vous pouvez avoir autant de symboles que vous le souhaitez).
Comment les chaînes viennent-elles avoir des sous-séquences communes? Est-ce dû à des modifications répétées ou de coïncidence des données?
Imaginez HTML statique sans support pour CSS. Vous avez beaucoup de HTML redondant et seulement très peu de pièces modifiées contenant les informations réelles.
1 Go de RAM tiendra de l'ordre de 100 000 blobs non compressés de 3 à 4 Ko. Avez-vous vraiment besoin de cela pour s'adapter à moins?
Ouais. Je traite avec> = 500.000 et cela ne fait qu'une partie des données (dans une application 32 bits ...).