algorithm - 如何编写一个网址缩短?

  显示原文与译文双语对照的内容

我想创建一个URL缩短服务,你可以在一个输入字段中写入一个长 URL,该服务缩短了指向" http://www.example.org/abcdef"的URL 。 除了" abcdef"之外,还可以有任何其他包含六个字符的字符串 a-z, A-Z and 0-9 这使得 56 ~57 可能的字符串。

编辑:由于持续的对这个话题的兴趣,我上传了我用 GitHub的代码,以实现 JavaPHPJavaScript 。 如果愿意,添加解决方案:

我的方法:

我有一个包含三列的数据库表:

  1. id,整数,auto-increment
  2. 长,字符串,用户输入的长 URL
  3. 短,字符串,缩短的URL ( 或者六个字符)

然后我会在表格中插入长长的URL 。 然后我会选择" id"auto-increment值并建立一个散列。 这里哈希值应该作为" short"插入。 但是应该构建什么样的哈希? 像MD5这样的哈希算法创建的字符串太长。 我不使用这些算法,我认为。 self-built算法也能工作。

我的想法是:

对于" http://www.google.de/",我得到auto-increment标识 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 a-z and A-Z.

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

时间:


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, len = str.length(); i <len; i++ )
 {
 num = num * BASE + ALPHABET.indexOf( str.charAt(i) ); 
 }

 return num;
 } 
}


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

这是我为谁需要的版本。

这是我的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;
 }
}

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

...