US5455577A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for data compression
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1993-03-12
•
Granted: 1995-10-03
•
Expires: 2013-03-12
Abstract
Abstract A method and system for compressing a stream of bytes in a compression system. The compression system has a search data structure containing slots for identifying the position of occurrences of byte sequences in an input stream. A byte sequence is retrieved from the input stream. The method then determines whether the search data structure contains a slot identifying the position of a byte sequence that matches the retrieved byte sequence. If the search data structure contains a slot which identifies a matching byte sequence, then the contents of a search data structure slot containing the match is replaced with the position of the retrieved byte sequence. If the search data structure does not contain a slot identifying a matching byte sequence, then a slot is selected using a least recently updated slot algorithm. The contents of this least recently updated slot are then replaced with the position of the retrieved byte sequence. When a matching byte sequence is determined, an indicator of the position identified in the slot before replacement is output. If no matching byte sequence is determined, then a byte of the retrieved byte sequence is output.
Inventors
- 👤 Benjamin W. Slivka
- 👤 Richard F. Rashid
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 07:26
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3086; G; G06; G06T; G06T9/00; G06T9/005
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
193 words
A method of compressing a stream of bytes in a compression system, each byte having a position within the stream, the compression system having a search data structure containing an entry for each byte value, each entry having a plurality of slots, each slot for identifying the position of an occurrence of a byte sequence, the method comprising the steps of: retrieving a byte sequence from the stream; determining whether the search data structure contains a slot identifying the position of a byte sequence that matches the retrieved byte sequence by selecting an entry corresponding to one of the byte values in the retrieved byte sequence, and by searching the slots of the selected entry to determine whether the byte sequence identified by the slot matches the retrieved byte sequence, when the search data structure contains such a slot, replacing the position contained in the slot with the position of the retrieved byte sequence; and when the search data structure does not contain such a slot, selecting a least recently updated slot of the selected entry and replacing the position contained in the selected slot with the position of the retrieved byte sequence.
Claim 2
Independent Claim
193 words
A method of compressing a stream of bytes in a compression system, each byte having a position within the stream, the compression system having a search data structure containing an entry for each byte value, each entry having a plurality of slots, each slot for identifying the position of an occurrence of a byte sequence, the method comprising the steps of: retrieving a byte sequence from the stream; determining whether the search data structure contains a slot identifying the position of a byte sequence that matches the retrieved byte sequence by selecting an entry corresponding to one of the byte values in the retrieved byte sequence, and by searching the slots of the selected entry to determine whether the byte sequence identified by the slot matches the retrieved byte sequence, when the search data structure contains such a slot, replacing the position contained in the slot with the position of the retrieved byte sequence; and when the search data structure does not contain such a slot, selecting a least recently updated slot of the selected entry and replacing the position contained in the selected slot with the position of the retrieved byte sequence.
Claim 3
Dependent Claim
69 words
The method of claim 1 wherein the compression system includes a least recently updated data structure, the least recently updated data structure having an entry corresponding to each entry of the search data structure, and including the additional step of when the search data structure does not contain such a slot, updating the corresponding entry of the least recently updated data structure to identify the least recently updated slot.
Claim 4
Independent Claim
153 words
A method of compressing a stream of bytes in a compression system, each byte having a position within the stream, the compression system having a search data structure with slots for identifying the position of occurrences of byte sequences, the method comprising the steps of: retrieving a byte sequence from the stream; determining whether the search data structure contains a slot identifying the position of a byte sequence that matches the retrieved byte sequence; When the search data structure contains such a slot, replacing the position contained in the slot with the position of the retrieved byte sequence and outputting an indicator of the position identified in the slot; and when the search data structure does not contain such a slot, selecting a least recently updated slot and replacing the position contained in the selected slot with the position of the retrieved byte sequence and outputting a byte of the retrieved byte sequence.
Claim 5
Independent Claim
153 words
A method of compressing a stream of bytes in a compression system, each byte having a position within the stream, the compression system having a search data structure with slots for identifying the position of occurrences of byte sequences, the method comprising the steps of: retrieving a byte sequence from the stream; determining whether the search data structure contains a slot identifying the position of a byte sequence that matches the retrieved byte sequence; When the search data structure contains such a slot, replacing the position contained in the slot with the position of the retrieved byte sequence and outputting an indicator of the position identified in the slot; and when the search data structure does not contain such a slot, selecting a least recently updated slot and replacing the position contained in the selected slot with the position of the retrieved byte sequence and outputting a byte of the retrieved byte sequence.
Claim 6
Independent Claim
175 words
A method in a compression system of compressing a stream of bytes, each byte having a position within the stream, the compression system having a search data structure with slots for identifying the position of occurrences of byte sequences, the method comprising the steps of: retrieving a byte sequence from the stream; determining whether the search data structure contains a slot identifying the position of a byte sequence that matches the retrieved byte sequence; and when the search data structure contains such a slot, when the offset between the position contained in the slot and the position of the retrieved byte sequence is greater than a maximum allowable offset, selecting a least recently updated slot and replacing the position contained in the selected slot with the position of the retrieved byte sequence; and when the offset between the position contained in the slot and the position of the retrieved byte sequence is not greater than a maximum allowable offset, replacing the position contained in the identifying slot with the position of the retrieved byte sequence.
Claim 7
Independent Claim
175 words
A method in a compression system of compressing a stream of bytes, each byte having a position within the stream, the compression system having a search data structure with slots for identifying the position of occurrences of byte sequences, the method comprising the steps of: retrieving a byte sequence from the stream; determining whether the search data structure contains a slot identifying the position of a byte sequence that matches the retrieved byte sequence; and when the search data structure contains such a slot, when the offset between the position contained in the slot and the position of the retrieved byte sequence is greater than a maximum allowable offset, selecting a least recently updated slot and replacing the position contained in the selected slot with the position of the retrieved byte sequence; and when the offset between the position contained in the slot and the position of the retrieved byte sequence is not greater than a maximum allowable offset, replacing the position contained in the identifying slot with the position of the retrieved byte sequence.
Claim 8
Dependent Claim
43 words
The method of claim 4 including the step of when the search data structure does not contain such a slot, selecting a least recently updated slot and replacing the position contained in the selected slot with the position of the retrieved byte sequence.
Claim 9
Dependent Claim
51 words
The method of claim 4 or 5 including the steps of: when replacing the position contained in the selected slot, outputting a byte of the retrieved byte sequence; and when replacing the position contained in the identifying slot, outputting an indicator of the position identified in the slot before being replaced.
Claim 10
Independent Claim
177 words
A method in a data compression system for identifying a previously occurring matching string in an input stream, the previously occurring strings being identified by an identifier and comprising a plurality of characters, the data compression system having a search data structure with a search entry for each possible character, each search entry having a plurality of slots, each slot having an identifier, the method comprising the steps of: determining whether an identifier identifies a previously occurring string that matches a current string by searching the search entry in the search data structure corresponding to a character of the current string for a slot that contains such an identifier; when a slot containing the identifier of a matching string is found, replacing the identifier with an identifier of the current string; and when a slot containing the identifier of a matching string is not found, replacing the identifier, in a slot of the search entry corresponding to a character of the current string, that identifies a least recently occurring string with an identifier of the current string.
Claim 11
Independent Claim
177 words
A method in a data compression system for identifying a previously occurring matching string in an input stream, the previously occurring strings being identified by an identifier and comprising a plurality of characters, the data compression system having a search data structure with a search entry for each possible character, each search entry having a plurality of slots, each slot having an identifier, the method comprising the steps of: determining whether an identifier identifies a previously occurring string that matches a current string by searching the search entry in the search data structure corresponding to a character of the current string for a slot that contains such an identifier; when a slot containing the identifier of a matching string is found, replacing the identifier with an identifier of the current string; and when a slot containing the identifier of a matching string is not found, replacing the identifier, in a slot of the search entry corresponding to a character of the current string, that identifies a least recently occurring string with an identifier of the current string.
Claim 12
Dependent Claim
36 words
The method of claim 11 including the step of maintaining a least recently updated (LRU) direct access table with an LRU entry containing an indicator of the least recently updated slot in the corresponding search entry.
Claim 13
Independent Claim
142 words
A method of compressing a stream of bytes in a compression system, each byte having a position within the stream, the compression system having a search data structure with slots for identifying the position of occurrences of byte sequences, the method comprising the steps of: retrieving a byte sequence from the stream; determining whether the search data structure contains a slot identifying the position of a byte sequence that matches the retrieved byte sequence; when the search data structure contains such a slot, replacing the position contained in the slot with the position of the retrieved byte sequence; and when the search data structure does not contain such a slot, selecting a least recently updated slot by selecting the slot with the smallest position value and replacing the position contained in the selected slot with the position of the retrieved byte sequence.
Claim 14
Independent Claim
142 words
A method of compressing a stream of bytes in a compression system, each byte having a position within the stream, the compression system having a search data structure with slots for identifying the position of occurrences of byte sequences, the method comprising the steps of: retrieving a byte sequence from the stream; determining whether the search data structure contains a slot identifying the position of a byte sequence that matches the retrieved byte sequence; when the search data structure contains such a slot, replacing the position contained in the slot with the position of the retrieved byte sequence; and when the search data structure does not contain such a slot, selecting a least recently updated slot by selecting the slot with the smallest position value and replacing the position contained in the selected slot with the position of the retrieved byte sequence.
Claim 15
Dependent Claim
38 words
The method of claim 1 wherein the number of slots comprising each entry is determined by the expected frequency that the byte value used to determine the selection of an entry will occur in a stream of bytes.
Claim 16
Dependent Claim
15 words
The method of claim 1 wherein the number of slots comprising each entry is eight.
Claim 17
Dependent Claim
62 words
The method of claim 1 wherein the step of selecting an entry corresponding to one of the byte values is performed using the first byte in the retrieved byte sequence as an index corresponding to an entry and the step of searching the slots is performed using the second byte in the retrieved byte sequence as an index corresponding to a slot.
References Cited (Backward Citations)
US4021782A
Cited
US4464650A
Cited
US4814746A
Cited
US4701745A
Cited
US4730348A
Cited
US4906991A
Cited
US5016009A
Cited
US5155484A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-10-02 | 1999-04-03 | 1999-10-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-10-02 | 2003-04-03 | 2003-10-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-10-02 | 2007-04-03 | 2007-10-03 | $7700.00 | Window Closed / Lapsed |