¿Cómo diseñar una URL pequeña o un acortador de URL?

Cómo diseñar un sistema que tome direcciones URL grandes como «https://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/» y las convierta en un carácter corto de 6 URL Se da que las URL se almacenan en la base de datos y cada URL tiene una identificación de número entero asociada. 

Una cosa importante a tener en cuenta es que la URL larga también debe ser identificable de forma única a partir de la URL corta. Entonces necesitamos una función biyectiva  

Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.

Una solución simple podría ser Hashing. Use una función hash para convertir una string larga en una string corta. En hashing, eso puede ser colisiones (2 URL largas se asignan a la misma URL corta) y necesitamos una URL corta única para cada URL larga para que podamos acceder a la URL larga.

Una mejor solución es usar la identificación del entero almacenada en la base de datos y convertir el entero en una string de caracteres que tenga como máximo 6 caracteres. Básicamente, este problema puede verse como un problema de conversión de base en el que tenemos un número de entrada de 10 dígitos y queremos convertirlo en una string de 6 caracteres. 

A continuación hay una observación importante sobre los posibles caracteres en la URL.

Un carácter de URL puede ser uno de los siguientes 

1. Un alfabeto en minúsculas [‘a’ a ‘z’], total 26 caracteres 
2. Un alfabeto en mayúsculas [‘A’ a ‘Z’], total 26 caracteres 
3. Un dígito [‘0’ a ‘9’], 10 caracteres en total

Hay un total de 26 + 26 + 10 = 62 caracteres posibles.
Entonces, la tarea es convertir un número decimal a un número de base 62. 
Para obtener la URL larga original, necesitamos obtener la identificación de la URL en la base de datos. La identificación se puede obtener utilizando la conversión de base 62 a decimal.

Implementación:

// C++ program to generate short url from integer id and
// integer id back from short url.
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
  
// Function to generate a short url from integer ID
string idToShortURL(long int n)
{
    // Map to store 62 possible characters
    char map[] = "abcdefghijklmnopqrstuvwxyzABCDEF"
                 "GHIJKLMNOPQRSTUVWXYZ0123456789";
  
    string shorturl;
  
    // Convert given integer id to a base 62 number
    while (n)
    {
        // use above map to store actual character
        // in short url
        shorturl.push_back(map[n%62]);
        n = n/62;
    }
  
    // Reverse shortURL to complete base conversion
    reverse(shorturl.begin(), shorturl.end());
  
    return shorturl;
}
  
// Function to get integer ID back from a short url
long int shortURLtoID(string shortURL)
{
    long int id = 0; // initialize result
  
    // A simple base conversion logic
    for (int i=0; i < shortURL.length(); i++)
    {
        if ('a' <= shortURL[i] && shortURL[i] <= 'z')
          id = id*62 + shortURL[i] - 'a';
        if ('A' <= shortURL[i] && shortURL[i] <= 'Z')
          id = id*62 + shortURL[i] - 'A' + 26;
        if ('0' <= shortURL[i] && shortURL[i] <= '9')
          id = id*62 + shortURL[i] - '0' + 52;
    }
    return id;
}
  
// Driver program to test above function
int main()
{
    int n = 12345;
    string shorturl = idToShortURL(n);
    cout << "Generated short url is " << shorturl << endl;
    cout << "Id from url is " << shortURLtoID(shorturl);
    return 0;
}

// Java program to generate short url from integer id and 
// integer id back from short url. 
import java.util.*;
import java.lang.*;
import java.io.*;
  
class GFG
{
    // Function to generate a short url from integer ID 
    static String idToShortURL(int n) 
    { 
        // Map to store 62 possible characters 
        char map[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789".toCharArray(); 
      
        StringBuffer shorturl = new StringBuffer(); 
      
        // Convert given integer id to a base 62 number 
        while (n > 0) 
        { 
            // use above map to store actual character 
            // in short url 
            shorturl.append(map[n % 62]);
            n = n / 62; 
        } 
      
        // Reverse shortURL to complete base conversion 
        return shorturl.reverse().toString(); 
    } 
      
    // Function to get integer ID back from a short url 
    static int shortURLtoID(String shortURL) 
    { 
        int id = 0; // initialize result 
      
        // A simple base conversion logic 
        for (int i = 0; i < shortURL.length(); i++) 
        { 
            if ('a' <= shortURL.charAt(i) && 
                       shortURL.charAt(i) <= 'z') 
            id = id * 62 + shortURL.charAt(i) - 'a'; 
            if ('A' <= shortURL.charAt(i) && 
                       shortURL.charAt(i) <= 'Z') 
            id = id * 62 + shortURL.charAt(i) - 'A' + 26; 
            if ('0' <= shortURL.charAt(i) && 
                       shortURL.charAt(i) <= '9') 
            id = id * 62 + shortURL.charAt(i) - '0' + 52; 
        } 
        return id; 
    } 
      
    // Driver Code
    public static void main (String[] args) throws IOException
    {
        int n = 12345; 
        String shorturl = idToShortURL(n); 
        System.out.println("Generated short url is " + shorturl); 
        System.out.println("Id from url is " + 
                            shortURLtoID(shorturl)); 
    }
}
  
// This code is contributed by shubham96301

# Python3 code for above approach 
def idToShortURL(id):
    map = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
    shortURL = ""
      
