Algoritmo de URL de YouTube?

¿Cómo podría generar las URL de video únicas que usa YouTube?

Ejemplo:

  • http://www.youtube.com/watch?v=CvUN8qg9lsk

Usando alguna función de hashing no trivial. La probabilidad de colisión es muy baja, dependiendo de la función, los parámetros y el dominio de entrada. Tenga en cuenta que los hash criptográficos se diseñaron específicamente para tener tasas de colisión muy bajas para entradas no aleatorias (es decir, hashes completamente diferentes para dos entradas cercanas pero desiguales).

Esta publicación de Jeff Attwood es una buena descripción general del tema.

Y aquí hay una calculadora hash en línea con la que puedes jugar.

YouTube usa la encoding Base64 para generar identificadores para cada video. Los personajes involucrados en la generación de ID constan de

(AZ) + (az) + (0-9) + (-) + (_). (64 caracteres).

Al usar la encoding Base64 y solo hasta 11 caracteres, pueden generar más de 73 identificadores únicos quintilianos. ¿Cuánto grupo grande de ID es ese?

Bueno, es suficiente para que todos en la tierra produzcan video cada minuto por 18000 años.

Y han logrado un número tan grande usando solo 11 caracteres (64 * 64 * 64 * 64 * 64 * 64 * 64 * 64 * 64 * 64 * 64). Si necesitan más ID, simplemente tendrán que agregar 1 carácter más a sus identificaciones

Por lo tanto, cuando se sube un video en YouTube, básicamente seleccionan aleatoriamente entre la opción Quintiliana de más de 73 y ver si ya se ha tomado o no. Si no la usa, busque otra.

Consulte este video para una explicación detallada.

No hay necesidad de usar un hash. Probablemente sea solo un valor casi aleatorio de 64 bits pasado a través de base64 o algún equivalente.

Por cuasialeatorio, quiero decir que es solo un mapeo de uno a uno con los enteros de conteo, simplemente mezclados.

Por ejemplo, podría tomar una identificación de base de datos que aumenta monótonamente y multiplicarla por un primo cerca de 2 ^ 64, luego base64 el resultado. Si no desea que las personas puedan adivinar, puede elegir un mapeo más complejo o simplemente elegir un número al azar que aún no se encuentre en la base de datos.

La base64 normal agregaría un igual al final, pero en este caso está implícito porque se conoce el tamaño. El mapeo de caracteres podría ser algo más que el estándar.

El enlace de Eli con el artículo de Jeff es, en mi opinión, irrelevante. El acortamiento de URL no es lo mismo que presentar una identificación al mundo. En su lugar, una forma más agradable sería convertir su ID entero existente en una raíz diferente.

Un ejemplo en PHP:

$id = 9999; //$url_id = base_convert($id, 10, 26+26+10); // PHP doesn't like this $url_id = base_convert($id, 10, 26+10); // Works, but only digits + lowercase 

Lamentablemente, PHP solo admite hasta la base 36 (dígitos + alfabeto). La base 62 admitiría el alfabeto en mayúsculas y minúsculas.


La gente está hablando de estos otros sistemas:

  • Número aleatorio / letras – ¿Por qué? Si desea que las personas no vean el siguiente video (id + 1), solo haga que sea privado. En un sitio web como youtube, donde muestra activamente cualquier video que tiene, ¿por qué molestarse con los identificadores aleatorios?
  • Hashing a ID: este concepto de diseño realmente apesta. Piénsalo; entonces usted tiene una identificación garantizada por su software de DBM para ser única, y la tiene (¿introduce un factor de colisión)? Dame una razón por la cual considerar esta idea.
  • Usar la ID en la URL: para ser sincero, tampoco veo ningún problema con esto, aunque crecerá hasta ser grande, cuando en realidad puedes express el mismo número con menos letras (de ahí mi solución).
  • Usando Base64 – Base64 espera bytes de datos, literalmente cualquier cosa, desde nulos a espacios. ¿Por qué utilizar esta función cuando sus datos consisten en un número (es decir, una mezcla de 10 caracteres diferentes, en lugar de 256)?

Probablemente su mejor opción sea simplemente generar cadenas aleatorias y realizar un seguimiento (en una base de datos, por ejemplo) de qué cadenas ya ha utilizado para que no se duplique. Esto es muy fácil de implementar y no puede fallar si se implementa correctamente (no hay duplicados, etc.).

Puede generar un GUID y tenerlo como ID para el video. Es muy poco probable que las guías colisionen.

No creo que el parámetro URL v tenga nada que ver con el contenido (propiedades del video, título, descripción, etc.).

Es una cadena de longitud fija generada aleatoriamente y contiene un conjunto muy específico de caracteres. No se permiten duplicados.

Sugiero usar una función hash perfecta:

Función perfecta de hash para códigos de orden de lectura humana

Como lo indica la respuesta aceptada, tome un número, luego aplique una secuencia de operaciones “biyectivas” (o reversibles) en el número para obtener un número hash.

Los números de entrada deben estar en secuencia: 0, 1, 2, 3, y así sucesivamente.

Simplemente elija valores aleatorios hasta que tenga uno nunca visto antes.

Escoger aleatoriamente y agotar todos los valores de un conjunto se ejecuta en el tiempo esperado O(nlogn) : ¿Cuál es el valor de O para la selección aleatoria ingenua del conjunto finito?

En su caso, no agotaría el conjunto, por lo que debería obtener selecciones de tiempo constante. Simplemente use una estructura de datos rápida para hacer las búsquedas de duplicación.

Probablemente, YouTube tiene una tabla de base de datos pregenerada con todas las posibilidades desde 000000 aaaaaa hasta XXXXXX. Cuando se crea un video, se busca, elimina y utiliza una fila al azar de la tabla para la identificación del video. Con esta técnica, las identificaciones serán garantizadas únicas y aleatorias para los humanos. ¡La tabla podría ser prefiltrada en entradas como 00bbee!