Method of optimizing an N-gram memory structure
AssigneeTriada, Ltd.
InventorsTao Zhang, Joseph M. Bugajski, K. R. Raghavan
Life of this patent
Estimating the term…
Abstract
By placing a low cardinality node or a leaf in a lower level, and a high cardinality node or a leaf at a higher level, an optimal memory structure is automatically generated which yields the best compression within N-gram technology. After making an initial list of parallel streams or fields, the streams are ordered in accordance with increasing cardinality. Adjacent streams (fields), or nodes, are paired, and the children of the resulting node are eliminated from the list, while a new parent node is added to the list. The resulting new list is re-arranged from right to left as a function of increasing cardinality, and the pairing steps are repeated until a single root node is remains for the final memory structure.
Claims10
A method of organizing a multi-level memory structure having an upper root end with lower nodes and branches representative of parallel data fields to be compressed, the method comprising the steps of:
- eliminating the data fields at each lower branch or node, as the case may be, and replacing the parent node for that level with one of the lower branches or nodes in accordance with an optimality criterion;
- and
- repeating the above step until reaching the upper root end.
A method of arranging an N-gram data structure to maximize the compression thereof, the method comprising the steps of:
- (a) receiving a set of parallel data fields to be compressed;
- (b) ordering the set as a function of increasing cardinality, if not already so ordered;
- (c) comparing adjacent fields of lowest cardinality to create a new parent node;
- (d) replacing the adjacent fields with the new parent node;
- and
- (e) repeating steps (b) through (d) until only a single node remains in the set.
A method of arranging an N-gram data structure to maximize the compression thereof, the method comprising the steps of:
- (a) inputting m leaf nodes;
- (b) sorting the nodes in terms of increasing cardinality as follows:
- Cn1<Cn2<
- . . . <Cnm
- where Cn1 is the cardinality of node n-1;
- (c) pairing nodes n1 and ni to create a new parent node Ni;
- (d) exiting if i=m;
- otherwise:
- (e) comparing the cardinality of node N1i with that of ni+1 and, if the cardinality of node Ni is less than the cardinality of node ni+1:
- (i) deleting nodes n1 and ni,
- (ii) adding node N1i to the structure, and
- (iii) decrementing m, and exiting if m <2;
- otherwise:
- (iv) returning to step (b), above;
- otherwise:
- (f) pairing nodes n1 and ni+1 to create a new parent node N1i+1;
- (g) comparing the cardinality of node N1i with that of Ni+1 and, if the cardinality of node N1i is less than the cardinality of node Ni+1, repeating steps (i) to (iii) above;
- otherwise:
- (h) if i+1 is equal to m:
- (v) deleting nodes n1 and ni+1,
- (vi) adding node N1i+1 to the structure, and
- (vii) returning to step (iii), above;
- otherwise:
- (i) comparing the cardinality of node N1i+1 with that of ni+2 and, if the cardinality of node N1i+1 is less than the cardinality of node ni+2, repeating steps (v) to (vii) above, otherwise:
- (j) setting i=i+1 and returning to step (f), above.
Dependencies are inferred from the claim text.