Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 算法 » 

短链接算法实现

短链接由于微博的流行变得应用非常广泛,短连接简单来说就是把一个很长的URL地址转化为相对简短的地址而且仍然可以正常使用,如把地址http://noalgo.info/转化为http://t.cn/R74gDvp,当然我这里本来就比较短,不过对于再长的地址也是转化成为相同长度的短链接。
本文将介绍短链接的简介及生成的算法原理,最后提供一个C++版本的短链接生成代码。

简介

短链接的例子上面已经介绍了,其现在应用非常广泛,谷歌、百度、新浪等网站都加入了短链接的功能,短链接相对于原始的链接,其主要的作用包括:

  • 用户友好。使用短链接可以让用户不受很长而又没有太大实际意义的链接地址内容影响,让用户关注于内容本省。
  • 长度缩短。比如微博只允许发140 字,如果链接地址太长的话,那么发送的字数就大大减少,短链接可以把原来很长的地址压缩成只有6个字母的短链接地址同时又可以进行正常跳转,于是可以添加其他有意义的内容。
  • 统一管理。短链接的跳转需要经过该网站的短链接服务器,这样可以方便地统计导出流量及其他信息。

算法原理

其实短链接并没有一个固定的算法,其原理就是把长链接通过一定的规则得到一个短链接,然后把这个长短链接关系在服务器上记录下来,具体使用的数据库可以是关系数据库或者是非关系数据库NoSql。当在页面上点击短链接时,会访问到短链接服务器,然后服务器根据短链接查找到对应的长连接,然后进行重定向。
由上面可知,纯粹在本地生成的短链接是没有作用的。因为短链接需要解析,需要跳转到短链接解析服务器,然后在服务器上查找对应的长链接,最后才可以进行对应的跳转。如果纯粹在本地生产的短链接,服务器上没有响应的数据,则是不能进行正常访问的。

算法本质上就是一个长短链接的映射过程,那么一个简单的想法是用递增的序号来表示短链接,每次进来一个长链接时,把它映射成当前的序号,同时把序号递增以供下一个链接使用。因为链接地址同时使用的是a-z、A-Z和0-9这62个字符,把10进制的序号值转化为这个62进制的表示即可得到对应的短链接。

这个直接的想法非常简单粗暴,另外一个直观的想法是使用随机的方法生成长短链接的映射关系。每次进来一个长链接时就随机一个短链接来进行映射,如果通过数据库查询发现此短链接已经使用过,则重新进行随机直到产生一个未曾使用过的短链接为止。

网上流传较广的是另外一种利用MD5进行哈希的算法,其具体过程为:

  1. 将原始长链接进行MD5加密,为了避免防止算法泄漏,可以在原链接上添加自定义的字符串作为密钥。
  2. 把128位的MD分成四组,每组32位,对应一个候选短链接。
  3. 对于每个32位的数,将它与0x3FFFFFFF进行位与运算,取其低30位的数据。把得到的值与0x0000003D进行位与运算,再把得到的结果作为下标在字符表中选取字符,再把原数字右移5位进行相同操作,重复进行6次得到6个字符,即组成一个候选短链接地址。
  4. 在4个候选短链接中随机选择一个作为最终的短链接,把长短链接映射关系存入数据库中。

服务器收到一个短链接请求时,需要把从http地址中解析出短链接,然后将得到的短链接在数据库中进行查询,找到其对应的长连接,进而重定向到该长长链接对应的地址。另外,服务器在此时可以随意进行一些需要的统计工作。

代码实现

这里实现了一个使用MD5算法进行哈希的算法,由于C++标准并没有提供MD5的对应函数,这里使用了之前实现过的一个MD5算法,具体可以参考MD5算法原理及实现
代码的主要功能可以通过URLshorten完成,在main函数中进行了简单的测试。

#include "md5.h"
#include <ctime>
#include <string>
#include <iostream>
using namespace std;

//生成一个长URL的短链接
string URLshorten(string longURL)
{
	//加密字符串
	string key = "URLshorten";
	//URL字符表,共62个,下标为0~61
	string text = "abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	string md5text = md5(key + longURL);

	string shortURLs[4];
	for (int i = 0; i < 4; i++)
	{
		string str = md5text.substr(i*8, 8);

		//取出MD5中第i个字节,并忽略超过30位的部分
		unsigned int num;
		sscanf(str.c_str(), "%x", &num); //把str里的十六进制表示转化成int
		num &= 0x3FFFFFFF;               //选择低30位

		//取30位的后6位与0x0000003D进行逻辑与操作,结果范围是0~61,作为text的下标选择字符
		//把num左移5位重复进行,得到6个字符组成短URL
		string shortURL;
		for (int j = 0; j < 6; j++)
			shortURL += text[num & 0x0000003D], num >>= 5;

		// cout << "Candidate " << i << ": " << shortURL << endl;
		shortURLs[i] = shortURL;
	}

	//随机返回四个短URL中的一个
	srand(time(0));
	return shortURLs[rand() % 4];
}

int main (int argc, char *argv[])
{
	string URL = "http://noalgo.info/";
	cout << "Long URL: " << URL << endl;
	cout << "Short URL: " << URLshorten(URL) << endl;
}
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论