问题描述
我想创建一个URL缩短服务,您可以在其中将长URL写入输入字段,然后该服务将URL缩短为 http://www.example.org/abcdef
。
除了 abcdef
之外,还可以有包含六个字符的其他任何字符串,其中包含 az,AZ和0-9
。这使56〜570亿个可能的字符串成为可能。
我的方法:
我有一个包含三列的数据库表:
- id,整数,自动递增
- 长字符串,字符串,用户的长网址输入
- 短,字符串,缩短的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
- 想想我们要使用的字母。您的情况是
[a-zA-Z0-9]
。它包含 62个字母。 -
采用自动生成的唯一数字键(自动递增的
id 。
在此示例中,我将使用125 (125以10为底)。
-
现在,您必须将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
反之则更加容易。您只需按字母反向查找即可。
-
e9a 将解析为第4 ,第61个和第0个字母。
e9a = [4,61,0]
= 4×62 + 61×62 + 0×62 = 19158
-
现在找到带有 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:
- id, integer, auto-increment
- long, string, the long URL the user entered
- 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
- Think of an alphabet we want to use. In your case, that's
[a-zA-Z0-9]
. It contains 62 letters. 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).
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.
e9a will be resolved to "4th, 61st, and 0th letter in the alphabet".
e9a = [4,61,0]
= 4×62 + 61×62 + 0×62 = 19158
Now find your database-record with WHERE id = 19158
and do the redirect.
Example implementations (provided by commenters)
这篇关于如何创建URL缩短器?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!