Encoder for TinyURL

Introduction

We have discussed the overall design of a short URL generator (SUG) in detail, but two aspects need more clarification:

1. How does encoding improve the readability of the short URL?
2. How the sequencer and the base-58 encoder in the short URL generation are related?

Why Encoding?

Our sequencer generates a 64-bit ID in base-10 which can be converted to a base-64 short URL; base-64 is the most common encoding for alphanumeric strings generation. However, there are some inherent issues with sticking to the base-64 for this design problem: the generated short URL might have readability issues because of look-alike characters. Characters like O(capital o) and 0(zero), I (capital I), and l (lower case L) can be confused while characters like + and / should be avoided because of other system-dependent encodings.

We, therefore, slash out the six characters and use base-58 instead of base-64 (includes A-Z, a-z, 0-9, + and /) for enhanced readability purposes. Let's have a look at our base-58 definition.

The highlighted cells contain the succeeding characters of the omitted ones -- 0, O, I and l.

Base 10 -> Base 58

As we are converting base-10 numeric IDs to base-58 alphanumeric IDs, explaining the conversion process will be helpful in grasping the underlying mechanism as well as the overall scope of the SUG. To achieve the above functionality, we use the modulus function.

Process: We keep diving the base-10 number by 58, making note of the remainder at each step. We stop where there is no remainder left. Then we assign the character indexes to the remainders, starting from assigning the recent-most remainder to the left-most place and the oldest remainder to the right-most place.

Example: Let's assume that the selected unique ID is 2468135791013. Following are the steps depicting the remainder calculations:

Base-10 = 2468135791013

1.   $2468135791013 \ \% \ 58 = 17$
2.   $42554065362 \ \% \ 58 = 6$
3.   $733690782 \ \% \ 58 = 4$
4.   $12649841 \ \% \ 58 = 41$
5.   $218100 \ \% \ 58 = 20$
6.   $3760 \ \% \ 58 = 48$
7.   $64 \ \% \ 58 = 6$
8.   $1 \ \% \ 58 = 1$

Now, we need to write the remainders in the recent-most to the oldest order.

Base-58 = [1] [6] [48] [20] [41] [4] [6] [17]

Using the table above, we can write the associated characters with the above-written remainders.

Base-58 = 27qMi57J

Both the base-10 numeric IDs and base-64 alphanumeric IDs have 64-bits, as per our sequencer design.

Let's see the above example with the help of the following illustration.

Base-58 -> Base-10

The decoding process holds equal importance as the encoding process, as we used a decoder in case of custom short URLs generation, explained in the design lesson.

Process: The process of converting a base-58 number into a base-10 number is also straightforward: we just need to multiply each character index (value column from the table above) by the number of 58s that position holds, and add all the individual multiplication results.

Example: Let's reverse engineer the above example to see how decoding works.

Base-58: 27qMi57J

  $2_{58} = 1 \times 58^{7} = 2207984167552$ ...