Method and apparatus for data compression and restoration

• US 4,872,009 A
• Filed: 12/07/1987
• Issued: 10/03/1989
• Est. Priority Date: 12/12/1986
• Status: Expired due to Fees

• Current Assignee: Hitachi Computer Peripherals Company Limited (Hitachi, Ltd.), Hitachi, Ltd.
• Original Assignee: Hitachi Computer Peripherals Company Limited (Hitachi, Ltd.), Hitachi, Ltd.
• Inventors: Hirose, Osamu, Tsukiyama, Tokuhiro, Yashiki, Hiroshi
• Primary Examiner(s): Shoop, Jr., William M.
• Assistant Examiner(s): YOUNG, BRIAN K
• Application Number:
  US07/129,186
• Time in Patent Office: 666 Days
• Field of Search: 340/347 DD, 341/51, 341/55, 341/59, 341/87, 341/95, 341/106, 358/261.1, 358/261.2, 360/39, 360/40, 360/48
• US Class Current: 341/95
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/46 Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind

Abstract

A method of data compression for recording data on a recording medium such as a magentic tape, a method of data restoration for data which has been compressed for recording, and an apparatus of data compression and restoration prescribe the data to be compressed based on type or value and encode the compression object data, thereby reducing the number of bits necessary to indicate the compression object data. Compression is implemented only for consecutive data fewer in number of repeating consecutive bytes than a certain number, thereby reducing the number of bits necessary to indicate the number of bytes of the consecutive data. A compression mark indicative of compression is appended to the compressed data, consisting of data made by encoding the compression object consecutive data and data indicating the number of bytes of the data, either at the front or rear of the compressed data, whereby an input data string can be compressed drastically and compressed data, even including errors, can be restored.

Claims

1. A method of transforming an input data string comprising a plurality of data bytes, said plurality including portions of a plurality of consecutive data bytes identical to one another, wherein said data bytes may be of a plurality of types, each type representing different information, said method comprising the steps of:

selecting, in advance, a first subset of the plurality of types of data bytes which may occur, said subset including those data byte types which more frequently appear repetitively and consecutively than those data byte types not included in the first subset;

detecting a compressible portion of the data string when one of said data bytes types of said first subset appears consecutively in the string a certain minimum number of times up to a certain maximum number of times,

compressing the compressible portion according to a first compression method, said compression method including encoding the data byte of the compressible portion and counting the number of data bytes of the portion to produce a compressed portion representative of the number and kind of data bytes in the compressible portion;

appending a compression mark byte, which indicates that compression has been affected, either at the front or rear of said compressed portion to generate a first compression information data;

when said input data string contains a third portion consisting of one or more consecutive data bytes the same as a first compression mark byte, said compression step further includes encoding and counting data bytes contained in said third portion to obtain a compressed third portion; and

connecting data bytes of said input data string that are not included in said first compressed information data and said compressed third portion, with said first compressed information data and said compressed third portion to produce a compressed output data string.

2. A method according to claim 1, wherein a plurality of compression methods are available and said compression mark byte identifies a type of compression method selected from said plurality of compression methods.

5. A method of restoring a data string which has been compressed by the method of claim 1, comprising the steps of:

reading out said output data string sequentially in a forward or reverse direction;

restoring, upon detection of said compression mark byte, said compressed information at the front or rear of said compression mark byte to the corresponding data byte depending on the reading direction of said data string, and outputting said restored data block; and

outputting said read-out data string directly when said compression mark byte is not detected.

7. A method according to claim 1, further comprising the steps of:

selecting a second subset of a plurality of data byte types excluding those belonging to said first subset;

detecting when said input data string contains a fourth portion consisting of a number not less than a fifth predetermined number and not greater than a sixth predetermined number, of consecutive identical data bytes of a type belonging to said second subset;

compressing said fourth portion, said step of compressing said fourth portion including

encoding the data byte type of that portion and counting data bytes constituting said fourth portion to obtain a compressed fourth portion representative of the kind and number of the data bytes constituting said fourth portion;

appending a second compression mark byte indicating that compression has been effected on said fourth portion, to one end of said compressed fourth portion, to form a second compression to information data; and

connecting data bytes contained in said input data string that are not compressed with said first and second compressed information data and said third compressed portion to produce said compressed output data string.

8. A method according to claim 1, wherein said compressed portion consists of one byte, said first compression mark byte consists of one byte and said first compression information data consists of said one-byte compressed portion and said one-byte first compression mark byte.

9. A method according to claim 7, wherein said compressed fourth portion consists of two bytes, said second compression mark byte consists of one byte and said second compression information data consists of the two-byte compressed fourth portion and the one-byte second compression mark byte.

3. An apparatus for transforming an input data string comprising a plurality of data bytes, said plurality including a consecutive portion having a plurality of consecutive data bytes identical to one another and the input data string is formed as a combination of data bytes of a plurality of types, each type representing different information, said apparatus comprising:

means for detecting if a data byte is of a type that corresponds to one of a first subset of data bytes including a first predetermined number of types selected in advance among said plurality of data byte types where said first number of bytes predetermined more frequently occur consecutively and repetitively than other data byte types,

means for encoding data bytes of said type corresponding to one of said first subset in accordance with a first transforming format when the data byte of that type appears consecutively a minimum number of times;

means for counting the number of said data bytes constituting said consecutive portion within a certain range of maximum value and for encoding said number;

means for generating a compression mark byte which includes the presence of said encoded data blocks and the encoded number;

means for detecting if the data string includes a portion including one or more consecutive data bytes the same as said compression mark byte;

means for encoding a portion detected to include one or more consecutive data bytes the same as the compression mark byte and for counting the number of bytes of said portion to produce a second compressed portion; and

switching means for combining compression information data consisting of said encoded data bytes, the encoded number and compression mark byte with data bytes of said input data string which are not compressed, and with a compressed second portion to thereby produce a compressed output data string.

4. An apparatus according to claim 3 further comprising means which operates on said means for detecting, means for encoding, means for generating and means for switching, for selecting a compression format from a plurality of different formats wherein each format defines a transforming format, a maximum number of consecutive data bytes for compression, and a compression mark.

6. A compression/restoration apparatus for transforming an input data string of a plurality of data bytes, which includes a consecutive portion of a plurality of consecutive data bytes identical to one another, and is formed as a combination of data bytes of a plurality of types, each type representing different information, into a compressed output data string, and restoring the original data string, said apparatus including a compression section and a restoration section, said compression section comprising:

means for detecting if the data byte of said consecutive portion corresponds to a data byte which more frequently occurs consecutively and repetitively and corresponds to a data byte type of a first certain number of types selected in advance among said data bytes of a plurality of types;

means for encoding data bytes of said consecutive portion, detected to be data bytes of one of said first number of data byte types selected, in accordance with a first transformation format;

means for counting and for encoding the number of said data bytes which constitute said consecutive portion within the range of a certain maximum value;

means for generating a compression mark byte which indicates that said encoded data bytes and the encoded number are present; and

switching means for connecting compression information data consisting of said encoded data blocks, encoded number and compression mark byte to input data from said data string that is without compression, thereby generating a compressed output data string,

said restoration section comprising;

means for reading out said output data string;

means for detecting said compression mark byte in said read-out output data string;

encoding means, when said compression mark is detected, for decoding said encoded data bytes located at the front or rear of said compression mark byte and outputting said decoded data bytes consecutively in number equal to the number indicated by said encoded number associated with said consecutive data; and

switching means for selecting the output of said decoding means when said compression mark byte has been detected, or the output of said read-out output data string directly when said compression mark byte has not been detected.