JPH0511973A - Data compression method using universal code - Google Patents

Abstract

(57) [Abstract] [Purpose] A data compression method using a universal code that compresses and encodes an input character string such as character information using a universal type algorithm. An encoded character string is obtained by incorporating the correlation between characters. The purpose is to obtain a high compression rate by encoding with reduced redundancy between. [Structure] An encoded character string is held in the dictionary 12,
A universal code that searches the input character string of the character input unit 10 for a substring whose maximum length matches the coded character string of the dictionary 12 and encodes it with a set of the start position and the matching length of the maximum length matching substring is used. The character input unit 10
Search the matching subsequences S1, S2, S3, S4 of the coded character strings held in the dictionary 12 starting from the same first character as the immediately preceding character 18 for the input character string of , Substring S4 with maximum length matching
Is encoded as a start position when encoding is performed in a pair with the matching length by using the appearance order in which the preceding character of the maximum length matching subsequence appears.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a data compression method using a universal code which compresses and encodes an input character string such as character information using a universal type algorithm.
In recent years, various types of data such as character codes, vector information, and images have been handled by computers,
The amount of data handled is also increasing rapidly. When handling a large amount of data, omitting redundant parts of the data and compressing the amount of data reduces the storage capacity and enables faster transmission.

Universal coding has been proposed as a method of compressing such various data by one method. Here, the field of the present invention is not limited to compression of character codes and can be applied to various data, but in the following, the word used in information theory is followed, and one word unit of data is called a character, A string in which data is connected to arbitrary words is called a character string.

As a typical method of the universal code,
There is a Ziv-Lempel code (for details,
For example, see Munakata "Ziv-Lempel Data Compression Method", Information Processing, Vol.26, No.1, 1985). Two algorithms of (1) universal type and (2) incremental decomposition type (Incremental parsing) have been proposed for the Jibulermpel code.

Further, as an improvement of the universal type algorithm, LZSS code (TC Bell, "Better OPM / L Tex
t Compression ”, IEEE Trans. on Commun., Vol.COM-3
4, No. 12, Dec. 1986), or QIC-122, which is the standard compression method for 1/4 inch cartridge magnetic tape.
There is a sign. Further, as an improvement of the incremental decomposition type algorithm, there is a LZW (Lempel-Ziv-Welch) code (TA W
elch, “A Technique for High-Performance Data Comp
ression ”, Computer, June 1984).

These improved codes have come to be used for file compression of an auxiliary storage device and data transmission in personal computer communication.

[0006]

2. Description of the Related Art First, a conventional universal type algorithm and a QIC-122 code which is one of its improvements will be described. [Universal type algorithm] The universal type algorithm is a data compression method that can obtain a high compression rate although the amount of calculation is large.

That is, in the universal type algorithm, a character string to be encoded is divided into a sequence having a maximum length match from any position of the encoded character string, that is, a so-called substring, and the input character string is divided. Encode as a copy of a substring with the same maximum length in the past. FIG. 10 shows an encoding method of the universal Dibulenpel code. In FIG. 10, an already-input character string is stored in the P buffer 12 having a function as a dictionary, and a character string to be encoded is input to the Q buffer 10 as a character input unit. The pattern matching unit 14 matches the character string in the Q buffer 10 with the series in the P buffer 12,
Find the matching maximum length character substring in 2. Then, in order to specify a substring matching the maximum length searched in the P buffer 12, it is encoded as a start position (start address) matching length (length) of the maximum length matching sequence in the information set P buffer of FIG. If there is no matching sequence, raw data is output together with the mismatched symbol.

Next, the encoded character string in the Q buffer 10 is moved to the P buffer 12, and a new encoded character string is registered. Hereinafter, the same operation is repeated, and the input character string is decomposed into substrings and encoded. As described above, in the Gibble-Rempel code, the current character string is encoded as a duplicate of the encoded past character string. When the Gibulen-pelpel code is used, the document information of the character code can be compressed to about 1/2.

