US5239298A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data compression
Assignee: Nytell Software LLC
•
Filing: 1992-04-17
•
Granted: 1993-08-24
•
Expires: 2012-04-17
Abstract
Abstract Methodology and concomitant circuitry for compacting an incoming data stream into an outgoing compacted data stream utilize a multiple, doubly-linked list and an associated class promotion data structure. The incoming data stream is partitioned into a sequence of symbols. A memory associated with the data structure stores each symbol, information regarding the recency rank of each symbol as it arrives in sequence as well as class information and pointer information for each symbol. For each symbol, the memory is checked to determine if the symbol is new or repeated. If the symbol is repeated, only the recency rank is used to form that part of the outgoing data stream associated with the new symbol. If the symbol is new, identification information is added to the symbol and both the identification information are emitted as part of the compacted stream. Memory update operations are then effected to change class, recency rank and pointer information. The decoding methodology and circuitry performs the inverse to the compacting operations using the class promotion data structure.
Inventors
- 👤 Victor K. Wei
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 07:29
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/40; H03M7/42
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
270 words
A method for compressing an incoming data stream to produce an outgoing compacted data stream, the method utilizing: an associative memory; and a main memory for storing at each location a multiple-doubly-linked list including pointer information, class membership information, and recency rank information, and for storing at an associated location class pointer information, all information arranged according to a class promotion data structure, the method comprising the steps of (a) parsing the incoming data stream to generate a corresponding stream of symbols, (b) sequentially processing each symbol from said stream of symbols to determine if said each symbol is stored in the associative memory and the main memory and, if so, continuing with step (c); otherwise, invoking step (f), (c) determining a storage location of said each symbol in the main memory from the associative memory, (d) extracting the recency rank information from said storage location and propagating the recency rank information as a bit stream in the outgoing compacted data stream, (e) updating the pointer, class membership, class pointer, and recency rank information in the main memory using the class promotion data structure, and returning to step (b), (f) propagating in the outgoing compacted data stream a predetermined delimiter bit pattern, the length of said each symbol, and a bit stream representative of said each symbol, (g) entering said each symbol into the associative memory at an available location, (h) providing said available location to the main memory, (i) entering the pointer, class membership, class pointer, and recency rank information corresponding to said each symbol into the main memory corresponding to said available location, and returning to step (b).
Claim 2
Independent Claim
270 words
A method for compressing an incoming data stream to produce an outgoing compacted data stream, the method utilizing: an associative memory; and a main memory for storing at each location a multiple-doubly-linked list including pointer information, class membership information, and recency rank information, and for storing at an associated location class pointer information, all information arranged according to a class promotion data structure, the method comprising the steps of (a) parsing the incoming data stream to generate a corresponding stream of symbols, (b) sequentially processing each symbol from said stream of symbols to determine if said each symbol is stored in the associative memory and the main memory and, if so, continuing with step (c); otherwise, invoking step (f), (c) determining a storage location of said each symbol in the main memory from the associative memory, (d) extracting the recency rank information from said storage location and propagating the recency rank information as a bit stream in the outgoing compacted data stream, (e) updating the pointer, class membership, class pointer, and recency rank information in the main memory using the class promotion data structure, and returning to step (b), (f) propagating in the outgoing compacted data stream a predetermined delimiter bit pattern, the length of said each symbol, and a bit stream representative of said each symbol, (g) entering said each symbol into the associative memory at an available location, (h) providing said available location to the main memory, (i) entering the pointer, class membership, class pointer, and recency rank information corresponding to said each symbol into the main memory corresponding to said available location, and returning to step (b).
Claim 3
Independent Claim
198 words
A method for compacting an incoming data stream to generate a compacted outgoing data stream comprising the steps of parsing the incoming data stream to partition the incoming stream into a sequence of source symbols, and for each of the source symbols, determining if said each source symbol is stored in a memory having recency rank, class information and pointer information in correspondence to a class promotion data structure, if said each symbol is located in the memory, transmitting the recency rank associated with said each symbol as a segment of the compacted data stream corresponding to said each symbol, and updating the recency rank, class information and pointer information in the memory in accordance with the class promotion data structure, if said each symbol is not located in the memory, transmitting as a segment of the compacted data stream corresponding to said each symbol a data block including a predetermined delimiter, the length of said each symbol, and a preselected representation for said each symbol, storing said each symbol in an available location in the memory, and updating the recency rank, class information and pointer information in the memory in accordance with the class promotion data structure.
Claim 4
Independent Claim
198 words
A method for compacting an incoming data stream to generate a compacted outgoing data stream comprising the steps of parsing the incoming data stream to partition the incoming stream into a sequence of source symbols, and for each of the source symbols, determining if said each source symbol is stored in a memory having recency rank, class information and pointer information in correspondence to a class promotion data structure, if said each symbol is located in the memory, transmitting the recency rank associated with said each symbol as a segment of the compacted data stream corresponding to said each symbol, and updating the recency rank, class information and pointer information in the memory in accordance with the class promotion data structure, if said each symbol is not located in the memory, transmitting as a segment of the compacted data stream corresponding to said each symbol a data block including a predetermined delimiter, the length of said each symbol, and a preselected representation for said each symbol, storing said each symbol in an available location in the memory, and updating the recency rank, class information and pointer information in the memory in accordance with the class promotion data structure.
Claim 5
Dependent Claim
63 words
The method as recited in claim 2 wherein said first step of updating includes the steps of promoting said each symbol to a higher class to produce a promoted symbol, demoting the symbol previously occupying the location of said promoted symbol to a lower class to produce a demoted signal, and rearranging pointer information associated with said promoted signal and said demoted symbol.
Claim 6
Dependent Claim
36 words
The method as recited in claim 3 wherein the step of promoting said each symbol to a higher class includes the step of moving said promoted symbol to the top-most position in the next highest class.
Claim 7
Dependent Claim
52 words
The method as recited in claim 4 wherein said step of demoting the symbol previously occupying the location of said promoted symbol includes the step of pushing down in the class structure all of said symbols occupying class positions between the top-most position and the position previously occupied by said promoted symbol.
Claim 8
Dependent Claim
35 words
The method as recited in claim 3 wherein the step of promoting said each symbol to a higher class includes the step of moving said promoted symbol half-way to the top of the class structure.
Claim 9
Dependent Claim
39 words
The method as recited in claim 6 wherein said step of demoting the symbol previously occupying the location of said promoted symbol includes the step of moving said demoted symbol to the location previously occupied by the promoted symbol.
Claim 10
Dependent Claim
26 words
The method as recited in claim 3 wherein said second step of updating includes the step of rearranging the associated pointers associated with said available location.
Claim 11
Independent Claim
270 words
A method for compressing an incoming data stream to produce an outgoing compacted data stream, the method utilizing: an associative memory; and a main memory for storing at each location a multiple-doubly-linked list including pointer information, class membership information, and recency rank information, and for storing at an associated location class pointer information, all information arranged according to a move half-way to front data structure, the method comprising the steps of (a) parsing the incoming data stream to generate a corresponding stream of symbols, (b) sequentially processing each symbol from said stream of symbols to determine if said each symbol is stored in the main memory and, if so, continuing with step (c); otherwise, invoking step (f), (c) determining a storage location of said each symbol in the main memory from the associative memory, (d) extracting the recency rank information from said storage location and propagating the recency rank information as a bit stream in the outgoing compacted data stream, (e) updating the pointer, class membership, class pointer, and recency rank information in the main memory using the move half-way to front data structure, and returning to step (b), (f) propagating in the outgoing compacted data stream a predetermined delimiter bit pattern, the length of said each symbol, and a bit stream representative of said each symbol, (g) entering said each symbol into the associative memory at an available location, (h) providing said available location to the main memory, (i) entering the pointer, class membership, class pointer, and recency rank information corresponding to said each symbol into the main memory corresponding to said available location, and returning to step (b).
Claim 12
Independent Claim
270 words
A method for compressing an incoming data stream to produce an outgoing compacted data stream, the method utilizing: an associative memory; and a main memory for storing at each location a multiple-doubly-linked list including pointer information, class membership information, and recency rank information, and for storing at an associated location class pointer information, all information arranged according to a move half-way to front data structure, the method comprising the steps of (a) parsing the incoming data stream to generate a corresponding stream of symbols, (b) sequentially processing each symbol from said stream of symbols to determine if said each symbol is stored in the main memory and, if so, continuing with step (c); otherwise, invoking step (f), (c) determining a storage location of said each symbol in the main memory from the associative memory, (d) extracting the recency rank information from said storage location and propagating the recency rank information as a bit stream in the outgoing compacted data stream, (e) updating the pointer, class membership, class pointer, and recency rank information in the main memory using the move half-way to front data structure, and returning to step (b), (f) propagating in the outgoing compacted data stream a predetermined delimiter bit pattern, the length of said each symbol, and a bit stream representative of said each symbol, (g) entering said each symbol into the associative memory at an available location, (h) providing said available location to the main memory, (i) entering the pointer, class membership, class pointer, and recency rank information corresponding to said each symbol into the main memory corresponding to said available location, and returning to step (b).
Claim 13
Dependent Claim
275 words
Circuitry for compressing an incoming data stream to produce an outgoing compacted data stream comprising, an associative memory a main memory for storing at each location a multiple-doubly-linked list including pointer information, class membership information, and recency rank information, and for storing at an associated location class pointer information, all information arranged according to a class promotion data structure, means for parsing the incoming data stream to generate a corresponding stream of symbols, means for sequentially processing each symbol from said stream of symbols to determine if said each symbol is stored in the main memory, means for determining a storage location of said each symbol in the main memory from the associative memory whenever each said symbol is stored in the main memory, for extracting the recency rank information from said storage location and propagating the recency rank information as a bit stream in the outgoing compacted data stream, and for updating the pointer, class membership, class pointer, and recency rank information in the main memory using the class promotion data structure, and for reinvoking said means for processing, and means for propagating in the outgoing compacted data stream a predetermined delimiter bit pattern, the length of said each symbol, and a bit stream representative of said each symbol whenever said each symbol is not stored in main memory, for entering said each symbol into the associative memory at an available location, for providing said available location to the main memory, for entering the pointer, class membership, class pointer, and recency rank information corresponding to said each symbol into the main memory corresponding to said available location, and for reinvoking said means for processing.
Claim 14
Dependent Claim
275 words
Circuitry for compressing an incoming data stream to produce an outgoing compacted data stream comprising, an associative memory a main memory for storing at each location a multiple-doubly-linked list including pointer information, class membership information, and recency rank information, and for storing at an associated location class pointer information, all information arranged according to a class promotion data structure, means for parsing the incoming data stream to generate a corresponding stream of symbols, means for sequentially processing each symbol from said stream of symbols to determine if said each symbol is stored in the main memory, means for determining a storage location of said each symbol in the main memory from the associative memory whenever each said symbol is stored in the main memory, for extracting the recency rank information from said storage location and propagating the recency rank information as a bit stream in the outgoing compacted data stream, and for updating the pointer, class membership, class pointer, and recency rank information in the main memory using the class promotion data structure, and for reinvoking said means for processing, and means for propagating in the outgoing compacted data stream a predetermined delimiter bit pattern, the length of said each symbol, and a bit stream representative of said each symbol whenever said each symbol is not stored in main memory, for entering said each symbol into the associative memory at an available location, for providing said available location to the main memory, for entering the pointer, class membership, class pointer, and recency rank information corresponding to said each symbol into the main memory corresponding to said available location, and for reinvoking said means for processing.
Claim 15
Independent Claim
250 words
A method utilizing a memory for decoding a compacted data stream into an output data stream, the compacted data stream formed by compressing an incoming data stream partitioned into a sequence of symbols using a class promotion data structure to encode the compacted data stream, the compacted data stream having a predetermined delimiter to distinguish each new symbol from each repeated symbol, and a preselected number of data locations following the delimiter allocated to the length of the each new symbol, the memory storing at each storage location for each repeated symbol information including the symbol, recency rank information, class information, and pointer information, the method comprising steps of (a) sequentially parsing the compacted data stream to determine whether the next incoming one of said symbols is a new symbol or a repeated symbol, and if said next symbol is a new symbol, proceeding to step (c); otherwise continuing with step (b), (b) determining the storage location of said repeated symbol based on said recency rank, delivering the symbol from the memory to the output data stream, updating the memory using the class promotion data structure, and returning to step (a), and and returning to step (a), and (c) determining the length of said new symbol from the predetermined number of data locations following the delimiter, gating data from the compacted data stream to the output data stream based on the length of said new symbol, updating the memory using the class promotion data structure, and returning to step (a).
Claim 16
Independent Claim
250 words
A method utilizing a memory for decoding a compacted data stream into an output data stream, the compacted data stream formed by compressing an incoming data stream partitioned into a sequence of symbols using a class promotion data structure to encode the compacted data stream, the compacted data stream having a predetermined delimiter to distinguish each new symbol from each repeated symbol, and a preselected number of data locations following the delimiter allocated to the length of the each new symbol, the memory storing at each storage location for each repeated symbol information including the symbol, recency rank information, class information, and pointer information, the method comprising steps of (a) sequentially parsing the compacted data stream to determine whether the next incoming one of said symbols is a new symbol or a repeated symbol, and if said next symbol is a new symbol, proceeding to step (c); otherwise continuing with step (b), (b) determining the storage location of said repeated symbol based on said recency rank, delivering the symbol from the memory to the output data stream, updating the memory using the class promotion data structure, and returning to step (a), and and returning to step (a), and (c) determining the length of said new symbol from the predetermined number of data locations following the delimiter, gating data from the compacted data stream to the output data stream based on the length of said new symbol, updating the memory using the class promotion data structure, and returning to step (a).
Claim 17
Dependent Claim
252 words
Circuitry for decoding a compacted data stream into an output data stream, the compacted data stream formed by utilizing a memory to compress an incoming data stream partitioned into a sequence of symbols using a class promotion data structure to encode the compacted data stream, the compacted data stream having a predetermined delimiter to distinguish each new symbol from each repeated symbol, and a preselected number of data locations following the delimiter allocated to the length of the each new symbol, the memory storing at each storage location for each repeated symbol information including the symbol, recency rank information, class information, and pointer information, the circuitry comprising means for sequentially parsing the compacted data stream to determine whether the next incoming one of said symbols is a new symbol or a repeated symbol, means for determining the storage location of said repeated symbol based on said recency rank whenever said next symbol is a repeated symbol, for delivering the symbol from the memory to the output data stream, for updating the memory using the class promotion data structure, and for reinvoking said means for sequentially parsing, and means for determining the length of said new symbol from the predetermined number of data locations following the delimiter when said next symbol is a new symbol, for gating data from the compacted data stream to the output data stream based on the length of said new symbol, for updating the memory using the class promotion data structure, and for reinvoking said means for parsing.
Claim 18
Dependent Claim
252 words
Circuitry for decoding a compacted data stream into an output data stream, the compacted data stream formed by utilizing a memory to compress an incoming data stream partitioned into a sequence of symbols using a class promotion data structure to encode the compacted data stream, the compacted data stream having a predetermined delimiter to distinguish each new symbol from each repeated symbol, and a preselected number of data locations following the delimiter allocated to the length of the each new symbol, the memory storing at each storage location for each repeated symbol information including the symbol, recency rank information, class information, and pointer information, the circuitry comprising means for sequentially parsing the compacted data stream to determine whether the next incoming one of said symbols is a new symbol or a repeated symbol, means for determining the storage location of said repeated symbol based on said recency rank whenever said next symbol is a repeated symbol, for delivering the symbol from the memory to the output data stream, for updating the memory using the class promotion data structure, and for reinvoking said means for sequentially parsing, and means for determining the length of said new symbol from the predetermined number of data locations following the delimiter when said next symbol is a new symbol, for gating data from the compacted data stream to the output data stream based on the length of said new symbol, for updating the memory using the class promotion data structure, and for reinvoking said means for parsing.
References Cited (Backward Citations)
US4464650A
Cited
US4558302A
Cited
US4558302B1
Cited
US4796003A
Cited
US4906991A
Cited
US5087913A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-08-23 | 1997-02-22 | 1997-08-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-08-23 | 2001-02-22 | 2001-08-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-08-23 | 2005-02-22 | 2005-08-24 | $7700.00 | Window Closed / Lapsed |