compression à Scala

Question

Je travaille sur Scala avec des listes très larg de Int (peut-être grand) et je dois les compresser et de le maintenir en mémoire. La seule exigence est que je puisse tirer (et décompresser) le premier numéro sur la liste avec lequel travailler, sans toucher le reste de la liste.

J'ai beaucoup de bonnes idées mais la plupart d'entre elles traduisent les nombres en bits. Exemple:

vous pouvez écrire un nombre x comme tuple | log (x) |, X- | log (x) | le premier élément nous le plaçons comme une chaîne de 1 et un 0 à la fin (code unaire) et le second en binaire. par exemple:

1 -> 0,1 -> 0 1

...

5 -> 2,1 -> 110 01

...

8 -> 3,0 -> 1110 000

9 -> 3,1 -> 1110 001

...

Alors qu'un Int prend 32 bits fixes de la mémoire et une longue 64, avec cette compression x nécessite 2log (x) bits pour le stockage et peut atteindre indefinetly. Cette compression est réducemémoire dans la plupart des cas.

Comment gérez-vous ce type de données? Y at-il quelque chose comme bitarray ou quelque chose? Un autre moyen de compresser de telles données dans Scala?

Merci

Answer 1

En fonction de la faible densité et la portée de votre ensemble de données, vous pouvez conserver vos données comme une liste de deltas au lieu de chiffres. Cela est utilisé pour la compression sonore, par exemple, et peut être à la fois avec ou sans perte, selon vos besoins.

Par exemple, si vous avez Int chiffres mais sachez qu'ils seront presque jamais être plus qu'un (signé) Byte à part, vous pouvez faire quelque chose comme cette liste d'octets:

-1   // Use -1 to imply the next number cannot be computed as a byte delta 
0, 0, 4, 0 // 1024 encoded as bytes 
1   // 1025 as a delta 
-5   // 1020 as a delta 
-1   // Next number can't be computed as a byte delta 
0, 0, -1, -1 // 65535 encoded as bytes -- -1 doesn't have special meaning here 
10   // 65545 as a delta 

donc vous ne avoir à gérer des bits en utilisant cet encodage particulier. Mais, vraiment, vous n'obtiendrez pas de bonnes réponses sans une indication très claire du problème particulier, les caractéristiques des données, etc

Relecture de votre question, il semble que vous n'êtes pas en éliminant les techniques de compression qui tournent les données en bits. Si non, alors je suggère Huffman - prédictif si nécessaire - ou quelque chose de la famille Lempel-Ziv.

Et, non, Scala n'a malheureusement pas de bibliothèque pour gérer les données binaires. Bien que paulp a probablement quelque chose comme ça dans le compilateur lui-même.