Patent US5748955A successfully refreshed from Google Patents.
US5748955A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Stream data compression system using dynamic connection groups
Assignee: Individual
•
Filing: 1994-12-20
•
Granted: 1998-05-05
•
Expires: 2014-12-20
Abstract
Abstract A generalized system for compression of data such as text or images. Compression is achieved by identifying new connections between consecutive data units, existing connections or both. A representation of each new connection is then used to replace the consecutive items throughout the data, which are typically considered in pairs. A hierarchical connection structure resembling a tree is built up as data is received, so that the effectiveness of compression increases with time. After each session of data reception, the initially compressed data may be reorganized with new connections being identified and stored in an index for future use, while also further compressing the existing data.
Inventors
- 👤 Rodney J. Smith
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 19:15
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
255 words
A method of compressing data by computer, in which connection groups of two or more consecutive data units are identified and recorded as compression proceeds, comprising: receiving a stream of data units to be compressed, with no predetermined variety of data unit having significance as a delimiter of other data units, storing a record of each received data unit in a processing block of computer memory, determining whether each received data unit forms an already identified connection group existing in an index block of computer memory, when considered in relation to any immediately preceding data unit or connection group recorded in said processing block, storing in said processing block a fresh record of any such already identified connection group formed by said received data unit, in place of said received data unit and said immediately preceding data unit or connection group recorded in said processing block, determining whether each connection group freshly recorded in said processing block forms a larger already identified connection group existing in said index block, when considered in relation to any respective immediately preceding data unit or connection group recorded in said processing block, storing a further fresh record of any such larger already identified connection group, in place of said connection group freshly recorded in said processing block and said respective immediately preceding data unit or connection group recorded in said processing block, delivering the records stored in said processing block for further storage or for transmission as required, once said stream of data units has been received and compressed.
Claim 2
Independent Claim
255 words
A method of compressing data by computer, in which connection groups of two or more consecutive data units are identified and recorded as compression proceeds, comprising: receiving a stream of data units to be compressed, with no predetermined variety of data unit having significance as a delimiter of other data units, storing a record of each received data unit in a processing block of computer memory, determining whether each received data unit forms an already identified connection group existing in an index block of computer memory, when considered in relation to any immediately preceding data unit or connection group recorded in said processing block, storing in said processing block a fresh record of any such already identified connection group formed by said received data unit, in place of said received data unit and said immediately preceding data unit or connection group recorded in said processing block, determining whether each connection group freshly recorded in said processing block forms a larger already identified connection group existing in said index block, when considered in relation to any respective immediately preceding data unit or connection group recorded in said processing block, storing a further fresh record of any such larger already identified connection group, in place of said connection group freshly recorded in said processing block and said respective immediately preceding data unit or connection group recorded in said processing block, delivering the records stored in said processing block for further storage or for transmission as required, once said stream of data units has been received and compressed.
Claim 3
Dependent Claim
118 words
A method according to claim 1, in which at least one data stream has been received and stored, further comprising: determining a number of occurrences of at least one pair of consecutive records in said received data, determining whether the number of occurrences of said at least one pair of consecutive records exceeds a threshold number, storing in said index block a record of a new connection group for any such pair of consecutive records in said received data having a number of occurrences greater than said threshold number, storing in said received data a record of said new connection group in place of each occurrence of said consecutive pair of records which said new connection group represents.
Claim 4
Dependent Claim
34 words
A method according to claim 2, comprising, repeatedly, storing records of connection groups representing consecutive pairs of records having at least the threshold number of occurrences, until no further such pairs can be found.
Claim 5
Dependent Claim
45 words
A method of compressing data according to claim 1, further comprising: determining whether each received data unit exists in a values block of already identified data units or is a new data unit, storing a record of each new data unit in said values block.
Claim 6
Dependent Claim
16 words
A method according to claim 1 wherein the data units are of a substantially uniform length.
Claim 7
Dependent Claim
15 words
A method according to claim 5 wherein the data units are characters or image pixels.
Claim 8
Independent Claim
399 words
A method of compressing data by computer, comprising, repeatedly, receiving a new data stream and storing an initially compressed data stream wherein connection groups of two or more consecutive data units are identified and recorded as compression proceeds by performing the steps of: receiving a stream of data units to be compressed, with no predetermined variety of data unit having significance as a delimiter of other data units, storing a record of each received data unit in a processing block of computer memory, determining whether each received data unit forms an already identified connection group existing in an index block of computer memory, when considered in relation to any preceding data unit or connection group recorded in said processing block, storing in said processing block a fresh record of any such already identified connection group formed by said received data unit, in place of said received data unit and said immediately preceding data unit or connection group recorded in said processing block, determining whether each connection group freshly recorded in said processing block forms a larger already identified connection group existing in said index block, when considered in relation to any respective immediately preceding data unit or connection group recorded in said processing block, storing a further fresh record of any such larger already identified connection group, in place of said connection group freshly recorded in said processing block and said respective immediately preceding data unit or connection group recorded in said processing block, delivering the records stored in said processing block for further storage or for transmission as required, once said stream of data units has been received and compressed, and reorganizing said initially compressed data stream by creating and storing new connection groups wherein at least one data stream has been received and stored by performing the steps of: determining a number of occurrence of at least one pair of consecutive records in said received data, determining whether the number of occurrences of said at least one pair of consecutive records exceeds a threshold number, storing in said index block a record of a new connection group for any such pair of consecutive records in said received data having a number of occurrences greater than said threshold number, storing in said received data a record of said new connection group in place of each occurrence of said consecutive pair of records which said new connection group represents.
Claim 9
Independent Claim
399 words
A method of compressing data by computer, comprising, repeatedly, receiving a new data stream and storing an initially compressed data stream wherein connection groups of two or more consecutive data units are identified and recorded as compression proceeds by performing the steps of: receiving a stream of data units to be compressed, with no predetermined variety of data unit having significance as a delimiter of other data units, storing a record of each received data unit in a processing block of computer memory, determining whether each received data unit forms an already identified connection group existing in an index block of computer memory, when considered in relation to any preceding data unit or connection group recorded in said processing block, storing in said processing block a fresh record of any such already identified connection group formed by said received data unit, in place of said received data unit and said immediately preceding data unit or connection group recorded in said processing block, determining whether each connection group freshly recorded in said processing block forms a larger already identified connection group existing in said index block, when considered in relation to any respective immediately preceding data unit or connection group recorded in said processing block, storing a further fresh record of any such larger already identified connection group, in place of said connection group freshly recorded in said processing block and said respective immediately preceding data unit or connection group recorded in said processing block, delivering the records stored in said processing block for further storage or for transmission as required, once said stream of data units has been received and compressed, and reorganizing said initially compressed data stream by creating and storing new connection groups wherein at least one data stream has been received and stored by performing the steps of: determining a number of occurrence of at least one pair of consecutive records in said received data, determining whether the number of occurrences of said at least one pair of consecutive records exceeds a threshold number, storing in said index block a record of a new connection group for any such pair of consecutive records in said received data having a number of occurrences greater than said threshold number, storing in said received data a record of said new connection group in place of each occurrence of said consecutive pair of records which said new connection group represents.
Claim 10
Dependent Claim
111 words
A structure in computer memory, comprising a plurality of records of data units and a plurality of records of connections, wherein: each record of a data unit represents the respective data unit, and the presence or absence of a chain of records of connections in which the data unit is represented, and each record of a connection represents a respective connection relationship between two data units, two connection relationships, and data unit and a connection relationship, or a connection relationship and a data unit, and the presence or absence of a chain of records of connections in which the respective connection relationship is in turn represented as part of further relationships.
Claim 11
Dependent Claim
111 words
A structure in computer memory, comprising a plurality of records of data units and a plurality of records of connections, wherein: each record of a data unit represents the respective data unit, and the presence or absence of a chain of records of connections in which the data unit is represented, and each record of a connection represents a respective connection relationship between two data units, two connection relationships, and data unit and a connection relationship, or a connection relationship and a data unit, and the presence or absence of a chain of records of connections in which the respective connection relationship is in turn represented as part of further relationships.
Claim 12
Dependent Claim
40 words
A structure according to claim 8, wherein each record of a connection has primary and secondary components which represent the two data units, the two connection relationships, the data unit and connection relationship, or the connection relationship and data unit.
Claim 13
Dependent Claim
41 words
A structure according to claim 9, wherein each record of a connection has a further component which represents the presence or absence of another record of a connection having a primary component in common with said each record of a connection.
Claim 14
Dependent Claim
40 words
A structure according to claim 9, wherein each record of a connection has a further component which represents the presence or absence of another record of a connection having a primary component which represents said each record of a connection.
Claim 15
Dependent Claim
39 words
A structure according to claim 9, wherein each said chain of records of connections in which the data unit is represented contains every such record of a connection in which the data unit is represented as the primary component.
Claim 16
Dependent Claim
40 words
A structure according to claim 9, wherein each said chain of records of connections in which the respective connection relationship is represented contains every such record of a connection in which the connection relationship is represented as the primary component.
Claim 17
Dependent Claim
28 words
A structure according to claim 9, wherein the primary and secondary components of each record of a connection are related by their consecutive occurrence in a data stream.
Claim 18
Dependent Claim
14 words
Computer apparatus containing program instructions which create a data structure according to claim 8.
Claim 19
Independent Claim
204 words
A method of compressing a data stream, in which a groups of data units are replaced by connection representations from an existing data structure, including the steps of: (a) storing a newly received data unit in a processing array which has already received at least one data unit, (b) searching the data structure for a connection representation to replace the newly received data unit and a preceding data unit or preceding connection representation in the array, (c) storing the connection representation in the array if located in (b) as a replacement for the newly received data unit and the preceding data unit or connection representation as the case may be, (d) searching the data structure for a further connection representation to replace the newly stored connection representation in (c) and a respective preceding data unit or preceding connection representation in the array, (e) storing the further connection representation in the array if located in (d), as a replacement for said newly stored connection representation and said respective preceding data unit or preceding connection representation in the array, (f) repeating steps (d) to (e) until no further connection representation is located, and (g) repeating steps (a) to (f) until no further data unit is received.
Claim 20
Independent Claim
204 words
A method of compressing a data stream, in which a groups of data units are replaced by connection representations from an existing data structure, including the steps of: (a) storing a newly received data unit in a processing array which has already received at least one data unit, (b) searching the data structure for a connection representation to replace the newly received data unit and a preceding data unit or preceding connection representation in the array, (c) storing the connection representation in the array if located in (b) as a replacement for the newly received data unit and the preceding data unit or connection representation as the case may be, (d) searching the data structure for a further connection representation to replace the newly stored connection representation in (c) and a respective preceding data unit or preceding connection representation in the array, (e) storing the further connection representation in the array if located in (d), as a replacement for said newly stored connection representation and said respective preceding data unit or preceding connection representation in the array, (f) repeating steps (d) to (e) until no further connection representation is located, and (g) repeating steps (a) to (f) until no further data unit is received.
Claim 21
Dependent Claim
94 words
A method according to claim 16 further including the steps of: (h) scanning the data stream which has been compressed according to steps (a) to (g) to determine the number of occurrences of each consecutive data unit pair, connection representation pair, data unit and connection representation pair, or connection representation and data unit pair, (i) storing a new connection representation in the data stream to replace each pair determined in (h) for which the number of occurrences is greater than a threshold number, and (j) storing each new connection representation in the data structure.
Claim 22
Dependent Claim
22 words
A method according to claim 16 wherein no predetermined variety of data unit has significance as a delimiter of other data units.
Claim 23
Dependent Claim
13 words
Computer apparatus containing program instructions which implement a method according to claim 16.
References Cited (Backward Citations)
US4491934A
Cited
WO1988009586A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-04 | 2001-11-03 | 2002-05-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-04 | 2005-11-03 | 2006-05-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-04 | 2009-11-03 | 2010-05-05 | $7700.00 | Window Closed / Lapsed |