网上各种短网址算法应用的初步详细汇总-php手册-PHP中文网

看过新浪的短连接服务，发现后面主要有6个字符串组成，于是第一个想到的就是原来公司写的一个游戏激活码规则，也就是下面的算法2，26个大写字母 26小写字母，10个数字，随机生成6个然后插入数据库对应一个id，短连接跳转的时候，根据字符串查询到对应id，即

看过新浪的短连接服务，发现后面主要有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 * 8, 8); $int = 0x3FFFFFFF & (1 * ('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 = 0; i 4; i++) { //把加密字符按照8位一组16进制与0x3FFFFFFF进行位与运算 int hexint = 0x3FFFFFFF & Convert.ToInt32("0x" + hex.Substring(i * 8, 8), 16); string outChars = string.Empty; for (int j = 0; j 6; j++) { //把得到的值与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]

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

<span><span><?php  <br>
</span><span>/* <br>
* MoXie (SysTem128@GMail.Com) 2010-6-30 17:53:57 <br>
*  <br>
* Copyright © 2008-2010 Zoeey.Org . All rights are reserved. <br>
* Code license: Apache License  Version 2.0 <br>
* http://www.apache.org/licenses/LICENSE-2.0.txt <br>
*/ <br>
</span><span>error_reporting</span><span>(</span><span>E_ALL</span><span>); <br>
<br>
</span><span>/** <br>
* 返回一字符串，十进制 number 以 radix 进制的表示。 <br>
* @param dec       需要转换的数字 <br>
* @param toRadix    输出进制。当不在转换范围内时，此参数会被设定为 2，以便及时发现。 <br>
* @return    指定输出进制的数字 <br>
*/ <br>
</span><span>function </span><span>dec2Any</span><span>(</span><span>$dec</span><span>, </span><span>$toRadix</span><span>) { <br>
    </span><span>$MIN_RADIX </span><span>= </span><span>2</span><span>; <br>
    </span><span>$MAX_RADIX </span><span>= </span><span>62</span><span>; <br>
    </span><span>$num62 </span><span>= </span><span>'0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'</span><span>; <br>
    if (</span><span>$toRadix </span><span><span>$MIN_RADIX </span><span>|| </span><span>$toRadix </span><span>> </span><span>$MAX_RADIX</span><span>) { <br>
        </span><span>$toRadix </span><span>= </span><span>2</span><span>; <br>
    } <br>
    if (</span><span>$toRadix </span><span>== </span><span>10</span><span>) { <br>
        return </span><span>$dec</span><span>; <br>
    } <br>
    </span><span>// -Long.MIN_VALUE 转换为 2 进制时长度为65 <br>
    </span><span>$buf </span><span>= array(); <br>
    </span><span>$charPos </span><span>= </span><span>64</span><span>; <br>
    </span><span>$isNegative </span><span>= </span><span>$dec </span><span><span>0</span><span>; </span><span>//(bccomp($dec, 0) 
    </span><span>if (!</span><span>$isNegative</span><span>) { <br>
        </span><span>$dec </span><span>= -</span><span>$dec</span><span>; </span><span>// bcsub(0, $dec); <br>
    </span><span>} <br>
<br>
    while (</span><span>bccomp</span><span>(</span><span>$dec</span><span>, -</span><span>$toRadix</span><span>) <span>0</span><span>) { <br>
        </span><span>$buf</span><span>[</span><span>$charPos</span><span>--] = </span><span>$num62</span><span>[-</span><span>bcmod</span><span>(</span><span>$dec</span><span>, </span><span>$toRadix</span><span>)]; <br>
        </span><span>$dec </span><span>= </span><span>bcdiv</span><span>(</span><span>$dec</span><span>, </span><span>$toRadix</span><span>); <br>
    } <br>
    </span><span>$buf</span><span>[</span><span>$charPos</span><span>] = </span><span>$num62</span><span>[-</span><span>$dec</span><span>]; <br>
    if (</span><span>$isNegative</span><span>) { <br>
        </span><span>$buf</span><span>[--</span><span>$charPos</span><span>] = </span><span>'-'</span><span>; <br>
    } <br>
    </span><span>$_any </span><span>= </span><span>''</span><span>; <br>
    for (</span><span>$i </span><span>= </span><span>$charPos</span><span>; </span><span>$i </span><span><span>65</span><span>; </span><span>$i</span><span>++) { <br>
        </span><span>$_any </span><span>.= </span><span>$buf</span><span>[</span><span>$i</span><span>]; <br>
    } <br>
    return </span><span>$_any</span><span>; <br>
} <br>
<br>
</span><span>/** <br>
* 返回一字符串，包含 number 以 10 进制的表示。<br> <br>
* fromBase 只能在 2 和 62 之间（包括 2 和 62）。 <br>
* @param number    输入数字 <br>
* @param fromRadix    输入进制 <br>
* @return  十进制数字 <br>
*/ <br>
</span><span>function </span><span>any2Dec</span><span>(</span><span>$number</span><span>, </span><span>$fromRadix</span><span>) { <br>
    </span><span>$num62 </span><span>= </span><span>'0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'</span><span>; <br>
    </span><span>$dec </span><span>= </span><span>0</span><span>; <br>
    </span><span>$digitValue </span><span>= </span><span>0</span><span>; <br>
    </span><span>$len </span><span>= </span><span>strlen</span><span>(</span><span>$number</span><span>) - </span><span>1</span><span>; <br>
    for (</span><span>$t </span><span>= </span><span>0</span><span>; </span><span>$t </span><span><span>$len</span><span>; </span><span>$t</span><span>++) { <br>
        </span><span>$digitValue </span><span>= </span><span>strpos</span><span>(</span><span>$num62</span><span>, </span><span>$number</span><span>[</span><span>$t</span><span>]); <br>
        </span><span>$dec </span><span>= </span><span>bcadd</span><span>(</span><span>bcmul</span><span>(</span><span>$dec</span><span>, </span><span>$fromRadix</span><span>), </span><span>$digitValue</span><span>); <br>
    } <br>
    return </span><span>$dec</span><span>; <br>
} <br>
<br>
</span><span>$sol </span><span>= </span><span>'<br>' </span><span>. </span><span>PHP_EOL</span><span>; <br>
echo </span><span>dec2Any</span><span>(</span><span>'56800235583'</span><span>, </span><span>62</span><span>), </span><span>$sol</span><span>; </span><span>// ZZZZZZ <br>
</span><span>echo </span><span>any2Dec</span><span>(</span><span>'ZZZZZZ'</span><span>, </span><span>62</span><span>), </span><span>$sol</span><span>; </span><span>// 56800235583 <br>
</span><span>echo </span><span>dec2Any</span><span>(</span><span>'123456'</span><span>, </span><span>62</span><span>), </span><span>$sol</span><span>; </span><span>// w7e <br>
</span><span>echo </span><span>any2Dec</span><span>(</span><span>'w7e'</span><span>, </span><span>62</span><span>), </span><span>$sol</span><span>; </span><span>// 123456 <br>
</span><span>?></span></span></span></span></span></span></span>

另外,介绍一下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($curlObj, CURLOPT_URL, 'https://www.googleapis.com/urlshortener/v1/url'); curl_setopt($curlObj, CURLOPT_RETURNTRANSFER, 1); curl_setopt($curlObj, CURLOPT_SSL_VERIFYPEER, 0); curl_setopt($curlObj, CURLOPT_HEADER, 0); curl_setopt($curlObj, CURLOPT_HTTPHEADER, array('Content-type:application/json')); curl_setopt($curlObj, CURLOPT_POST, 1); curl_setopt($curlObj, CURLOPT_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($curlObj, CURLOPT_URL, 'https://www.googleapis.com/urlshortener/v1/url?shortUrl='.$short_url); curl_setopt($curlObj, CURLOPT_HEADER, 0); curl_setopt($curlObj, CURLOPT_RETURNTRANSFER, 1); curl_setopt($curlObj, CURLOPT_SSL_VERIFYPEER, 0); $response = curl_exec($curlObj); curl_close($curlObj); $json = json_decode($response); return $json->longUrl; } ?> 
在此处有个生成器,但是无代码奉献.点击此处