Creando su propio uid de estilo Tinyurl

Question

Estoy escribiendo un pequeño artículo sobre alternativas legibles para las personas a los Guids/UID, por ejemplo los utilizados en TinyURL para los hashes de url (que a menudo se imprimen en revistas, por lo que deben ser cortos).

El uid simple que estoy generando es de 6 caracteres: una letra minúscula (a-z) o 0-9.

"De acuerdo con mis cálculos capitán", son 6 eventos mutuamente excluyentes, aunque calcular la probabilidad de un choque es un poco más difícil que P (A o B) = P (A) + P (B), obviamente incluye números y del código a continuación, puede ver que funciona si usar un número o letra usando 50/50.

Me interesa la tasa de choque y si el siguiente código es una simulación realista de la tasa de choque anticipada que obtendrías al generar un hash. En promedio, recibo 40-50 choques por millón, sin embargo, teniendo en cuenta que el uid no se generaría un millón de veces a la vez, sino probablemente solo entre 10 y 1000 veces por minuto.

¿Cuál es la probabilidad de un choque cada vez, y alguien puede sugerir una mejor manera de hacerlo?

static Random _random = new Random(); 

public static void main() 
{ 
    // Size of the key, 6 
    HashSet<string> set = new HashSet<string>(); 
    int clashes = 0; 
    for (int n=0;n < 1000000;n++) 
    { 
     StringBuilder builder = new StringBuilder(); 

     for (int i =0;i < 7;i++) 
     { 
      if (_random.NextDouble() > 0.5) 
      { 
       builder.Append((char)_random.Next(97,123)); 
      } 
      else 
      { 
       builder.Append(_random.Next(0,9).ToString()); 
      } 
     } 

     if (set.Contains(builder.ToString())) 
     { 
      clashes++; 
      Console.WriteLine("clash: (" +n+ ")" +builder.ToString()); 
     } 

     set.Add(builder.ToString()); 
     _random.Next(); 
     //Console.Write(builder.ToString()); 
    } 

    Console.WriteLine("Clashes: " +clashes); 
    Console.ReadLine(); 
} 

ACTUALIZACIÓN: Here's the resulting article de esta pregunta

Realmente hizo dos preguntas aquí, así que estaba haciendo trampa. La respuesta que estaba buscando era la de Rcar, sin embargo, Sklivvz también es la respuesta a la segunda parte (una alternativa). ¿Es posible crear un generador de ID único personalizado en una base de datos, o sería del lado del cliente (lo que serían 2 posibles lecturas primero)?

La idea general que perseguía era usar Ids en bases de datos u otras tiendas que se pueden usar por teléfono o material impreso, no como un guiado gigante de 16 bytes.

ACTUALIZACIÓN 2: Puse la fórmula para dos eventos mutuamente excluyentes arriba en lugar de 2 independientes (ya que obtener una 'a' la primera vez no significa que no puede obtener una 'a' la segunda vez) Debería haber sido P (A y B) = P (A) x P (B)

Answer 1

La probabilidad de una colisión contra un ID específico es:

p = (0.5 * ((0.5*1/10) + (0.5*1/26)))^6 

que es de alrededor de 1,7 x 10^-9.

La probabilidad de una colisión después de generar n IDs es 1-p^n, por lo que tendrá aproximadamente un 0,17% de probabilidad de una colisión por cada nueva inserción después de haber insertado 1 millón de ID, alrededor del 1,7% después de 10 millones de ID, y alrededor del 16% después de 100 millones.

1000 identificadores/minuto equivale a unos 43 millones/mes, por lo que, como señaló Sklivvz, probablemente sea mejor utilizar una identificación incremental en este caso.

EDIT:

para explicar las matemáticas, que está volteando esencialmente una moneda y luego elegir un número o una letra 6 veces. Hay una probabilidad de 0.5 de que el lanzamiento de moneda coincida, y luego el 50% del tiempo hay una probabilidad de 1/10 de igualación y un 50% de probabilidad de una probabilidad de coincidencia de 1/26. Eso sucede 6 veces de forma independiente, por lo que multiplicas esas probabilidades juntas.

