número grande (o cadena) al valor pequeño

Question

Mi página ASP.NET tiene siguiente parámetro de cadena de consulta:

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

Aquí IDs parámetro siempre tendrá números separados por algo, en este caso ,. Actualmente hay 4 números, pero normalmente estarían entre 3 y 7.

Ahora, estoy buscando un método para convertir cada gran número de arriba en el menor valor posible; comprimir específicamente el valor de IDs parámetro de cadena de consulta. Ambos, la compresión de cada algoritmo de número o la compresión de todo el valor de IDs parámetro de cadena de consulta son bienvenidos.

1. Codificar o decodificar no es un problema; simplemente comprimiendo el valor IDs parámetro de cadena de consulta.
2. Creando un pequeño valor único para IDs y luego recuperando su valor de alguna fuente de datos está fuera del alcance.

¿Hay un algoritmo para comprimir tales números grandes a valores pequeños o para comprimir el valor del parámetro cadena de consulta IDs todos juntos?

Answer 1

Básicamente necesita mucho espacio para sus números porque está utilizando la base 10 para representarlos. Una mejora sería usar base 16 (hex). Entonces, por ejemplo, puede representar 255 (3 dígitos) como ff (2 dígitos).

que puede tomar ese concepto aún más mediante el uso de un número de base mucho más grande ... el conjunto de todos los caracteres que son válidos los parámetros de cadena de consulta: ''

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

Eso le da una base de 67 caracteres para trabajar (vea Wikipedia on QueryString).

Eche un vistazo a this SO post para los enfoques para convertir la base 10 en bases de números arbitrarios.

EDIT:

En el post relacionado SO, mira a esta 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'}); 

que es casi lo que necesita. Sólo expandirlo mediante la adición de los pocos personajes que le falta:

yz.- ~ _ +

Ese puesto le falta un método para volver a la base 10. No voy a escribir :-) pero el procedimiento es el siguiente:

Defina un contador al que llamaré TOTAL.

Mira el derecho más personaje y encuentra su posición en la matriz.
TOTAL = (la posición del carácter en la matriz) Ejemplo: La entrada es BA1. TOTAL es ahora 1 (ya que "1" está en la posición 1 en la matriz)

Ahora mire el siguiente carácter a la izquierda del primero y encuentre su posición en la matriz. TOTAL + = 47 * (la posición del carácter en la matriz) Ejemplo: La entrada es BA1. TOTAL es ahora (47 * 11) + 1 = 518

Ahora mire el siguiente carácter a la izquierda del anterior y encuentre su posición en la matriz. TOTAL + = 47 * 47 * (la posición del carácter en la matriz) Ejemplo: La entrada es BA1. El total es ahora (47 * 47 * 10) + (47 * 11) + 1 = 243508

Y así sucesivamente.

Le sugiero que escriba una prueba unitaria que convierta un grupo de números base 10 en base 47 y luego otra vez para asegurarse de que su código de conversión funcione correctamente.

Nota cómo representado un número de 6 dígitos de base 10 en sólo 3 dígitos de base 47 :-)

Answer 2

Si el único problema es la longitud de la URL, puede convertir los números a , a continuación, convertirlos de nuevo a los números en el lado del servidor

Answer 3

¿Cuál es el rango de sus números? Suponiendo que pueden caber en un entero de 16 bits, que serían:

• , guarda todos tus números 16-bit integers (2 bytes por número, rango de -32.768 a 32.767)
• construir una corriente de bytes de enteros de 16 bits (XDR podría ser una buena opción en este caso, al menos, asegurarse de manejar endianness correctamente)
• Base64 codificar la corriente de bytes, utilizando la codificación base64 modificado para URL (neto es de 3 caracteres por número)

Como un Además, ya no necesitas los caracteres de coma porque sabes que cada número tiene 2 bytes.

Alternativamente, si eso no es lo suficientemente bueno, usaría zlib para comprimir la secuencia de enteros y luego base64 la secuencia comprimida de zlib. También puede cambiar a enteros de 32 bits si el rango de 16 bits no es lo suficientemente grande (es decir, si realmente necesita números en el rango de 1,000,000,000).

Editar:

Tal vez demasiado tarde, pero aquí es una aplicación que podría hacer lo que tiene:

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

