如何编码一个URL缩短？

我想创build一个URL shortener服务，您可以在input字段中写入一个长URL，该服务将URL缩短为“ http://www.example.org/abcdef ”。

编辑：由于对这个主题的持续兴趣，我已经发布了一个有效的解决scheme，GitHub的JavaScript ， PHP ， Python和Java的实现 。 如果你喜欢，请加上你的解

除了“ abcdef ”之外，还可以使用其他string，其中包含az, AZ and 0-9 6个字符。 这使得56-570亿可能的string。

我的方法是：

我有一个三列的数据库表：

1. ID，整数，自动递增
2. 长，string，用户input的长URL
3. 短，string，缩短的url（或只是六个字符）

然后我会将长URL插入表中。 然后，我将select“ id ”的自动增量值并构build它的散列。 这个散列应该被插入为“ short ”。 但是我应该build立什么样的散列？ 像MD5这样的散列algorithm会造成太长的string。 我想，我不使用这些algorithm。 自buildalgorithm也可以工作。

我的想法：

对于“ http://www.google.de/ ”，我得到自动增量编号239472 。 然后我执行以下步骤：

 short = ''; if divisible by 2, add "a"+the result to short if divisible by 3, add "b"+the result to short ... until I have divisors for az and AZ. 

这可以重复，直到这个数字不再可以被整除。 你认为这是一个好方法吗？ 你有更好的主意吗？

Answer 1

我会继续你的“将数字转换为string”的方法。 然而，如果你的ID是一个素数并且大于52 ，你会意识到你提出的algorithm会失败。

理论背景

你需要一个双射函数 f 。 这是必要的，这样你可以为你的f（123）='abc'函数find一个反函数g（'abc'）= 123 。 意即：

• 一定不存在x1，x2（其中x1≠x2） ，使f（x1）= f（x2） ，
• 对于每一个你必须能够find一个x使得f（x）= y 。

如何将ID转换为缩短的URL

1. 想想我们要使用的字母表。 在你的情况是[a-zA-Z0-9] 。 它包含62个字母 。

2. 采取自动生成的唯一数字键（例如，MySQL表的自动递增的id ）。

   对于这个例子，我将使用125 ₁₀ （125的基数为10）。

3. 现在你必须把125 ₁₀转换成₆₂ （62）。

   125 ₁₀ = 2×62 ¹ + 1×62 ⁰ = [2,1]

   这需要使用整数除法和模数。 一个伪代码示例：

    digits = [] while num > 0 remainder = modulo(num, 62) digits.push(remainder) num = divide(num, 62) digits = digits.reverse 

   现在将索引2和1映射到您的字母表。 这就是你的映射（例如一个数组）的样子：

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

   使用2→c和1→b，您将收到cb ₆₂作为缩短的URL。

    http://shor.ty/cb 

如何将缩短的URLparsing为初始ID

相反更容易。 你只需要在你的字母表中进行反向查找。

1. e9a ₆₂将被parsing为“字母表中的第四，第六十一和第十_个字母”。

   e9a ₆₂ = [4,61,0] = 4×62 ² + 61×62 ¹ + 0×62 ⁰ = 19158 ₁₀

2. 现在用WHERE id = 19158find你的数据库logging并做redirect。

一些实现（由评论者提供）

• ruby
• python
• CoffeeScript的
• 哈斯克尔
• Perl的
• C＃

Answer 2

你为什么要使用散列？
您只需使用简单的自动增量值转换为字母数字值即可。 你可以通过使用一些基础转换来轻松完成。 假设你的字符空间（AZ，az，0-9等）有40个字符，将ID转换为一个基数为40的数字，使用的字符是数字。

