US5977890A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for data compression utilizing efficient pattern discovery
Assignee: International Business Machines Corp
•
Filing: 1998-02-13
•
Granted: 1999-11-02
•
Expires: 2018-02-13
Abstract
Abstract The method of the present invention discovers patterns in an sequence of characters in two phases. In a sampling phase, preferably proper templates corresponding to the sequence of characters are generated. Patterns are then generated corresponding to the templates and stored in memory. In a convolution phase, the patterns stored in memory are combined to identify a set of maximal patterns. A subset of the maximal patterns is selected. Compressed data representing the sequence of characters is generated. The compressed data includes first data data representing each selected pattern of the subset, and second data representing the sequence of characters wherein occurrences of each selected pattern within the sequence of characters is replaced by a reference to first data corresponding to the selected pattern. The method is useful in compressing information stored in a database or compressing information communicated over a communication link.
Inventors
- 👤 Isidore Rigoutsos
- 👤 Aristidis Floratos
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 00:18
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 48
Claim 1
Independent Claim
174 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for compression of a sequence of characters, said method steps comprising: identifying a set of proper templates; identifying a first set of patterns based on said set of proper templates and said sequence of characters, wherein each pattern within said first set of patterns is contained within said sequence of characters; and combining patterns within said first set of patterns to form a second set of patterns, wherein each pattern within said second set of patterns is contained within said sequence of characters; selecting a subset of said second set of patterns; and generating compressed data representing said sequence of characters, said compressed data comprising first data and second data, said first data representing each selected pattern of said subset, and second data representing said sequence of characters wherein occurrences of each selected pattern within said sequence of characters is replaced by a reference to first data corresponding to the selected pattern.
Claim 2
Dependent Claim
174 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for compression of a sequence of characters, said method steps comprising: identifying a set of proper templates; identifying a first set of patterns based on said set of proper templates and said sequence of characters, wherein each pattern within said first set of patterns is contained within said sequence of characters; and combining patterns within said first set of patterns to form a second set of patterns, wherein each pattern within said second set of patterns is contained within said sequence of characters; selecting a subset of said second set of patterns; and generating compressed data representing said sequence of characters, said compressed data comprising first data and second data, said first data representing each selected pattern of said subset, and second data representing said sequence of characters wherein occurrences of each selected pattern within said sequence of characters is replaced by a reference to first data corresponding to the selected pattern.
Claim 3
Dependent Claim
31 words
The program storage device of claim 1, wherein said sequence of characters comprise data stored in a database, and said method steps further comprise storing said compressed data in said database.
Claim 4
Dependent Claim
57 words
The program storage device of claim 1, wherein said sequence of characters comprise data that is to be communicated from a first network device to a second network device over a communication link, and said method steps further comprise communicating said compressed data from said first network device to said second network device over said communication network.
Claim 5
Dependent Claim
15 words
The program storage device of claim 1, wherein said second set of patterns is non-redundant.
Claim 6
Dependent Claim
26 words
The program storage device of claim 1, wherein said second set of patterns comprise a set of all non-redundant patterns contained within said sequence of characters.
Claim 7
Dependent Claim
20 words
The program storage device of claim 1, wherein each pattern within said second set of patterns satisfies a predetermined criterion.
Claim 8
Dependent Claim
25 words
The program storage device of claim 6, wherein said predetermined criterion comprises one of a minimum number of occurrences and a maximum number of occurrences.
Claim 9
Dependent Claim
21 words
The program storage device of claim 6, wherein said predetermined criterion comprises one of a minimum length and a maximum length.
Claim 10
Dependent Claim
28 words
The program storage device of claim 1, further comprising the step of reporting a subset of said second set of patterns to a user via an input/output device.
Claim 11
Dependent Claim
30 words
The program storage device of claim 1, wherein each template within said proper set of proper templates is defined by data representing a sequence of characters over an alphabet {0,1}.
Claim 12
Dependent Claim
22 words
The program storage device of claim 1, wherein each pattern is associated with a first field that identifies characters of said pattern.
Claim 13
Dependent Claim
40 words
The program storage device of claim 1, wherein each pattern is associated with a an offset list that comprises a set of offset identifiers each identifying offset of an occurrence of characters of said pattern within said sequence of characters.
Claim 14
Dependent Claim
25 words
The program storage device of claim 1, wherein convolvable patterns within said first set of patterns are combined to form said second set of patterns.
Claim 15
Dependent Claim
49 words
The program storage device of claim 13, further comprising the step of identifying a third set of patterns within said second set of patterns, wherein each pattern within said third set satisfies a predetermined criterion, and wherein the selecting step selects a subset of said third set of patterns.
Claim 16
Dependent Claim
44 words
The program storage device of claim 14, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that number of occurrences of said pattern P within said sequence of characters is greater than a predetermined minimum number of occurrences.
Claim 17
Dependent Claim
44 words
The program storage device of claim 14, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that number of occurrences of said pattern P within said sequence of characters is less than a predetermined maximum number of occurrences.
Claim 18
Dependent Claim
35 words
The program storage device of claim 14, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that said pattern P has a length greater than a predetermined minimum length.
Claim 19
Dependent Claim
34 words
The program storage device of claim 14, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that said pattern has a length less than a predetermined maximum length.
Claim 20
Dependent Claim
25 words
The program storage device of claim 14, further comprising the step of reporting said third set of patterns to a user via an input/output device.
Claim 21
Dependent Claim
32 words
The program storage device of claim 14, wherein patterns within said first set of patterns that are convolvable under the operator ⊕ R are combined to form said second set of patterns.
Claim 22
Dependent Claim
42 words
The program storage device of claim 14, further comprising the step of identifying a value L, and wherein patterns within said first set of patterns that are convolvable under the operator ⊕ L-1 are combined to form said second set of patterns.
Claim 23
Dependent Claim
157 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for compression of a sequence of characters, said method steps comprising: identifying a first set of patterns, wherein each pattern within said first set of patterns is contained within said sequence of characters; and combining convolvable patterns within said first set of patterns to form a second set of patterns, wherein each pattern within said second set of patterns is contained within said sequence of characters; selecting a subset of said second set of patterns; and generating compressed data representing said sequence of characters, said compressed data comprising first data and second data, said first data representing each selected pattern of said subset, and second data representing said sequence of characters wherein occurrences of each selected pattern within said sequence of characters is replaced by a reference to first data corresponding to the selected pattern.
Claim 24
Dependent Claim
157 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for compression of a sequence of characters, said method steps comprising: identifying a first set of patterns, wherein each pattern within said first set of patterns is contained within said sequence of characters; and combining convolvable patterns within said first set of patterns to form a second set of patterns, wherein each pattern within said second set of patterns is contained within said sequence of characters; selecting a subset of said second set of patterns; and generating compressed data representing said sequence of characters, said compressed data comprising first data and second data, said first data representing each selected pattern of said subset, and second data representing said sequence of characters wherein occurrences of each selected pattern within said sequence of characters is replaced by a reference to first data corresponding to the selected pattern.
Claim 25
Dependent Claim
31 words
The program storage device of claim 22, wherein said sequence of characters comprise data stored in a database, and said method steps further comprise storing said compressed data in said database.
Claim 26
Dependent Claim
57 words
The program storage device of claim 22, wherein said sequence of characters comprise data that is to be communicated from a first network device to a second network device over a communication link, and said method steps further comprise communicating said compressed data from said first network device to said second network device over said communication network.
Claim 27
Dependent Claim
49 words
The program storage device of claim 22, further comprising the step of: identifying a third set of patterns within said second set of patterns, wherein each pattern within said third set satisfies a predetermined criterion, and wherein the selecting step selects a subset of said third set of patterns.
Claim 28
Dependent Claim
44 words
The program storage device of claim 25, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that number of occurrences of said pattern P within said sequence of characters is greater than a predetermined minimum number of occurrences.
Claim 29
Dependent Claim
44 words
The program storage device of claim 25, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that number of occurrences of said pattern P within said sequence of characters is less than a predetermined maximum number of occurrences.
Claim 30
Dependent Claim
35 words
The program storage device of claim 25, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that said pattern P has a length greater than a predetermined minimum length.
Claim 31
Dependent Claim
34 words
The program storage device of claim 25, wherein, for each pattern P within said third set of patterns, said predetermined criterion requires that said pattern has a length less than a predetermined maximum length.
Claim 32
Dependent Claim
25 words
The program storage device of claim 25, further comprising the step of reporting said third set of patterns to a user via an input/output device.
Claim 33
Dependent Claim
22 words
The program storage device of claim 22, wherein the combining step combines patterns that are convolvable under the operator ⊕ R .
Claim 34
Dependent Claim
150 words
The program storage device of claim 31, further comprising the steps of: i) storing at least one pattern belonging to said first set of patterns in a stack; ii) selecting a pattern P stored in a top entry of said stack; iii) identifying a set Q of patterns, wherein each pattern within said set Q is convolvable with said pattern P under said operator ⊕ R ; iv) ordering said set Q of patterns according to a predetermined ordering scheme; v) traversing through said ordered set of patterns and determining whether a given pattern within said set of ordered patterns satisfies a first predetermined criterion; and vi) if said given pattern satisfies said first predetermined criterion, combining said given pattern with said pattern P to form a combined pattern, storing said combined pattern as a top entry in said stack, and returning to step ii) to process said combined pattern.
Claim 35
Dependent Claim
26 words
The program storage device of claim 32, wherein said first predetermined criterion comprises one of a minimum number of occurrences and a maximum number of occurrences.
Claim 36
Dependent Claim
63 words
The program storage device of claim 33, wherein each pattern is associated with an offset list that comprises a set of offset identifiers each identifying offset of an occurrence of said characters of said pattern within said sequence of characters; and wherein number of occurrences of a pattern is determined by number of offset identifiers in said offset list associated with said pattern.
Claim 37
Dependent Claim
22 words
The program storage device of claim 32, wherein said first predetermined criterion comprises one of a minimum length and a maximum length.
Claim 38
Dependent Claim
42 words
The program storage device of claim 35, wherein each pattern is associated with a first field that identifies characters of said pattern; wherein length of a pattern is determined by calculating number of characters in said first field associated with said pattern.
Claim 39
Dependent Claim
110 words
The program storage device of claim 32, wherein each pattern is associated with a first field that identifies characters of said pattern and is associated with an offset list that comprises a set of offset identifiers each identifying offset of an occurrence of said characters of said pattern within said sequence of characters; and wherein, for a combined pattern corresponding to patterns P1 and Q1, said first field identifies characters of said patterns P1 and Q1 that make up said combined pattern, and said offset list comprises a set of offset identifiers each identifying offset of an occurrence of said characters of said combined pattern within said sequence of characters.
Claim 40
Dependent Claim
82 words
The program storage device of claim 32, further comprising the steps of: vi) if the set of ordered patterns is empty or no pattern within the ordered set of patterns satisfies said first predetermined matching criterion, adding pattern P to said third set of patterns if pattern P satisfies a second predetermined criterion, removing the entry corresponding to the pattern P from the stack, and returning to step ii) to process the top entry of the stack until the stack is empty.
Claim 41
Dependent Claim
29 words
The program storage device of claim 35, wherein, for each pattern P' within said third set of patterns, said second predetermined criterion requires that said pattern P' is maximal.
Claim 42
Dependent Claim
30 words
The program storage device of claim 32, wherein, in step iv), said predetermined ordering scheme orders said set Q of patterns such that maximal patterns are generated before non-maximal patterns.
Claim 43
Dependent Claim
23 words
The program storage device of claim 40, wherein said predetermined ordering scheme orders said set Q of patterns according to a prefix relation.
Claim 44
Dependent Claim
27 words
The program storage device of claim 41, wherein said prefix relation dictates that any pattern P1 is listed before any other pattern Q1 when P1≦ pf Q1.
Claim 45
Dependent Claim
23 words
The program storage device of claim 40, wherein said predetermined ordering scheme orders said set Q of patterns according to a suffix relation.
Claim 46
Dependent Claim
28 words
The program storage device of claim 43, wherein said suffix relation dictates that any pattern P1 is listed before any other pattern Q1 when P1 ≦ sf Q1.
Claim 47
Dependent Claim
52 words
The program storage device of claim 22, wherein said first set of patterns are identified by: identifying a set of templates; identifying a set of patterns based on said set of templates and said sequence of characters, wherein each pattern within said set of patterns is contained within said sequence of characters.
Claim 48
Dependent Claim
19 words
The program storage device of claim 45, wherein each template within said set of templates is a proper template.
References Cited (Backward Citations)
US4814746A
Cited
US5111415A
Cited
US5469161A
Cited
US5282194A
Cited
US5383142A
Cited
US5570306A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-01 | 2003-05-03 | 2003-11-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-01 | 2007-05-03 | 2007-11-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-01 | 2011-05-03 | 2011-11-02 | $7700.00 | Window Closed / Lapsed |