cómo estampada son los identificadores que está recibiendo? si dígito a dígito, los ID son aleatorios, entonces el método que voy a proponer no será muy eficiente. pero si los ID que proporcionó como ejemplo son representativos de los tipos que obtendría, entonces ¿podría funcionar lo siguiente?

Motivo esta idea con el ejemplo.

tiene, por ejemplo, 1000000012 como ID que le gustaría comprimir. ¿Por qué no almacenarlo como [{1}, {0,7}, {12}]? Esto significaría que el primer dígito es un 1 seguido de 7 ceros seguido por un 12. Así que si usamos la notación {x} que representaría una instancia de x, mientras que si usamos {x, y} eso significaría que x ocurre y veces en una fila.

puede ampliar esto con un poco de coincidencia de patrón y/o ajuste de función.

por ejemplo, coincidencia de patrón: 1000100032 sería [{1000,2} {32}].

por ejemplo, ajuste de función: si sus ID son de 10 dígitos, luego divida la ID en dos números de 5 dígitos y almacene la ecuación de la línea que atraviesa ambos puntos. si ID = 1000000012, tiene y1 = 10000 y y2 = 12. por lo tanto, su pendiente es -9988 y su intersección es 10000 (suponiendo x1 = 0, x2 = 1). En este caso, no es una mejora, pero si los números fueran más aleatorios, podría ser. Equivalentemente, puede almacenar la secuencia de ID con funciones lineales por partes.

En cualquier caso, esto depende principalmente de la estructura de sus identificaciones.

Answer 5

Asumo que está haciendo esto como una solución para las restricciones de longitud solicitud de URL ...

Otras respuestas han sugerido que codifica los números de identificación de decimales en hexadecimal, base47 o base 64, pero se puede (en teoría) hacer una mucho mejor que eso mediante el uso de LZW (o similar) para comprimir la lista de identificación. Según la cantidad de redundancia que haya en sus listas de ID, podría obtener una reducción de más del 40%, incluso después de volver a codificar los bytes comprimidos como texto.

En pocas palabras, sugiero que encuentre una biblioteca de compresión de texto lista para usar implementada en Javascript y usarla para comprimir la lista de ID. Luego codifique la cadena de bytes comprimida utilizando base47/base64, y pase la cadena codificada como el parámetro URL. En el lado del servidor, haga lo contrario; es decir, decodificación seguida de descompresión.

EDITAR: Como experimento, creé una lista de 36 identificadores diferentes como los que suministró y compré utilizando gzip. El archivo original tiene 396 bytes, el archivo comprimido tiene 101 bytes y el archivo comprimido + base64 138 bytes. Eso es una reducción del 65% en general. Y la relación de compresión podría mejorar para archivos más grandes. Sin embargo, cuando probé esto con un pequeño conjunto de entrada (por ejemplo, solo los 4 identificadores originales), no obtuve compresión, y después de la codificación el tamaño fue mayor que el original.

Google "biblioteca lzw javascript"

En teoría, podría ser una solución más simple. Envíe los parámetros como "datos de publicación" en lugar de en la URL de solicitud, y obtenga que el navegador aplique la compresión usando una de las codificaciones que entiende. Eso le dará más ahorros también, ya que no es necesario codificar los datos comprimidos en caracteres de URL legales.

El problema consiste en hacer que el navegador comprima la solicitud ... y hacerlo de forma independiente del navegador.

Answer 6

Aquí hay otro esquema realmente simple que debería dar una buena compresión para un conjunto de números del formulario N + delta donde N es una constante grande.

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

Esto debería reducir el conjunto {1000000012,1000000021,1000000013,1000000022} a la lista [1000000012,1,9,1], que luego se puede comprimir adicionalmente mediante la representación de los números en base47 codificación como se describe en otra respuesta.

Usando codificación decimal simple, esto va de 44 caracteres a 16 caracteres; es decir, 63%. (Y usar base47 dará incluso más compresión).

Si no es aceptable ordenar los identificadores, no obtendrá una compresión tan buena. Para este ejemplo, {1000000012,1000000021,1000000013,1000000022} se comprime en la lista [1000000012,9,-8,9].Es solo un carácter más largo para este ejemplo

De cualquier forma, esto es mejor que un algoritmo de compresión genérico o esquemas de codificación ... PARA ESTE TIPO DE ENTRADA.