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

winston

看过新浪的短连接服务，发现后面主要有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/ ,
代码如下:

1. <?php  
2. function shorturl($input) {  
3. $base32 =
4. array (  
5. 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h',  
6. 'i', 'j', 'k', 'l',
7. 'm', 'n', 'o', 'p',  
8. 'q', 'r', 's', 't', 'u', 'v', 'w', 'x',  
9. 'y', 'z',
10. '0', '1', '2', '3', '4', '5'  
11. );  
12. $hex = md5($input);  
13. $hexLen =
14. strlen($hex);  
15. $subHexLen = $hexLen / 8;  
16. $output = array();  
17.   for
18. ($i = 0; $i < $subHexLen; $i++) {  
19. $subHex = substr ($hex, $i * 8, 8);  
21. $int = 0x3FFFFFFF & (1 * ('0x'.$subHex));  
22. $out = '';  
23.     for
24. ($j = 0; $j < 6; $j++) {  
25. $val = 0x0000001F & $int;  
26. $out .=
27. $base32[$val];  
28. $int = $int >> 5;  
29.     }  
30. $output[] = $out;  
32.   }  
33.   return $output;  
34. }  
35. ?>

复制代码

另一个是纯随机数算法

1. <?php  
2. function random($length, $pool = '')  
3.     {  
5. $random = '';  
6.         if (empty($pool)) {  
7. $pool    =
8. 'abcdefghkmnpqrstuvwxyz';  
9. $pool   .= '23456789';  
10.         }  
11. srand
12. ((double)microtime()*1000000);  
13.         for($i = 0; $i < $length; $i++)   
15.         {  
16. $random .= substr($pool,(rand()%(strlen ($pool))), 1);  
18.         }  
19.         return $random;  
20.     }  
21. ?>

复制代码

各大微博短网址(ShortUrl)的算法 ,第一种算法的C#实现

1. <?php  
2. //
3. 这是c#代码,受编辑器的限制,只能用php  
4. public static string[] ShortUrl(string url)  
6.         {  
7. //可以自定义生成MD5加密字符传前的混合KEY  
8. string key = "Leejor";  
10. //要使用生成URL的字符  
11. string[] chars = new string[]{  
13. "a","b","c","d","e","f","g","h",  
14. "i","j","k","l","m","n","o","p",  
16. "q","r","s","t","u","v","w","x",  
17. "y","z","0","1","2","3","4","5",  
19. "6","7","8","9","A","B","C","D",  
20. "E","F","G","H","I","J","K","L",  
22. "M","N","O","P","Q","R","S","T",  
23. "U","V","W","X","Y","Z"  
24. };  
26. //对传入网址进行MD5加密  
27. string hex =
28. System.Web.Security.FormsAuthentication.HashPasswordForStoringInConfigFile(key +
29. url, "md5");
30. string[] resUrl = new string[4];  
31.             for (int i =
32. 0; i < 4; i++)  
33.             {  
34. //把加密字符按照8位一组16进制与0x3FFFFFFF进行位与运算  
36. int hexint = 0x3FFFFFFF & Convert.ToInt32("0x" + hex.Substring(i * 8,
37. 8), 16);  
38. string outChars = string.Empty;  
39.                 for (int j =
40. 0; j < 6; j++)  
41.                 {  
43. //把得到的值与0x0000003D进行位与运算，取得字符数组chars索引  
44. int index = 0x0000003D &
45. hexint;  
46. //把取得的字符相加  
47. outChars += chars[index];  
48. //每次循环按位右移5位  
50. hexint = hexint >> 5;  
51.                 }  
52. //把字符串存入对应索引的输出数组  
54. resUrl[i] = outChars;  
55.             }  
56.             return resUrl;  
58.         }  
59. ?>

复制代码

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

1. <?php  
2. //id 自增序列/自增编号  
3. //url 目标链接  
4. //*suffix* 短网址后缀
5. （并不需要存储在数据库内）  
6. +------------+-----------------------+---------+  
8. |id          | url                   | *suffix*|  
10. +------------+-----------------------+---------+  
11. |123456      |
12. http://zoeey.com/     | w7e     |  
14. +------------+-----------------------+---------+  
15. |123457      |
16. http://www.zoeey.com/ | w7f     |  
18. +------------+-----------------------+---------+  
19. |56800235582 |
20. http://zoeey.org/     | ZZZZZY  |  
22. +------------+-----------------------+---------+  
23. |56800235583 |
24. http://www.zoeey.org/ | ZZZZZZ  |  
26. +------------+-----------------------+---------+  
27. ?>

复制代码

短网址使用流程：

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

下面是进制转换所需要的源码：

