Compression de tableau de grand nombre

Question

J'ai une application javascript qui envoie une grande quantité de données numériques sur le réseau. Ces données sont ensuite stockées dans une base de données. J'ai des problèmes de taille (trop de bande passante, la base de données devient trop grande). Je suis maintenant prêt à sacrifier certaines performances pour la compression.

Je pensais implémenter un numéro de base 62 à chaîne (62) et à parseInt (compressé, 62). Cela réduirait certainement la taille des données, mais avant d'aller de l'avant et de le faire, j'ai pensé que je mettrais les gens ici, car je sais qu'il doit y avoir une solution hors des sentiers battus que je n'ai pas envisagée.

Les spécifications de base sont les suivants: - Compresser grands tableaux de nombres en chaînes pour le transfert JSONP (Je pense donc que UTF est hors) - être relativement rapide, regardez je ne suis pas attendre même performance que j'ai maintenant mais je aussi don ne veux pas de compression gzip non plus.

Toutes les idées seraient grandement appréciées.

Merci

Guido Tapia

Answer 1

Eh bien, comme mentionné dans la réponse acceptée à this question, the jsolait library a une implémentation de compression LZW en JavaScript ...

Answer 2

options

• utilisation une librairie js (voir la réponse de Josh) mais attention aux timeouts de script
• Utilisez une sorte de activex ou silverlight Uploader qui fait aussi zip
• Utilisez un plug-in java
• Utilisez un flash à base de compression Uploader

Answer 3

Une autre façon de faire cela pourrait être de coder à des types binaires tels en tant qu'ints signés/non signés, et décoder manuellement comme http://snippets.dzone.com/posts/show/685 qui nécessiterait le code côté serveur pour créer les données binaires.

Vous pouvez ensuite compresser Huffman ou quelque chose de similaire comme RLE (voir http://rosettacode.org/wiki/Run-length_encoding#JavaScript pour une implémentation, bien qu'il puisse avoir quelques problèmes dans IE sans modifier) ​​pour compresser les données plus loin.

EDIT: Sinon, vous pouvez convertir les nombres eux-mêmes à une base (radix) dans la gamme de caractères URI non codés (voir http://en.wikipedia.org/wiki/Percent-encoding) qui devrait bien fonctionner si la plupart des chiffres sont supérieurs à 2 chiffres. J'ai converti le code à http://code.activestate.com/recipes/111286-numeric-base-converter-that-accepts-arbitrary-digi/ à partir de python pour ce faire.

Il ne gère pas actuellement des flotteurs, mais il pourrait se faire assez facilement:

function get_map(s) { 
    d = {} 
    for (var i=0; i<s.length; i++) { 
     d[s.charAt(i)] = i} 
    d.length = s.length 
    d._s = s 
    return d} 

var separate_with = '~'; 
var encodable = get_map('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_.'); // - is reserved for negatives obviously :-P 
var base10 = get_map('') 

// UNCOMMENT ME for length/speed testing in a wider base! 
// You may wish to experiment with the ranges for a happy medium between bandwidth and DB space :-P 
/*var encodable = '' 
for (var i=1; i<128; i++) { 
    encodable += String.fromCharCode(i) 
} 
encodable = get_map(encodable)*/ 

function baseconvert(number, fromdigits, todigits) { 
    var number = String(number) 

    if (number.charAt(0) == '-') { 
     number = number.slice(1, number.length) 
     neg=1} 
    else { 
     neg=0} 

    // make an integer out of the number 
    var x = 0 
    for (var i=0; i<number.length; i++) { 
     var digit = number.charAt(i) 
     x = x*fromdigits.length + fromdigits[digit] 
    } 

    // create the result in base 'todigits.length' 
    res = "" 
    while (x>0) { 
     remainder = x % todigits.length 
     res = todigits._s.charAt(remainder) + res 
     x = parseInt(x/todigits.length) 
    } 

    if (neg) res = "-"+res 
    return res 
} 

function encodeNums(L) { 
    var r = [] 
    for (var i=0; i<L.length; i++) { 
     r.push(baseconvert(L[i], base10, encodable)) 
    } 
    return r.join(separate_with) 
} 

function decodeNums(s) { 
    var r = [] 
    var s = s.split(separate_with) 
    for (var i=0; i<s.length; i++) { 
     r.push(parseInt(baseconvert(s[i], encodable, base10))) 
    } 
    return r 
} 

var test = [5, 654645, 24324, 652124, 65, 65289543, 65278432, 643175874158, 652754327543] 
alert(encodeNums(test)) 
alert(decodeNums(encodeNums(test))) 

Answer 4

Je suis maintenant avec l'toying idée de coder la longueur du nombre dans le nombre lui-même. Je n'ai toujours pas perfectionné cet algorithme, mais je l'afficherai une fois terminé.Mais à peu près ce que je suis en train de réaliser actuellement:

Limites:

• perte de précision est autorisé (+ - 3)
• Nombre maximum sera 3200
• Min est 0 (si pas de négatifs)
• Pas de décimales - flotteurs

Alors maintenant, étant donné mon numéro de permis max Je sais que la longueur du chiffre codé dans la base 62 aura une longueur maximale de 2. Ainsi, tout nombre encodé a une longueur de 1 ou 2 caractères. Impressionnant. Alors maintenant, je vais faire le nombre impair ou même en fonction de ses 1 ou 2 caractères (rappelez-vous que je peux gérer la perte de précision). Cela supprime le besoin de séparateurs.

Maintenant, je vois une compression de 70% -80% avec ceci, c'est très buggy en ce moment mais je suis excité à ce sujet, donc le poste pour encourager la discussion autour de cette méthodologie.