compressione grande numero (o stringa) al valore piccolo

Question

La mia pagina ASP.NET ha seguente parametro di stringa di query:

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

Qui IDs parametro avrà sempre numeri separati da qualcosa, in questo caso ,. Attualmente ci sono 4 numeri ma normalmente sarebbero tra 3 e 7.

Ora, sto cercando il metodo per convertire ogni grande numero dall'alto nel valore più piccolo possibile; comprimendo in modo specifico il valore del parametro stringa di query IDs. Entrambi, la compressione di ogni algoritmo numerico o la compressione dell'intero valore del parametro stringa di query IDs sono i benvenuti.

1. Codifica o decodifica non è un problema; basta comprimere il valore IDs parametro stringa di query.
2. La creazione di un valore piccolo univoco per IDs e il recupero del suo valore da qualche origine dati non rientra nell'ambito.

Esiste un algoritmo per comprimere numeri così grandi in valori piccoli o per comprimere il valore del parametro stringa di query IDs tutti insieme?

Answer 1

Fondamentalmente hai bisogno di tanto spazio per i tuoi numeri perché stai usando la base 10 per rappresentarli. Un miglioramento sarebbe utilizzare la base 16 (esadecimale). Ad esempio, potresti rappresentare 255 (3 cifre) come ff (2 cifre).

si può prendere quel concetto ulteriormente utilizzando un numero molto maggiore di base ... l'insieme di tutti i caratteri che sono validi i parametri di stringa di query: ''

AZ, az, 0-9,, '- ',' ~ ',' _ ',' + '

Fornisce una base di 67 caratteri con cui lavorare (vedere Wikipedia on QueryString).

Dai un'occhiata a this SO post per gli approcci alla conversione della base 10 in basi di numeri arbitrari.

EDIT:

Nel post SO collegato, guarda questa parte:

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'}); 

che è quasi quello che ti serve. Basta ampliata con l'aggiunta di pochi personaggi che manca:

yz.- ~ _ +

Questo post è manca un metodo per tornare alla base 10. Non ho intenzione di scriverlo :-) ma la procedura è la seguente:

Definire un contatore che chiamerò TOTALE.

Guarda il a destra gran parte dei caratteri e trova la sua posizione nell'array.
TOTAL = (la posizione del carattere nell'array) Esempio: l'ingresso è BA1. TOTAL ora è 1 (poiché "1" è nella posizione 1 nell'array)

Ora guarda il prossimo carattere a sinistra del primo e trova la sua posizione nell'array. TOTAL + = 47 * (la posizione del carattere nell'array) Esempio: l'ingresso è BA1. TOTAL è ora (47 * 11) + 1 = 518

Ora guarda il prossimo carattere a sinistra del precedente e trova la sua posizione nell'array. TOTAL + = 47 * 47 * (la posizione del carattere nell'array) Esempio: l'ingresso è BA1. Totale è ora (47 * 47 * 10) + (47 * 11) + 1 = 243508

E così via.

Suggerisco di scrivere un test unitario che converta un gruppo di numeri di base 10 nella base 47 e quindi di nuovo indietro per assicurarsi che il codice di conversione funzioni correttamente.

Nota come si rappresentava un 6 cifre numero di base 10 in soli 3 cifre di base di 47 :-)

Answer 2

Se l'unico problema è la lunghezza dell'URL, è possibile convertire i numeri in , poi convertirli indietro ai numeri lato server

Answer 3

Qual è l'intervallo dei numeri? Supponendo che può andare bene in un intero a 16 bit, vorrei:

• Conservare tutti i numeri come 16-bit integers (2 byte per numero, range 32.768 a 32.767)
• costruire un bytestream di interi a 16 bit (XDR potrebbe essere una buona opzione qui; almeno, assicurarsi di gestire endianness correttamente)
• Base64 codificare il bytestream, utilizzando la codifica base64 modificato per gli URL (netto è di circa 3 caratteri per numero)

Come un aggiunto bonus non hai più bisogno di caratteri virgola perché sai che ogni numero è 2 byte.

