Algorithme de Compression pour les données IEEE-754

quelqu'un a une recommandation sur un bon algorithme de compression qui fonctionne bien avec virgule flottante double précision des valeurs? Nous avons constaté que la représentation binaire des valeurs à virgule flottante entraîne des taux de compression très faibles avec les programmes de compression courants (par exemple Zip, RAR, 7-Zip, etc.).

les données que nous devons compresser sont un tableau unidimensionnel de valeurs de 8 octets triées dans un ordre croissant monotone. Les valeurs représentent les températures en Kelvin avec une portée typiquement inférieur à 100 degrés. Le nombre de valeurs varie de quelques centaines à plus de 64 ko.

Précisions

  • toutes les valeurs dans le tableau sont distinctes, bien que la répétition existe au niveau des octets en raison de la façon dont les valeurs flottantes sont représentées.

  • un algorithme sans perte est souhaité car il s'agit de données scientifiques. Conversion à une représentation à point fixe avec une précision suffisante (~5 décimales) peut être acceptable à condition qu'il existe une amélioration significative de l'efficacité du stockage.

mise à Jour

Trouvé un article intéressant sur ce sujet. Je ne sais pas dans quelle mesure l'approche est applicable à mes besoins.

http://users.ices.utexas.edu / ~burtscher / papers / dcc06.

19
demandé sur Brian Tompsett - 汤莱恩 2010-02-10 20:05:44

6 réponses

Première chose à considérer: essayez de compresser les données avant vous le convertissez en double précision. Re votre commentaire à David Thornley, à moins que vos ADC d'imagerie IR ont 24 bits significatifs, les flotteurs 32 bits devraient avoir plus que assez de précision; c'est seulement votre exigence de préserver exactement le bruit généré par le traitement ultérieur qui est un problème. Sinon, il pourrait être pratique de rétro-concevoir votre traitement, en déterminant une table de VALEURs il génère, et stocke un index à cette table à la place.

Second: si votre algorithme de compression sait que vos données sont en morceaux de 8 octets, il sera beaucoup plus efficace; c'est parce qu'il ne lancera pas vos octets les plus significatifs avec les octets les moins significatifs. Comme méthode de prétraitement brute, vous pourriez essayer de préfixer chaque double avec un octet distinctif (ASCII virgule, Peut-être?) avant de le raccorder à un compresseur basé sur un octet comme gzip; cela devrait permettre d'obtenir un meilleur la compression, même si le flux intermédiaire est 12% plus grand. Moins brut mais plus d'effort serait d'écrire votre propre compression adaptée à cette tâche -- peut-être en utilisant un arbre de 8 niveaux pour représenter les valeurs attendues de chaque octet dans votre double.

Troisièmement: comme les données d'image sont très redondantes, une certaine forme de codage delta ou une autre compression liée à l'image devrait permettre d'économiser de l'espace. Cependant, il ne vous gagnera pas une quantité terriblement grande si vous exigez la compression sans perte, comme l'image le bruit est intrinsèquement incompressible. En outre, il ne vous aidera pas à traiter le hachage pseudo-aléatoire dans les bits moins significatifs de vos doubles, comme expliqué ci-dessus.

4
répondu comingstorm 2010-02-10 19:48:17

tous les encodeurs que vous listez sont orientés byte, et sont rejetés par quelques propriétés de doubles. Pour un il y a la disposition où l'exposant/signe de 12-bit ne joue pas vraiment bien avec les limites de byte, pour d'autres il y a le bruit de votre entrée. La première partie est facile à traiter dans une multitude de façons, la seconde va limiter l'efficacité de toute compression sans perte que vous lancez sur elle. Je pense que même le meilleur résultat sera moins étonnant, je ne sais pas vos données, mais j'avais suspect vous pouvez compter sur seulement 25% d'économie, plus ou moins.

du haut de ma tête, et peut-être inutile parce que vous avez pensé à tout sur cette liste...

  1. traiter le flux comme des entiers de 64 bits et des valeurs adjacentes de delta-encode. Si vous avez des passages de valeurs avec le même exposant, il va effectivement le mettre à zéro, ainsi que peut-être quelques bits mantissa élevés. Il y aura des débordements, mais les données n'ont encore besoin que de 64 bits et l'opération peut être reveresed.

  2. à ce stade, vous pouvez éventuellement essayer une prévision d'entier brut, et enregistrer des différences.

  3. si vous avez suivi la suggestion auparavant, vous aurez presque la moitié des valeurs à partir de 000... et presque la moitié avec FFF... Pour éliminer cela, tourner la valeur vers la gauche (ROL) de 1 bit et XOR avec tous les Fs si le LSB courant est 1. L'inverse est XOR avec Fs si LSB est 0 alors ROR.

