Reversible method of encoding data

• US 5,640,158 A
• Filed: 09/14/1995
• Issued: 06/17/1997
• Est. Priority Date: 09/14/1994
• Status: Expired due to Term

• Current Assignee: Seiko Epson Corporation (Seiko Group)
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Kitazawa, Noboru, Okayama, Toshiaki
• Primary Examiner(s): DEBOER, TODD
• Application Number:
  US08/527,904
• Time in Patent Office: 642 Days
• Field of Search: 341/51, 341/55, 341/67, 341/82
• US Class Current: 341/51
• 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

Abstract

A method of reversible data compression is disclosed. The method is an improvement on the Lempel-Ziv data compression method that does not require a prefix for every noncompressed data unit in the encoded data stream. A code is inserted at the beginning of each string of consecutive noncompressed data bytes to indicate that the string is of noncompressed data and the number of bytes in the string. By eliminating the requirement for a separate prefix for each noncompressed data, a higher compression ratio is achieved over conventional Lempel-Ziv encoding methods.

Claims

1. A method of data compression to encode a plurality of sequential data bytes to provide an encoded data stream, the encoded data stream including noncompressed data strings interleaved with compressed data strings, each compressed data string having a plurality of consecutive compressed data units, each compressed data unit indicating a length and an offset, each compressed data unit corresponding to at least a first predetermined number of sequential data bytes, each noncompressed data string having a plurality of consecutive noncompressed data bytes, each noncompressed data byte corresponding to one of the sequential data bytes, the encoded data stream having an initial noncompressed data string having at least a second predetermined number of consecutive bytes, the method comprising the steps of:

comparing the plurality of sequential data bytes that are not encoded to the encoded data stream to determine the longest match therewith;

appending to the encoded data stream a compressed data unit corresponding to the match for each match of at least the first predetermined number of sequential data bytes that are not encoded, the compressed data unit indicating the length of the match and the offset between the data unit and the matching encoded data;

appending to the encoded data stream a noncompressed data byte for each sequential data byte not contained in any match of at least the first predetermined number of sequential data bytes that are not encoded;

inserting into each noncompressed data string a code indicating the number of consecutive bytes in the noncompressed data string; and

inserting into each compressed data string a code indicating the number of compressed data units in the compressed data string.

2. The method of claim 1 wherein the compressed data units comprise one byte of data bits, a first portion of data bits indicating the length and a second portion of the data bits indicating the offset.

3. The method of claim 1 wherein the code inserted into each noncompressed data string is a Wyle code that precedes the first byte of encoded data noncompressed data string.

4. The method of claim 1 wherein the code inserted into each compressed data string is a Wyle code that precedes the first compressed data unit.

5. A method of data compression to encode a plurality of sequential data bytes to provide an encoded data stream, the encoded data stream including noncompressed data strings interleaved with compressed data strings, each compressed data string having a plurality of consecutive compressed data units, each compressed data unit indicating a length and an offset, each compressed data unit corresponding to at least a first predetermined number of consecutive sequential data bytes, each noncompressed data string having a plurality of consecutive noncompressed data bytes, each noncompressed data byte corresponding to one of the sequential data bytes, the encoded data stream having an initial noncompressed data string having at least a second predetermined number of consecutive bytes beginning at the start of the plurality of sequential data bytes, the method comprising the steps of:

comparing the plurality of sequential data bytes that are not encoded to the encoded data stream to determine the longest match therewith;

appending to the encoded data a compressed data unit corresponding to the match for each match of at least a first predetermined number of sequential data bytes that are not encoded, the compressed data unit indicating the length of the match, and the offset of the data unit to the matching encoded data;

appending to the encoded data stream a noncompressed data byte for each sequential data byte not contained in any match of at least the first predetermined number of sequential data bytes that are not encoded; and

inserting into each noncompressed data string a code indicating the number of consecutive bytes in the noncompressed data string, wherein

each compressed data unit further indicating whether a noncompressed data byte immediately follows.

