我想创建一个URL缩短服务,您可以在其中将长URL写入输入字段,该服务将URL缩短为“ http://www.example.org/abcdef
” .
可以是包含 a-z, A-Z and 0-9
的六个字符的任何其他字符串,而不是“ abcdef
” . 这使得56到570亿个可能的字符串 .
我的方法:
我有一个包含三列的数据库表:
-
id,整数,自动递增
-
long,string,用户输入的长URL
-
short,string,缩短的URL(或只是六个字符)
然后我会将长URL插入表中 . 然后我会选择“ id
" and build a hash of it. This hash should then be inserted as " 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的实现 . 如果你愿意,添加你的解决方案
27 回答
这是一个适合PHP的URL编码功能...
我会继续你的"convert number to string"方法 . 但是,如果您的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
) .对于这个例子,我将使用12510(125的基数为10) .
12510 = 2×621 1×620 =
[2,1]
这需要使用整数除法和模数 . 一个伪代码示例:
现在将索引2和1映射到您的字母表 . 这是您的映射(例如,使用数组)的样子:
使用2→c和1→b,您将收到cb62作为缩短的URL .
如何将缩短的URL解析为初始ID
反过来更容易 . 您只需在字母表中执行反向查找 .
e9a62 =
[4,61,0]
= 4×622 61×621 0×620 = 1915810WHERE id = 19158
找到您的数据库记录并执行重定向 .一些实现(由评论者提供)
Ruby
Python
CoffeeScript
Haskell
Perl
C#
你为什么要使用哈希?
您可以使用自动增量值的简单转换为字母数字值 . 您可以使用一些基本转换轻松完成此操作 . 假设您的字符空间(A-Z,a-z,0-9等)有40个字符,将id转换为base-40数字并将字符用作数字 .
不是您问题的答案,但我不会使用区分大小写的缩短网址 . 它们很难记住,通常是不可读的(许多字体渲染1和l,0和O以及其他字符非常相似,几乎不可能分辨出来)并且容易出错 . 尽量只使用小写或大写 .
此外,尝试使用一种格式,以预定义的形式混合数字和字符 . 有研究表明,人们倾向于比其他人更好地记住一种形式(想想电话号码,其中数字以特定形式分组) . 尝试使用num-char-char-num-char-char之类的东西 . 我知道这会降低组合,特别是如果你没有大小写,但它会更有用,因此更有用 .
我的方法:获取数据库ID,然后Base36 Encode it . 我不会同时使用大写和小写字母,因为这会使通过电话传输这些URL成为一场噩梦,但您当然可以轻松地将该功能扩展为基本62 /解码器 .
这是我的PHP 5课程 .
C# version:
您可以对整个URL进行哈希处理,但如果您只想缩短ID,请按照marcel的建议进行操作 . 我写了这个Python实现:
https://gist.github.com/778542
如果你不想重新发明轮子...... http://lilurl.sourceforge.net/
这是我的版本,适合任何需要它的人 .
Node.js和MongoDB解决方案
因为我们知道MongoDB用来创建一个12字节的新ObjectId的格式 .
一个4字节的值,表示自Unix纪元以来的秒数,
一个3字节的机器标识符,
一个2字节的进程ID
一个3字节计数器(在您的机器中),以随机值开始 .
示例(我选择随机序列) a1b2c3d4e5f6g7h8i9j1k2l3
a1b2c3d4表示自Unix纪元以来的秒数,
4e5f6g7代表机器标识符,
h8i9表示进程ID
j1k2l3表示计数器,以随机值开头 .
由于如果我们将数据存储在同一台机器中,计数器将是唯一的,我们可以毫不怀疑它将是重复的 .
So the short URL will be the counter 这是一个代码片段,假设您的服务器正常运行 .
不知道是否有人会发现这有用 - 它更像是一种'黑客n斜线'方法,但如果你只想要特定的字符,它很简单并且效果很好 .
我不断在数据库中为每个域递增一个整数序列,并使用Hashids将整数编码为URL路径 .
我运行了一个脚本,看看它耗尽了多长时间才能消耗字符长度 . 对于六个字符,它可以执行
164,916,224
链接,然后最多可以输出七个字符 . 有点使用七个字符 . 五个字符对我来说很奇怪 .Hashids可以将URL路径解码回整数,但更简单的解决方案是使用整个短链接
sho.rt/ka8ds3
作为主键 .这是完整的概念:
为什么不将你的id翻译成字符串?您只需要一个将数字(例如0到61)之间的数字映射到单个字母(大写/小写)或数字的函数 . 然后将其应用于创建4个字母的代码,并且您已覆盖了1470万个URL .
这是我用的:
它非常快,可以采用长整数 .
对于一个类似的项目,为了得到一个新的密钥,我围绕一个调用生成器的random string generator创建一个包装器函数,直到我得到一个尚未在我的哈希表中使用的字符串 . 一旦你的名字空间开始变满,这个方法会变慢,但正如你所说,即使只有6个字符,你也有足够的命名空间可供使用 .
我有一个问题的变体,因为我存储来自许多不同作者的网页,需要通过猜测来防止发现页面 . 所以我的短网址为Base-62字符串添加了几个额外的数字作为页码 . 这些额外数字是根据页面记录本身中的信息生成的,它们确保3844个URL中只有1个有效(假设2位Base-62) . 您可以在http://mgscan.com/MBWL查看大纲说明 .
非常好的答案,我已经创建了bjf的Golang实现:
主持人在github:https://github.com/xor-gate/go-bjf
在Scala中实现:
使用Scala测试的测试示例:
基于Xeoncross Class的函数
你故意省略O,0和我吗?
我刚刚根据Ryan的解决方案创建了一个PHP类 .
这是一个很可能是bit.ly的Node.js实现 . 生成一个高度随机的七个字符的字符串 .
它使用Node.js加密来生成高度随机的25个字符集,而不是随机选择7个字符 .
我的Python 3版本
有关高质量的Node.js / JavaScript解决方案,请参阅id-shortener模块,该模块经过全面测试,已在 生产环境 中使用了数月 .
它提供了一个有效的id / URL缩短器,由可插入存储默认 Redis 支持,您甚至可以自定义短ID字符集以及缩短是否是幂等的 . 这是一个重要的区别,并非所有URL缩短程序都考虑在内 .
关于此处的其他答案,本模块实现了Marcel Jackwerth在上面的优秀接受答案 .
该解决方案的核心由以下Redis Lua提供snippet: