Data compression method and system

• US 5,572,206 A
• Filed: 07/06/1994
• Issued: 11/05/1996
• Est. Priority Date: 07/06/1994
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Slivka, Ben W., Miller, John W.
• Primary Examiner(s): Young, Brian K.
• Application Number:
  US08/271,125
• Time in Patent Office: 853 Days
• Field of Search: 341/51, 341/106, 341/107, 341/87, 341/55
• US Class Current: 341/51
• CPC Class Codes: G06F 9/30178 of compressed or encrypted instructions
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

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.

Claims

1. 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.

2. The method of claim 1 wherein the appending step includes assigning the match code according to the token type of the selected byte.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. The method of claim 1, further comprising:

decompressing the encoded data stream into a decompressed data stream identical to the input stream.

10. 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.

11. The method of claim 10 wherein the appending step includes assigning the match code according to the token type of the selected token.

12. 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.

13. 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.

14. 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.

15. 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.

16. The method of claim 10, further comprising:

decompressing the encoded data stream into a decompressed data stream identical to the input stream.

17. 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.

18. 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.

19. 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.

21. 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.

20. 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.

22. 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.

23. 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.

24. 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.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.

30. 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.

31. 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.

32. 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.

33. 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.

34. 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.

35. 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.