短連結算法收集與分析

短連結就不說了，大家已經都清楚了，如下所示就是短連結：

新浪微網誌     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<[email protected]>

     * @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<[email protected]>

     * @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、短網址算法初步彙總