US5966709A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of optimizing an N-gram memory structure
Assignee: RAYMOND WALSH & ENWRIGHT PC AS AGENT
•
Filing: 1997-09-26
•
Granted: 1999-10-12
•
Expires: 2017-09-26
Abstract
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.
Inventors
- 👤 Tao Zhang
- 👤 Joseph M. Bugajski
- 👤 K. R. Raghavan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 22:33
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
80 words
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.
Claim 2
Independent Claim
80 words
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.
Claim 3
Dependent Claim
11 words
The method of claim 1, wherein the optimality criterion is entropy.
Claim 4
Dependent Claim
14 words
The method of claim 1, wherein the optimality criterion is based upon correlation coefficients.
Claim 5
Dependent Claim
14 words
The method of claim 1, wherein the optimality criterion is based upon mutual information.
Claim 6
Dependent Claim
11 words
The method of claim 1, wherein the optimality criterion is cardinality.
Claim 7
Dependent Claim
35 words
The method of claim 5, further including the step of ordering the data fields as a function of increasing cardinality prior to the step of replacing the data fields each time the step is performed.
Claim 8
Dependent Claim
27 words
The method of claim 1, wherein the multi-level memory structure is a binary tree structure, and wherein the data fields at each level are adjacent data fields.
Claim 9
Independent Claim
84 words
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.
Claim 10
Independent Claim
84 words
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.
Claim 11
Dependent Claim
63 words
The method of claim 8, wherein step (c) further includes that steps of: (i) pairing the nodes of lowest cardinality; (ii) pairing the result of (i) with the node of next greater cardinality; (iii) comparing the results of(i) and (ii); and (iv) discontinue the process if the result of (i) has less cardinality than that of (ii), otherwise, retain the result of (ii).
Claim 12
Independent Claim
238 words
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.
Claim 13
Independent Claim
238 words
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.
References Cited (Backward Citations)
US4853696A
Cited
US5274805A
Cited
US5245337A
Cited
US5293164A
Cited
US5592667A
Cited
US5533148A
Cited
US5694591A
Cited
US5781906A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-10-11 | 2003-04-12 | 2003-10-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-10-11 | 2007-04-12 | 2007-10-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-10-11 | 2011-04-12 | 2011-10-12 | $7700.00 | Window Closed / Lapsed |