In alternativa, se ciò non è sufficiente, utilizzare zlib per comprimere il flusso di numeri interi e quindi base64 il flusso compresso con zlib. È anche possibile passare a numeri interi a 32 bit se 16 bit non è un intervallo sufficientemente ampio (ad esempio se si ha realmente bisogno di numeri nell'intervallo 1.000.000.000).

Edit:

Forse troppo tardi, ma qui è un'implementazione che potrebbe fare quello che ti serve:

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 4

come fantasia sono gli ID hai trovato? se cifra per cifra, gli ID sono casuali, quindi il metodo che sto per proporre non sarà molto efficiente. ma se gli ID che hai fornito come esempio sono rappresentativi dei tipi che stai ricevendo, allora forse potrebbe funzionare come segue?

motivare questa idea con l'esempio.

, ad esempio, 1000000012 come ID che desideri comprimere. perché non memorizzarlo come [{1}, {0,7}, {12}]? Ciò significherebbe che la prima cifra è una 1 seguita da 7 zeri seguita da una 12. Quindi se usiamo la notazione {x} che rappresenterebbe un'istanza di x, mentre se usiamo {x, y} significherebbe che x si verifica y volte di seguito.

si potrebbe estendere questo con un po 'di corrispondenza del modello e/o funzione di montaggio.

ad esempio, corrispondenza modello: 1000100032 sarebbe [{1000,2} {32}].

ad esempio, raccordo funzione: se gli ID sono 10 cifre, quindi dividere l'ID in due numeri a 5 cifre e memorizzare l'equazione della linea che attraversa entrambi i punti. se ID = 1000000012, hai y1 = 10000 e y2 = 12. quindi, la tua inclinazione è -9988 e l'intercetta è 10000 (assumendo x1 = 0, x2 = 1). In questo caso, non è un miglioramento, ma se i numeri fossero più casuali, potrebbe essere. Equivalentemente, è possibile memorizzare la sequenza di ID con funzioni lineari a tratti.

in ogni caso, ciò dipende principalmente dalla struttura dei tuoi ID.

Answer 5

Presumo si sta facendo questo come una soluzione per le restrizioni di lunghezza richiesta URL ...

altre risposte hanno suggerito la codifica dei numeri ID decimali in esadecimale, base47 e base64, ma (in teoria) si può fare un molto meglio di così usando LZW (o simili) per comprimere la lista di identificazione. A seconda della quantità di ridondanza presente negli elenchi di ID, è possibile ottenere una riduzione significativa di oltre il 40%, anche dopo la ricodifica dei byte compressi come testo.

In un guscio di noce, suggerisco di trovare una libreria di compressione del testo disponibile in Javascript e usarla sul lato client per comprimere l'elenco di ID. Quindi codifica il test compresso utilizzando base47/base64 e passa la stringa codificata come parametro URL. Sul lato server fare il contrario; cioè decodificare seguito da decompressione.

MODIFICA: Come esperimento, ho creato un elenco di 36 identificatori diversi come quelli che hai fornito e compresso usando gzip. Il file originale è 396 byte, il file compresso è 101 byte e il file compresso + base64 138 byte. Questa è una riduzione del 65% nel complesso. E il rapporto di compressione potrebbe effettivamente migliorare per i file più grandi. Tuttavia, quando ho provato questo con un piccolo set di input (ad esempio solo i 4 identificatori originali), non ho ottenuto alcuna compressione e, dopo la codifica, la dimensione era maggiore dell'originale.

Google "libreria LZW javascript"

In teoria, ci potrebbe essere la soluzione più semplice. Invia i parametri come "post data" piuttosto che nell'URL della richiesta e ottieni il browser per applicare la compressione utilizzando una delle codifiche che comprende. Ciò ti darà anche più risparmi poiché non è necessario codificare i dati compressi in caratteri URL legali.

Il problema è far sì che il browser comprima la richiesta ... e lo faccia in modo indipendente dal browser.

Answer 6

Ecco un altro schema molto semplice che dovrebbe fornire una buona compressione per una serie di numeri del modulo N + delta dove N è una costante di grandi dimensioni.

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; 
} 

Questo dovrebbe ridurre il set {1000000012,1000000021,1000000013,1000000022} all'elenco [1000000012,1,9,1], che è quindi possibile comprimere ulteriormente rappresentando numeri nella codifica base47 come descritto in un'altra risposta.

Utilizzando la codifica decimale semplice, questo va da 44 caratteri a 16 caratteri; cioè il 63%. (E l'uso di base47 darà ancora più compressione).

Se non è possibile ordinare gli ID, non si ottiene una compressione altrettanto buona. Per questo esempio, {1000000012,1000000021,1000000013,1000000022} viene compresso nell'elenco [1000000012,9,-8,9].Questo è solo un carattere più lungo per questo esempio

In entrambi i casi, questo è migliore di un algoritmo di compressione generico o schemi di codifica ... PER QUESTO TIPO DI INGRESSO.