6. The method of claim 5 wherein the code inserted into each noncompressed data string is a Wyle code that precedes the first byte of encoded data in the noncompressed data string.

7. The method of claim 5 wherein each compressed data unit includes a suffix indicating whether the data immediately following is a noncompressed data string or a compressed data unit.

8. A method of decoding an encoded data stream to provide a plurality of sequential data the encoded data stream including noncompressed data strings interleaved with compressed data strings, each compressed data string having a plurality of consecutive compressed data units and a code indicating the number of compressed data units in the compressed data string, each compressed data unit indicating a length and an offset, the length indicating the number of bytes of matching uncompressed data, the offset indicating the separation of the compressed data unit from the matching uncompressed data bytes, each compressed data unit corresponding to at least a first predetermined number of consecutive sequential data bytes, each noncompressed data string having a plurality of consecutive noncompressed data bytes and a code indicating the number of consecutive bytes in the noncompressed data stream, each noncompressed data byte corresponding to one of the sequential data bytes, the encoded data stream having an initial noncompressed data string having at least a second predetermined number of consecutive bytes beginning at the start of the plurality of sequential data bytes, the method comprising the steps of:

receiving the encoded data stream from a source;

detecting the code of each noncompressed data string to determine a count of the corresponding data bytes to be appended to the plurality of sequential data bytes;

appending the corresponding noncompressed data bytes to the plurality of sequential data bytes according to the detected count for each noncompressed data string;

detecting the code of each compressed data string to determine a count of the compressed data units in the compressed data string;

determining the offset and length of each compressed data unit in each compressed data string;

forming a string of contiguous data bytes matching the contiguous portion of the sequential data bytes starting at a location determined by the offset relative to the compressed data unit and having a length determined by the length of the compressed data unit for each compressed data unit; and

appending each string of contiguous data bytes formed from the compressed data units to the plurality of sequential data bytes.

9. The method of claim 8 wherein the compressed data units comprise one byte of data bits, a first portion of the data bits indicating the length and a second portion of the data bits indicating the offset.

10. The method of claim 8 wherein the code inserted into each noncompressed data string is a Wyle code that precedes the first byte of encoded data in the noncompressed data string.

11. The method of claim 8 wherein the code inserted into each compressed data string is a Wyle code that precedes the first compressed data unit in the compressed data string.

12. A method of decoding an encoded data stream to provide a plurality of sequential data, the encoded data stream including noncompressed data strings interleaved with compressed data units, each compressed data unit indicating whether a noncompressed data byte immediately follows, each compressed data unit indicating a length and an offset, the length indicating the number of bytes of matching uncompressed data, the offset indicating the separation of the compressed data unit from the matching uncompressed data bytes, each compressed data unit corresponding to at least a first predetermined number of sequential data bytes, each noncompressed data string having a plurality of consecutive noncompressed data bytes and a code indicating the number of consecutive bytes in the noncompressed data stream, each noncompressed data byte corresponding to one of the sequential data bytes, the encoded data stream having an initial noncompressed data string having at least a second predetermined number of consecutive bytes beginning at the start of the plurality of sequential data bytes, the method comprising the steps of:

receiving the encoded data stream from a source;

detecting the code of each noncompressed data string to determine a count of the corresponding data bytes to be appended to the plurality of sequential data bytes;

appending the corresponding noncompressed data bytes according to the detected count for each noncompressed data string;

detecting each compressed data unit to determine the location of the matching noncompressed data bytes from the offset of the compressed data unit, the number of matching noncompressed data bytes represented by the data unit from the length, and determine whether a noncompressed data byte immediately follows the compressed data unit;

forming for each detected compressed data unit a string of contiguous data bytes corresponding to the contiguous portion of the sequential data bytes starting at a location determined by the offset of the compressed data unit relative to the compressed data unit and having a length determined by the length of the compressed data unit; and

appending the string of contiguous data bytes formed from the detections of compressed data units to the plurality of sequential data bytes.

