algorithm - How do I create a URL shortener?

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

Answer 1

I would continue your "convert number to string" approach. However, you will realize that your proposed algorithm fails if your ID is a prime and greater than 52.

Theoretical background

You need a Bijective Function f. This is necessary so that you can find a inverse function g('abc') = 123 for your f(123) = 'abc' function. This means:

• There must be no x1, x2 (with x1 ≠ x2) that will make f(x1) = f(x2),
• and for every y you must be able to find an x so that f(x) = y.

How to convert the ID to a shortened URL

1. Think of an alphabet we want to use. In your case, that's [a-zA-Z0-9]. It contains 62 letters.

2. Take an auto-generated, unique numerical key (the auto-incremented id of a MySQL table for example).

   For this example, I will use 125₁₀ (125 with a base of 10).

3. Now you have to convert 125₁₀ to X₆₂ (base 62).

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

   This requires the use of integer division and modulo. A pseudo-code example:

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

   Now map the indices 2 and 1 to your alphabet. This is how your mapping (with an array for example) could look like:

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

   With 2 → c and 1 → b, you will receive cb₆₂ as the shortened URL.

   http://shor.ty/cb
   

How to resolve a shortened URL to the initial ID

The reverse is even easier. You just do a reverse lookup in your alphabet.

1. e9a₆₂ will be resolved to "4th, 61st, and 0th letter in the alphabet".

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

2. Now find your database-record with WHERE id = 19158 and do the redirect.

Example implementations (provided by commenters)

• C++
• Python
• Ruby
• Haskell
• C#
• CoffeeScript
• Perl