如何设计一个很小的URL或URL缩短器？

本文概述

• C ++
• Java
• Python3

如何设计一个采用大网址的系统并将其转换为短6个字符的系统网址。假定URL已存储在数据库中, 并且每个URL都有一个关联的整数ID。

需要注意的重要一件事是, 长网址也应该可以从短网址中唯一地识别出来。所以我们需要一个

双射函数

一个简单的解决方案可能是哈希。使用哈希函数将长字符串转换为短字符串。在散列中, 可能是冲突(2个长URL映射到相同的短URL), 并且我们需要为每个长URL唯一的短URL, 以便我们可以返回长URL。

一种更好的解决方案是使用存储在数据库中的整数id并将该整数转换为最多6个字符长的字符串。这个问题基本上可以看作是一个基本转换问题, 其中我们有一个10位数字的输入数字, 我们想将其转换为6个字符长的字符串。

以下是有关URL中可能字符的一项重要观察。

URL字符可以是以下之一

1)小写字母[a]到[z], 共26个字符

2)大写字母[A至Z], 共26个字符

3)数字[‘0’到’9’], 共10个字符

一共有26 + 26 + 10 = 62个可能的字符。

因此, 任务是将十进制数转换为以62为基数的数字。

要获取原始的长URL, 我们需要在数据库中获取URL ID。可以使用以62为底的十进制转换获得id。

C ++

//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

//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

# 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))

输出如下：

Generated short url is dnh
Id from url is 12345

优化：我们可以避免idToShortURL()中的反向步骤。为了确保返回相同的ID, 我们还需要更改shortURLtoID()以从头开始而不是从头开始处理字符。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。