Compression of javascript object notation data using structure information

Patent metadata

Field	Value
Publication number	US-10122380-B2
Application number	US-201514941831-A
Country	US
Kind code	B2
Filing date	Nov 16, 2015
Priority date	Nov 16, 2015
Publication date	Nov 6, 2018
Grant date	Nov 6, 2018

Abstract

A method for encoding and decoding a javascript object notation (JSON) document utilizing a statistical tree representing a JSON Schema. The encoded statistical tree may be optimized.

First claim

What is claimed is:

1. A method for encoding a javascript object notation (JSON) document utilizing a statistical tree representing a JSON Schema, comprising the steps of:
a computer establishing a root node of the statistical tree;
the computer sequentially selecting each of a plurality of fragments of the JSON document;
the computer locating a genuine node having properties corresponding to the respective fragment in the statistical tree corresponding to each of the selected fragments;
the computer determining a binary code representing a path of traversal through the statistical tree to the corresponding genuine node from the root node;
the computer ordering the binary code in accordance with the sequence of the respective fragments in the JSON document;
the computer analyzing each located genuine node to determine the type of node, with the determined type being utilized to establish a next genuine node for encoding the sequentially next fragment of the JSON document; and
the computer optimizing the statistical tree to reduce a number of bits comprising the binary code representing elements, enumerations, and attributes of the JSON document.

2. The method of claim 1 , wherein the optimizing of the statistical tree further comprises for each genuine node which is of a determined type:
setting an immediate parent node of the genuine node as the root node;
searching for and counting a number of times the genuine node is found in the tree; and
if the count has reached a maximum number of occurrences determined by the JSON Schema, removing the genuine node from the tree and moving a peer node of the genuine node indicated by ‘0’ to the position of the ‘0’ of the immediate parent node;
wherein in the node removed was a fragment, and any other attributes are still being referenced, repeating the steps of setting the immediate parent node of the genuine node as the root node; searching for and counting the number of times the genuine node is found in the tree; and removing the genuine node from the tree and moving a peer node of the genuine node indicated by ‘0’ to the position of the ‘0’ of the immediate parent node until all attributes of the node representing a fragment have been removed.

3. The method of claim 2 , further comprising the step of reordering the tree based on rules used to build the tree after all attributes being references by nodes representing fragments that exceeded a maximum occurrence have been removed and moved to the position of its immediate parent node.

4. The method of claim 3 , wherein the rules comprise:
a) attributes with enumerations are of a greater priority than other elements;
b) a smaller the number of possible occurrences, a greater a priority;
c) if multiple occurrences are assigned a same level of priority based on rules a) and b), one or more components are further prioritized according to a minimum number of occurrences of each component, wherein a higher minimum occurrence is assigned a higher level of priority; and
d) if multiple occurrences are assigned a same level of priority based on rules a), b), and c), the one or more components are further prioritized based on a length of name of the JSON component, wherein a greater length of name is assigned a higher level of priority.

5. The method of claim 1 , wherein if the analyzed genuine node is determined not to be a predefined type, the computer retrieves and merges the respective type tree corresponding to a type of the located node with the located node.

6. The method of claim 5 , further comprising the step of the computer designating the located node merged with the retrieved type tree as the root node.

7. The method of claim 6 , further comprising the step of the computer designating a parent genuine node of the root node as a new root node once traversal through a merged type tree has been performed.

8. The method of claim 7 , wherein the designating of a new root node occurs when a non-genuine leaf node is located.

9. The method of claim 1 , further comprising the step of the computer combining the binary code with the retrieved data to form the encoded JSON document.

10. A method for decoding a JSON document represented by a binary encoded sequence, the method comprising:
a computer establishing a root node in a statistical tree representing a JSON Schema of the JSON document;
the computer traversing the statistical tree from the designated root node to locate a next genuine node, the traversal based upon at least one portion of the binary encoded sequence bits;
the computer generating a fragment of the JSON document, the fragment corresponding to the located genuine node;
the computer ordering the generated fragments in accordance with the order of the corresponding bits in the binary sequence;
the computer analyzing each located genuine node to determine the type of node, with the determined type being utilized to establish a next genuine node for decoding the sequentially next fragment of the JSON document; and
the computer optimizing the statistical tree to reduce a number of bits comprising the binary code representing elements, enumerations, and attributes of the JSON document;
wherein each genuine node is analyzed to determine a type of the node, the type of node determining if a next genuine node is to be designated for traversing the statistical tree in according with the bits corresponding to the sequentially next at least one portion of the binary encoded sequence.

11. The method of claim 10 , wherein if the genuine node is a leaf node whose path from a parent node is designated by a binary ‘0’, the genuine parent node of the designated root node is assigned as the root node for traversing the statistical tree to decode the sequentially next at least one portion of the binary encoded sequence.

12. The method of claim 10 , wherein the optimizing of the statistical tree further comprises for each genuine node which is of a determined type:
setting an immediate parent node of the genuine node as the root node;
searching for and counting a number of times the genuine node is found in the tree; and
if the count has reached a maximum number of occurrences determined by the JSON Schema, removing the genuine node from the tree and moving a peer node of the genuine node indicated by ‘0’ to the position of the ‘0’ of the immediate parent node;
wherein in the node removed was a fragment, and any other attributes are still being referenced, repeating the steps of setting the immediate parent node of the genuine node as the root node; searching for and counting the number of times the genuine node is found in the tree; and removing the genuine node from the tree and moving a peer node of the genuine node indicated by ‘0’ to the position of the ‘0’ of the immediate parent node until all attributes of the node representing a fragment have been removed.

13. The method of claim 12 , further comprising the step of reordering the tree based on rules used to build the tree after all attributes being references by nodes representing fragments that exceeded a maximum occurrence have been removed and moved to the position of its immediate parent node.

14. The method of claim 13 , wherein the rules comprise:
a) attributes with enumerations are of a greater priority than other elements;
b) a smaller the number of possible occurrences, a greater a priority; and
c) if multiple occurrences are assigned a same level of priority based on rules a) and b), one or more components are further prioritized according to a minimum number of occurrences of each component, wherein a higher minimum occurrence is assigned a higher level of

Assignees

• IBM

Inventors

• Balegar Umesh Kumar Balaraj
• Rajamanickam Logeswaran T
• Shetty Ashrith
• Shetty Rohit

Classifications

• G06F17/30327

  Physics · mapped topic

• H03M7/707

  Structured documents, e.g. XML · CPC title

• H03M7/3079 Primary

  Context modeling · CPC title

• H03M7/60 Primary

  General implementation details not specific to a particular type of compression · CPC title

• G06F17/30536

  Physics · mapped topic