如何创建URL缩短器？

Question

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

而不是" abcdef"可以有任何其他六个字符包含的字符串a-z, A-Z and 0-9.这使得56到570亿个可能的字符串.

我的方法:

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

1. id,integer,auto-increment
2. long,string,用户输入的长URL
3. short,string,缩短的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.

这可以重复,直到数字不再可分.你认为这是一个好方法吗？你有更好的主意吗？

_{由于对该主题的持续兴趣,我发布了一个有效的GitHub解决方案,包括JavaScript,PHP,Python和Java的实现.如果你愿意,可以添加你的解}

Answer 1

我会继续你的"转换数字串"方法.但是,如果您的ID是素数并且大于52,您将意识到您提出的算法会失败.

理论背景

你需要一个双射函数 f.这是必要的,这样你可以找到一个反函数克("ABC")= 123为您的F(123)="ABC"功能.这意味着:

• 必须没有x1,x2(x1≠x2)才能使f(x1)= f(x2),
• 并且对于每个y,你必须能够找到x,使得f(x)= y.

如何将ID转换为缩短的URL

1. 想想我们想要使用的字母表.在你的情况下,那是[a-zA-Z0-9].它包含62个字母.

2. 使用自动生成的唯一数字键(id例如,MySQL表的自动递增).

   对于这个例子,我将使用125 ₁₀(125基础为10).

3. 现在你必须将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
   

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

反过来更容易.您只需在字母表中执行反向查找.

1. e9a ₆₂将被解析为"字母表中的第4个,第61个和第0个字母".

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

2. 现在找到您的数据库记录WHERE id = 19158并执行重定向.

一些实现(由评论者提供)

• 红宝石
• 蟒蛇
• CoffeeScript的
• 哈斯克尔
• Perl的
• C#

Answer 2

你为什么要使用哈希？

您可以使用自动增量值的简单转换为字母数字值.您可以使用一些基本转换轻松完成此操作.假设您的字符空间(AZ,az,0-9等)有40个字符,将id转换为base-40数字并将字符用作数字.

Answer 3

public class UrlShortener {
    private static final String ALPHABET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private static final int    BASE     = ALPHABET.length();

    public static String encode(int num) {
        StringBuilder sb = new StringBuilder();
        while ( num > 0 ) {
            sb.append( ALPHABET.charAt( num % BASE ) );
            num /= BASE;
        }
        return sb.reverse().toString();   
    }

    public static int decode(String str) {
        int num = 0;
        for ( int i = 0; i < str.length(); i++ )
            num = num * BASE + ALPHABET.indexOf(str.charAt(i));
        return num;
    }   
}

Answer 4

不是您问题的答案,但我不会使用区分大小写的缩短网址.它们很难记住,通常是不可读的(许多字体渲染1和l,0和O以及其他字符非常相似,几乎不可能分辨出来)并且容易出错.尽量只使用小写或大写.

另外,尝试使用一种格式,以预定义的形式混合数字和字符.有研究表明,人们倾向于比其他人更好地记住一种形式(想想电话号码,其中数字以特定形式分组).尝试使用num-char-char-num-char-char之类的东西.我知道这会降低组合,特别是如果你没有大写和小写,但它会更有用,因此更有用.

Answer 5

我的方法:获取数据库ID,然后Base36编码.我不会同时使用大写和小写字母,因为这会使通过电话传输这些URL成为一场噩梦,但您当然可以轻松地将该功能扩展为基本62 /解码器.

Answer 6

这是我的PHP 5课程.

<?php
class Bijective
{
    public $dictionary = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

    public function __construct()
    {
        $this->dictionary = str_split($this->dictionary);
    }

    public function encode($i)
    {
        if ($i == 0)
        return $this->dictionary[0];

        $result = '';
        $base = count($this->dictionary);

        while ($i > 0)
        {
            $result[] = $this->dictionary[($i % $base)];
            $i = floor($i / $base);
        }

        $result = array_reverse($result);

        return join("", $result);
    }

    public function decode($input)
    {
        $i = 0;
        $base = count($this->dictionary);

        $input = str_split($input);

        foreach($input as $char)
        {
            $pos = array_search($char, $this->dictionary);

            $i = $i * $base + $pos;
        }

        return $i;
    }
}

Answer 7

Node.js和MongoDB解决方案

既然我们知道MongoDB用于创建具有12个字节的新ObjectId的格式。

• 一个4字节的值，表示自Unix时代以来的秒数，
• 一个3字节的机器标识符，
• 一个2字节的进程ID
• 一个3字节的计数器（在您的计算机中），以随机值开头。

示例（我选择一个随机序列） a1b2c3d4e5f6g7h8i9j1k2l3

• a1b2c3d4代表自Unix时代以来的秒数，
• 4e5f6g7代表机器标识符，
• h8i9表示进程ID
• j1k2l3代表从随机值开始的计数器。

由于如果我们将数据存储在同一台计算机上，计数器将是唯一的，因此毫无疑问，它可以重复获得。

因此，短网址将是计数器，这是一个假定您的服务器正常运行的代码段。

const mongoose = require('mongoose');
const Schema = mongoose.Schema;

// Create a schema
const shortUrl = new Schema({
    long_url: { type: String, required: true },
    short_url: { type: String, required: true, unique: true },
  });
const ShortUrl = mongoose.model('ShortUrl', shortUrl);

// The user can request to get a short URL by providing a long URL using a form

app.post('/shorten', function(req ,res){
    // Create a new shortUrl */
    // The submit form has an input with longURL as its name attribute.
    const longUrl = req.body["longURL"];
    const newUrl = ShortUrl({
        long_url : longUrl,
        short_url : "",
    });
    const shortUrl = newUrl._id.toString().slice(-6);
    newUrl.short_url = shortUrl;
    console.log(newUrl);
    newUrl.save(function(err){
        console.log("the new URL is added");
    })
});

Answer 8

我一直在数据库中为每个域增加一个整数序列，并使用Hashids将整数编码为 URL 路径。

static hashids = Hashids(salt = "my app rocks", minSize = 6)

我运行了一个脚本来查看它用完字符长度需要多长时间。对于六个字符，它可以进行164,916,224链接，然后最多可增加七个字符。Bitly 使用七个字符。五个字符以下对我来说看起来很奇怪。

Hashids可以将 URL 路径解码回整数，但更简单的解决方案是使用整个短链接sho.rt/ka8ds3作为主键。

这是完整的概念：

function addDomain(domain) {
    table("domains").insert("domain", domain, "seq", 0)
}

function addURL(domain, longURL) {
    seq = table("domains").where("domain = ?", domain).increment("seq")
    shortURL = domain + "/" + hashids.encode(seq)
    table("links").insert("short", shortURL, "long", longURL)
    return shortURL
}

// GET /:hashcode
function handleRequest(req, res) {
    shortURL = req.host + "/" + req.param("hashcode")
    longURL = table("links").where("short = ?", shortURL).get("long")
    res.redirect(301, longURL)
}