快捷導(dǎo)航

php 短鏈接算法收集與分析

更新時(shí)間：2011年12月30日 00:01:44 投稿：mdxy-dxy

php 短鏈接算法收集與分析,需要的朋友可以參考下。

短鏈接就不說(shuō)了，大家已經(jīng)都清楚了，如下所示就是短鏈接：
新浪微博 http://t.cn/SVpONM
騰訊微博 http://url.cn/302yor
Yun.io http://d.yun.io/PNri2v
短鏈接的好處：1、內(nèi)容需要；2、用戶友好；3、便于管理。
如何實(shí)現(xiàn)呢，大概有三個(gè)步驟：
1、定義一個(gè)URL映射算法，可以將長(zhǎng)的URL映射成短字符串；
2、使用一個(gè)存儲(chǔ)（數(shù)據(jù)庫(kù)？NoSQL？）來(lái)存儲(chǔ)完成的映射；
3、實(shí)現(xiàn)自己的URL映射算法；
一般來(lái)說(shuō)，第三步是我們比較頭疼的，如何將一個(gè)長(zhǎng)的URL字符串，映射成一個(gè)較短的字符串呢。我總結(jié)了三種辦法：
普通實(shí)現(xiàn)
我想以前大家學(xué)習(xí)過(guò)十進(jìn)制和二進(jìn)制的互相轉(zhuǎn)換，或者十進(jìn)制和十六進(jìn)制的互相轉(zhuǎn)換，那么為了更短，我們可以使用62進(jìn)制，對(duì)于一個(gè)數(shù)字ID進(jìn)行轉(zhuǎn)碼，轉(zhuǎn)換成一個(gè)短字符串。
這種做法的缺點(diǎn)是沒(méi)有辦法保證所有鏈接都是固定的位數(shù)的長(zhǎng)度，而且在高并發(fā)的情況下，如何保證能夠快速分發(fā)是個(gè)問(wèn)題。
具體實(shí)現(xiàn)方法：

復(fù)制代碼代碼如下:

/**
* 利用62進(jìn)制對(duì)數(shù)字ID進(jìn)行短鏈接編碼，缺點(diǎn)不能保證每個(gè)短鏈接是固定長(zhǎng)度
*
* @author wanshiqiang<wangshiqiang@#>
* @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;
}
/**
* 對(duì)62進(jìn)制編碼的短鏈接進(jìn)行解碼
*
* @author wangshiqiang<wangshiqiang@#>
* @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;
}

文藝實(shí)現(xiàn)
算法描述：使用6個(gè)字符來(lái)表示短鏈接，我們使用ASCII字符中的'a'-'z','0'-'5'，共計(jì)32個(gè)字符做為集合。每個(gè)字符有32種狀態(tài)，六個(gè)字符就可以表示32^6（1073741824），那么如何得到這六個(gè)字符，描述如下：
對(duì)傳入的長(zhǎng)URL進(jìn)行Md5，得到一個(gè)32位的字符串，這個(gè)字符串變化很多，是16的32次方，基本上可以保證唯一性。將這32位分成四份，每一份8個(gè)字符，這時(shí)機(jī)率變成了16的8次方，是4294967296，這個(gè)數(shù)字碰撞的機(jī)率也比較小啦，關(guān)鍵是后面的一次處理。我們將這個(gè)8位的字符認(rèn)為是16進(jìn)制整數(shù)，也就是1*('0x'.$val)，然后取0-30位，每5個(gè)一組，算出他的整數(shù)值，然后映射到我們準(zhǔn)備的32個(gè)字符中，最后就能夠得到一個(gè)6位的短鏈接地址。
PHP實(shí)現(xiàn)如下：

復(fù)制代碼代碼如下:

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

實(shí)現(xiàn)
下面這個(gè)函數(shù)使用了純隨機(jī)的方式來(lái)生成一個(gè)短鏈接，雖然我們可以通過(guò)查詢操作來(lái)確保不重復(fù)使用短鏈接，可是... 這樣真的靠譜嗎~~

復(fù)制代碼代碼如下:

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