[QIC-122 Code] QIC (Quauter Inch Cartrrige S), which is a group of manufacturers centering on 3M
tandard Inc.) adopted the standard compression method for 1/4 inch cartridge magnetic tape. QIC-
In the 122 code algorithm, 20 is used as the P buffer.
A mode which has a history of 48 bytes and represents a character string to be encoded in the Q buffer as a copy of the character string in the P buffer,
It has two modes of encoding raw data byte by byte. Then, when the maximum length matching character string in the P buffer is two characters or more, the encoding is performed in the duplication mode, and in other cases, the encoding is performed in the raw data mode.

FIG. 12 shows the QI expressed in the BNF meta language.
The codeword format of a C-122 code is shown. Also BN
The meta symbols used in the F metalanguage have the meanings shown in FIG. The code word format of the QIC-122 code in FIG. 12 will be described in detail as follows. (1) The compressed stream (Compressed Stream) is composed of a compressed string and an end marker.

(2) The compressed string is represented by an ASCII raw byte following identification bit 0 for raw data, and an identification bit 1 followed by a compression byte for compressed data. (3) The ASCII raw byte is represented by 1 byte of 8 bits. (4) The compressed byte is a set of offset (start position) and length (match length). (5) The offset (start position) is represented by 7 bits when the identification bit is 1. When the identification bit is 0, it is represented by 11 bits. (6) The end marker is 110000000 and the offset is 0. (7) Bit b is 0 or 1. (8) Length (match length) is represented by a variable length code as shown in FIG.

FIG. 14 shows a specific example of encoding the QIC-122 code. FIG. 14 shows the character string "ABAAAAAACAB.
The case where "A" is input is taken as an example. First, since the number of matching characters in the P buffer for the first three characters "ABA" is one or less, the bit sequence of the ASCII raw byte is output. Since the 5th "A" from the 4th character to the 8th character matches the character "A" immediately before in the P buffer, the compressed byte identification bit 7-bit offset identification bit offset = 1 length = 5 bytes Series "1 100000001 110
It is output as "0".

Here, the value of the offset indicating the starting position of the substring having the maximum length match indicates the number of the position starting from the latest registration position (address) of the P buffer. The ninth character "C" is not in the P buffer, so it outputs an ASCII raw byte. The 10th-12th character "ABA" is P
Since it has already been registered as three characters from the beginning of the buffer, a bit sequence "1 1 001 001 001" consisting of compressed byte identification bit 7 bit offset identification bit offset = 9 length = 3 bytes is output.

Since all the input characters have been encoded as described above, "1 1000000" is output as the end data and the process is terminated.

[0015]

However, in the conventional data compression method using the universal code such as the Dibulenpel code or the QIC-122 code, the maximum length matching character string to be copied is "match start". Since the encoding was performed by expressing the combination of the "position" and the "match length", when the coded character string held in the P buffer increases, the match start position is expressed by the address of the memory forming the P buffer. Therefore, there is a problem in that it has to be represented by a long number of bits, redundancy remains between encoded character strings, and a high compression rate cannot be obtained.

The present invention has been made in view of the above conventional problems, and obtains a high compression rate by encoding by reducing the redundancy between encoded character strings by incorporating the correlation between characters. It is an object of the present invention to provide a data compression method using a universal code capable of performing.

[0017]

FIG. 1 is a diagram for explaining the principle of the present invention. First, the present invention converts an encoded character string into a dictionary (P
Buffer) 12 and searches for a substring having the maximum length that matches the input character string of the character input unit (Q buffer) 10 in the encoded character string of the dictionary 12 and starts the maximum length matching substring. The target is a data compression method using a universal code that is encoded by a set of position and matching length.

In the present invention as a data compression method using such a universal code, the coded characters stored in the dictionary 12 starting from the same first character as the immediately preceding character 18 for the input character string of the character input unit 10 are used. The matching subsequences S1, S2, S3, S4 of the columns are searched, the subsequence S4 having the maximum length matching is searched, and the maximum length matching subsequence S4 of the maximum length matching subsequence S4 is set as a start position when the substring S4 having the maximum length matching is encoded. It is characterized in that an encoding unit 14 is provided which encodes in combination with the matching length by using the appearance order (4th) in which the immediately preceding character appears.