Answer 2

Busque el Birthday Paradox, es el problema exacto con el que se está encontrando.

La pregunta es: ¿Cuántas personas necesita para reunirse en una habitación, de modo que tiene un 50% de probabilidades de que dos personas tengan la misma fecha de nacimiento? La respuesta puede sorprenderte.

Answer 3

¿Por qué no usar simplemente un algoritmo hash? y usar un hash de la url?

si usa números aleatorios es probable que tenga conflictos porque son indeterminados.

hashes no son provablemente únicos, pero existe una gran posibilidad de que el hash de una cadena sea único.

Corrección

En realidad espera que desea que sean humanamente legible, ... si se los pone en hexadecimal son técnicamente humanamente legible.

o puede usar un algoritmo que convierte un hash en una cadena humanamente legible. si la cadena humanamente legible es una representación diferente del hash, también debería ser tan "única" como el hash, es decir, la base 36 del hash original.

Answer 4

¿Por qué desea utilizar una función aleatoria? Siempre asumí que tinyurl usaba una representación de base 62 (0-9A-Za-z) de un Id secuencial. No hay enfrentamientos y las urls son siempre lo más cortas posible.

Usted tiene una tabla DB como

Id URL 
1 http://google.com 
2 ... 
... ... 
156 ... 
... ... 

y las URL correspondientes serían:

http://example.com/1 
http://example.com/2 
... 
http://example.com/2W 
... 

Answer 5

que generaría un valor representativo aleatoria de los datos que se va a hachís, y luego, haga un hash y compruebe los clahses en lugar de intentar simular con hashes aleatorios manualmente. Esto te dará un mejor indicador. Y tendrás más aleatoriedad porque tendrás más para aleatorizar (suponiendo que tus datos para ser hasheados son más grandes :)).

Answer 6

Si está usando 6 caracteres, a-z y 0-9, eso es un total de 36 caracteres. El número de permutaciones es, por lo tanto, 36^6, que es 2176782336 .. por lo que solo debe chocar 1/2176782336 veces.

Answer 7

de wikipedia:

Al imprimir menos caracteres que se desea, GUID son a veces codificados en una cadena base64 o ASCII85. Base64 codificado GUID se compone de 22 a 24 caracteres (dependiendo de relleno), por ejemplo:

7QDBkvCA1+B9K/U0vrQx1A 
7QDBkvCA1+B9K/U0vrQx1A== 

y ASCII85 codificación da sólo 20 caracteres, e. g .:

5:$Hj:Pf\4RLB9%kU\Lj 

Así que si usted está preocupado con singularidad, una base64 GUID que se pone un poco más cerca de lo que quiere, aunque no es de 6 caracteres.

Lo mejor es trabajar en bytes primero, luego traducir esos bytes a hexadecimal para mostrar, en lugar de trabajar con caracteres directamente.

Answer 8

Hace un tiempo hice exactamente esto, y seguí el camino mencionado por Sklivvz. Toda la lógica se desarrolló con un procedimiento almacenado del servidor SQL y un par de UDF (funciones definidas por el usuario). Los pasos fueron:

• decir que desea acortar esta url: Creating your own Tinyurl style uid
• Introduzca la URL en una mesa
• obtener el valor de @@ identidad de la última inserción (un identificador numérico)
• transformar el id en un valor alfanumérico correspondiente, sobre la base de un "dominio" de letras y números (que en realidad utilizado este conjunto: "ABCDEFGHIJKLMNOPQRSTUVWXYZ")
• devolverá ese valor hacia atrás, algo así como 'A0'

La conversión se realizó a través de un par de UDF muy cortas.

Dos valores de conversión llamado uno tras otro volvería "secuencial" como estos:

select dbo.FX_CONV (123456) -- returns "1f5n" 

select dbo.FX_CONV (123457) -- returns "1f5o" 

Si usted está interesado puedo compartir el código de la UDF.