php 短链接算法收集与分析

短链接就不说了，大家已经都清楚了，如下所示就是短链接：
新浪微博 http://t.cn/SVpONM
腾讯微博 http://url.cn/302yor
Yun.io http://d.yun.io/PNri2v
短链接的好处：1、内容需要；2、用户友好；3、便于管理。
如何实现呢，大概有三个步骤：
1、定义一个URL映射算法，可以将长的URL映射成短字符串；
2、使用一个存储（数据库？NoSQL？）来存储完成的映射；
3、实现自己的URL映射算法；
一般来说，第三步是我们比较头疼的，如何将一个长的URL字符串，映射成一个较短的字符串呢。我总结了三种办法：
普通实现
我想以前大家学习过十进制和二进制的互相转换，或者十进制和十六进制的互相转换，那么为了更短，我们可以使用62进制，对于一个数字ID进行转码，转换成一个短字符串。
这种做法的缺点是没有办法保证所有链接都是固定的位数的长度，而且在高并发的情况下，如何保证能够快速分发是个问题。
具体实现方法：


代码如下:

/**
* 利用62进制对数字ID进行短链接编码，缺点不能保证每个短链接是固定长度
*
* @author wanshiqiang<wangshiqiang@360.cn>
* @param integer $integer
* @param string $base
*/
private function getShortenedURLFromID ($integer, $base = ALLOWED_CHARS)
{
$length = strlen($base);
while($integer > $length - 1)
{
$out = $base[fmod($integer, $length)] . $out;
$integer = floor( $integer / $length );
}
return $base[$integer] . $out;
}
/**
* 对62进制编码的短链接进行解码
*
* @author wangshiqiang<wangshiqiang@360.cn>
* @param string $string
* @param string $base
*/
private function getIDFromShortenedURL ($string, $base = ALLOWED_CHARS)
{
$length = strlen($base);
$size = strlen($string) - 1;
$string = str_split($string);
$out = strpos($base, array_pop($string));
foreach($string as $i => $char)
{
$out += strpos($base, $char) * pow($length, $size - $i);
}
return $out;
}

文艺实现
算法描述：使用6个字符来表示短链接，我们使用ASCII字符中的'a'-'z','0'-'5'，共计32个字符做为集合。每个字符有32种状态，六个字符就可以表示32^6（1073741824），那么如何得到这六个字符，描述如下：
对传入的长URL进行Md5，得到一个32位的字符串，这个字符串变化很多，是16的32次方，基本上可以保证唯一性。将这32位分成四份，每一份8个字符，这时机率变成了16的8次方，是4294967296，这个数字碰撞的机率也比较小啦，关键是后面的一次处理。我们将这个8位的字符认为是16进制整数，也就是1*('0x'.$val)，然后取0-30位，每5个一组，算出他的整数值，然后映射到我们准备的32个字符中，最后就能够得到一个6位的短链接地址。
PHP实现如下：


代码如下:

function shorten( $long_url )
{
$base32 = "abcdefghijklmnopqrstuvwxyz012345";
$hex = md5( $long_url );
$hexLen = strlen( $hex );
$subHexLen = $hexLen / 8;
$output = array();
for( $i = 0; $i < $subHexLen; $i++ )
{
$subHex = substr( $hex, $i * 8, 8 );
$subHex = 0x3FFFFFFF & ( 1 * ('0x' . $subHex ) );
　　　 $out = '';
for( $j = 0; $j < 6; $j++ )
{
$val = 0x0000001F & $int;
$out .= $base32[$val];
$int = $int >> 5;
}
$output[] = $out;
}
return $output;
}

二逼实现
下面这个函数使用了纯随机的方式来生成一个短链接，虽然我们可以通过查询操作来确保不重复使用短链接，可是... 这样真的靠谱吗~~


代码如下:

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;
}

Technorati 标签: 短链接,Short Url,映射,哈希

参考资料：

1、微博短地址原理解析

2、微博短域名原理及作用

3、Yours.org

4、Free PHP URL Shorten script that kicks ass

5、PHP Short Url Algorithm Implementation

6、Implement your own short URL

7、短网址算法初步汇总

8、Short Url 实现方式

赞 (0)