If the substring of the coded character string with the maximum length matching retrieved from the dictionary 12 is the continuous character string S2 of the first character 18, the coding section 10 starts the continuous character string S2. It is characterized in that the order of appearance is assigned to the position or the end position, and the position and the end position are encoded as a set with the matching length. in this case,
It is also possible to allocate two appearance orders of the start position and the end position of the continuous character string S2 and to code the appearance order of both the start position and the end position of the continuous character string as a set with the matching length.

The encoding unit 14 does not encode the input character string when the number of characters of the substring having the maximum matching length of the encoded character string of the dictionary 12 to be encoded is less than a predetermined character, for example, less than three characters. Is output as it is, and when the number of characters is a predetermined value, for example, 3 characters or more, it is encoded by a combination of the appearance order and the matching length. Further, when the number of characters in the substring having the maximum matching length of the coded character string of the dictionary 12 to be encoded is small, the encoding unit 14 encodes with a set of the start position (conventional method) of the substring and the matching length, When the number of characters is large, encoding may be performed using a combination of the appearance order (method of the present invention) and the matching length.

Further, the encoding unit 14 encodes the input character string, for example, using the code word of the QIC-122 code which is the standard compression system of the 1/4 inch cartridge magnetic tape.

[0022]

As described above, according to the present invention, a coded character having the preceding character (the latest character registered in the P buffer) already coded for the character string to be coded in the Q buffer as the first character Conventionally, when matching all substrings in a decision, the appearance order is known, and when encoding as a copy of the substring with the maximum matching length in the matching substring, conventionally, the matching position matches the starting position of the maximum matching length substring. According to the present invention, what is encoded by a set of lengths is represented by a set of the order of appearance of the subsequence having the maximum match length in the P buffer and the match length and is encoded.

Therefore, the conventional start position (start address)
Compared with the above, the number of appearance orders of the subsequence is much smaller, and the appearance order can be expressed by a smaller number of bits, so that the compression rate can be significantly improved. For example, the present invention uses QI
It is applied to the encoding of C-122 code, searches for the maximum length matching character string of the P buffer that continues from the immediately preceding character as the one character immediately before the Q buffer, and finds the start position of the maximum length matching character string immediately before in the P buffer. Express the characters in the order in which they appear.

[0024]

2 is a block diagram of an embodiment showing one embodiment of the present invention. In FIG. 2, reference numeral 16 denotes a buffer memory, which is assigned to a Q buffer 10 as a character string input unit for storing a character string to be encoded and a P buffer 12 functioning as a dictionary in which encoded character strings are registered. To be

Reference numeral 14 denotes a pattern matching unit as a coding unit using a CPU, which searches the P buffer 12 for a substring having the maximum length matching the character string of the Q buffer 10 according to the universal coding algorithm, and matches the maximum length. A codeword consisting of a set of the start position and the matching length is output as a copy of the subsequence. FIG. 3 shows the pattern matching unit 1 of FIG.
FIG. 4 is an explanatory diagram showing an encoding process of the present invention according to No. 4;

In FIG. 3, first, assuming that the character string "acba ..." To be encoded is stored in the Q buffer 10, it includes the immediately preceding character "b" which is one character just before being encoded. Then, it is searched whether or not a character string matching the character string of the Q buffer 10 is present in the P buffer 12 following the immediately preceding character "b". It is assumed that, for example, the character strings S1, S2, S3, S4 can be retrieved as the character strings satisfying this condition.

Since the appearance numbers of the character strings S1 to S4 are registered in the P buffer 12 from the right, the character string S1: the first character string S2: the second character string S3: the third character string S4: the fourth The appearance order is set, and the appearance numbers 1, 2, 3, and 4 are sequentially assigned.

Next, the character string S4 having the maximum length matching the input character string is searched from the character strings S1 to S4, and this character string S4 is searched.
The start position of is represented by appearance number 4, and is output as a codeword paired with the match length. On the other hand, for a character string such as the character string S2 in which the preceding character "b" is continuous, the continuous character string S2
The appearance number is assigned to either the start point or the end point of and encoded. 2 at the start and end of the continuous character string S
One appearance number may be assigned and encoded as a code word of a pair of two appearance numbers and a matching length.