13. The method of claim 12 wherein the code inserted into each noncompressed data string is a Wyle code that precedes the first byte of encoded data in the noncompressed data string.

14. The method of claim 12 wherein each compressed data unit includes a suffix indicating whether the data immediately following is a noncompressed data string.

15. An apparatus for encoding a plurality of sequential data bytes, to provide an encoded data stream, the encoded data stream including noncompressed data strings interleaved with compressed data strings, each compressed data string having a plurality of consecutive compressed data units, each compressed data unit indicating a length and an offset, each compressed data unit corresponding to at least a first predetermined number of consecutive sequential data bytes, each noncompressed data string having a plurality of consecutive noncompressed data bytes, each noncompressed data byte corresponding to one of the sequential data bytes, the encoded data stream having an initial noncompressed data string having at least a second predetermined number of consecutive bytes corresponding to the start of the plurality of sequential data bytes, the apparatus comprising:

an encoding type detection section for comparing the plurality of sequential data bytes that are not encoded to the encoded data stream to determine the longest match therewith;

a compressed data encoder for appending to the encoded data stream compressed data units corresponding to matches of at least the first predetermined number of consecutive sequential data bytes that are not encoded, the compressed data unit indicating the length of the match and the offset between the data unit and the matching encoded data, and inserting into each compressed data string a code indicating the number of compressed data units in the compressed data string; and

a noncompressed data encoder for appending to the encoded data stream a noncompressed data byte each sequential data byte not contained in any match of at least a first predetermined number of consecutive sequential data bytes that are not encoded, and inserting into each noncompressed data string a code indicating the number of consecutive bytes in the noncompressed data string.

16. The apparatus of claim 15 wherein the compressed data units comprise one byte of data bits, a first portion of the data bits indicating the length and a second portion of the data bits indicating the offset.

17. The apparatus of claim 15 wherein the code inserted into each noncompressed data string is a Wyle code that precedes the first byte of encoded data.

18. The apparatus of claim 15 wherein the code inserted into each noncompressed data string is a Wyle code that precedes the first compressed data unit.

19. An apparatus for encoding a plurality of sequential data bytes, to provide an encoded data stream, the encoded data stream including noncompressed data strings interleaved with compressed data strings, each compressed data string having a plurality of consecutive compressed data units, each compressed data unit indicating a length and an offset, each compressed data unit corresponding to at least a first predetermined number of consecutive sequential data bytes, each noncompressed data string having a plurality of consecutive noncompressed data bytes, each noncompressed data byte corresponding to one of the sequential data bytes, the encoded data stream having an initial noncompressed data string having at least a second predetermined number of consecutive bytes beginning at the start of the plurality of sequential data bytes, the apparatus comprising:

an encoding type detection section for comparing the plurality of sequential data bytes that are not encoded to the encoded data stream to determine the longest match therewith;

a compressed data encoder for appending to the encoded data a compressed data unit corresponding to the longest of matches of at least the first predetermined number of consecutive sequential data bytes with consecutive encoded data units, the compressed data unit indicating the length of the match, and the offset of the data unit to the matching encoded data; and

a noncompressed data encoder for appending to the encoded data stream a noncompressed data byte for each sequential data byte not contained in any match of at least the first predetermined number of consecutive sequential data units that are encoded, and inserting each noncompressed data string a code indicating the number of consecutive bytes in the noncompressed data string, wherein

each compressed data unit further indicating whether a noncompressed data byte immediately follows.

20. The apparatus of claim 19 wherein the code inserted into each noncompressed data string is a Wyle code that precedes the first byte of encoded data in the noncompressed data stream.

21. The apparatus of claim 19 wherein each compressed data unit includes a suffix indicating whether the data immediately following is a noncompressed data string or a compressed data unit.

