¿Cómo creo un acortador de URL? [cerrado]

Quiero crear un servicio de acortamiento de URL en el que pueda escribir una URL larga en un campo de entrada y el servicio acorta la URL a " http://www.example.org/abcdef".

En lugar de " abcdef" puede haber cualquier otra cadena que contenga seis caracteres a-z, A-Z and 0-9. Eso hace que haya entre 56 y 57 mil millones de cadenas posibles.

Mi acercamiento:

Tengo una tabla de base de datos con tres columnas:

id, entero, incremento automático
largo, cadena, la URL larga que ingresó el usuario
short, string, la URL acortada (o solo los seis caracteres)

Luego insertaría la URL larga en la tabla. Luego seleccionaría el valor de incremento automático para " id" y crearía un hash del mismo. Luego, este hash debe insertarse como " short". Pero, ¿qué tipo de hash debería crear? Los algoritmos hash como MD5 crean cadenas demasiado largas. Creo que no uso estos algoritmos. Un algoritmo de creación propia también funcionará.

Mi idea:

Para " http://www.google.de/" obtengo la identificación de incremento automático 239472. Luego hago los siguientes pasos:

short = '';
if divisible by 2, add "a"+the result to short
if divisible by 3, add "b"+the result to short
... until I have divisors for a-z and A-Z.

Esto podría repetirse hasta que el número ya no sea divisible. ¿Crees que este es un buen enfoque? Tienes una mejor idea?

_{Debido al interés continuo en este tema, publiqué una solución eficiente en GitHub , con implementaciones para JavaScript , PHP , Python y Java . Añade tus soluciones si quieres :)}

Apr 12 '09 23:04 caw

Continuaría con su enfoque de "convertir número en cadena". Sin embargo, se dará cuenta de que el algoritmo propuesto falla si su ID es primo y mayor que 52 .

Antecedentes teóricos

Necesitas una función biyectiva f . Esto es necesario para que puedas encontrar una función inversa g('abc') = 123 para tu función f(123) = 'abc' . Esto significa:

No debe haber x1, x2 (con x1 ≠ x2) que haga que f(x1) = f(x2) ,
y para cada y debes poder encontrar una x para que f(x) = y .

Cómo convertir el ID a una URL acortada

Piense en un alfabeto que queramos usar. En tu caso, eso es [a-zA-Z0-9]. Contiene 62 letras .
Tome una clave numérica única generada automáticamente (el incremento automático idde una tabla MySQL, por ejemplo).

Para este ejemplo, usaré 125 ₁₀ (125 con una base de 10).
Ahora tienes que convertir 125 ₁₀ a X ₆₂ (base 62).

125 ₁₀ = 2×62 ¹ + 1×62 ⁰ =[2,1]

Esto requiere el uso de división de enteros y módulo. Un ejemplo de pseudocódigo:
```
digits = []

while num > 0
  remainder = modulo(num, 62)
  digits.push(remainder)
  num = divide(num, 62)

digits = digits.reverse
```
Ahora asigna los índices 2 y 1 a tu alfabeto. Así es como podría verse su mapeo (con una matriz, por ejemplo):
```
0  → a
1  → b
...
25 → z
...
52 → 0
61 → 9
```
Con 2 → c y 1 → b, recibirá cb ₆₂ como URL abreviada.
```
http://shor.ty/cb
```

Cómo resolver una URL acortada al ID inicial

Lo contrario es aún más fácil. Simplemente haces una búsqueda inversa en tu alfabeto.

e9a ₆₂ se resolverá en "4ª, 61ª y 0ª letra del alfabeto".

e9a ₆₂ = [4,61,0]= 4×62 ² + 61×62 ¹ + 0×62 ⁰ = 19158 ₁₀
Ahora busque el registro de su base de datos WHERE id = 19158y realice la redirección.

Implementaciones de ejemplo (proporcionadas por comentaristas)

C++
Pitón
Rubí
Haskell
C#
CaféScript
perla

Apr 12 '2009 16:04 Marcel Jackwerth

¿Por qué querrías usar un hash?

Puede utilizar una traducción simple de su valor de incremento automático a un valor alfanumérico. Puede hacerlo fácilmente utilizando alguna conversión de base. Digamos que su espacio de caracteres (AZ, az, 0-9, etc.) tiene 62 caracteres, convierta la identificación a un número de base 40 y use los caracteres como dígitos.

Apr 12 '2009 16:04 shoosh