sur la seconde la pensée simplement XORing des prédictions aux valeurs vraies peut être mieux que la différence, parce que vous ne devez pas faire l'étape 3 alors.

  1. vous pouvez essayer de réorganiser les octets pour regrouper les octets ayant la même signification ensemble. Comme, d'abord tous les octets les plus significatifs, et ainsi de suite. Au moins, vous devriez obtenir quelque chose comme une série massive de zéros avec au plus quelques bits de bruit d'abord.

  2. passer à travers un compresseur générique ou même le premier RLE sur la course des zéros, puis un encodeur entropy, comme huffman, ou mieux, un encodeur range de 7zip/LZMA.

il y a une bonne chose à propos de vos données, c'est monotone. Il y a une mauvaise chose à propos de vos données: c'est tout simplement un ensemble trop petit. Combien voulez-vous économiser, simples kilobyes? pour quoi? L'efficacité de compression souffrira beaucoup s'il y a souvent une différence d'exposant entre les valeurs adjacentes.

Si vous traitez un grand nombre de ces jeux de données, vous devriez envisager en utilisant leur similarité pour mieux les compresser ensemble - peut-être les entrelacer à un certain stade. Si vous pouvez vivre avec une certaine perte, la mise à zéro de quelques octets les moins significatifs pourrait être une bonne idée - peut-être à la fois sur les données source et sur la prédiction de sorte que vous ne réintroduisez pas le bruit là.

3
répondu 3yE 2010-03-28 22:51:14

les algorithmes de Compression vivent sur les répétitions et les régularités, et les nombres à virgule flottante ne fonctionnent pas bien à cela.

la première question Est de savoir si vous pouvez utiliser des valeurs à virgule flottante de précision simple, ce qui vous donnera une compression de 50% immédiatement. Peu de thermomètres sont précis à sept chiffres, et l'exposant représentera des températures considérablement inférieures à tout ce qu'on m'a dit que vous pouvez obtenir.

Si non, vous pouvez filtrer vos températures, en les arrondissant hors de l'équivalent de N chiffres (plus probable N/.301 bits)? Cela peut introduire suffisamment de régularités pour être utile.

si vous devez vraiment stocker 64 bits d'information pour chaque lecture de température, et que tous les bits sont significatifs et non prévisibles à partir des autres bits, alors vous ne pouvez pas les compresser efficacement.

1
répondu David Thornley 2010-02-10 17:34:54

Pouvez-vous faire un delta entre les valeurs?

Est-il une limite à combien une valeur peut changer entre les mesures? Est-il acceptable de limiter ce changement à une certaine valeur de taux maximale (au prix d'un certain lissage)?)

il y a évidemment une limite à la précision réelle des valeurs du capteur thermique, avez-vous besoin de stocker 64 bits de précision ou Êtes-vous mieux de stocker un nombre entier de disons 0,01 unités Kelvin?

Si vous pouvez vivre avec un peu plus d'erreur et l'augmentation est relativement lisse, vous pourriez être mieux ajuster une fonction aux données et de stocker seulement quelques termes de la fonction.

EDIT:

Prendre un coup d'oeil à une série de données et de regarder les différences entre les valeurs. Ensuite, regardez quelle précision vous avez besoin pour représenter ceci.

par exemple. Si vous avez une différence max 1deg entre les lectures, vous pouvez stocker des changements de 1/256 de ceci dans un octet. Si vous avez besoin de stocker une plus grande ou plus de précision utilisez un court divisé par un facteur.

Alors, la prochaine lecture serait = last_reading + (float)incrément/256.0

1
répondu Martin Beckett 2010-02-10 19:15:03

si vous souhaitez un stockage d'archives à haute compression, "high Throughput Compression of Double-Precision Floating-Point Data" par Burtscher & Patanaworabhan ou "Fast and Efficient Compression of Floating-Point Data" par Lindstrom & Isenberg peut vous être utile.

si vous voulez un accès dynamique plus rapide au détriment d'un taux de compression plus faible, alors une ondelette de levage 1D peut être appropriée. Vous pouvez quantifier les données les plus petits entiers en spécifiant le nombre de chiffres à garder. Puis utilisez l'encodage delta avec un modèle prédictif suivi d'une transformation avec Haar ou une transformation en ondelette plus coûteuse et l'encodage arithmétique des coefficients supérieurs à une valeur spécifiée.

j'espère que ça aide

Vous pouvez obtenir Lindstrom du PDZ algorithme ici: https://github.com/LLNL/zfp

1
répondu James Fremen 2018-01-18 03:02:03

vous pourriez penser à recoder vos données avec un codeur entropie (Huffman, Shannon-Fano, codage arithmétique). Mais cela ne donnera de bons résultats que si vous avez beaucoup de répétitions des points de données et si vous savez quels symboles apparaîtront avec quelle probabilité.

0
répondu Sebastian Dressler 2010-02-10 17:22:56