相关推荐

  • php数字转汉字代码(算法)

    复制代码 代码如下: //将数字转换为汉字,比如1210转换为一千二百一十 $num = "842105580";//九位数 function del0($num) //去掉数字段前面的0 { return "".intval($num); } function n2c($x) //单个数字变汉字 { $arr_n = array("零","一","二","三","四"

  • PHP大转盘中奖概率算法实例

    本文实例讲述了PHP大转盘中奖概率算法的实现方法,分享给大家供大家参考.具体如下: 大转盘是最近很多线上网动中一个比较有意思的东西了,下面我们就来看看这个大转盘中奖概率算法与例子,希望对各位有所帮助. 这是一个APP客户端有大转盘抽奖算法,具体如何抽奖当然在我们服务端实现了.下面和大家简单分享一下实现代码: 复制代码 代码如下: header("Content-type: text/html; charset=utf-8"); $prize_arr = array( '0' =>

  • PHP回溯法解决0-1背包问题实例分析

    本文实例讲述了PHP回溯法解决0-1背包问题的方法.分享给大家供大家参考.具体分析如下: 这段代码是根据<软件设计师>教程的伪代码写的: 最麻烦的不是伪代码改成php,而是数组下标从0开始,及相应的下标判断问题: 带着调试输出一块写上 <?php $v_arr = array(11,21,31,33,43,53,55,65); $w_arr = array(1,11,21,23,33,43,45,55); $n = count($w_arr ); //测试输出 var_dump(bkna

  • php约瑟夫问题解决关于处死犯人的算法

    本文实例讲述了php约瑟夫问题解决关于处死犯人的算法.分享给大家供大家参考.具体分析如下: 古代某法官要判决IV个犯人的死刑,他有一条荒唐的法律将犯人站成一个圆圈,从第s个人开始数起,每到第D个人就拉出来处死,然后再数D个,再拉出来处决-- 直到剩下最后一个可以赦免. function getNum($n,$m){ //用于把所有的数存到数组初始化 $a = array(); //遍历,存入数组 for($i=1;$i<=$n;$i++){ $a[$i] = $i; } //指针归0 reset

  • PHP树的深度编历生成迷宫及A*自动寻路算法实例分析

    本文实例讲述了PHP树的深度编历生成迷宫及A*自动寻路算法.分享给大家供大家参考.具体分析如下: 有一同事推荐了三思的迷宫算法,看了感觉还不错,就转成php 三思的迷宫算法是采用树的深度遍历原理,这样生成的迷宫相当的细,而且死胡同数量相对较少! 任意两点之间都存在唯一的一条通路. 至于A*寻路算法是最大众化的一全自动寻路算法 废话不多说,贴上带代码 迷宫生成类: 复制代码 代码如下: class Maze{     // Maze Create     private $_w;     priv

  • PHP实现基于回溯法求解迷宫问题的方法详解

    本文实例讲述了PHP实现基于回溯法求解迷宫问题的方法.分享给大家供大家参考,具体如下: 引言 最近在leetcode上看了些算法题,有些看着很简单的很常用的东西,竟然一下子想不出来怎么求解,比如说:实现sqrt函数,求数组的排列.如果高数学的不好,这些看似简单的问题,第一次碰到也会感觉很难求解,当然了,今天要说的是这样一个问题,求解迷宫的所有解,这个问题的求解用到了回溯法的思想,不了解这个思想的话,很多稍微复杂点的问题都很难解了. 问题描述 这个问题是在实在瞎逛的时候碰到的,具体哪里记不太清了.

  • PHP mcrypt可逆加密算法分析

    数据加密在我们生活中的地位已经越来越重要了,尤其是考虑到在网络上发生的大量交易和传输的大量数据.对于不需要还原为原始数据的信息我们可以使用MD5.sha1等不可逆加密算法对数据进行加密处理,但对于交易信息等需要还原为原始数据的重要信息则必须使用可还原的加密算法进行加密了.当然你可以自己写一个可逆加密的算法进行加密和解密计算.本文中我们介绍的是使用 mcrypt模块进行加密解密操作. Mcrypt的优点不仅仅在于其提供的加密算法较多,在windows下随PHP包一起发布,还在于它可以对数据进行加/

  • php实现猴子选大王问题算法实例

    本文实例讲述了php实现猴子选大王问题算法.分享给大家供大家参考.具体分析如下: 一.问题: n只猴子围坐成一个圈,按顺时针方向从1到n编号. 然后从1号猴子开始沿顺时针方向从1开始报数,报到m的猴子出局,再从刚出局猴子的下一个位置重新开始报数, 如此重复,直至剩下一个猴子,它就是大王. 设计并编写程序,实现如下功能: (1)   要求由用户输入开始时的猴子数$n.报数的最后一个数$m. (2)   给出当选猴王的初始编号. 二.解决方法: /** * @param int $n 开始时的猴子数

  • php编写的抽奖程序中奖概率算法

    们先完成后台PHP的流程,PHP的主要工作是负责配置奖项及对应的中奖概率,当前端页面点击翻动某个方块时会想后台PHP发送ajax请求,那么后台PHP根据配置的概率,通过概率算法给出中奖结果,同时将未中奖的奖项信息一并以JSON数据格式发送给前端页面. 先来看概率计算函数 function get_rand($proArr) { $result = ''; //概率数组的总概率精度 $proSum = array_sum($proArr); //概率数组循环 foreach ($proArr as

  • 适用于抽奖程序、随机广告的PHP概率算法实例

    那么我们在程序里必然会设计到算法,即按照一定的概率让用户获得奖品.先来看两个概率算法函数. 算法一 复制代码 代码如下: /** * 全概率计算 * * @param array $p array('a'=>0.5,'b'=>0.2,'c'=>0.4) * @return string 返回上面数组的key */function random($ps){    static $arr = array();    $key = md5(serialize($ps)); if (!isset

  • php 大数据量及海量数据处理算法总结

    下面的方法是我对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题.下面的一些问题基本直接来源于公司的面试笔试题目,方法不一定最优,如果你有更好的处理方法,欢迎与我讨论. 1.Bloom filter 适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集 基本原理及要点: 对于原理来说很简单,位数组+k个独立hash函数.将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明

  • PHP实现的回溯算法示例

    PHP实现的回溯算法示例

    本文实例讲述了PHP实现的回溯算法.分享给大家供大家参考,具体如下: 问题: 一头大牛驼2袋大米,一头中牛驼一袋大米,两头小牛驼一袋大米,请问100袋大米需要多少头大牛,多少头中牛,多少头小牛? 实现代码: <?php /* * k = 2x + y + 1/2z 取值范围 * 0 <= x <= 1/2k * 0 <= y <= k * 0 <= z < = 2k * x,y,z最大值 2k */ $daMi = 100; $result = array();

随机推荐