JavaScript implementation of Gzip [closed]

Question

I'm writing a Web application that needs to store JSON data in a small, fixed-size server-side cache via AJAX (think: Opensocial quotas). I do not have control over the server.

I need to reduce the size of the stored data to stay within a server-side quota, and was hoping to be able to gzip the stringified JSON in the browser before sending it up to the server.

However, I cannot find much in the way of JavaScript implementations of Gzip. Any suggestions for how I can compress the data on the client side before sending it up?

Caligula

You are sending it up to the server. That's why there are the notions of "upload" and "download". Maybe that's why you are getting answers that tell you "the server can do it". – Vaas

A proper implementation of this is probably tricky, since javascript is single threaded. It would probably have to compress in batches, using setTimeout(), so that the UI doesn't lock up while compressing. – Ditzel

perhaps you could write your own compression algorithm – Geotaxis

@AugustLilleaas now you can use webworkers to do this :) – Deranged

Answer 1

Edit There appears to be a better LZW solution that handles Unicode strings correctly at http://pieroxy.net/blog/pages/lz-string/index.html (Thanks to pieroxy in the comments).

---

I don't know of any gzip implementations, but the jsolait library (the site seems to have gone away) has functions for LZW compression/decompression. The code is covered under the LGPL.

// LZW-compress a string
function lzw_encode(s) {
    var dict = {};
    var data = (s + "").split("");
    var out = [];
    var currChar;
    var phrase = data[0];
    var code = 256;
    for (var i=1; i<data.length; i++) {
        currChar=data[i];
        if (dict[phrase + currChar] != null) {
            phrase += currChar;
        }
        else {
            out.push(phrase.length > 1 ? dict[phrase] : phrase.charCodeAt(0));
            dict[phrase + currChar] = code;
            code++;
            phrase=currChar;
        }
    }
    out.push(phrase.length > 1 ? dict[phrase] : phrase.charCodeAt(0));
    for (var i=0; i<out.length; i++) {
        out[i] = String.fromCharCode(out[i]);
    }
    return out.join("");
}

// Decompress an LZW-encoded string
function lzw_decode(s) {
    var dict = {};
    var data = (s + "").split("");
    var currChar = data[0];
    var oldPhrase = currChar;
    var out = [currChar];
    var code = 256;
    var phrase;
    for (var i=1; i<data.length; i++) {
        var currCode = data[i].charCodeAt(0);
        if (currCode < 256) {
            phrase = data[i];
        }
        else {
           phrase = dict[currCode] ? dict[currCode] : (oldPhrase + currChar);
        }
        out.push(phrase);
        currChar = phrase.charAt(0);
        dict[code] = oldPhrase + currChar;
        code++;
        oldPhrase = phrase;
    }
    return out.join("");
}

Koodoo

How can the code be LGPL if the algorithm is patented? Or are all patents truly expired? – Caligula

According to Wikipedia, the patents expired a few years ago. It might be a good idea to check that out though. – Koodoo

LZW is way too old to still be patented. Last patents ran out in 2003 or so. There are loads of free implementations. – Cleancut

I see at least two problems with the code above: 1) try to compress "Test to compress this \u0110\u0111\u0112\u0113\u0114 non ascii characters.", 2) No error is reported if code > 65535. – Conspecific

And I forgot the third one: The output from encode is in UTF-16. Does your application handle that? – Conspecific

Here is some info on how to compress Unicode: unicode.org/faq/compression.html. Looks if this was not so trivial. – Vaas

There's a different LZW implmentation at zapper.hodgers.com/files/javascript/lzw_test/lzw.js I've no idea whether this addresses any of the above concerns. Also see the related blog post: zapper.hodgers.com/labs/?p=90 – Woodshed

FWIW -- I don't think the zapper.hodgers.com implementation addresses the problems described above. It worked fine with 'plain old ASCII', but when I tried it on a string generated by the HTML canvas toDataUrl() method, for example, the compressed-then-decompressed string didn't match the original. Has anyone implemented JavaScript compression and decompression in a way that addresses the issues above and can cope performance-wise with strings up to about 500K in length -- I realise this is a tall order! – Berserker

@Sam - try utf8_encode(lzw_encode(my_string)). Here's a UTF8 encoder in Javascript: farhadi.ir/works/utf8. – Atherosclerosis

Here are implementations in 21 different languages rosettacode.org/wiki/LZW_compression it's written that it's in public domain from 2004. – Selfsustaining

Has anyone written a compression algorithm that works properly yet? – Jubbah

I couldn't find jsolait library in the link, can I just use the code of answer in my free website app? – Ludicrous

@Ludicrous It looks like the site has been taken down (the content at least). Yes, the LGPL lets you use the code as-is in your application. – Koodoo

@Conspecific I just released a small lib correcting exactly the problems you're pointing out here: pieroxy.net/blog/pages/lz-string/index.html – Toland

@Toland Thanks, I added a link to your site. – Koodoo

@Matthew Crumley thanks. I'm using the lib for a home-grown RSS reader and it seems pretty stable. I've compressed (and successfully decompressed) several dozens of megabytes so far with no issue in sight. I'm already thinking of adding some Huffman to properly encode the tokens generated by LZW but I like the speed of it, so I don't know where I'm going to go with this yet. – Toland

