JSON is horribly inefficient data format for data exchange between a web server and a browser. For one, it converts everything to text. The value 3.141592653589793 takes only 8 bytes of memory, but JSON.stringify() expands it to 17. A second problem is its excessive use of quotes, which add two bytes to every string. Thirdly, it has no standard format for using a schema. When multiple objects are serialized in the same message, the key names for each property must be repeated, even though they are the same for each object.
JSON used to have an advantage because it could be directly parsed by a javascript engine, but even that advantage is gone because of security and interoperability concerns. About the only thing JSON going for it is that it is usually more compact than the alternative, XML, and it is well supported by many web programming languages.
Compression of JSON data is useful when large data structures must be transmitted from the web browser to the server. In that direction, it is not possible to use gzip compression, because it is not possible for the browser to know in advance whether the server supports gzip. The browser must be conservative, because the server may have changed abilities between requests.
Today, let's tackle the most pressing problem: the need to constantly repeat key names over and over. I will present a Javascript library for compressing JSON strings by automatically deriving a schema from multiple objects. The library can be used as a drop in replacement for the methods JSON.stringify() and JSON.parse(), except that it lacks support for a reviver function. In combination with Rison, the savings could be significant.
Suppose you have to transmit several thousand points and rectangles. JSON might encode them like this (without the comments):
[
{ // This is a point
"x": 100,
"y": 100
},
{ // This is a rectangle
"x": 100,
"y": 100,
"width": 200,
"height": 150
},
{}, // an empty object
... // thousands more
]
A lot of the space is taken up by repeating the key names "x", "y", "width", and "height". They only need to be stored once for each object type:
Each object in the original input is transformed. Instead of listing the keys, the "type" field refers to a list of keys in the schema array. (The type is 1-based, instead of zero based, and I will explain why later). But we are still repeating "x", and "y". The rectangle shared these properties with the point type, and there is no need to repeat them in the schema:
We prefix each key list in the schema with a number. This number is the one-based index of a prior schema which is prepended to it to form the combined list. Zero means the empty object, which is why we use one-based indicies.
But we can still go a little further. Instead of having a separate "type" field in each object, we stick the type as the first element of the values array.
The hard part is finding the objects which share sets of keys. It sounds a lot like the Set Cover problem, and if so, an optimal solution is NP-complete. Instead, we will approximate the solution using a tree structure. While we are building the value array, when we encounter an object, we add all of its keys to the tree in the order that we encounter them.
At the end of the process, we can traverse the nodes of the tree and create the templates. Nodes which represent the end of a key list (shown in gray) must have entry in the key list. Although not illustrated here, nodes with multiple children are also points where the the child object types inherit from a common parent, so they also get an entry.
The astute reader will realize that the final schema depends on the order that we inserted the keys into the tree. For example, if, when we encountered the rectangle, we inserted the keys "width" and "height" before "x", and "y", the algorithm would not find any common entries.
It is possible to gain more efficient packing by using a greedy algorithm. In the greedy algorithm, before we begin, an initial pass through all the objects would be made to build a list of unique object types. Then when it comes time to insert keys into the tree, they are first sorted so that the ones which occur in the most unique types are inserted first. However, this method adds a lot of extra processing and I feel the gains would not be worthwhile.
Real world savings
Here is an actual document from my web site, Zwibbler.com. Click on "Transform" to see how CJSON compresses it vs. JSON.
The automatic type extraction that is used here is a perfect fit for converting unstructured data into structured data in the format required by my new serializer. See on Github: That3Percent/tree-buf
By utilizing this technique, far greater gains can be realized than are possible with gzip.
As I said in the article, gzip is certainly better. But it is not currently possible to use gzip compression when sending in the browser to server direction. As far as I know, web browsers do not allow this.
This is cool, but I don't see the benefit. If the size is critical, for example on a web page, then you can just use a generic compression algorithm. The example with 19,468 bytes becomes 12,451 using this method, and 1,752 with default gzip on my machine.
Great idea, but why to keep explicit index of data schemes. Look at RJSON that build index of schemes during decoding and so uses implicit index www.cliws.com/e/06pogA9VwXylo_GknPEeFA/
If I didn't care about order of points and rectangles, only that they were preserved within each type, I might be inclined to omit the type flags in the items by storing items separately by type. Something like this:
Sorry VeganBen but the quotes around the key names (which are strings) must be present if the JSON is to be valid. A lot of parsers are relaxed to allow them to be omitted, but that is non-standard.
If you really want to save on band-width and don't care about readability.. you can also store your data as an array of arrays instead of using objects since javascript arrays are not typed like in e.g. Java. It's comparable to using tuples (see Scala)
I was about the write the same final step as Josh, then read the comments.
Couple of further points.. keys do _not_ need to be enquoted.
I like the "values" portion. I think the embedding of templates in each other is an optimisation too far. It does more for obfuscation than it does for either minification or optimisation.
It might be more "optimised" in the data, but the extra process to extract the full template from a nested template can't be helpful.
Its a good codification strategy, but if you want to minimize the size, why not go into object serialization or a custom format with gzip applied on top? json is by purpose a verbose codification.
Most people choose json because of its simplicity (readibility) and your algorigthm breaks that feature.
Your JSON minifying algorithm looks nice, however when you gzip the minified and the non-minified version, the filesizes only differ by about 7%. This is because the Huffman-Encoding in gzip can deal quite well with repeated text structures.
Interesting notion! My only concern would be the extra processing required to decode and rebuild the original JSON, particularly for large JSON strings, which is where you'd see the most savings. Have you done any performance testing on the encoding and decoding functions?
After many months, your software sale is complete! You've got a purchase order, sent the invoice, delivered the software. You're already handling some support issues from users at BigCorp. Then BANG! Martha from Procurement emails back, as a favour, just to let you know that BigCorp has not received your W8 form with a valid tax id, and therefore will be withholding 30% of the purchase price of your multi-thousand dollar product for taxes.
Much ink has been spilled about the use of cell phones on airplanes. Here's the truth, which will be disappointing to conspiracy theorists: Cell phone signals most definately have an effect on other electronic equipment. Read on for more.
If you have to draw something called "UML Sequence Diagrams" for work or school, you already know that it can take hours to get a diagram to look right. Here's a web site that will save you some time.
Is it possible to make money on the internet, if you try really hard? I want to find out.
I have always been interested in getting money for doing nothing.
After many months, your software sale is complete! You've got a purchase order, sent the invoice, delivered the software. You're already handling some support issues from users at BigCorp. Then BANG! Martha from Procurement emails back, as a favour, just to let you know that BigCorp has not received your W8 form with a valid tax id, and therefore will be withholding 30% of the purchase price of your multi-thousand dollar product for taxes.