Answer 3

 public class UrlShortener { private static final String ALPHABET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"; private static final int BASE = ALPHABET.length(); public static String encode(int num) { StringBuilder sb = new StringBuilder(); while ( num > 0 ) { sb.append( ALPHABET.charAt( num % BASE ) ); num /= BASE; } return sb.reverse().toString(); } public static int decode(String str) { int num = 0; for ( int i = 0; i < str.length(); i++ ) num = num * BASE + ALPHABET.indexOf(str.charAt(i)); return num; } } 

Answer 4

不是您的问题的答案，但我不会使用区分大小写的缩短的URL。 他们很难记住，通常是不可读的（许多字体呈现1和1，0和O和其他字符非常相似，他们几乎不可能分辨），并且容易出错。 尽量只使用大写或小写。

另外，请尝试使用预定义格式混合数字和字符的格式。 有研究表明，人们倾向于记住一种forms比其他人更好（认为电话号码，其中的数字被分组在一个特定的forms）。 试试类似于num-char-char-num-char-char。 我知道这会降低组合，特别是如果你没有大写和小写，但它会更有用，因此有用。

Answer 5

我的方法是：取数据库ID，然后Base36对其进行编码 。 我不会使用大写字母和小写字母，因为这会使得通过电话传输这些URL成为一场噩梦，但是您当然可以轻松地将该function扩展为基本的62解码器。

Answer 6

这是我的PHP 5类。

 <?php class Bijective { public $dictionary = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"; public function __construct() { $this->dictionary = str_split($this->dictionary); } public function encode($i) { if ($i == 0) return $this->dictionary[0]; $result = ''; $base = count($this->dictionary); while ($i > 0) { $result[] = $this->dictionary[($i % $base)]; $i = floor($i / $base); } $result = array_reverse($result); return join("", $result); } public function decode($input) { $i = 0; $base = count($this->dictionary); $input = str_split($input); foreach($input as $char) { $pos = array_search($char, $this->dictionary); $i = $i * $base + $pos; } return $i; } } 

Answer 7

你可以散列整个url，但是如果你只是想缩短身份证，请按照marcel的build议。 我写了这个python实现：

https://gist.github.com/778542

Answer 8

C＃版本：

 public class UrlShortener { private static String ALPHABET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"; private static int BASE = 62; public static String encode(int num) { StringBuilder sb = new StringBuilder(); while ( num > 0 ) { sb.Append( ALPHABET[( num % BASE )] ); num /= BASE; } StringBuilder builder = new StringBuilder(); for (int i = sb.Length - 1; i >= 0; i--) { builder.Append(sb[i]); } return builder.ToString(); } public static int decode(String str) { int num = 0; for ( int i = 0, len = str.Length; i < len; i++ ) { num = num * BASE + ALPHABET.IndexOf( str[(i)] ); } return num; } } 

Answer 9

如果你不想重新发明轮子… http://lilurl.sourceforge.net/

Answer 10

 alphabet = map(chr, range(97,123)+range(65,91)) + map(str,range(0,10)) def lookup(k, a=alphabet): if type(k) == int: return a[k] elif type(k) == str: return a.index(k) def encode(i, a=alphabet): '''Takes an integer and returns it in the given base with mappings for upper/lower case letters and numbers 0-9.''' try: i = int(i) except Exception: raise TypeError("Input must be an integer.") def incode(i=i, p=1, a=a): # Here to protect p. if i <= 61: return lookup(i) else: pval = pow(62,p) nval = i/pval remainder = i % pval if nval <= 61: return lookup(nval) + incode(i % pval) else: return incode(i, p+1) return incode() def decode(s, a=alphabet): '''Takes a base 62 string in our alphabet and returns it in base10.''' try: s = str(s) except Exception: raise TypeError("Input must be a string.") return sum([lookup(i) * pow(62,p) for p,i in enumerate(list(reversed(s)))])a 

这是我的版本，无论谁需要它。

Answer 11

 // simple approach $original_id = 56789; $shortened_id = base_convert($original_id, 10, 36); $un_shortened_id = base_convert($shortened_id, 36, 10); 

Answer 12

为什么不把你的id翻译成string？ 您只需要一个函数，将0和61之间的数字映射到单个字母（大写/小写）或数字。 然后将其应用于创build4个字母的代码，并且覆盖了1470万个url。

Answer 13

这是一个体面的URL编码function的PHP …

 // From http://snipplr.com/view/22246/base62-encode--decode/ private function base_encode($val, $base=62, $chars='0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ') { $str = ''; do { $i = fmod($val, $base); $str = $chars[$i] . $str; $val = ($val - $i) / $base; } while($val > 0); return $str; } 

Answer 14

不知道是否有人会发现这个有用的 – 它更像是一个“黑客n斜线”的方法，但是如果你只想要特定的字符，它很简单，很好地工作。

 $dictionary = "abcdfghjklmnpqrstvwxyz23456789"; $dictionary = str_split($dictionary); // Encode $str_id = ''; $base = count($dictionary); while($id > 0) { $rem = $id % $base; $id = ($id - $rem) / $base; $str_id .= $dictionary[$rem]; } // Decode $id_ar = str_split($str_id); $id = 0; for($i = count($id_ar); $i > 0; $i--) { $id += array_search($id_ar[$i-1], $dictionary) * pow($base, $i - 1); } 

Answer 15

这是我使用的：

 # Generate a [0-9a-zA-Z] string ALPHABET = map(str,range(0, 10)) + map(chr, range(97, 123) + range(65, 91)) def encode_id(id_number, alphabet=ALPHABET): """Convert an integer to a string.""" if id_number == 0: return alphabet[0] alphabet_len = len(alphabet) # Cache result = '' while id_number > 0: id_number, mod = divmod(id_number, alphabet_len) result = alphabet[mod] + result return result def decode_id(id_string, alphabet=ALPHABET): """Convert a string to an integer.""" alphabet_len = len(alphabet) # Cache return sum([alphabet.index(char) * pow(alphabet_len, power) for power, char in enumerate(reversed(id_string))]) 

这是非常快，可以采取长整数。

Answer 16

对于一个类似的项目，为了得到一个新的密钥，我围绕一个随机的string生成器来调用生成器的包装函数，直到我得到一个尚未在我的哈希表中使用的string。 一旦你的名字空间开始变满，这个方法会变慢，但正如你所说的，即使只有6个字符，你也可以使用大量的名字空间。

Answer 17

我故意忽略O，0吗？

刚刚创build了一个基于Ryan的解决scheme的PHP类。

 <?php $shorty = new App_Shorty(); echo 'ID: ' . 1000; echo '<br/> Short link: ' . $shorty->encode(1000); echo '<br/> Decoded Short Link: ' . $shorty->decode($shorty->encode(1000)); /** * A nice shorting class based on Ryan Charmley's suggestion see the link on stackoverflow below. * @author Svetoslav Marinov (Slavi) | http://WebWeb.ca * @see http://stackoverflow.com/questions/742013/how-to-code-a-url-shortener/10386945#10386945 */ class App_Shorty { /** * Explicitely omitted: i, o, 1, 0 because they are confusing. Also use only lowercase ... as * dictating this over the phone might be tough. * @var string */ private $dictionary = "abcdfghjklmnpqrstvwxyz23456789"; private $dictionary_array = array(); public function __construct() { $this->dictionary_array = str_split($this->dictionary); } /** * Gets ID and converts it into a string. * @param int $id */ public function encode($id) { $str_id = ''; $base = count($this->dictionary_array); while ($id > 0) { $rem = $id % $base; $id = ($id - $rem) / $base; $str_id .= $this->dictionary_array[$rem]; } return $str_id; } /** * Converts /abc into an integer ID * @param string * @return int $id */ public function decode($str_id) { $id = 0; $id_ar = str_split($str_id); $base = count($this->dictionary_array); for ($i = count($id_ar); $i > 0; $i--) { $id += array_search($id_ar[$i - 1], $this->dictionary_array) * pow($base, $i - 1); } return $id; } } ?> 

Answer 18

我有一个问题的变种，因为我存储来自许多不同作者的网页，并需要通过猜测来防止发现网页。 所以我的短url为页码添加了一些额外的数字到Base-62string。 这些额外的数字是根据页面logging本身的信息生成的，它们确保3844个URL中只有1个有效（假定是2位Base-62）。 您可以在http://mgscan.com/MBWL上查看概要说明。;

Answer 19

非常好的答案，我创build了一个Golang的bjf实现：

 package bjf import ( "math" "strings" "strconv" ) const alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" func Encode(num string) string { n, _ := strconv.ParseUint(num, 10, 64) t := make([]byte, 0) /* Special case */ if n == 0 { return string(alphabet[0]) } /* Map */ for n > 0 { r := n % uint64(len(alphabet)) t = append(t, alphabet[r]) n = n / uint64(len(alphabet)) } /* Reverse */ for i, j := 0, len(t) - 1; i < j; i, j = i + 1, j - 1 { t[i], t[j] = t[j], t[i] } return string(t) } func Decode(token string) int { r := int(0) p := float64(len(token)) - 1 for i := 0; i < len(token); i++ { r += strings.Index(alphabet, string(token[i])) * int(math.Pow(float64(len(alphabet)), p)) p-- } return r } 

在github托pipe： https ： //github.com/xor-gate/go-bjf

Answer 20

 /** * <p> * Integer to character and vice-versa * </p> * */ public class TinyUrl { private final String characterMap = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"; private final int charBase = characterMap.length(); public String covertToCharacter(int num){ StringBuilder sb = new StringBuilder(); while (num > 0){ sb.append(characterMap.charAt(num % charBase)); num /= charBase; } return sb.reverse().toString(); } public int covertToInteger(String str){ int num = 0; for(int i = 0 ; i< str.length(); i++) num += characterMap.indexOf(str.charAt(i)) * Math.pow(charBase , (str.length() - (i + 1))); return num; } } class TinyUrlTest{ public static void main(String[] args) { TinyUrl tinyUrl = new TinyUrl(); int num = 122312215; String url = tinyUrl.covertToCharacter(num); System.out.println("Tiny url: " + url); System.out.println("Id: " + tinyUrl.covertToInteger(url)); } } 

Answer 21

我的python3版本

 base_list = list("0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ") base = len(base_list) def encode(num: int): result = [] if num == 0: result.append(base_list[0]) while num > 0: result.append(base_list[num % base]) num //= base print("".join(reversed(result))) def decode(code: str): num = 0 code_list = list(code) for index, code in enumerate(reversed(code_list)): num += base_list.index(code) * base ** index print(num) if __name__ == '__main__': encode(341413134141) decode("60FoItT") 

Answer 22

这里是Node.js的实现，可能bit.ly. 生成高度随机的7string。 使用Node.jsencryption生成高度随机的25个字符集，而不是随机select7个字符。

 var crypto = require("crypto"); exports.shortURL = new function () { this.getShortURL = function () { var sURL = '', _rand = crypto.randomBytes(25).toString('hex'), _base = _rand.length; for (var i = 0; i < 7; i++) sURL += _rand.charAt(Math.floor(Math.random() * _rand.length)); return sURL; }; } 

Answer 23

对于高质量的NodeJS / Javascript解决scheme，请参阅id-shortener模块，该模块已经过全面testing，已经在生产中使用了数月。

它提供了一个高效的ID / URL缩短器，可插拔的存储默认为redis ，你甚至可以自定义你的短ID字符集，缩短是否是幂等的 。 这是一个重要的区别，并不是所有的url缩写都会考虑在内。

关于这里的其他答案，这个模块实现了上面Marcel Jackwerth杰出的接受答案。

该解决scheme的核心由以下Redis Lua 代码片段提供 ：

 local sequence = redis.call('incr', KEYS[1]) local chars = '0123456789ABCDEFGHJKLMNPQRSTUVWXYZ_abcdefghijkmnopqrstuvwxyz' local remaining = sequence local slug = '' while (remaining > 0) do local d = (remaining % 60) local character = string.sub(chars, d + 1, d + 1) slug = character .. slug remaining = (remaining - d) / 60 end redis.call('hset', KEYS[2], slug, ARGV[1]) return slug