短网址算法PHP实例详细介绍 - 其他 - 技术文章

短网址算法PHP实例详细介绍

时间：2011-11-09 作者：佚名出处：互联网

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

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

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

算法原理
算法一
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]

下面是进制转换所需要的源码：
<?php
/*
* MoXie (SysTem128@GMail.Com) 2010-6-30 17:53:57
*
* Copyright © 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($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;
}
?>

yourls项目：http://code.google.com/p/yourls/

网友留言/评论

我要留言/评论

MyEclipse快捷键使用详细介绍:Eclipse是一款非常受欢迎的java开发工具，使国内的用户越来越多，熟悉快捷键将会使你的编程工作得心应手，请看下面的分类详细介绍。

免费的Android UI库及组件推荐:短短数年时间Android平台就已经形成了一个庞大而活跃的开发者社区。许多社区开发的项目业已进入成熟阶段，甚至可以用于商业的软件生产中，且不用担心质量问题。

网站运营数据分析的指标和算法介绍:网站运营过程中针对网站的数据分析，已经成了每个网站策划和网站运营人员，每天的必备功课，通过这些数据指标可以帮助我们准确的抓住用户动向和网站的实际状况。其实根据网站类型的不同则分析所采用指标项也各有不同，可以有许多不同的指标来衡量。但是如何衡量网站运营的数据指标，哪些是网站运营的关键指标，是每个新人感到困惑。其实通常来说网站分析指标有内容指标和商业指标，内容指标指的是衡量访问者的活动的指标，商业指标是指衡量访问者活动转化为商业利润的指标。为了获得这些数据，我们可以使用51啦，GOOGLE分析工具来得到部分信息，但是为了更加精准的获得某些网站运营时的关键数据，则在网站策划和网站规划阶段时，需要充分将这部分内容考虑进去，对网站做些指标参数的设定，这样就可以降低网站的重复开发工作。

20条编程经验:作者乔纳森·丹尼可（Jonathan Danylko）是一位自由职业的web架构师和程序员，编程经验已超过20年，涉足领域有电子商务、生物技术、房地产、医疗、保险和公用事业。正如乔纳森在文中所言，本文适合刚毕业的大学生和刚入门的程序员。如果你已是高级开发人员，或许你能在本文中看到自己的身影。

Lazy Load, 延迟加载图片的 jQuery 插件:本文翻译自 Lazy Load Plugin for jQuery, 介绍一个 jQuery 插件, 它提供懒汉式加载页面图片的功能.

被高估的云计算 - OOPSLA辩论:现在对云计算的炒作就如同上百人在电话会议中狂吼一样喧嚣。回顾20年来IT的演变，较为特别（其实也不那么特别）的一点就是每次新技术的诞生都发生了喧嚣的炒作。以4到5年为周期的技术更新意味着大量赚钱的良机。从最早的大型机到客户端-服务器、CASE工具、.COM、企业架构(如EJB和 DCOM)、SOA，以及发展到现在的云计算，IT一如既往地关注于如何想方设法赚钱。

分享自己感触最深的几条设计哲学:今天读到一些UNIX下的编程哲学，对自己相当的有冲击力，把我觉得有用并且有道理的，自己组织了一下

如何做一个好的技术型领导:

如何招聘程序员 - 技术经理必知:你有过招聘程序员的经历么，面试过程中是否有些误区，请看本文阐述~

敏捷开发的二十六条至理名言 - 借此导航自己人生:敏捷开发真正的问题是什么？其实敏捷主要还是一种观念，一种意识，通过人来推动。本文总结了26条有关敏捷开发的关键原则，供读者参考借鉴。

网友留言/评论

我要留言/评论

相关文章