如何$ C℃的URL缩短$？ [英] How to code a URL shortener?

问题描述

我想创建一个URL缩短服务，您可以编写一个长的URL到输入字段和服务缩短的URL为 http://www.example.org/abcdef 。而不是 ABCDEF 可以有其他任何字符串包含包括AZ，az和0-9 六个字符。这使得56〜57十亿可能的字符串。

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.

编辑：由于这个话题在持续的兴趣，我已经上传了code，我使用的到GitHub上，以实现对的Java ，< A HREF =htt​​ps://github.com/delight-im/ShortURL/blob/master/PHP/ShortURL.php> PHP 和的 JavaScript的。添加您的解决方案，如果你喜欢：）

Due to the ongoing interest in this topic, I've uploaded the code that I used to GitHub, with implementations for Java, PHP and JavaScript. Add your solutions if you like :)

我的方法：

我有三列的数据库表：

1. 的id，整数，自动递增
2. 长字符串，用户输入的长的URL
3. 短，字符串，缩短URL（或只是六个字符）

我会再插入长的URL到表中。然后，我会选择 ID 自动递增值，并建立它的哈希值。这个hash应该再增加一条，作为短。但我应该建立什么样的哈希？哈希算法，如MD5创建过长的字符串。我不使用这些算法，我想。自建的算法将工作了。

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.

我的想法：

有关 http://www.google.de/ 我得到的自动递增ID 239472 。然后，我做以下步骤：

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?

推荐答案

我会继续你的转换号码字符串的方法。但是你会发现，你的算法失败，如果你的ID是的素数，大于52 的。

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.

您需要双射函数的 F 的。这是必要的，这样你可以找到一个反函数的克（'ABC'）= 123 的为您的 F（123）='ABC'的功能。这意味着：

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:

• 必须有没有的 X1，X2（与X1≠X2）的，这将使的 F（X）= F（X2）的
• ，并为每一位的是的你一定能找到的 X 的，这样的 F（X）= Y 的

• 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.

1. 认为我们要使用一个字母。你的情况这是 [A-ZA-Z0-9] 。它包含的 62字母的

2. 取（MySQL表例如自动递增 ID ）自动生成的，唯一的数字键。

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

在这个例子中，我将使用125 ₁₀ （125与10的位置）。

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

现在你要转换125 ₁₀ 至X ₆₂ （基地62）。

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

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

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

这需要使用整数除法和模数的。一个伪code例如：

This requires 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

现在映射的指数2和1 的你的字母。这就是你的映射（一个数组为例）可能看起来像：

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

使用2→c和1→B您将收到CB ₆₂ 为缩短的URL。

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 ₆₂ 将被解析为第4，第61，而在第0拼音字母。

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

E9A ₆₂ = [4,61,0] = 4×62 ² + 61×62 < SUP> 1 + 0×62 ⁰ = 19158 ₁₀

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

现在发现你的数据库记录与 WHERE ID = 19158 并执行重定向。

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

• 红宝石
• 的Python
• CoffeeScript的
• 哈斯克尔
• 的Perl
• C＃

Some implementations (provided by commenters)

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

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