    # for each digit find the base 62
    while(id > 0):
        shortURL += map[id % 62]
        id //= 62
  
    # reversing the shortURL
    return shortURL[len(shortURL): : -1]
  
def shortURLToId(shortURL):
    id = 0
    for i in shortURL:
        val_i = ord(i)
        if(val_i >= ord('a') and val_i <= ord('z')):
            id = id*62 + val_i - ord('a')
        elif(val_i >= ord('A') and val_i <= ord('Z')):
            id = id*62 + val_i - ord('Z') + 26
        else:
            id = id*62 + val_i - ord('0') + 52
    return id
  
if (__name__ == "__main__"):
    id = 12345
    shortURL = idToShortURL(id)
    print("Short URL from 12345 is : ", shortURL)
    print("ID from", shortURL, "is : ", shortURLToId(shortURL))

// C# program to generate short url from integer id and 
// integer id back from short url. 
using System;
  
public class GFG
{
    // Function to generate a short url from integer ID 
    static String idToShortURL(int n) 
    { 
        // Map to store 62 possible characters 
        char []map = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789".ToCharArray(); 
      
        String shorturl = "";  
       
        // Convert given integer id to a base 62 number 
        while (n > 0) 
        { 
            // use above map to store actual character 
            // in short url 
            shorturl+=(map[n % 62]);
            n = n / 62; 
        } 
      
        // Reverse shortURL to complete base conversion 
        return reverse(shorturl); 
    } 
    static String reverse(String input) {
        char[] a = input.ToCharArray();
        int l, r = a.Length - 1;
        for (l = 0; l < r; l++, r--) {
            char temp = a[l];
            a[l] = a[r];
            a[r] = temp;
        }
        return String.Join("",a);
    }
    // Function to get integer ID back from a short url 
    static int shortURLtoID(String shortURL) 
    { 
        int id = 0; // initialize result 
      
        // A simple base conversion logic 
        for (int i = 0; i < shortURL.Length; i++) 
        { 
            if ('a' <= shortURL[i] && 
                       shortURL[i] <= 'z') 
            id = id * 62 + shortURL[i] - 'a'; 
            if ('A' <= shortURL[i] && 
                       shortURL[i] <= 'Z') 
            id = id * 62 + shortURL[i] - 'A' + 26; 
            if ('0' <= shortURL[i] && 
                       shortURL[i] <= '9') 
            id = id * 62 + shortURL[i] - '0' + 52; 
        } 
        return id; 
    } 
      
    // Driver Code
    public static void Main(String[] args)
    {
        int n = 12345; 
        String shorturl = idToShortURL(n); 
        Console.WriteLine("Generated short url is " + shorturl); 
        Console.WriteLine("Id from url is " + 
                            shortURLtoID(shorturl)); 
    }
}
  
// This code is contributed by 29AjayKumar

<script>
// Javascript program to generate short url from integer id and
// integer id back from short url.
  
// Function to generate a short url from integer ID
function idToShortURL(n) 
{
  
    // Map to store 62 possible characters
    let map = "abcdefghijklmnopqrstuvwxyzABCDEF"
    "GHIJKLMNOPQRSTUVWXYZ0123456789";
  
    let shorturl = [];
  
    // Convert given integer id to a base 62 number
    while (n) 
    {
        // use above map to store actual character
        // in short url
        shorturl.push(map[n % 62]);
        n = Math.floor(n / 62);
    }
  
    // Reverse shortURL to complete base conversion
    shorturl.reverse();
  
    return shorturl.join("");
}
  
// Function to get integer ID back from a short url
function shortURLtoID(shortURL) {
    let id = 0; // initialize result
  
    // A simple base conversion logic
    for (let i = 0; i < shortURL.length; i++) {
        if ('a' <= shortURL[i] && shortURL[i] <= 'z')
            id = id * 62 + shortURL[i].charCodeAt(0) - 'a'.charCodeAt(0);
        if ('A' <= shortURL[i] && shortURL[i] <= 'Z')
            id = id * 62 + shortURL[i].charCodeAt(0) - 'A'.charCodeAt(0) + 26;
        if ('0' <= shortURL[i] && shortURL[i] <= '9')
            id = id * 62 + shortURL[i].charCodeAt(0) - '0'.charCodeAt(0) + 52;
    }
    return id;
}
  
// Driver program to test above function
  
let n = 12345;
let shorturl = idToShortURL(n);
document.write("Generated short url is " + shorturl + "<br>");
document.write("Id from url is " + shortURLtoID(shorturl));
  
// This code is contributed by gfgking.
</script>

Generated short url is dnh
Id from url is 12345

Complejidad temporal : O(n) 
Espacio auxiliar : O(1)

Optimización: podemos evitar el paso inverso en idToShortURL(). Para asegurarnos de recuperar el mismo ID, también debemos cambiar shortURLtoID() para procesar los caracteres desde el final en lugar de desde el principio.