FIG. 4 is a flow chart showing an embodiment of the universal coding algorithm according to the present invention using the QIC-122 code as an example. In FIG. 4, first, in step S1, the contents of the P buffer are emptied, and the Q buffer is filled with input data to be encoded. Next, in step S2, the longest character string S in the P buffer that matches the character string from the position of the immediately preceding character in the Q buffer is searched. Subsequently, in step S3, it is determined whether or not the longest character string S that can be searched is three characters or more.

If the longest character string S is one character or two characters, the process proceeds to step S4 to enter the raw data mode, and the frac bit 0 and ASC indicating the raw data mode.
Outputs 1 byte of raw data consisting of II code. on the other hand,
If the longest character string S is 3 characters or more, the process proceeds to step S5, the duplication mode is set, and a set of the appearance order of the longest character string and the matching length is coded after the flag bit 1 indicating compressed data. Turn into.

In step S6, the encoded character string or character in the Q buffer is moved to the P buffer, and the same number of new characters is input to the Q buffer. Further QIC-12
Since the P buffer is fixed at 2048 bytes in the 2-code algorithm, the oldest characters corresponding to the number of characters moved to the P buffer are discarded from the P buffer. The same process is repeated thereafter.

FIG. 5 shows Q encoded in the replication mode of FIG.
FIG. 13 is an explanatory diagram of a format using an IC-122 code word, and an offset is a 3-bit expression indicating an appearance number as compared with FIG. 12. Therefore, up to 7 character string start positions can be encoded. Here, the appearance number 0 is used for the END mark. Also, the match length includes the previous character,
Since it represents a character string of three or more characters, match length = | S | −2 is used.

As described above, in the present invention, the offset of the appearance number can be expressed by a small number of bits of 3 bits instead of the conventional offset indicating the starting position of 7 bits or 11 bits, thereby improving the compression rate. it can. FIG. 6 shows the data format output in the raw data mode of FIG. 4 and the data format of the codeword output in the copy mode.

FIG. 7 shows a QIC showing another embodiment of the present invention.
6 is a flowchart showing an encoding algorithm using -122 code, and in this embodiment, in addition to the raw data mode of FIG. 4 and the duplication mode for outputting code words using the appearance order, It is characterized in that a duplication mode for outputting a code word using the start position (start address) of is combined.

In FIG. 7, after the initial processing is performed in step S1, the longest character string S1 having the maximum matching length following the immediately preceding character string is searched for in step S2 as in step S2 of FIG. Find the match length. Then, in step S3, the longest character string S2 in the P buffer is searched irrespective of the immediately preceding character, and the start position and the matching length are obtained.

Next, the longest character string S retrieved in step S2
It is checked whether 2 is 3 characters or more. If 3 characters or more, the process proceeds to step S8 to output the code word of the duplication mode (2) of FIG. 9C. If it is less than 3 characters, the process proceeds to step S5, and it is checked whether the longest character string S2 searched in step S3 is 2 characters or more. If it is 2 characters or more, the process proceeds to step S7, and the duplication mode (1 ) Codeword, that is, a set of the start position and the matching length is encoded.

Further, when the longest character string S2 is one character, the process proceeds to step S6, and the code word in the raw data mode of FIG. 9A is output. When the encoding is completed in any of these steps S6, S7 or S8, the process proceeds to step S9, where the next encoded character string or character in the Q buffer is moved to the P buffer, and the same number of new characters is written. Since there is a limit to the capacity of the P buffer after inputting into the Q buffer, the oldest characters corresponding to the number of characters moved to the P buffer are discarded from the P buffer, and the same processing is repeated thereafter.

FIG. 8 shows a format structure using QIC-122 codewords encoded in the duplication modes (1) and (2) in the embodiment of FIG. Although the size of the appearance number is limited to, for example, 3 bits in the above embodiment, it may be represented by a variable length code without limitation. Also,
Although the order of appearance is counted from the old right of registration to the new left of registration in the P-buffer, this may in turn be counted from left to right.

Further, although the above-mentioned embodiment has been described with the QIC-122 code as an example, it can be applied as it is to an appropriate universal code such as the Dibullenpel code.

[0040]

As described above, according to the present invention, when a coded character string is represented by a set of "match start position" and "match length" as a copy of the coded character string, conventionally, the match start position is Is expressed as an address, whereas it is expressed as a relative order by the number of the character string in which the immediately preceding character matches, so it can be expressed with a shorter number of bits than before and a high compression rate can be achieved. Obtainable.