Nice - jsfiddle.net/lordloh/uJj7d – Amrita

it didn't work correctly in my test - jsfiddle.net/4rh4js8h/1 – Haplography

@Haplography It looks like you're running into the Unicode issue with the second "-" that's not a regular hyphen character. I would try pieroxy's code, which should be able to handle non-ASCII characters. – Koodoo

Answer 2

I had another problem, I did not want to encode data in gzip but to decode gzipped data. I am running javascript code outside of the browser so I need to decode it using pure javascript.

It took me some time but i found that in the JSXGraph library there is a way to read gzipped data.

Here is where I found the library: http://jsxgraph.uni-bayreuth.de/wp/2009/09/29/jsxcompressor-zlib-compressed-javascript-code/ There is even a standalone utility that can do that, JSXCompressor, and the code is LGPL licencied.

Just include the jsxcompressor.js file in your project and then you will be able to read a base 64 encoded gzipped data:

<!doctype html>
</head>
<title>Test gzip decompression page</title>
<script src="jsxcompressor.js"></script>
</head>
<body>
<script>
    document.write(JXG.decompress('<?php 
        echo base64_encode(gzencode("Try not. Do, or do not. There is no try.")); 
    ?>'));
</script>
</html>

I understand it is not what you wanted but I still reply here because I suspect it will help some people.

Inshrine

Thank you alot for still sharing. This is exactly what I needed. You probably saved me hours of unsuccessful searching which I really can't spare. +1 – Anility

I wonder why on earth it is called "compressor" when it is an UNcompressor. lol – Briant

almost 5 years later, still useful. thank you. I'm dumping a large JSON directly to the page, instead of AJAX'ing it. by pre-compressing it with PHP and decompressing it back in JavaScript's client side - I'm saving some of the overhead. – Singlephase

Do we need the <?php.. bit?.. I'm asking because it is passed to decompress method. – Endaendall

i get 14:16:28.512 TypeError: e.replace is not a function[Weitere Informationen] jsxcompressor.min.js:19:12201 – Coryza

THANK YOU! It really help me, I've been searching for the solution for 2 days! Again, thank you so much... – Edessa

Answer 3

We just released pako https://github.com/nodeca/pako , port of zlib to javascript. I think that's now the fastest js implementation of deflate / inflate / gzip / ungzip. Also, it has democratic MIT licence. Pako supports all zlib options and its results are binary equal.

Example:

var inflate = require('pako/lib/inflate').inflate; 
var text = inflate(zipped, {to: 'string'});

Gauffer

Please provide a client-side example for decoding gzipped strings. – Cagle

var inflate = require('pako/lib/inflate').inflate; var text = inflate(zipped, {to: 'string'}); @Cagle here's how I use pako. – Perennate

That clientside example throws incorrect header check – Cuticle

Answer 4

I ported an implementation of LZMA from a GWT module into standalone JavaScript. It's called LZMA-JS.

Vedavedalia

do you have a compatible php module for it? – Wale

Answer 5

Here are some other compression algorithms implemented in Javascript:

• Huffman
• LZ77

Ladybug

this LZMA implementation requires BrowserPlus (a browser extension) and does not look to be pure Javascript – Brittney

this LZ77 implementation is no longer available and at least it's Python version (published on the same page) was incorrect for quite simple inputs. – Brittney

geocities dead, will update the link – Ladybug

This is pretty close to what i want. googling things too will update here – Jurywoman

Answer 6

I did not test, but there's a javascript implementation of ZIP, called JSZip:

https://stuk.github.io/jszip/

Wale

That's zip, not gzip, and it uses pako under the hood. Difference is that zip has file info metadata. – Gauffer

Answer 7

I guess a generic client-side JavaScript compression implementation would be a very expensive operation in terms of processing time as opposed to transfer time of a few more HTTP packets with uncompressed payload.

Have you done any testing that would give you an idea how much time there is to save? I mean, bandwidth savings can't be what you're after, or can it?

Vaas

I need to keep the total data size within a certain quota--size is more important than time. – Caligula

Hm... Why is the limit? Just curious. – Vaas

Well, here's Google's take on it: code.google.com/apis/opensocial/articles/… -- Typical Opensocial quotas are around 10K. – Caligula

Depending on how intensive the compression, you could use web workers to perform the task behind the scenes. – Helli

Answer 8

Most browsers can decompress gzip on the fly. That might be a better option than a javascript implementation.

Dichroism

Yes, but I need to compress the data on the client side before sending it down... – Caligula

Answer 9

You can use a 1 pixel per 1 pixel Java applet embedded in the page and use that for compression.

It's not JavaScript and the clients will need a Java runtime but it will do what you need.

Arthrospore

Interesting, but I'd rather avoid including an applet if possible. – Caligula

I'd like to add the real use cases – Vaporish

Not a good solution as it adds a dependency to Java. Apart from that, not everyone has bothered to install java - the site won't work for some people. Personally I have java installed since I needed it for something a long time ago, but I prefer to visit sites that don't use java. – Hundredpercenter