网上各种短网址算法应用的初步详细汇总-阿里云开发者社区

开发者社区> y0umer> 正文

网上各种短网址算法应用的初步详细汇总

简介: 看过新浪的短连接服务,发现后面主要有6个字符串组成,于是第一个想到的就是原来公司写的一个游戏激活码规则,也就是下面的算法2,26个大写字母 26小写字母,10个数字,随机生成6个然后插入数据库对应一个id,短连接跳转的时候,根据字符串查询到对应id,即可实现相应的跳转!不过2的62次方,不知...
+关注继续查看

看过新浪的短连接服务,发现后面主要有6个字符串组成,于是第一个想到的就是原来公司写的一个游戏激活码规则,也就是下面的算法2,26个大写字母 26小写字母,10个数字,随机生成6个然后插入数据库对应一个id,短连接跳转的时候,根据字符串查询到对应id,即可实现相应的跳转!不过2的62次方,不知道有没有重复的,小概率可以,但是对应不是很大的网站应该足够了


自从twitter推出短网址(shorturl),继之国内各大微博跟风,google公开goo.gl使用API,短网址之风愈演愈烈.不得不说这是一个新兴又一大热门web2.0服务.现整理一下,包括完整短网址网站,短网址算法原理,算法举例,以及优劣比较,同时还介绍几个phper个人实现的.

yourls,完整的ShortUrl网站.由国外著名 WordPress 插件大师级人物 Ozh Richard 和 Lester Chan 一起写的.官方网站是yourls.org.此为开源版本,可以从这里下载.最新版本1.5,昨天试用了一下,默认第一个是1,感觉不是很好,还是喜欢twitter风格的.

turl,phper的个人实现,可下载源码,点击此处

算法原理
算法一
1)将长网址md5生成32位签名串,分为4段, 每段8个字节;
2)对这四段循环处理, 取8个字节, 将他看成16进制串与0x3fffffff(30位1)与操作, 即超过30位的忽略处理;
3)这30位分成6段, 每5位的数字作为字母表的索引取得特定字符, 依次进行获得6位字符串;
4)总的md5串可以获得4个6位串; 取里面的任意一个就可作为这个长url的短url地址;

这种算法,虽然会生成4个,但是仍然存在重复几率,下面的算法一和三,就是这种的实现.

算法二
a-zA-Z0-9 这64位取6位组合,可产生500多亿个组合数量.把数字和字符组合做一定的映射,就可以产生唯一的字符串,如第62个组合就是aaaaa9,第63个组合就是aaaaba,再利用洗牌算法,把原字符串打乱后保存,那么对应位置的组合字符串就会是无序的组合。
把长网址存入数据库,取返回的id,找出对应的字符串,例如返回ID为1,那么对应上面的字符串组合就是bbb,同理 ID为2时,字符串组合为bba,依次类推,直至到达64种组合后才会出现重复的可能,所以如果用上面的62个字符,任意取6个字符组合成字符串的话,你的数据存量达到500多亿后才会出现重复的可能。
具体参看这里彻底完善新浪微博接口和超短URL算法,算法四可以算作是此算法的一种实现,此算法一般不会重复,但是如果是统计的话,就有很大问题,特别是对域名相关的统计,就抓瞎了.

短网址算法枚举

