22.05.2023

The Best String Compression in JavaScript

A mini comparison of some string compression algorithms

edit: 23.05.22 - add benchmarks of gzip, zlib and deflate via wasm-flate

Lately, I needed to find a decent algorithm to compress strings in JavaScript so that I could encode it as a URL param. Since the strings to be encoded where p5 sketches that ran in the p5.cljs web editor, it was important that the compressed string was short enough to enable longer sketches to be written.

The algorithms

After some searching on the web, I found some algorithms that I could use for this purpose. These are:

• u-lzss - an algorithm created by Google
• lz-string - an LZ-compression based algorithm
• lzw - another algorithm also based on LZ-compression
• gzip - this, and the next two algorithms, are a part of wasm-flate
• zlib
• deflate

If you don’t know what LZ compression is, well, I confess … neither do I. What I noticed was that LZ-based compression is rather ubiquitous.

Hiccups

There were many more compression algorithms that I could find for JavaScript. However, many of them were either only for Node.js, using the Buffer api, or just didn’t work. For algorithms using the Buffer api, wasm implementations are a godsend.

The benchmark

Since the only thing that mattered to me was the resulting base64 string at the end of the compression process, the benchmarks I ran only measured the length of the resulting string. The compression process looks like this:

• compress the string using the algorithm
• encode the resulting string as a Uint8Array
• convert this the Uint8Array to base64

I the following string sources to test the algorithms.

• sketch - an example sketch for the p5.cljs web editor. Lines: 42.
• simplexNoise - a GLSL snippet for 4D simplex noise. Lines: 92.
• quil - a part of the Quil source code. Lines: 191.
• triangle - a JS wrapper for the C triangulation library triangle. Lines: 391.
• modele - a part of Open Music’s source code. Lines: 588.

Since triangle contained template literals, I had to modify the source to escape the backticks and $.

The results

character count

ratio

compression ratio increases as file size gets larger

From this mini-benchmark, we see that the deflate algorithm performed the best, reaching almost a compression ratio of around 30% for the largest source text. That said, gzip, zlib and deflate have almost the same results.

For all three algorithms that were tested, the compression ratio improved as the length of the source string increased. But beyond a certain size, it seems to go back down.

Reversibility

Testing the reversibility of the algorithms, I was surprised to see that Google’s u-lzss wasn’t 100% reversible. For longer source strings, the decompressed string contained corrupted and malformed strings towards the end of the file.

Snippet of original string

class TriangulateIO {
    static get LENGTH() { return 23; }
    constructor(props = {}) {

Malformed output of u-lzss

lass TangleuleMoIO
cstr ic         etTy LENGTH({
eturn nu23; }   const tctor =(prop= pt{}{

Conclusion

Compression is probably better done elsewhere than a browser environment. But sometimes you just need to have a handy compression tool, like in the p5.cljs editor, which shares sketches by storing them as a url param instead of in a server somewhere. In this situation, I’ll be choosing deflate for my use case.

If you want to checkout the benchmark, it’s on github. Also, I don’t have a deep understanding of compression and maybe missing out on something. If you know better, do reach out on my socials or email!