1. <?php  
2. /*  
3. * MoXie (SysTem128@GMail.Com)
4. 2010-6-30 17:53:57  
5. *   
6. * Copyright &copy; 2008-2010 Zoeey.Org . All
7. rights are reserved.  
8. * Code license: Apache License  Version 2.0  
9. *
10. http://www.apache.org/licenses/LICENSE-2.0.txt  
11. */  
13. error_reporting(E_ALL);  
14. /**  
15. * 返回一字符串，十进制 number 以 radix 进制的表示。  
17. * @param dec       需要转换的数字  
18. * @param toRadix    输出进制。当不在转换范围内时，此参数会被设定为
19. 2，以便及时发现。  
20. * @return    指定输出进制的数字  
21. */  
22. function dec2Any($dec,
23. $toRadix) {  
24. $MIN_RADIX = 2;  
25. $MAX_RADIX = 62;  
26. $num62 =
27. '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';  
28.     if
29. ($toRadix < $MIN_RADIX || $toRadix > $MAX_RADIX) {  
30. $toRadix = 2;  
32.     }  
33.     if ($toRadix == 10) {  
34.         return $dec;  
35.     }  
37. // -Long.MIN_VALUE 转换为 2 进制时长度为65  
38. $buf = array();  
39. $charPos = 64;  
41. $isNegative = $dec < 0; //(bccomp($dec, 0) < 0);  
42. if
43. (!$isNegative) {  
44. $dec = -$dec; // bcsub(0, $dec);  
45. }  
46.     while
47. (bccomp($dec, -$toRadix) <= 0) {  
48. $buf[$charPos--] = $num62[-bcmod($dec,
49. $toRadix)];  
50. $dec = bcdiv($dec, $toRadix);  
51.     }  
52. $buf[$charPos] =
53. $num62[-$dec];  
54.     if ($isNegative) {  
55. $buf[--$charPos] = '-';  
56.    
57. }  
58. $_any = '';  
59.     for ($i = $charPos; $i < 65; $i++) {  
60. $_any
61. .= $buf[$i];  
62.     }  
63.     return $_any;  
64. }  
65. /**  
66. * 返回一字符串，包含
67. number 以 10 进制的表示。<br />  
68. * fromBase 只能在 2 和 62 之间（包括 2 和 62）。  
69. *
70. @param number    输入数字  
71. * @param fromRadix    输入进制  
72. * @return  十进制数字  
74. */  
75. function any2Dec($number, $fromRadix) {  
76. $num62 =
77. '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';  
78. $dec =
79. 0;  
80. $digitValue = 0;  
81. $len = strlen($number) - 1;  
82.     for ($t = 0;
83. $t <= $len; $t++) {  
84. $digitValue = strpos($num62, $number[$t]);  
85. $dec
86. = bcadd(bcmul($dec, $fromRadix), $digitValue);  
87.     }  
88.     return $dec;  
90. }  
91. $sol = '<br />' . PHP_EOL;  
92. echo dec2Any('56800235583',
93. 62), $sol; // ZZZZZZ  
94. echo any2Dec('ZZZZZZ', 62), $sol; // 56800235583  
96. echo dec2Any('123456', 62), $sol; // w7e  
97. echo any2Dec('w7e', 62), $sol;
98. // 123456  
99. ?>

复制代码

另外,介绍一下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来处理哈。

1. <?php  
2. // 生成  
3. function shortenGoogleUrl($long_url){  
5. $apiKey = 'API-KEY'; //Get API key from :
6. http://code.google.com/apis/console/  
7. $postData = array('longUrl' =>
8. $long_url, 'key' => $apiKey);  
9. $jsonData = json_encode($postData);  
11. $curlObj = curl_init();  
12. curl_setopt($curlObj, CURLOPT_URL,
13. 'https://www.googleapis.com/urlshortener/v1/url');  
14. curl_setopt($curlObj,
15. CURLOPT_RETURNTRANSFER, 1);  
16. curl_setopt($curlObj, CURLOPT_SSL_VERIFYPEER,
17. 0);  
18. curl_setopt($curlObj, CURLOPT_HEADER, 0);  
19. curl_setopt($curlObj,
20. CURLOPT_HTTPHEADER, array('Content-type:application/json'));  
22. curl_setopt($curlObj, CURLOPT_POST, 1);  
23. curl_setopt($curlObj,
24. CURLOPT_POSTFIELDS, $jsonData);  
25. $response = curl_exec($curlObj);  
27. curl_close($curlObj);  
28. $json = json_decode($response);  
29. return
30. $json->id;  
31. }  
32. //还原  
33. function expandGoogleUrl($short_url){  
35. $curlObj = curl_init();  
36. curl_setopt($curlObj, CURLOPT_URL,
37. 'https://www.googleapis.com/urlshortener/v1/url?shortUrl='.$short_url);  
39. curl_setopt($curlObj, CURLOPT_HEADER, 0);  
40. curl_setopt($curlObj,
41. CURLOPT_RETURNTRANSFER, 1);  
42. curl_setopt($curlObj, CURLOPT_SSL_VERIFYPEER,
43. 0);  
44. $response = curl_exec($curlObj);  
45. curl_close($curlObj);  
46. $json
47. = json_decode($response);  
48. return $json->longUrl;  
49. }  
50. ?>

复制代码

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

http://item.feedsky.com/~feedsky/php10086/~8835780/622430876/6954309/1/item.html