Background

Recently I built a web app. There was a static list with around 100 items, each of which can be selected or deselected. I hope that the selecting status can be preserved when refreshing the page, and the entire state of the page is persisted into the URL so that it can be easily shared.

The most straightforward way to do so is to add a URL parameter like ids=1,2,3. However, when selecting all or most of the items, the parameter will be terribly long. It is not good for sharing and it won’t work as the list grows. So I expected a better solution.

Booleans In Binary

I noted that the status of the list is determined by a list of boolean values, i.e. whether each item is selected or not.

Each boolean value can be represented as 0 or 1. So the entire status of the list can be represented by a sequence of 0s and 1s, for example:

Now the length of the value will always be the same as the size of the list, still too long.

But given it is just a sequence of 0s and 1s, it seems easy to make it shorter.

Achievement so far:

value.length = list.length;

Booleans in Hexadecimal

If I convert the base-2 value into base-16, the value will be much shorter.

For example:

If the length of the value is not a multiple of 4, I need to add 0s to the end.

When restoring the status, I will just ignore the redundant numbers.

Since every 4 base-2 digits are encoded into 1 base-16 digit, the length of the new value is 1/4 the size of the list.

Achievement:

value.length = Math.ceil(list.length / 4);

Booleans in Base-64

By converting to base-16 value, I got 1/4 of the original length. What if I use a even more compact encoding like base-64?

For example:

Note the trailing =s can be removed safely.

The way we need to convert the 0/1 sequence into bytes first, merging every 8 digits into 1 byte, making the value length 1/8 of the original list size. Then encode the byte sequence in Base-64, blowing up the value length by 4/3 because only visible characters can be used in the final string.

It is not done yet. Base-64 uses a few special characters that are escaped in URLs: +/=. =s used for padding in the end can be safely removed. So I only need to care about + and /.

Take 1111 1011 as an example, it will be encoded into +/ in base-64, then escaped as %2B%2F in the URL. It is even longer, absolutely unacceptable.

Luckily, there are other characters not necessarily escaped, so I can replace + with -, and / with _, which is known as the Base-64-url encoding.

After the substitution, 1111 1011 is converted to -_ and preserved in the URL.

With this approach, 100 boolean values can be remarkably compressed into a string of only 14 characters.

Achievement:

value.length = Math.ceil((Math.ceil(list.length / 8) * 4) / 3);

Takeaway

An efficient way to encode a large number of boolean values is to first convert the values into a 0/1 sequence, then compact them into bytes, and finally encod them using Base-64, or Base-64-url for URLs.