如何创建URL缩短器？ [英] How do I create a URL shortener?

问题描述

我想创建一个URL缩短服务，您可以在其中将长URL写入输入字段，然后该服务将URL缩短为 http://www.example.org/abcdef 。

除了 abcdef 之外，还可以有包含六个字符的其他任何字符串，其中包含 az，AZ和0-9 。这使56〜570亿个可能的字符串成为可能。

我的方法：

我有一个包含三列的数据库表：

1. id，整数，自动递增


2. 长字符串，字符串，用户的长网址输入


3. 短，字符串，缩短的URL（或仅输入六个字符）

I然后将长网址插入表格中。然后，我将为 id 选择自动递增值，并为其构建一个哈希值。然后，此哈希应插入为 short 。但是我应该建立什么样的哈希？像MD5这样的哈希算法创建的字符串太长。我认为我不使用这些算法。

我的想法：

对于 http://www.google.de/ ，我得到了自动递增ID 239472 。然后，我执行以下步骤：

  short =’； 
如果可以被2整除，则将 a +结果除以短
如果可以被3整除，则将 b +结果除以短
 ... ...直到我得到除数为a和AZ。 
  

可以重复进行直到该数字不再可除。您认为这是个好方法吗？您有更好的主意吗？

_{由于对该主题的持续关注，我发布了GitHub的有效解决方案，其中包含 JavaScript ， PHP ， Python 和 Java 。如果愿意，可以添加您的解决方案：）}

解决方案

I将继续您的将数字转换为字符串方法。但是，您将意识到，如果您的ID是素数且大于52 ，则建议的算法将失败。

理论背景

您需要双射函数 f 。这是必要的，以便您可以为 f（123）=‘abc’函数找到反函数 g（'abc'）= 123 。这意味着：

• 必须没有 x1，x2（x1≠x2） > f（x1）= f（x2），


• ，对于每个 y ，您都必须能够找到 x ，这样 f（x）= y 。

如何将ID转换为缩短的URL

1. 想想我们要使用的字母。您的情况是 [a-zA-Z0-9] 。它包含 62个字母。



2. 采用自动生成的唯一数字键（自动递增的 id 。

   
   
   

   在此示例中，我将使用125 ₁₀ （125以10为底）。




3. 现在，您必须将125 ₁₀ 转换为X ₆₂ （以62为基数）。 / p>
   
   

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

   
   
   

   这需要使用整数除法和取模。伪代码示例：

     digits = [] 
    
   而num> 0 
   余数=模（num，62）
   位.push（remainder）
    num =除法（num，62）
    
   位=位数。 $ b  

   现在将索引2和1 映射到您的字母。这就是您的映射（例如，带有数组）的样子：

     0→a 
    1→b 
    ... 
    25→z 
    ... 
    52→0 
    61→9 
     

   使用2→c和1→b，您将收到cb ₆₂ 作为缩短的URL。

     http：//shor.ty/cb 
     





如何将缩短的URL解析为初始ID

反之则更加容易。您只需按字母反向查找即可。

1. e9a ₆₂ 将解析为第4 ，第61个和第0个字母。

   
   
   

   e9a ₆₂ = [4,61,0] = 4×62 ² + 61×62 ¹ + 0×62 ⁰ = 19158 ₁₀




2. 现在找到带有 WHERE id = 19158 的数据库记录，并进行重定向。 / p>

示例实现（由评论者提供）

• C ++


• Python


• Ruby


• 哈斯克尔


• C＃


• CoffeeScript


• Perl

I want to create a URL shortener service where you can write a long URL into an input field and the service shortens the URL to "http://www.example.org/abcdef".

Instead of "abcdef" there can be any other string with six characters containing a-z, A-Z and 0-9. That makes 56~57 billion possible strings.

My approach:

I have a database table with three columns:

1. id, integer, auto-increment
2. long, string, the long URL the user entered
3. short, string, the shortened URL (or just the six characters)

I would then insert the long URL into the table. Then I would select the auto-increment value for "id" and build a hash of it. This hash should then be inserted as "short". But what sort of hash should I build? Hash algorithms like MD5 create too long strings. I don't use these algorithms, I think. A self-built algorithm will work, too.

My idea:

For "http://www.google.de/" I get the auto-increment id 239472. Then I do the following steps:

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.

That could be repeated until the number isn't divisible any more. Do you think this is a good approach? Do you have a better idea?

_{Due to the ongoing interest in this topic, I've published an efficient solution to GitHub, with implementations for JavaScript, PHP, Python and Java. Add your solutions if you like :)}

解决方案

I would continue your "convert number to string" approach. However, you will realize that your proposed algorithm fails if your ID is a prime and greater than 52.

Theoretical background

You need a Bijective Function f. This is necessary so that you can find a inverse function g('abc') = 123 for your f(123) = 'abc' function. This means:

• There must be no x1, x2 (with x1 ≠ x2) that will make f(x1) = f(x2),
• and for every y you must be able to find an x so that f(x) = y.

How to convert the ID to a shortened URL

1. Think of an alphabet we want to use. In your case, that's [a-zA-Z0-9]. It contains 62 letters.

2. Take an auto-generated, unique numerical key (the auto-incremented id of a MySQL table for example).

   For this example, I will use 125₁₀ (125 with a base of 10).

3. Now you have to convert 125₁₀ to X₆₂ (base 62).

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

   This requires the use of integer division and modulo. A pseudo-code example:

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

   Now map the indices 2 and 1 to your alphabet. This is how your mapping (with an array for example) could look like:

   0  → a
   1  → b
   ...
   25 → z
   ...
   52 → 0
   61 → 9
   

   With 2 → c and 1 → b, you will receive cb₆₂ as the shortened URL.

   http://shor.ty/cb
   

How to resolve a shortened URL to the initial ID

The reverse is even easier. You just do a reverse lookup in your alphabet.

1. e9a₆₂ will be resolved to "4th, 61st, and 0th letter in the alphabet".

   e9a₆₂ = [4,61,0] = 4×62² + 61×62¹ + 0×62⁰ = 19158₁₀

2. Now find your database-record with WHERE id = 19158 and do the redirect.

Example implementations (provided by commenters)

• C++
• Python
• Ruby
• Haskell
• C#
• CoffeeScript
• Perl

这篇关于如何创建URL缩短器？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！