[Brief description of drawings]

FIG. 1 is an explanatory view of the principle of the present invention.

FIG. 2 is a block diagram of an embodiment of the present invention.

FIG. 3 is an explanatory diagram of encoding processing of the present invention.

FIG. 4 is a flowchart showing a QIC-122 encoding algorithm using the present invention.

FIG. 5 is an explanatory diagram of a codeword format in the copy mode of FIG.

6 is an explanatory diagram of the data format of the code word in FIG. 4.

FIG. 7 is a flowchart showing another embodiment of the QIC-122 encoding algorithm using the present invention.

8 is an explanatory diagram of a codeword format in the copy mode of FIG.

9 is an explanatory diagram of a data format of the code word in FIG. 7.

FIG. 10 is an explanatory diagram of a universal Dibulenpel code encoding method.

FIG. 11 is an explanatory diagram of a universal codeword data format.

FIG. 12 is an explanatory diagram of a format of QIC122 code.

13 is an explanatory diagram of the BNF meta language used in FIG.

FIG. 14 is an explanatory diagram showing a specific example of encoding by QIC-122 code.

[Explanation of symbols]

10: Character input section (Q buffer) 12: Dictionary (P buffer) 14: Encoding unit (pattern matching unit) 16: Buffer memory 18: last character

   ─────────────────────────────────────────────────── ─── Continued front page    (72) Inventor Hirotaka Chiba             1015 Kamiodanaka, Nakahara-ku, Kawasaki City, Kanagawa Prefecture             Within Fujitsu Limited

Claims (6)

[Claims] 1. A coded character string is held in a dictionary 12, and a substring in the coded character string of the dictionary 12 having a maximum length matching the input character string of a character input unit 10 is searched, In a data compression method using a universal code for encoding with a set of a start position and a match length of the maximum length matching subsequence, a character 18 immediately preceding the input character string of the character input unit 10
And the matching subsequences S1, S2, S3, S4 of the coded character strings held in the dictionary 12 starting from the same first character are searched, and the maximum length matching subsequence S4 is searched, and the maximum length matching part is searched. An encoding unit 14 that encodes in combination with a match length by using the appearance order in which the preceding character of the maximum length matching subsequence S4 appears as the starting position when encoding the string S4.
A data compression method using a universal code. 2. The data compression method using a universal code according to claim 1, wherein the encoding unit 10 searches the dictionary 12 for a substring of an encoded character string having a maximum length match. First character 1
If the continuous character string S2 is 8, the continuous character string S2
A data compression method using a universal code, characterized by assigning the order of appearance of the beginning position or the end position of and encoding in a set with the matching length. 3. The data compression method using a universal code according to claim 1, wherein the encoding unit 10 searches the dictionary 12 for a substring of an encoded character string having a maximum length match. First character 1
If the continuous character string S2 is 8, the continuous character string S
A universal code is used in which two appearance orders of the start position and the end position of 2 are assigned, and the appearance order of both the start position and the end position of the continuous character string S2 is encoded as a set with the matching length. Data compression method. 4. The data compression method using the universal code according to claim 1, wherein the encoding unit 14 determines that the number of characters of the substring of the maximum matching length of the encoded character string of the dictionary 12 to be encoded is When the number of characters is less than a predetermined value, the input character string is output as it is without encoding, and when the number of characters is more than a predetermined value, it is encoded by a combination of the order of appearance and the matching length. Compression method. 5. A data compression method using a universal code according to claim 1 or 4, wherein said encoding unit 14 has a maximum matching length portion of an encoded character string of a dictionary 12 for encoding. When the number of characters in the column is small,
A data compression method using a universal code, characterized in that encoding is performed with a combination of a start position of the subsequence and a matching length, and when there are a large number of characters, encoding is performed with a combination of an appearance order and a matching length. 6. A data compression method using a universal code according to any one of claims 1 to 5, wherein the encoding unit 14 uses a standard compression method of an input character string for a 1/4 inch cartridge magnetic tape. A certain QIC-12
A data compression method using a universal code, which is characterized by encoding into two codes.