短鏈接算法收集與分析

中關(guān)村村草

短鏈接算法收集與分析

短鏈接就不說了，大家已經(jīng)都清楚了，如下所示就是短鏈接：

新浪微博     http://t.cn/SVpONM

騰訊微博     http://url.cn/302yor

Yun.io         http://d.yun.io/PNri2v

短鏈接的好處：1、內(nèi)容需要；2、用戶友好；3、便于管理。

如何實現(xiàn)呢，大概有三個步驟：

1、定義一個URL映射算法，可以將長的URL映射成短字符串；

2、使用一個存儲（數(shù)據(jù)庫？NoSQL？）來存儲完成的映射；

3、實現(xiàn)自己的URL映射算法；

一般來說，第三步是我們比較頭疼的，如何將一個長的URL字符串，映射成一個較短的字符串呢。我總結(jié)了三種辦法：

普通實現(xiàn)

我想以前大家學(xué)習(xí)過十進制和二進制的互相轉(zhuǎn)換，或者十進制和十六進制的互相轉(zhuǎn)換，那么為了更短，我們可以使用62進制，對于一個數(shù)字ID進行轉(zhuǎn)碼，轉(zhuǎn)換成一個短字符串。

這種做法的缺點是沒有辦法保證所有鏈接都是固定的位數(shù)的長度，而且在高并發(fā)的情況下，如何保證能夠快速分發(fā)是個問題。

具體實現(xiàn)方法：

1.   /**
   
2.      * 利用62進制對數(shù)字ID進行短鏈接編碼，缺點不能保證每個短鏈接是固定長度
   
3.      *
   
4.      * @author  wanshiqiang<wangshiqiang@#>
   
5.      * @param integer $integer
   
6.      * @param string $base
   
7.      */
   
8.     private function getShortenedURLFromID ($integer, $base = ALLOWED_CHARS)
   
9.     {   
   
10.         $length = strlen($base);
    
11.         while($integer > $length - 1)
    
12.         {   
    
13.             $out = $base[fmod($integer, $length)] . $out;
    
14.             $integer = floor( $integer / $length );
    
15.         }   
    
16.         return $base[$integer] . $out;
    
17.     }   
    
18.     /**
    
19.      * 對62進制編碼的短鏈接進行解碼
    
20.      *
    
21.      * @author  wangshiqiang<wangshiqiang@#>
    
22.      * @param string $string
    
23.      * @param string $base
    
24.      */
    
25.     private function getIDFromShortenedURL ($string, $base = ALLOWED_CHARS)
    
26.     {   
    
27.         $length = strlen($base);
    
28.         $size = strlen($string) - 1;
    
29.         $string = str_split($string);
    
30.         $out = strpos($base, array_pop($string));
    
31.         foreach($string as $i => $char)
    
32.         {   
    
33.             $out += strpos($base, $char) * pow($length, $size - $i);
    
34.         }   
    
35.         return $out;
    
36.     }

復(fù)制代碼

文藝實現(xiàn)

算法描述：使用6個字符來表示短鏈接，我們使用ASCII字符中的'a'-'z','0'-'5'，共計32個字符做為集合。每個字符有32種狀態(tài)，六個字符就可以表示32^6（1073741824），那么如何得到這六個字符，描述如下：

對傳入的長URL進行Md5，得到一個32位的字符串，這個字符串變化很多，是16的32次方，基本上可以保證唯一性。將這32位分成四份，每一份8個字符，這時機率變成了16的8次方，是4294967296，這個數(shù)字碰撞的機率也比較小啦，關(guān)鍵是后面的一次處理。我們將這個8位的字符認(rèn)為是16進制整數(shù)，也就是1*('0x'.$val)，然后取0-30位，每5個一組，算出他的整數(shù)值，然后映射到我們準(zhǔn)備的32個字符中，最后就能夠得到一個6位的短鏈接地址。

PHP實現(xiàn)如下：

1. function shorten( $long_url )
   
2. {
   
3.      $base32 = "abcdefghijklmnopqrstuvwxyz012345";
   
4.      $hex = md5( $long_url );
   
5.      $hexLen = strlen( $hex );
   
6.      $subHexLen = $hexLen / 8;
   
7.      $output = array();
   
8.      for( $i = 0; $i < $subHexLen; $i++ )
   
9.      {
   
10.           $subHex = substr( $hex, $i * 8, 8 );
    
11.           $subHex = 0x3FFFFFFF & ( 1 * ('0x' . $subHex ) );
    
12. 
    
13. 　　　 $out = '';
    
14. 
    
15.           for( $j = 0; $j < 6; $j++ )
    
16.           {
    
17.                $val = 0x0000001F & $int;
    
18.                $out .= $base32[$val];
    
19.                $int = $int >> 5;
    
20.           }
    
21.           $output[] = $out;
    
22.      }
    
23.      return $output;
    
24. }

復(fù)制代碼

二逼實現(xiàn)

下面這個函數(shù)使用了純隨機的方式來生成一個短鏈接，雖然我們可以通過查詢操作來確保不重復(fù)使用短鏈接，可是... 這樣真的靠譜嗎~~

1. function random($length, $pool = '') {
   
2.      $random = '';
   
3.      if (empty($pool)) { $pool    = 'abcdefghkmnpqrstuvwxyz'; $pool   .=
   
4.      '23456789'; }
   
5.      srand ((double)microtime()*1000000);
   
6.      for($i = 0; $i < $length; $i++) { $random .=
   
7.      substr($pool,(rand()%(strlen ($pool))), 1); }
   
8.      return $random;
   
9. }

復(fù)制代碼

Technorati 標(biāo)簽: 短鏈接,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、短網(wǎng)址算法初步匯總

8、Short Url 實現(xiàn)方式

藍貓?zhí)詺饫怖?/a>

學(xué)習(xí)鳥謝謝分享