http://blog.csdn.net/beiyeqingteng/article/details/7706010

URL 解析：

當我們在瀏覽器里輸入?http://goo.gl/Jfs6q?時，DNS首先解析獲得http://goo.gl/的IP地址。當DNS獲得IP地址以后（比如：74.125.225.72），會向這個地址發送HTTP GET請求，查詢?Jfs6q， 這個時候，http://goo.gl/服務器會把請求通過HTTP 301轉到對應的長URL?http://blog.csdn.net/beiyeqingteng?。后面的解析過程就和平常網址解析是一樣的了。

短址本質：

短址本質上是實現了一個映射函數 f: X -> Y?。而這個映射函數必須同時具有兩個特點：

1. 如果 x1 != x2, 則 f (x1) != f(x2);

2. 對于每一個 y, 能夠找到唯一的一個 x 使得 f(x) = y;

對于任何的線性函數，比如 f(x) = 2x，都滿足這樣的條件。

好了，如果了解了短址的本質，我們再來看它是如何實現的。

注明：在google?URL shortener 服務中，它允許一個長 url 對應多個短的url。這可能是出于安全上的考慮。在本文中，我們不考慮這種情況。

實現：

短址的長度一般設為 6 位，而每一位是由 [a - z, A - Z, 0 - 9] 總共 62 個字母組成的，所以6位的話，總共會有 62^6 ~= 568億種組合，基本上夠用了。在google?URL shortener 服務中，短址長度為 5，大概有9億多種組合.

假設我們用數據庫來保存長地址和短地址的映射，那么，在表 LongtoShortURL 中，我們會有三列：

1. ID，int, ?自動增長；

2. LURL，varchar, ?// 長URL；

3. SURL, varchar, ?// 短URL。

現在我們考慮通過如何長URL得到唯一的短URL。

在講具體算法以前，先提一個問題：10進制數和16進制數之間的轉換是否滿足剛剛提到的映射函數?f: X -> Y中的兩個條件？

答案： 是。

本文的思路也是利用進制之間的轉換。因為我們總共有 62 個字母，我們可以自創一種進制，叫做 62 進制。其規則如下：

[html] view plaincopyprint?

0??→?a??

1??→?b??

...??

25?→?z??

...??

52?→?0??

61?→?9??

0 → a 1 → b ... 25 → z ... 52 → 0 61 → 9

所以，對于每一個長地址，我們可以根據它的ID，得到一個6位的 62 進制數，這個6位的 62 進制數就是我們的短址。具體實現如下：

[java] view plaincopyprint?

public?ArrayList<Integer>?base62(int?id)?{??

??????

????ArrayList<Integer>?value?=?new?ArrayList<Integer>();??

????while?(id?>?0)?{??

????????int?remainder?=?id?%?62;??

????????value.add(remainder);??

????????id?=?id?/?62;??

????}??

??????

????return?value;??

}??

public ArrayList<Integer> base62(int id) {ArrayList<Integer> value = new ArrayList<Integer>();while (id > 0) {int remainder = id % 62;value.add(remainder);id = id / 62;}return value; }

舉例：

對于 ID = 138，通過 base62(138), 我們得到 value = [14, 2]。根據上面的對應規則表，我們可以得到其對應的短址為：aaaabn 。(由 value 得到具體的短址，可以通過switch 語句得到，因為代碼太長，在此略過。)

當我們想通過短址找到所對應的長地址，方法也很簡單，就是把62進制數轉成10進制數即可，這樣我們就可以得到長地址的ID了。代碼如下：

[java] view plaincopyprint?

public?static?int?base10(ArrayList<Integer>?base62)?{??

????//make?sure?the?size?of?base62?is?6 ??

????for?(int?i?=?1;?i?<=?6?-?base62.size();?i++)?{??

????????base62.add(0,?0);??

????}??

??????

????int?id?=?0;??

????int?size?=?base62.size();??

????for?(int?i?=?0;?i?<?size;?i++)?{??

????????int?value?=?base62.get(i);??

????????id?+=?(int)?(value?*?Math.pow(62,?size?-?i?-?1));??

????}??

??????

????return?id;??

}??

public static int base10(ArrayList<Integer> base62) {//make sure the size of base62 is 6for (int i = 1; i <= 6 - base62.size(); i++) {base62.add(0, 0);}int id = 0;int size = base62.size();for (int i = 0; i < size; i++) {int value = base62.get(i);id += (int) (value * Math.pow(62, size - i - 1));}return id; }

比如，對于短址aaae9a，其62進制為[0, 0, 0, 4,61,0] ，則其長地址的ID 為[0, 0, 0, 4,61,0]?= 0×62^5+?0×62^4 +?0×62^3 +?4×62^2 + 61×62^1 + 0×62^0 = 1915810。有了ID，我們自然就可以得到長地址了。

參考：http://stackoverflow.com/questions/742013/how-to-code-a-url-shortener?(本文算法來源)

http://blog.sina.com.cn/s/blog_65db99840100lg4n.html

轉載請注明出處：http://blog.csdn.net/beiyeqingteng

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的短址(short URL)原理及其实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。