22. An apparatus for decoding an encoded data stream to provide a plurality of sequential data bytes, the encoded data stream including noncompressed data strings interleaved with compressed data strings, each compressed data string having a plurality of consecutive compressed data units and a code indicating the number of compressed data units in the compressed data string, each compressed data unit indicating a length and an offset, the length indicating the number of bytes of matching uncompressed data, the offset indicating the separation of the compressed data unit from the matching uncompressed data bytes, each compressed data unit corresponding to at least a first predetermined number of consecutive sequential data bytes, each noncompressed data string having a plurality of consecutive noncompressed data bytes and a code indicating the number of consecutive bytes in the noncompressed data stream, each noncompressed data byte corresponding to one of the sequential data bytes, the encoded data stream having an initial noncompressed data string having at least a second predetermined number of consecutive bytes beginning at the start of the plurality of sequential data bytes, the apparatus comprising:

a buffer for receiving the encoded data stream from a source;

a noncompressed data detection section for detecting the code of each noncompressed data string to determine a count of corresponding data bytes to be appended to the plurality of sequential data bytes;

a noncompressed data decoder for appending the corresponding noncompressed data bytes according to the detected count for each noncompressed data string;

a compressed data detection section for detecting the code of each compressed data string to determine a count of the compressed data units in the compressed data string; and

a compressed data unit decoder section for determining the offset and length of each compressed data unit in each compressed data string, forming a string of contiguous data bytes corresponding to the contiguous portion of the sequential data bytes starting at a location determined by the offset relative to the compressed data unit and having a length determined by the length of the compressed data unit for each compressed data unit, and appending the string of contiguous data bytes formed from the compressed data units to the plurality of sequential data bytes.

23. The apparatus of claim 22 wherein the compressed data units comprise one byte of data bits, a first portion of data bits indicating the length and a second portion of the data bits indicating the offset.

24. The apparatus of claim 22 wherein the code inserted into each noncompressed data string is a Wyle code that precedes the first byte of encoded data in the noncompressed data string.

25. The apparatus of claim 22 wherein the code inserted into each compressed data string is a Wyle code that precedes the first compressed data unit in the compressed data string.

26. An apparatus for decoding an encoded data stream to provide a plurality of sequential data bytes, the encoded data stream including noncompressed data strings interleaved with compressed data units, each compressed data unit indicating whether a noncompressed data byte immediately follows, each compressed data unit indicating a length and an offset, the length indicating the number of bytes of matching uncompressed data, the offset indicating the separation of the compressed data unit from the matching uncompressed data bytes, each compressed data unit corresponding to at least a first predetermined number of consecutive sequential data bytes, each noncompressed data string having a plurality of consecutive noncompressed data bytes and a code indicating the number of consecutive bytes in the noncompressed data stream, each noncompressed data byte corresponding to one of the sequential data bytes, the encoded data stream having an initial noncompressed data string having at least a second predetermined number of consecutive bytes beginning at the start of the plurality of sequential data bytes, the apparatus comprising:

a buffer for receiving the encoded data stream from a source;

a noncompressed data detection section for detecting the code of each noncompressed data string to determine a count of the corresponding data bytes to be appended to the plurality of sequential data bytes;

a noncompressed data decoder for appending the corresponding noncompressed data bytes according to the detected count for each noncompressed data string;

a compressed data detection section for detecting each compressed data unit to determine the location of the matching noncompressed data bytes from the offset of the compressed data unit, the number of matching noncompressed data bytes represented by the data unit from the length, and determine whether a noncompressed data byte immediately follows the compressed data unit; and

a compressed data decoder for forming a string of contiguous data bytes corresponding to the contiguous portion of the sequential data bytes starting at a location determined by the offset relative to the compressed data unit and having a length determined by the length of the compressed data unit, and appending the string of contiguous data bytes formed from the detections of compressed data units to the plurality of sequential data bytes.

27. The apparatus of claim 26 wherein the code inserted into each noncompressed data string is a Wyle code that precedes the first byte of encoded data.

28. The apparatus of claim 26 wherein the code inserted into each noncompressed data string is a Wyle code that precedes the first compressed data unit.

29. The apparatus of claim 26 wherein each compressed data unit includes a suffix indicating whether the data immediately following is a noncompressed data string or a compressed data unit.