algorithm - 如何创建 URL 缩短器？

<分区>

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

可以使用包含 a-z、A-Z 和 0-9 的六个字符的任何其他字符串来代替“abcdef”。这使得 56~570 亿个可能的字符串。

我的方法:

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

id，整数，自增
long, string, 用户输入的长URL
short，字符串，缩短的 URL(或只是六个字符)

然后我会将长 URL 插入表中。然后我会为“id”选择自动增量值并构建它的散列。然后应将此散列作为“short”插入。但是我应该构建什么样的哈希？像 MD5 这样的哈希算法会创建太长的字符串。我不使用这些算法，我想。自建算法也可以。

我的想法:

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

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.

这可以重复，直到数字不再可整除。你认为这是一个好方法吗？你有更好的主意吗？

_{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 :)}

最佳答案

我会继续您的“将数字转换为字符串”方法。但是，如果您的 ID 是素数且大于 52，您将意识到您提出的算法会失败。

理论背景

你需要一个 Bijective Function 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 个字母。
采用自动生成的唯一数字键(例如 MySQL 表的自动递增 id)。

对于这个例子，我将使用 125₁₀(125 以 10 为底)。
现在您必须将 125₁₀ 转换为 X₆₂(底数 62)。

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

这需要使用整数除法和取模。伪代码示例:
```
digits = []

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

digits = digits.reverse
```
现在将索引 2 和 1 映射到您的字母表。这就是您的映射(例如使用数组)的样子:
```
0  → a
1  → b
...
25 → z
...
52 → 0
61 → 9
```
对于 2 → c 和 1 → b，您将收到 cb₆₂ 作为缩短的 URL。
```
http://shor.ty/cb
```