Compression d'un grand nombre (ou d'une chaîne) en une petite valeur

Question

Ma page ASP.NET a le paramètre de chaîne de requête suivant :

…?IDs=1000000012,1000000021,1000000013,1000000022&...

Aquí IDs aura toujours des nombres séparés par quelque chose, dans ce cas-ci , . Actuellement, il y a 4 numéros mais normalement ils devraient se situer entre les deux. 3 y 7 .

Maintenant, je cherche une méthode pour convertir chaque grand nombre ci-dessus en une valeur aussi petite que possible, en particulier en comprimant la valeur de IDs paramètre de la chaîne d'interrogation. Tant la compression de chaque algorithme numérique que la compression de la valeur totale de l'algorithme de la IDs sont les bienvenues.

1. Le codage ou le décodage n'est pas un problème ; il s'agit simplement de compresser la valeur. IDs paramètre de la chaîne de requête.
2. Créer une petite valeur unique pour IDs et ensuite récupérer sa valeur à partir d'une source de données est hors de portée.

Existe-t-il un algorithme permettant de comprimer de tels grands nombres en petites valeurs ou de comprimer la valeur de l'indice de l'eau ? IDs le paramètre de chaîne de requête tous ensemble ?

Answer 1

Vous avez besoin de beaucoup de place pour vos chiffres car vous utilisez la base 10 pour les représenter. Une amélioration serait d'utiliser la base 16 (hex). Ainsi, par exemple, vous pourriez représenter 255 (3 chiffres) par ff (2 chiffres).

Vous pouvez pousser ce concept plus loin en utilisant une base numérique beaucoup plus large... l'ensemble de tous les caractères qui sont des paramètres de chaîne de requête valides :

A-Z, a-z, 0-9, '.', '-', '~', '_', '+'.

Vous disposez ainsi d'une base de 67 caractères pour travailler (cf. Wikipedia sur QueryString ).

Jetez un coup d'œil à ce poste SO pour les méthodes de conversion de la base 10 en bases numériques arbitraires.

EDITAR:

Dans le poste de SO lié, regardez cette partie :

string xx = IntToString(42, 
            new char[] { '0','1','2','3','4','5','6','7','8','9',
            'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',
            'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x'});

C'est presque ce dont vous avez besoin. Il suffit de l'étendre en ajoutant les quelques caractères qui lui manquent :

yz.-~_+

Il manque dans ce post une méthode pour revenir à la base 10. Je ne vais pas l'écrire :-) mais la procédure est la suivante :

Définissez un compteur que j'appellerai TOTAL.

Regardez le droite et trouver sa position dans le tableau.
TOTAL = (la position du caractère dans le tableau) Exemple : L'entrée est BA1. TOTAL est maintenant 1 (puisque "1" est en position 1 dans le tableau).

Maintenant, regardez le caractère suivant à gauche du premier et trouvez sa position dans le tableau. TOTAL += 47 * (la position du caractère dans le tableau) Exemple : L'entrée est BA1. TOTAL est maintenant (47 * 11) + 1 = 518

Maintenant, regardez le caractère suivant à gauche du précédent et trouvez sa position dans le tableau. TOTAL += 47 * 47 * (la position du caractère dans le tableau) Exemple : L'entrée est BA1. Le total est maintenant (47 * 47 * 10) + (47 * 11) + 1 = 243508

Et ainsi de suite.

Je vous suggère d'écrire un test unitaire qui convertit un certain nombre de nombres en base 10 en base 47 et vice-versa pour vérifier que votre code de conversion fonctionne correctement.

Notez comment vous avez représenté un nombre à 6 chiffres en base 10 en seulement 3 chiffres en base 47 :-)

Answer 2

Quelle est la fourchette de vos chiffres ? En supposant qu'ils puissent tenir dans un entier de 16 bits, je le ferais :

• Stockez tous vos numéros comme Entiers de 16 bits (2 octets par numéro, plage de -32 768 à 32 767)
• Construire un bytestream d'entiers de 16 bits ( XDR pourrait être une bonne option ici ; au moins, assurez-vous de traiter endiveté correctement)
• Base64 encoder le bytestream, en utilisant l'encodage base64 modifié pour les URLs (net est d'environ 3 caractères par numéro)

En prime, vous n'avez plus besoin de caractères de virgule, car vous savez que chaque nombre compte 2 octets.

Alternativement, si cela ne suffit pas, j'utiliserais zlib pour compresser votre flux d'entiers et ensuite base64 le flux compressé par zlib. Vous pouvez également passer à des nombres entiers de 32 bits si la plage de 16 bits n'est pas suffisamment large (par exemple, si vous avez vraiment besoin de nombres de l'ordre de 1 000 000 000).

Editar:

Peut-être trop tard, mais voici une implémentation qui pourrait faire ce dont vous avez besoin :

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Scratch {
    class Program {
        static void Main(string[] args) {
            //var ids = new[] { 1000000012, 1000000021, 1000000013, 1000000022 };
            var rand = new Random();
            var ids = new int[rand.Next(20)];
            for(var i = 0; i < ids.Length; i++) {
                ids[i] = rand.Next();
            }

            WriteIds(ids);
            var s = IdsToString(ids);
            Console.WriteLine("\nResult string is: {0}", s);
            var newIds = StringToIds(s);
            WriteIds(newIds);
            Console.ReadLine();
        }

        public static void WriteIds(ICollection<Int32> ids) {
            Console.Write("\nIDs: ");
            bool comma = false;
            foreach(var id in ids) {
                if(comma) {
                    Console.Write(",");
                } else {
                    comma = true;
                }
                Console.Write(id);
            }
            Console.WriteLine();
        }

        public static string IdsToString(ICollection<Int32> ids) {
            var allbytes = new List<byte>();
            foreach(var id in ids) {
                var bytes = BitConverter.GetBytes(id);
                allbytes.AddRange(bytes);                
            }
            var str = Convert.ToBase64String(allbytes.ToArray(), Base64FormattingOptions.None);
            return str.Replace('+', '-').Replace('/', '_').Replace('=', '.');
        }

        public static ICollection<Int32> StringToIds(string idstring) {
            var result = new List<Int32>();
            var str = idstring.Replace('-', '+').Replace('_', '/').Replace('.', '=');
            var bytes = Convert.FromBase64String(str);
            for(var i = 0; i < bytes.Length; i += 4) {
                var id = BitConverter.ToInt32(bytes, i);
                result.Add(id);
            }
            return result;
        }
    }
}

Answer 3

Voici un autre schéma très simple qui devrait donner une bonne compression pour un ensemble de chiffres de la forme N + delta où N est une grande constante.

public int[] compress(int[] input) {
    int[] res = input.clone();
    Arrays.sort(res);
    for (int i = 1; i < res.length; i++) {
        res[i] = res[i] - res[i - 1];
    }
    return res;
}

Cela devrait réduire l'ensemble {1000000012,1000000021,1000000013,1000000022} à la liste [1000000012,1,9,1] que vous pouvez ensuite compresser davantage en représentant les nombres en encodage base47, comme décrit dans une autre réponse.

En utilisant le codage décimal simple, on passe de 44 caractères à 16 caractères, soit 63%. (Et l'utilisation de la base47 donnera encore plus de compression).

S'il est inacceptable de trier les identifiants, vous n'obtenez pas une aussi bonne compression. Pour cet exemple, {1000000012,1000000021,1000000013,1000000022} compresse à la liste [1000000012,9,-8,9] . C'est juste un caractère de plus pour cet exemple

Quoi qu'il en soit, c'est mieux qu'un algorithme de compression générique ou des schémas d'encodage ... POUR CE TYPE D'ENTRÉE.

Answer 4

Si le seul problème est la longueur de l'URL, vous pouvez convertir les nombres en caractères base64 puis les reconvertir en chiffres du côté du serveur.

Answer 5

Si les identifiants que vous recevez sont aléatoires, chiffre par chiffre, la méthode que je vais proposer ne sera pas très efficace. mais si les identifiants que vous avez donnés en exemple sont représentatifs des types d'identifiants que vous obtenez, la méthode suivante pourrait peut-être fonctionner ?

Je motive cette idée par l'exemple.

Vous avez par exemple 1000000012 comme ID que vous souhaitez compresser. Pourquoi ne pas le stocker sous la forme [{1},{0,7},{12}] ? Cela signifierait que le premier chiffre est un 1 suivi de 7 zéros puis d'un 12. Ainsi, si nous utilisons la notation {x}, cela représente une instance de x, tandis que si nous utilisons {x,y}, cela signifie que x apparaît y fois de suite.

vous pourriez étendre cela avec un peu de correspondance de modèle et/ou d'ajustement de fonction.

par exemple, la correspondance des motifs : 1000100032 serait [{1000,2}{32}].

par exemple, l'ajustement des fonctions : si vos identifiants sont à 10 chiffres, divisez-les en deux nombres à 5 chiffres et stockez l'équation de la droite qui passe par les deux points. si ID = 1000000012, vous avez y1 = 10000 et y2 = 12. par conséquent, votre pente est -9988 et votre intercept est 10000 (en supposant que x1 = 0, x2 = 1). Dans ce cas, ce n'est pas une amélioration, mais si les nombres étaient plus aléatoires, cela pourrait l'être. De manière équivalente, vous pourriez stocker la séquence d'identifiants avec des fonctions linéaires par morceaux.

dans tous les cas, cela dépend surtout de la structure de vos identifiants.