c# - test - ¿Cómo los sitios como goo.gl o jsfiddle generan sus códigos URL?

test dome c#

Question

Me gustaría generar un código como los sitios web goo.gl y jsfiddle ( http://jsfiddle.net/XzKvP/ ).

Probé diferentes cosas que me dan una guía demasiado grande, un código alfanumérico que se repite, etc.

Estoy pensando que debería poder generar un código alfanumérico basado en la Clave principal en la tabla de mi base de datos. ¿De esta manera no se repetirá? El PK es un entero auto-incrementado por 1. Pero no estoy seguro de cómo debería hacerse.

Quiero que el código parezca aleatorio, pero NO tiene que serlo. Por ejemplo, NO quiero que el elemento 1234 de mi base de datos sea BCDE y que el elemento 1235 sea BCDF .

Ejemplos:

Observe cómo la url http://jsfiddle.net/XzKvP/ tiene un código de 5 caracteres exclusivo XzKvP asociado a la página. Quiero poder generar el mismo tipo de código.

goo.gl lo hace también: goo.gl tiene UEhtg

¿Cómo se hace esto?

Answer 1

Esto es lo que terminé haciendo.

(Actualizado desde la respuesta de Daniel Vérité):

class Program
{

    private static double RoundFunction(uint input)
    {
        // Must be a function in the mathematical sense (x=y implies f(x)=f(y))
        // but it doesn''t have to be reversible.
        // Must return a value between 0 and 1
        return ((1369 * input + 150889) % 714025) / 714025.0;
    }
    private static char Base62Digit(uint d)
    {
        if (d < 26)
        {
            return (char)(''a'' + d);
        }
        else if (d < 52)
        {
            return (char)(''A'' + d - 26);
        }
        else if (d < 62)
        {
            return (char)(''0'' + d - 52);
        }
        else
        {
            throw new ArgumentException("d");
        }
    }
    private static string ToBase62(uint n)
    {
        var res = "";
        while (n != 0)
        {
            res = Base62Digit(n % 62) + res;
            n /= 62;
        }
        return res;
    }
    private static uint PermuteId(uint id)
    {
        uint l1 = (id >> 16) & 65535;
        uint r1 = id & 65535;
        uint l2, r2;
        for (int i = 0; i < 3; i++)
        {
            l2 = r1;
            r2 = l1 ^ (uint)(RoundFunction(r1) * 65535);
            l1 = l2;
            r1 = r2;
        }
        return ((r1 << 16) + l1);
    }


    private static string GenerateCode(uint id)
    {
        return ToBase62(PermuteId(id));
    }

    static void Main(string[] args)
    {

        Console.WriteLine("testing...");

            try
            {

                for (uint x = 1; x < 1000000; x += 1)
                {
                    Console.Write(GenerateCode(x) + ",");

                }

            }
            catch (Exception err)
            {
                Console.WriteLine("error: " + err.Message);
            }

        Console.WriteLine("");
        Console.WriteLine("Press ''Enter'' to continue...");
        Console.Read();
    }
}

Answer 2

Las soluciones basadas en una subcadena aleatoria no son buenas porque las salidas chocarán. Puede suceder prematuramente (con mala suerte), y eventualmente sucederá cuando la lista de valores generados crezca. Ni siquiera tiene que ser tan grande para que la probabilidad de colisiones sea alta (ver ataque de cumpleaños ).

Lo que es bueno para este problema es una permutación pseudoaleatoria entre el ID incremental y su contraparte que se mostrará en la URL. Esta técnica garantiza que una colisión es imposible, mientras se sigue generando en un espacio de salida que es tan pequeño como el espacio de entrada.

Implementación

Sugiero esta versión C # de un cifrado Feistel con bloques de 32 bits, 3 rondas y una función redonda que está inspirada en generadores pseudoaleatorios.

private static double RoundFunction(uint input)
{
    // Must be a function in the mathematical sense (x=y implies f(x)=f(y))
    // but it doesn''t have to be reversible.
    // Must return a value between 0 and 1
    return ((1369 * input + 150889) % 714025) / 714025.0;
}

private static uint PermuteId(uint id)
{
    uint l1=(id>>16)&65535;
    uint r1=id&65535;
    uint l2, r2;
    for (int i = 0; i < 3; i++)
    {
        l2 = r1;
        r2 = l1 ^ (uint)(RoundFunction(r1) * 65535);
        l1 = l2;
        r1 = r2;
    }
    return ((r1 << 16) + l1);
}

Para expresar el ID permutado en una cadena base62:

private static string GenerateCode(uint id)
{
    return ToBase62(PermuteId(id));
}

La función Base62 es la misma que la respuesta anterior, excepto que toma uint lugar de int (de lo contrario, estas funciones tendrían que reescribirse para tratar con valores negativos).

Personalizando el algoritmo

RoundFunction es la salsa secreta del algoritmo. Puede cambiarlo a una versión no pública, posiblemente incluyendo una clave secreta. La red Feistel tiene dos propiedades muy bonitas:

• incluso si el RoundFunction suministrado no es reversible, el algoritmo garantiza que PermuteId() será una permutación en el sentido matemático (lo que implica una colisión cero).

• cambiar la expresión dentro de la función redonda incluso ligeramente cambiará drásticamente la lista de valores de salida finales.

Tenga en cuenta que poner algo demasiado trivial en la expresión redonda arruinaría el efecto pseudoaleatorio, aunque aún funcionaría en términos de singularidad de cada salida de PermuteId . Además, una expresión que no sería una función en el sentido matemático sería incompatible con el algoritmo, por lo que, por ejemplo, cualquier cosa que implique random() no está permitida.

Reversibilidad

En su forma actual, la función PermuteId es su propio inverso, lo que significa que:

PermuteId(PermuteId(id))==id

Entonces, dada una cadena corta producida por el programa, si la convierte de nuevo a uint con una función FromBase62 , y la da como entrada a PermuteId() , devolverá el ID inicial correspondiente. Eso es bastante bueno si no tiene una base de datos para almacenar las relaciones [ID interna / shortstring]: ¡en realidad no es necesario almacenarlas!

Produciendo cuerdas aún más cortas

El rango de la función anterior es de 32 bits, es decir, alrededor de 4 mil millones de valores de 0 a 2^32-1 . Para expresar ese rango en base62, se necesitan 6 caracteres.

Con solo 5 caracteres, podríamos esperar representar como máximo 62^5 valores, que es un poco menos de 1 billón. Si la cadena de salida se limita a 5 caracteres, el código se debe ajustar de la siguiente manera:

• encuentre N tal que N sea ​​par y 2^N sea ​​lo más alto posible pero más bajo que 62^5 . Eso es 28, por lo que nuestro rango de salida real que se ajusta a 62^5 será de 2^28 o alrededor de 268 millones de valores.

• en PermuteId , use PermuteId 28/2=14 valores de 28/2=14 bits para l1 y r1 lugar de 16 bits, teniendo cuidado de no ignorar un solo bit de la entrada (que debe ser menor que 2 ^ 28).

• multiplique el resultado de RoundFunction por 16383 en lugar de 65535, para mantenerse dentro del rango de 14 bits.

• al final de PermuteId , PermuteId r1 y l1 para formar un valor de 14+14=28 bits en lugar de 32.

El mismo método podría aplicarse para 4 caracteres, con un rango de salida de 2^22 , o aproximadamente 4 millones de valores.

Cómo se ve

En la versión anterior, las primeras 10 cadenas generadas que comienzan con id = 1 son:

cZ6ahF 3t5mM xGNPN dxwUdS ej9SyV cmbVG3 cOlRkc bfCPOX JDr8Q eg7iuA

Si hago un cambio trivial en la función de ronda, eso se convierte en:

ey0LlY ddy0ak dDw3wm bVuNbg bKGX22 c0s5GZ dfNMSp ZySqE cxKH4b dNqMDA

Answer 3

Puede pensar en el código de cinco letras como un número en la notación de base 62: sus "dígitos" son 26 letras minúsculas y mayúsculas, y dígitos del 0 al 9. (26 + 26 + 10) dígitos en total. Dado un número de 0 a 62^5 (que equivale a 916132832) (por ejemplo, su clave principal), puede hacer la conversión a una base de 62 de cinco dígitos de la siguiente manera:

private static char Base62Digit(int d) {
    if (d < 26) {
        return (char)(''a''+d);
    } else if (d < 52) {
        return (char)(''A''+d-26);
    } else if (d < 62) {
        return (char)(''0''+d-52);
    } else {
        throw new ArgumentException("d");
    }
}

static string ToBase62(int n) {
    var res = "";
    while (n != 0) {
        res = Base62Digit(n%62) + res;
        n /= 62;
    }
    return res;
}

private static int Base62Decode(char c) {
    if (c >= ''0'' && c <= ''9'') {
        return 52 + c - ''0'';
    } else if (c >= ''A'' && c <= ''Z'') {
        return 26 + c - ''A'';
    } else if (c >= ''a'' && c <= ''z'') {
        return c - ''a'';
    } else {
        throw new ArgumentException("c");
    }
}

static int FromBase62(string s) {
    return s.Aggregate(0, (current, c) => current*62 + Base62Decode(c));
}

Aquí es cómo generar números aleatorios criptográficamente fuertes (es necesario agregar una referencia a System.Security ):

private static readonly RNGCryptoServiceProvider crypto =
    new RNGCryptoServiceProvider();

private static int NextRandom() {
    var buf = new byte[4];
    crypto.GetBytes(buf);
    return buf.Aggregate(0, (p, v) => (p << 8) + v) & 0x3FFFFFFF;
}