PHP short link algorithm collection and analysis_PHP tutorial-PHP Tutorial-php.cn

PHP short link algorithm collection and analysis_PHP tutorial

WBOY

Release： 2016-07-21 15:21:41

Original

1061 people have browsed it

I won’t talk about the short link, everyone already knows it. The short link is as follows:
Sina Weibo http://t.cn/SVpONM
Tencent Weibo http://url.cn/302yor
Yun.io http://d.yun.io/PNri2v
Benefits of short links: 1. Content requirements; 2. User-friendly; 3. Easy management.
How to implement it, there are roughly three steps:
1. Define a URL mapping algorithm that can map long URLs into short strings;
2. Use a storage (database? NoSQL?) to store Completed mapping;
3. Implement your own URL mapping algorithm;
Generally speaking, the third step is a headache for us. How to map a long URL string into a shorter string? . I have summarized three methods:
Common implementation
I think everyone has learned about the conversion between decimal and binary, or the conversion between decimal and hexadecimal. In order to be shorter, we can use 62-digit system. , transcode a numeric ID into a short string.
The disadvantage of this approach is that there is no way to ensure that all links are of a fixed length in bits, and in the case of high concurrency, how to ensure rapid distribution is a problem.
Specific implementation method:

Copy code The code is as follows:

 
/**
* Use hexadecimal to encode digital IDs for short links. The disadvantage is that each short link cannot be guaranteed to be of fixed length
* 
* @author wanshiqiang 
* @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 ; 
} 
/**
* Decode the hexadecimal encoded short link
* 
* @author 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; 
} 

Literary implementation
Algorithm description: Use 6 characters to represent short links, we use 'a'-'z','0'-'5 in ASCII characters ', a total of 32 characters are used as a set. Each character has 32 states. Six characters can represent 32^6 (1073741824). So how to get these six characters is described as follows:
Perform Md5 on the incoming long URL to get a 32-bit character String, this string changes a lot, is 16 to the 32nd power, and can basically guarantee uniqueness. Divide these 32 bits into four parts, each part has 8 characters. At this time, the probability becomes 16 to the 8th power, which is 4294967296. The probability of collision of this number is also relatively small. The key is the subsequent processing. We think of this 8-bit character as a hexadecimal integer, that is, 1*('0x'.$val), and then take 0-30 bits, every group of 5, calculate its integer value, and then map it to our From the prepared 32 characters, you can finally get a 6-digit short link address.
PHP implementation is as follows:

Copy code The code is as follows:

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

Second implementation
The following function uses a purely random method to generate a short link, although We can use query operations to ensure that short links are not reused, but... Is this really reliable~~

Copy code The code is as follows:

 
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 tags: short link, Short Url, mapping, hash

Reference:

1. Analysis of the principle of Weibo short address

2. Principles and functions of Weibo short domain names

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. Preliminary summary of short URL algorithm

8. Short Url implementation