本文介绍了如何创建URL缩短器?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我想创建一个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。

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


解决方案

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>




示例实现(由评论者提供)












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?

解决方案

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)

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

08-20 11:40
查看更多