一个来自http://www.snippetit.com/2009/04/php-short-url-algorithm-implementation/ ,
代码如下:
<?php 
function shorturl($input) { 
  
$base32 = array ( 
    
'a''b''c''d''e''f''g''h'
    
'i''j''k''l''m''n''o''p'
    
'q''r''s''t''u''v''w''x'
    
'y''z''0''1''2''3''4''5' 
    
); 
  
  
$hex md5($input); 
  
$hexLen strlen($hex); 
  
$subHexLen $hexLen 8
  
$output = array(); 
  
  for (
$i 0$i $subHexLen$i++) { 
    
$subHex substr ($hex$i 88); 
    
$int 0x3FFFFFFF & (* ('0x'.$subHex)); 
    
$out ''
  
    for (
$j 0$j 6$j++) { 
      
$val 0x0000001F $int
      
$out .= $base32[$val]; 
      
$int $int >> 5
    } 
  
    
$output[] = $out
  } 
  
  return 
$output

?> 


另一个是纯随机数算法
<?php 
function random($length$pool ''
    { 
        
$random ''
  
        if (empty(
$pool)) { 
            
$pool    'abcdefghkmnpqrstuvwxyz'
            
$pool   .= '23456789'
        } 
  
        
srand ((double)microtime()*1000000); 
  
        for(
$i 0$i $length$i++)  
        { 
            
$random .= substr($pool,(rand()%(strlen ($pool))), 1); 
        } 
  
        return 
$random
    } 
?> 


各大微博短网址(ShortUrl)的算法 ,第一种算法的C#实现
<?php 
// 这是c#代码,受编辑器的限制,只能用php 
public static string[] ShortUrl(string url
        { 
            
//可以自定义生成MD5加密字符传前的混合KEY 
            
string key "Leejor"
            
//要使用生成URL的字符 
            
string[] chars = new string[]{ 
                
"a","b","c","d","e","f","g","h"
                
"i","j","k","l","m","n","o","p"
                
"q","r","s","t","u","v","w","x"
                
"y","z","0","1","2","3","4","5"
                
"6","7","8","9","A","B","C","D"
                
"E","F","G","H","I","J","K","L"
                
"M","N","O","P","Q","R","S","T"
                
"U","V","W","X","Y","Z" 

              
}; 
            
//对传入网址进行MD5加密 
            
string hex System.Web.Security.FormsAuthentication.HashPasswordForStoringInConfigFile(key url"md5");

            
string[] resUrl = new string[4]; 

            for (
int i 04i++) 
            { 
                
//把加密字符按照8位一组16进制与0x3FFFFFFF进行位与运算 
                
int hexint 0x3FFFFFFF Convert.ToInt32("0x" hex.Substring(88), 16); 
                
string outChars string.Empty; 
                for (
int j 06j++) 
                { 
                    
//把得到的值与0x0000003D进行位与运算,取得字符数组chars索引 
                    
int index 0x0000003D hexint
                    
//把取得的字符相加 
                    
outChars += chars[index]; 
                    
//每次循环按位右移5位 
                    
hexint hexint >> 5
                } 
                
//把字符串存入对应索引的输出数组 
                
resUrl[i] = outChars
            } 

            return 
resUrl
        } 
?> 


高进制数字转换,使用六十二进制将十进制数字变“短”。(作者自称很高效,但是来源页www.zoeey.com/cnphpdocs/short.url.radix.convert.html 打不开)
例如数据库中第 56800235583 条信息,对应的短网址后缀可以是 ZZZZZZ 。
下面是存储示例:

<?php 
//id 自增序列/自增编号 
//url 目标链接 
//*suffix* 短网址后缀 (并不需要存储在数据库内) 
+------------+-----------------------+---------+ 
|
id          url                   | *suffix*| 
+------------+-----------------------+---------+ 
|
123456      http://zoeey.com/     | w7e     | 
+------------+-----------------------+---------+ 
|
123457      http://www.zoeey.com/ | w7f     | 
+------------+-----------------------+---------+ 
|
56800235582 http://zoeey.org/     | ZZZZZY  | 
+------------+-----------------------+---------+ 
|
56800235583 http://www.zoeey.org/ | ZZZZZZ  | 
+------------+-----------------------+---------+ 
?> 

短网址使用流程:

  • 提交网址存储后获取其编号 如:123456
  • 用dec2Any将编号转换为62进制,并拼接网址 如:http://go.to/w7e
  • 用户访问到 http://go.to/w7e 时,提取短网址后缀 w7e
  • 用any2Dec将短网址后缀转换为10进制,得到链接编号 如:123456
  • 使用编号查询链接,并进行跳转[/list]


下面是进制转换所需要的源码:
<?php 
/* 
* MoXie (SysTem128@GMail.Com) 2010-6-30 17:53:57 
*  
* Copyright &copy; 2008-2010 Zoeey.Org . All rights are reserved. 
* Code license: Apache License  Version 2.0 
* http://www.apache.org/licenses/LICENSE-2.0.txt 
*/ 
error_reporting(E_ALL); 

/** 
* 返回一字符串,十进制 number 以 radix 进制的表示。 
* @param dec       需要转换的数字 
* @param toRadix    输出进制。当不在转换范围内时,此参数会被设定为 2,以便及时发现。 
* @return    指定输出进制的数字 
*/ 
function dec2Any($dec$toRadix) { 
    
$MIN_RADIX 2
    
$MAX_RADIX 62
    
$num62 '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
    if (
$toRadix $MIN_RADIX || $toRadix $MAX_RADIX) { 
        
$toRadix 2
    } 
    if (
$toRadix == 10) { 
        return 
$dec
    } 
    
// -Long.MIN_VALUE 转换为 2 进制时长度为65 
    
$buf = array(); 
    
$charPos 64
    
$isNegative $dec 0//(bccomp($dec, 0) < 0); 
    
if (!$isNegative) { 
        
$dec = -$dec// bcsub(0, $dec); 
    


    while (
bccomp($dec, -$toRadix) <= 0) { 
        
$buf[$charPos--] = $num62[-bcmod($dec$toRadix)]; 
        
$dec bcdiv($dec$toRadix); 
    } 
    
$buf[$charPos] = $num62[-$dec]; 
    if (
$isNegative) { 
        
$buf[--$charPos] = '-'
    } 
    
$_any ''
    for (
$i $charPos$i 65$i++) { 
        
$_any .= $buf[$i]; 
    } 
    return 
$_any


/** 
* 返回一字符串,包含 number 以 10 进制的表示。<br /> 
* fromBase 只能在 2 和 62 之间(包括 2 和 62)。 
* @param number    输入数字 
* @param fromRadix    输入进制 
* @return  十进制数字 
*/ 
function any2Dec($number$fromRadix) { 
    
$num62 '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
    
$dec 0
    
$digitValue 0
    
$len strlen($number) - 1
    for (
$t 0$t <= $len$t++) { 
        
$digitValue strpos($num62$number[$t]); 
        
$dec bcadd(bcmul($dec$fromRadix), $digitValue); 
    } 
    return 
$dec


$sol '<br />' PHP_EOL
echo 
dec2Any('56800235583'62), $sol// ZZZZZZ 
echo any2Dec('ZZZZZZ'62), $sol// 56800235583 
echo dec2Any('123456'62), $sol// w7e 
echo any2Dec('w7e'62), $sol// 123456 
?>

另外,介绍一下goo.gl接口api的应用.
据说此算法是各种短网址服务中 "......(这是)互联网上最稳定、最安全、最快速的短网址服务。"(google声称)

有人做了比较,证明确实如此。



除了速度快,goo.gl还提供详细的点击统计。比如,Yahoo首页的短网址是http://goo.gl/QuXj,那么它的统计数据就在http://goo.gl/info/QuXj。加上后缀".qr",还能得到这个网址的二维条形码,Yahoo的就是http://goo.gl/QuXj.qr

详细信息可从这查看:http://code.google.com/apis/urlshortener/overview.html

下面是http://www.biaodianfu.com/php-google-urlshortener-api.html弄的一个简单的PHP调用API生成短网址方法,分享给大家。
在使用前,请先到这里申请API Key:http://code.google.com/apis/console/
短网址的生成需要使用POST提交数据,所以使用了curl,短网址的还原可以直接使用file_get_contents()函数。不过为了统一,也使用了curl来处理哈。
<?php 
// 生成 
function shortenGoogleUrl($long_url){ 
 
$apiKey 'API-KEY'//Get API key from : http://code.google.com/apis/console/ 
 
$postData = array('longUrl' => $long_url'key' => $apiKey); 
 
$jsonData json_encode($postData); 
 
$curlObj curl_init(); 
 
curl_setopt($curlObjCURLOPT_URL'https://www.googleapis.com/urlshortener/v1/url'); 
 
curl_setopt($curlObjCURLOPT_RETURNTRANSFER1); 
 
curl_setopt($curlObjCURLOPT_SSL_VERIFYPEER0); 
 
curl_setopt($curlObjCURLOPT_HEADER0); 
 
curl_setopt($curlObjCURLOPT_HTTPHEADER, array('Content-type:application/json')); 
 
curl_setopt($curlObjCURLOPT_POST1); 
 
curl_setopt($curlObjCURLOPT_POSTFIELDS$jsonData); 
 
$response curl_exec($curlObj); 
 
curl_close($curlObj); 
 
$json json_decode($response); 
 return 
$json->id


//还原 
function expandGoogleUrl($short_url){ 
 
$curlObj curl_init(); 
 
curl_setopt($curlObjCURLOPT_URL'https://www.googleapis.com/urlshortener/v1/url?shortUrl='.$short_url); 
 
curl_setopt($curlObjCURLOPT_HEADER0); 
 
curl_setopt($curlObjCURLOPT_RETURNTRANSFER1); 
 
curl_setopt($curlObjCURLOPT_SSL_VERIFYPEER0); 
 
$response curl_exec($curlObj); 
 
curl_close($curlObj); 
 
$json json_decode($response); 
 return 
$json->longUrl

?> 

在此处有个生成器,但是无代码奉献.点击此处

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
网站更新频率真的很重要吗?不为人知的算法揭秘
网站更新频率真的很重要吗?不为人知的算法揭秘。很多人认为每天更新文章才能让搜索引擎更加喜欢,但事实上不是这样的,频繁更新更加不利于网站排名
33 0
YOLO 人脸识别算法以及应用 (1)
第四周 特殊应用:人脸识别和神经风格转换(Special applications: Face recognition &Neural style transfer) 4.
5889 0
一致性哈希算法应用与分析
  一致性哈希算法主要使用在分布式数据存储系统中,按照一定的策略将数据尽可能均匀分布到所有的存储节点上去,使得系统具有良好的负载均衡性能和扩展性。感觉一致性哈希与数据结构中的“循环队列”还是有一点联系的。
769 0
[算法题] 安排会议室——贪心算法的应用
题目描述 [题目描述] 在大公司里,会议是很多的,开会得有场子,要场子你得先在电子流里预订。如果你是项目组新来的小弟,那么恭喜你,每天抢订会议室的任务就光荣的分给你了。老大要求你尽可能多的订会议室,但是这些会议室之间不能有时间冲突。
760 0
计算机网络 自顶向下方法 第二章 应用层
版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/a724888/article/details/78197072 计算机网络 自顶向下方法 第二章 应用层  分类:计算机网络-笔记(2)  版权声明:本文为博主原创文章,未经博主允许不得转载。
1228 0
+关注
y0umer
高级网络安全技术员
906
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载