Methods of creating a dictionary for data compression
First Claim
1. A method for creating a static dictionary, the method comprising:
- providing a plurality of data trees, each of the plurality of data trees comprising a root node, at least one of the plurality of data trees comprising at least one child node, wherein each root node and each child node stores an associated binary pattern, wherein each child node is adapted to store a symbol associated with the child node and an occurrence count value associated with the child node;
defining a binary pattern string, the binary pattern string comprising a concatenation of the binary patterns in a direct path from the root node to a particular child node, and wherein an occurrence count value for the binary pattern string is the occurrence count value of the particular child node;
incrementing the occurrence count value of the particular child node when the particular child node is visited; and
incrementing an occurrence count value of a node in the direct path between the root node and the particular child node less frequently than the occurrence count value of the particular child node.
5 Assignments
0 Petitions
Accused Products
Abstract
Some aspects of the invention provide methods, systems, and computer program products for creating a static dictionary in which longer byte-strings are preferred. To that end, in accordance with aspects of the present invention, a new heuristic is defined to replace the aforementioned frequency count metric used to record the number of times a particular node in a data tree is visited. The new heuristic is based on counting the number of times an end-node of a particular byte-string is visited, while not incrementing a count for nodes storing characters in the middle of the byte-string as often as each time such nodes are visited. The result is an occurrence count metric that favors longer byte-strings, by being biased towards not incrementing the respective occurrence count values for nodes storing characters in the middle of a byte-string.
-
Citations
10 Claims
-
1. A method for creating a static dictionary, the method comprising:
-
providing a plurality of data trees, each of the plurality of data trees comprising a root node, at least one of the plurality of data trees comprising at least one child node, wherein each root node and each child node stores an associated binary pattern, wherein each child node is adapted to store a symbol associated with the child node and an occurrence count value associated with the child node; defining a binary pattern string, the binary pattern string comprising a concatenation of the binary patterns in a direct path from the root node to a particular child node, and wherein an occurrence count value for the binary pattern string is the occurrence count value of the particular child node; incrementing the occurrence count value of the particular child node when the particular child node is visited; and incrementing an occurrence count value of a node in the direct path between the root node and the particular child node less frequently than the occurrence count value of the particular child node. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A system for creating a static dictionary, comprising:
-
a processor; an element for providing a plurality of data trees, each of the plurality of data trees comprising a root node, at least one of the plurality of data trees comprising at least one child node, wherein each root node and each child node stores an associated binary pattern, wherein each child node is adapted to store a symbol associated with the child node and an occurrence count value associated with the child node; an element for defining a binary pattern string, the binary pattern string comprising a concatenation of the binary patterns in a direct path from the root node to a particular child node, and wherein an occurrence count value for the binary pattern string is the occurrence count value of the particular child node; an element for incrementing the occurrence count value of the particular child node when the particular child node is visited; and an element for incrementing an occurrence count value of a node in the direct path between the root node and the particular child node less frequently than the occurrence count value of the particular child node. - View Dependent Claims (7, 8, 9, 10)
-
Specification