Patent US2459039A successfully refreshed from Google Patents.
US5572206A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data compression method and system
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1994-07-06
•
Granted: 1996-11-05
•
Expires: 2014-07-06
Abstract
Abstract A method and system for compressing an input stream of data bytes into a compressed stream of data bytes using an LZ77-based compression scheme. The method and system also includes a decompressor for decompressing the compressed stream into a decompressed stream of data bytes that is identical to the input stream. The compression system encodes matches using token offsets rather than the byte offsets used by prior art LZ77-based compression schemes. The compression system uses knowledge of the internal format of the input stream to identify tokens that are used to determine the token offsets. Preferably, the method parses the input stream by dividing it into tokens and assigning a token type to each token. The method searches the input stream for a matching sequence of already processed tokens that is identical to a current sequence of tokens. If a matching sequence is found, the method determines whether the token type of a selected token, such as the first token, of the current sequence matches the token type of a corresponding token of the matching sequence. The method determines a token offset indicating the number of bytes of the matching token type occurring between the selected byte and the corresponding byte of the matching sequence. The method determines the length of the match and encodes the current sequence as a match pair that includes the token offset and the length of the match.
Inventors
- 👤 John W. Miller
- 👤 Ben W. Slivka
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 02:51
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/3017; G06F9/30178; G06T; G06T9/00; G06T9/005; H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3086; H03M7/40
Claims Analysis
Total Claims: 43
Claim 1
Independent Claim
136 words
A computer-implemented data compression method of compressing an input stream of bytes, each byte having a position, comprising: assigning a token type to each byte of the input stream, the token type assigned to each byte being selected from plural token types; searching for a matching sequence of already processed bytes that matches a current sequence of bytes; determining that a selected byte of the current sequence and a corresponding byte of the matching sequence have the same token type; determining a match length indicating the number of bytes in the matching sequence; determining a token offset indicating the number of already processed bytes of the same token type positioned between the current sequence and the matching sequence; and appending to an encoded data stream a match code indicating the token offset and the match length.
Claim 2
Dependent Claim
136 words
A computer-implemented data compression method of compressing an input stream of bytes, each byte having a position, comprising: assigning a token type to each byte of the input stream, the token type assigned to each byte being selected from plural token types; searching for a matching sequence of already processed bytes that matches a current sequence of bytes; determining that a selected byte of the current sequence and a corresponding byte of the matching sequence have the same token type; determining a match length indicating the number of bytes in the matching sequence; determining a token offset indicating the number of already processed bytes of the same token type positioned between the current sequence and the matching sequence; and appending to an encoded data stream a match code indicating the token offset and the match length.
Claim 3
Dependent Claim
23 words
The method of claim 1 wherein the appending step includes assigning the match code according to the token type of the selected byte.
Claim 4
Dependent Claim
30 words
The method of claim 1, further comprising: for each byte not forming part of a matched current sequence, appending to the encoded data stream a literal that indicates the byte.
Claim 5
Dependent Claim
29 words
The method of claim 3 wherein the step of appending a literal includes assigning the literal according to the token type of the byte being indicated by the literal.
Claim 6
Dependent Claim
54 words
The method of claim 3, further including appending a first literal flag code to the literal if the byte indicated by the literal is within a first range of values and appending a second literal flag code to the literal if the byte indicated by the literal is within a second range of values.
Claim 7
Dependent Claim
56 words
The method of claim 5, further including forming the literal from less than all of the bits of the byte indicated by the literal, such that when the first literal flag code is appended to the literal, the literal and first literal flag code do not include more bits than the byte indicated by the literal.
Claim 8
Dependent Claim
109 words
The method of claim 1 wherein the input stream of bytes is a stream of machine code bytes readable by a computer, and wherein the assigning step includes assigning an operation code token type to a plural number of the bytes and assigning a program relative displacement token type to a chosen byte, the chosen byte indicating the number of bytes between the chosen byte and a targeted byte that was assigned an operation code token type, the method further comprising: replacing the chosen byte with a token displacement byte indicating the number of operation code bytes in the input stream between the chosen byte and the targeted byte.
Claim 9
Dependent Claim
51 words
The method of claim 7 wherein the current sequence includes the chosen byte and the determining a token offset step includes determining the token offset to indicate the number of bytes of the program relative displacement token type positioned between the chosen byte and a corresponding byte of the matching sequence.
Claim 10
Dependent Claim
22 words
The method of claim 1, further comprising: decompressing the encoded data stream into a decompressed data stream identical to the input stream.
Claim 11
Dependent Claim
128 words
A computer-implemented data compression method of compressing an input stream of data, comprising: parsing the input stream by dividing the input stream into tokens and assigning a token type to each token; searching for a matching sequence of already processed tokens that matches a current sequence of tokens; determining that a selected token of the current sequence and a corresponding token of the matching sequence are each of a first token type; determining a match length indicating the number of tokens in the matching sequence; determining a token offset indicating the number of already processed tokens of the first token type between the current sequence and the matching sequence; and appending to an encoded data stream a match flag code indicating the token offset and the match length.
Claim 12
Dependent Claim
128 words
A computer-implemented data compression method of compressing an input stream of data, comprising: parsing the input stream by dividing the input stream into tokens and assigning a token type to each token; searching for a matching sequence of already processed tokens that matches a current sequence of tokens; determining that a selected token of the current sequence and a corresponding token of the matching sequence are each of a first token type; determining a match length indicating the number of tokens in the matching sequence; determining a token offset indicating the number of already processed tokens of the first token type between the current sequence and the matching sequence; and appending to an encoded data stream a match flag code indicating the token offset and the match length.
Claim 13
Dependent Claim
23 words
The method of claim 10 wherein the appending step includes assigning the match code according to the token type of the selected token.
Claim 14
Dependent Claim
53 words
The method of claim 10, further comprising: for each token not forming part of a current sequence that is identical to a matching sequence, appending to the encoded data stream a literal that indicates the token; and appending to the literal a literal flag code distinguishing the literal from the match flag code.
Claim 15
Dependent Claim
29 words
The method of claim 12 wherein the step of appending a literal includes assigning the literal according to the token type of the token being indicated by the literal.
Claim 16
Dependent Claim
109 words
The method of claim 10 wherein the input stream of data is a stream of machine code instructions readable by a computer, and wherein the parsing step includes assigning an operation code token type to a plural number of the tokens and assigning a program relative displacement token type to a chosen token, the chosen token indicating the number of tokens between the chosen token and a targeted token that was assigned an operation code token type, the method further comprising: replacing the chosen token with an token displacement token indicating the number of operation code tokens in the input stream between the chosen token and the targeted token.
Claim 17
Dependent Claim
51 words
The method of claim 14 wherein the current sequence includes the chosen token and the determining a token offset step includes determining the token offset to indicate the number of tokens of the program relative displacement token type positioned between the chosen token and a corresponding token of the matching sequence.
Claim 18
Dependent Claim
22 words
The method of claim 10, further comprising: decompressing the encoded data stream into a decompressed data stream identical to the input stream.
Claim 19
Independent Claim
102 words
A method in a computer system for compressing data, the data comprising a multiplicity of tokens, each token having a token value and one of a plurality of token types, the method comprising the steps of: determining the token type of each token; finding a matching sequence of tokens having the same token values as a current sequence and having a token with the same token type as a corresponding token in the current sequence; and representing the current sequence based on a count of tokens having the same token type, the count of tokens indicating a position of the matching sequence.
Claim 20
Independent Claim
102 words
A method in a computer system for compressing data, the data comprising a multiplicity of tokens, each token having a token value and one of a plurality of token types, the method comprising the steps of: determining the token type of each token; finding a matching sequence of tokens having the same token values as a current sequence and having a token with the same token type as a corresponding token in the current sequence; and representing the current sequence based on a count of tokens having the same token type, the count of tokens indicating a position of the matching sequence.
Claim 21
Dependent Claim
52 words
The method of claim 17, further comprising: appending to an encoded data stream a representation of the current sequence resulting from the representing step; and for each token not forming part of a current sequence that matches a matching sequence, appending to the encoded data stream a literal that indicates the token.
Claim 22
Dependent Claim
48 words
The method of claim 18, further including appending a first literal flag code if the token indicated by the literal is within a first range of values and appending a second literal flag code if the token indicated by the literal is within a second range of values.
Claim 23
Independent Claim
49 words
The method of clam 19, further including forming the literal from less than all of the token indicated by the literal, such that when the first literal flag code is appended to the literal, the literal and first literal flag code do not include more bits than the token.
Claim 24
Independent Claim
49 words
The method of clam 19, further including forming the literal from less than all of the token indicated by the literal, such that when the first literal flag code is appended to the literal, the literal and first literal flag code do not include more bits than the token.
Claim 25
Dependent Claim
60 words
The method of claim 17, further comprising: determining a match length indicating the number of tokens in the matching sequence having the same token values as the current sequence; and determining a token offset indicating the count of tokens, wherein the representing step includes representing the current sequence as a match code indicating the match length and the token offset.
Claim 26
Dependent Claim
103 words
A data compression system for compressing an input stream of data, comprising: a parser that parses the input stream by dividing the input stream into tokens and assigns a token type to each token; a match finder that finds a matching sequence of tokens that matches a current sequence of tokens, the matching sequence having a token with the same token type as a corresponding token in the current sequence; and an encoder that encodes the current sequence as a match code indicating a count of tokens of the same token type, the count of tokens indicating a position of the matching sequence.
Claim 27
Dependent Claim
103 words
A data compression system for compressing an input stream of data, comprising: a parser that parses the input stream by dividing the input stream into tokens and assigns a token type to each token; a match finder that finds a matching sequence of tokens that matches a current sequence of tokens, the matching sequence having a token with the same token type as a corresponding token in the current sequence; and an encoder that encodes the current sequence as a match code indicating a count of tokens of the same token type, the count of tokens indicating a position of the matching sequence.
Claim 28
Dependent Claim
37 words
The data compression system of claim 22 wherein the encoder includes means for appending to an encoded data stream a literal that represents a token not forming part of a current sequence that matches a matching sequence.
Claim 29
Dependent Claim
39 words
The data compression system of claim 23 wherein the match code is appended to an encoded data stream, the system further comprising a decompressor that decompresses the encoded data stream into a decompressed stream identical to the input stream.
Claim 30
Dependent Claim
108 words
A computer storage medium for controlling a computer to compress data, the data including a plurality of tokens, each token having a token value and one of a plurality of token types, comprising: computer instructions for determining the token type of each token; computer instructions for finding a matching sequence of tokens having the same token values as a current sequence and having a token with the same token type as a corresponding token in the current sequence; and computer instructions for representing the current sequence based on a count of tokens having the same token type, the count of tokens indicating a position of the matching sequence.
Claim 31
Dependent Claim
108 words
A computer storage medium for controlling a computer to compress data, the data including a plurality of tokens, each token having a token value and one of a plurality of token types, comprising: computer instructions for determining the token type of each token; computer instructions for finding a matching sequence of tokens having the same token values as a current sequence and having a token with the same token type as a corresponding token in the current sequence; and computer instructions for representing the current sequence based on a count of tokens having the same token type, the count of tokens indicating a position of the matching sequence.
Claim 32
Dependent Claim
64 words
The computer storage medium of claim 25, further comprising: computer instructions for appending to an encoded data stream a representation of the current sequence resulting from the instructions for representing the current sequence; and for each token not forming part of a current sequence that matches a matching sequence, computer instructions for appending to the encoded data stream a literal that indicates the token.
Claim 33
Dependent Claim
68 words
The computer storage medium of claim 26 wherein the computer instructions for appending a literal to the encoded data stream includes: computer instructions for appending a first literal flag code if the token indicated by the literal is within a first range of values; and computer instructions for appending a second literal flag code if the token indicated by the literal is within a second range of values.
Claim 34
Dependent Claim
40 words
The computer storage medium of claim 26 wherein the computer instructions for appending a literal to the encoded data stream includes computer instructions for assigning the literal according to the token type of the token being indicated by the literal.
Claim 35
Dependent Claim
78 words
The computer storage medium of claim 25, further including: computer instructions for determining a match length that indicates the number of tokens in the matching sequence having the same token values as the current sequence; and computer instructions for determining a token offset indicating the count of tokens, wherein the computer instructions for representing the current sequence include computer instructions for representing the current sequence as a match code that indicates the match length and the token offset.
Claim 36
Independent Claim
131 words
A method in a computer system for decompressing encoded data into decoded data having a multiplicity of tokens, each token having a token value and one of a plurality of token types, the encoded data comprising an encoded match code associated with a matched sequence of tokens, the method comprising the steps of: determining the token type of a selected token of the matched sequence; determining from the encoded match code a count of tokens having the same token type as the selected token of the matched sequence, the count of tokens indicating a position of a matching sequence of tokens that match the matched sequence of tokens: accessing the matching sequence using the count of tokens; and decoding the matched sequence based on the token values of the matching sequence.
Claim 37
Independent Claim
131 words
A method in a computer system for decompressing encoded data into decoded data having a multiplicity of tokens, each token having a token value and one of a plurality of token types, the encoded data comprising an encoded match code associated with a matched sequence of tokens, the method comprising the steps of: determining the token type of a selected token of the matched sequence; determining from the encoded match code a count of tokens having the same token type as the selected token of the matched sequence, the count of tokens indicating a position of a matching sequence of tokens that match the matched sequence of tokens: accessing the matching sequence using the count of tokens; and decoding the matched sequence based on the token values of the matching sequence.
Claim 38
Dependent Claim
99 words
The method of claim 30 wherein the encoded data includes a literal that represents a token not forming part of a matched sequence, further comprising: determining whether the literal includes a first literal flag code indicating that the token represented by the literal is within a first range of values, and if so, outputting the token from the first range of values; and determining whether the literal includes a literal flag code indicating that the token represented by the literal is within a second range of values, and if so, outputting the token from the second range of values.
Claim 39
Dependent Claim
70 words
The method of claim 30 wherein the encoded match code includes a token offset and a match length, the token offset indicating the count of tokens and the match length indicating the number of tokens in the matching sequence having the same token values as the matched sequence, and wherein the decoding step includes copying the token values of the tokens of the matching sequence based on the match length.
Claim 40
Independent Claim
112 words
A method in a computer system for compressing a data string having a sequence of data values, each data value having one of a plurality of data value types, the method comprising: identifying the data value type of a current data value in the data string; determining whether a matching data value and its data value type in the data string matches the current data value and its data value type; and encoding the current data value based on a count of data values having the same data value type as the current data value, the count of data values indicating a position of the matching data value in the data string.
Claim 41
Independent Claim
112 words
A method in a computer system for compressing a data string having a sequence of data values, each data value having one of a plurality of data value types, the method comprising: identifying the data value type of a current data value in the data string; determining whether a matching data value and its data value type in the data string matches the current data value and its data value type; and encoding the current data value based on a count of data values having the same data value type as the current data value, the count of data values indicating a position of the matching data value in the data string.
Claim 42
Dependent Claim
44 words
The method of claim 33 wherein the count of data values further indicates a number of data values that have the same data value type as the current data value and that are in between the current data value and the matching data value.
Claim 43
Dependent Claim
48 words
The method of claim 34, further including the step of determining a match length number of data values that follow the current data value and that match the data values that follow the matching data value, wherein the step of encoding further includes encoding the match length number.
References Cited (Backward Citations)
US4021782A
Cited
US4464650A
Cited
US4701745A
Cited
US4730348A
Cited
US4906991A
Cited
US5046027A
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) | 1999-11-05 | 2000-05-06 | 2000-11-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-11-05 | 2004-05-06 | 2004-11-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-11-05 | 2008-05-06 | 2008-11-05 | $7700.00 | Window Closed / Lapsed |