JPH0832454A - Data coding and decoding system - Google Patents

Abstract

(57) [Abstract] [Purpose] To speed up the decoding process of LZ code [Configuration] If the memory address unit is 1 byte and each character is a 1-byte data string consisting of a series of characters, a new The contents of the data string (new data string) and the previous data string (history data string) are compared, and if there is no match of two characters or more, the reference identifier is stored in the first buffer 6a and the new data string The first character is stored in the second buffer 6b as non-reference data. If there is a match of two or more characters, the history reference identifier is stored in the first buffer 6a, a history reference index indicating the position and length of the matching character string in the history data string is generated, and the second history reference index is generated. Store in buffer 6b. Then, the identifier obtained by the next similar comparison is added to the history reference index in the second buffer 6b so that the history reference index and the identifier become data of an integral multiple of 1 byte. .

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a system for compressing and encoding programs and data of an information processing device at high speed.

[0002]

2. Description of the Related Art As an algorithm for compressing and coding a data string such as a program or text of an information processing device in a form in which original data can be completely decoded, "IEEE Transa
ctionson Information Theory "Vol.IT-23, N
O.3, pp.337-343, by J. Ziv and A. Lempel, "A Universal Algorithm for Sequential D"
It is known that the method described in "ata Complession" is effective. This will be briefly described below.

The coding procedure according to this method is as follows.

First, the input data string is sequentially stored in a buffer. Such a data string on the buffer is called a history data string. Timing varies depending on the method,
When the history data string is accumulated in the buffer to some extent,
Further, the input data string (hereinafter referred to as a new data string) is compared with the history data string, and A) a data string (partial data string) that matches the contents from the beginning of the new data string is included in the history data string. If it exists, this is referred to as “history reference”, and the length of the data that matches the identifier (hereinafter, referred to as history reference identifier) indicating this and the index (hereinafter referred to as reference position index) indicating the position of the partial data string A code (hereinafter, referred to as a history reference index) including an index indicating the length (hereinafter, referred to as a reference length index) is generated and stored in the compressed data storage unit in the order of the history reference identifier and the history reference index.

B) If there is no partial data string in the history data string that matches the contents from the beginning of the new data string,
This is called "non-reference", and an identifier indicating this (hereinafter, referred to as non-reference identifier) is generated, and the first character (or 1 byte) of the new data string is used as a code (referred to as non-reference data). The reference identifier and the non-reference data are stored in the compressed data storage means in this order.

In this way, every time the new data sequence and the history data sequence are compared, the compressed data storage means additionally stores the identifier and the code, and the buffer stores them in the compressed data storage means. A new data string corresponding to the code is stored following the history data stored so far to become new history data. As a result, the newly added history data string is also compared with the new data string, but when the buffer capacity is full, the new history data string is added and the old history data string is excluded.

The above identifier and history reference index are composed of short codes. The part of the new data string whose contents match the partial data string in the history data string is replaced with the identifier and the history reference index. As a result, the part of the input data string whose content matches the partial data string is compressed as a redundant part, and therefore,
The new data string will be compressed and encoded.

The decoding process of such compressed data is as follows.

A buffer for holding history data of the same size as that in the encoding process is provided in advance. First, the identifier for the first code is read from the compressed data storage means storing the above compressed data, and this identifier is not referenced. If it is an identifier, the data for one character following this is read from the compressed data storage means and stored in the decompressed data storage means, and is also stored as a history data string in the buffer holding the history data.

If the above-mentioned read identifier is a history reference identifier, the history reference index following it is read from the compressed data storage means, and the information content indicated by the reference position index and the reference length index of the history reference index is stored in the buffer. The corresponding partial data string of the history data is read and stored in the decompressed data storage means, and is also stored as a new history data string following the history data string already stored in this buffer.

The above operation is repeated for all the compressed data in the compressed data storage means, whereby the compressed data is decoded.

With regard to the structure of the history reference index, an optimum bit length can be selected according to the redundancy of data to be compressed. For example, considering the case where the history reference index is expressed in a fixed-length binary, when compressing data with high redundancy such as the program source code and the length of the partial data string exceeds 9 bytes, By allocating 12 bits to the reference position index of the history reference index and 4 bits to the reference length index, the compression rate can be increased. Also, the redundancy is not so high as in the execution program code,
The reference position index is set to 1 when compressing data in which the length of the partial data string rarely exceeds 9 bytes.
If the reference length index is composed of 1 bit to 10 bits and is composed of 3 bits, the compression rate becomes high.

As described above, a method of holding the appearance pattern of data in a buffer and comparing it with an input data string for encoding is generally called a sliding dictionary method or an LZ encoding method, and refers to a history. Various methods have been proposed depending on the method and the configuration of codes.
The feature of this method is that the decoding process is simple.Therefore, the program code, initial values of data, menu screen data, etc. that are not normally changed are compressed and stored by this method, and are decrypted at the time of execution. It is suitable for applications such as use.

[0014]

By the way, the individual code in the compressed data encoded in this way has a length different from the byte unit or the character unit in the original data. In the conventional technology, such codes are sequentially stored in a single compressed data storage means in the order of generation. Also,
The code of the compressed data is decompressed and decoded in the same sequential manner.

A conventional technique for obtaining compressed data in the LZ encoding system will be described below with reference to FIG. However, FIG. 5A shows compressed data, FIG. 5B shows decompressed data (hence, original data), and FIG.
In (b), the non-reference identifier 10, the non-reference data 11, the history reference identifier 12, the history reference index 13, and the history copy data described later are distinguished by patterns.
The target table with these patterns is also shown.

It should be noted that one division in FIG. 5 (a) is 8 bits, and one division in FIG. 5 (b) represents an 8-bit character. The numbers circled are non-reference data 11.
It shows the order of.

When the data in FIG. 5B is the original data, the characters indicated by the delimiters are the first character, the second character, the third character, ... In this example, it is assumed that the third character and the seventh character have the same content as the first character and the fourth character, the sixth character, and the eighth character have the same content as the second character. The characters that are not the same in content as the previous character are the first character, the second character, and the fifth character. Characters that have the same contents as the previous characters are shown in white and circled numbers attached to the characters that have the same contents.

Here, assuming that each identifier is 1 bit and the history reference index is 14 bits, when such input data string (original data) is LZ-encoded, the original data shown in FIG. The compressed data is as shown in (b).

That is, since the first character and the second character have no preceding characters, the non-reference data 11
Therefore, the non-reference identifier 10 is added immediately before each of them. Therefore, the 1-bit non-reference identifier 10 is added to these characters and the 8-bit non-reference data 11 for the characters to become 9-bit data.

The third character and the fourth character are 1
Since the contents of the first character and the second character are the same, the history reference index 13 (which shows the same contents as the first character and the second character for these two characters) In FIG. 5A, a symbol A is formed, and a 1-bit history reference identifier 12 is added to the head of the symbol. Here, if the history reference index 12 consists of 14 bits, the 16-bit data of the third character and the fourth character is 14 + 1 = 1.
This means that the data has been compressed into 5-bit data.

The fifth character in FIG. 5 (b) is the non-reference data 11, and a 1-bit non-reference identifier 10 is added as shown in FIG. 5 (a). The 6th character, 7th character, and 8th character have the same contents as the 2nd character, 1st character, and 2nd character, respectively, so a 14-bit history reference index for these 3 characters 1
3 is formed, and a 1-bit history reference identifier 12 is added, as indicated by a symbol B in FIG.
In this case, the 24-bit data of three characters is compressed into the 15-bit data.

By the way, in the case of compressed data as shown in FIG. 5A, if it is divided into 8 bits, the non-reference data 1
This is a category that is not related to the category of 1 or the history reference data 13. For example, the first 8-bit division consists of 1-bit non-reference identifier 10 and 7 bits of non-reference data 11 for a character, and the next 8-bit division is 1 bit and 1 bit of non-reference data 11 for a character. Of the non-reference identifier 10 and 6 bits of the non-reference data 11 for the character. On the other hand, access to the memory is performed in address units, and the address unit is 8 bits or 16 bits. If the address unit is 8 bits, for example, the character and the non-reference data 11 for the character will be stored over two address units.

As described above, in the compressed data shown in FIG. 5A, the correspondence between the non-reference data 11 and the history reference index 13 and the address in the memory becomes very complicated, and the desired non-reference data is stored in the memory. When reading the reference data 11 and the history reference index 13, it is necessary to perform indexing in corresponding address units and cutting out corresponding portions.

Here, the compressed data shown in FIG.
The number of addresses (access capacity) required when writing to a memory whose address unit is 1 byte (8 bits) and reading the identifier, non-reference data, and history reference index in the order shown in FIG. , As shown in Table 1 below.

[0025]

[Table 1]

In Table 1, for example, when the first non-reference identifier 11 is read, this non-reference identifier 11 is 1
Since it is a bit (the number of acquired bits is 1), only one address is needed, and the access capacity in this case is 1 byte. Further, when reading the non-reference data 11 for a character, two addresses are required for the 8-bit non-reference data 11, and therefore the access capacity is 2 bytes. The same applies when the non-reference data 11 for a character is read. 14-bit history reference index 13
When reading out, as is clear from FIG.
Since three addresses are required, the address capacity is 3 bytes. In this way, in order to read the compressed data shown in FIG.
While the total access capacity is 17 bytes (= 136 bits), the access capacity is double or more.

Moreover, in reading out non-reference data or history reference index, it is necessary to cut out or combine data over a plurality of bytes (a plurality of addresses). For example, in order to obtain the non-reference data 11 for the character in FIG. 5A, since the non-reference data spans two addresses, each address is read and the read data of each address is read. It is necessary to cut out the portion of the non-reference data 11 and combine the cut-out portions. Since such processing is required, it takes a very long time to obtain these non-reference data and history reference index.

In the past, the history data for performing the decoding process was held in the buffer, but the history data must be updated as the decoding process progresses, which also results in processing time. There was a problem of this.

It is an object of the present invention to provide a data encoding and decoding system which solves the above problem and is capable of decoding compressed data at high speed.

[0030]

In order to achieve the above object, the present invention compares input data consisting of a character string with a character string input before and determines whether or not there is a character string having the same content. Is generated and an identifier representing the determination result is generated, and if there is no character string with the same content previously, the first character of the input data is made non-reference data, and if there is, the oldest character with the same content is used. An index (history reference index) that represents the position and length of the column is generated, and is obtained in this way when the data is compressed so that the history reference index is shorter than the original character string. The compressed data is composed of first data composed of an array of only identifiers in the input order, and second data composed of non-reference data and history reference indexes arrayed in the input order.

Further, according to the present invention, when the length of the history reference index is not an integral multiple of the length of the non-reference data, the history reference is made to the identifier of the character string following the original character string for this history reference index. Add to index.

[0032]

Since the identifier indicates the non-reference data or the history reference index, the number of bits can be less than or equal to the number of bits in the memory address unit. Therefore, the first data is stored in the memory. In this case, it becomes possible to store one identifier at each address of the memory. Also, if the length of the history reference index is an integral multiple of the length of the non-reference data, the second data can be delimited by the length of the non-reference data, and the length of the non-reference data can be stored in the memory. When the second data is stored in the memory by setting the number of bits in the address unit of, the non-reference data is stored only at one address in the memory, and the non-reference data is stored in the plurality of addresses in the memory. Only the history reference index of can be stored. As a result, when decompressing the data, when reading the compressed data from the memory, the identifier and non-reference data can be read by accessing one address, and furthermore, the identifier and non-reference data itself can be obtained by such access. . Further, when reading the history reference index, it is necessary to access multiple addresses, but since the length of the history reference index is set to be short from the viewpoint of data compression, the number of addresses to be accessed is also small. Moreover, the history reference index itself can be obtained by such access.

The length of the history reference index depends on how much of the character string that has already been input to be compared with the input character string is to be targeted. Becomes very long, and unless the character string to be replaced with the history reference index is very long, the effect of data compression does not appear, and it becomes impossible to perform data compression for a short character string. Since the length of the history reference index is determined from the above, the length of the history reference index is not always an integral multiple of the length of the non-reference data. In such a case, the present invention adds the identifier obtained for the next character string to the history reference index, as described above, so that the length of an integer multiple of the length of the non-reference data is added. Can be data.

[0034]

Embodiments of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing an embodiment of an encoding system and a decoding system according to the present invention, in which 1 is a CPU (arithmetic processing unit), 2 is a ROM (read only memory), and 3 is an RA.
M (random write / read memory), 4 is a system bus.

In the figure, CPU 1, ROM 2 and RA
The M3 and the M3 are connected to each other by the system bus 4, and data is exchanged between them via the system bus 4. The CPU 1 performs arithmetic processing based on the programs and data stored in the ROM 2 and the data stored in the RAM 3, and stores the arithmetic result in the RAM 3.

The ROM 2 stores a compression processing program 2A, a decompression processing program 2B, a management program 2C, an arithmetic processing program 2D, and arithmetic processing data 2E. The management program 2C is for performing initial processing after power is turned on, and when performing compression / expansion processing, it activates the compression processing program 2A or the expansion processing program 2B. The arithmetic processing program 2D is for performing arithmetic processing, and the arithmetic processing data 2E
Is used to perform this arithmetic processing, and is stored in a compressed form by the compression processing program 2A.

The RAM 3 is provided with a history buffer 5 used when performing compression processing, a compressed data storage buffer 6 that holds the result of compression, and an expanded data storage buffer 7 that holds expanded data, and an output destination control flag. 8 and an identifier acquisition flag 9 are stored. The compressed data storage buffer 6 further includes a first compressed data storage buffer 6
a and the second compressed data storage buffer 6b.

The history buffer 5 has a capacity of 2048 bytes, holds data by a FIFO (First In First Out), and when new data is read, the oldest data is erased in order.

Here, the compression code used in this embodiment is composed of the following four, as in the above-mentioned prior art. 1) Non-reference identifier 10 2) Non-reference data 11 3) History reference identifier 12 4) History reference index 13.

The non-reference identifier 10 and the history reference identifier 12 are composed of 1 bit. The former is "1" and the latter is "0". As in the case of the above-described conventional technique, the non-reference data 11 is data that does not match any partial data string in the history buffer 5, and is composed of 8 bits. The history reference index 13 is composed of 15 bits, and the 11-bit position index that indicates how many bytes before the new data string the content of the new data string starts and the contents match the new data string. A 4-bit length index indicating the data length of the partial data string to be processed is combined. The following Table 2 shows the correspondence between the position index and length index values and the actual reference position and reference length.

[0041]

[Table 2]

Unlike the other position indexes, the position index with the value 0 is used as the end code of the compressed data. When the decompression processing program 2B acquires the position index of this value 0, the processing ends. In the length index, the reference length is 2 bytes, but the value of the reference length index is 0. The length of 2 bytes is the minimum reference length, and a 4-bit length index can be used efficiently. This is because the reference length index of value 0 corresponds to a reference length of 2 bytes, and the reference length index of value 15 corresponds to a length of 17 bytes for use.

As will be described in detail later, in the compression processing by the execution of the compression processing program 2A, as in the above-described conventional technique, the compression processing program 2A determines whether or not the history data string on the history buffer 5 is compared with the new data string. The reference identifier 10 and the non-reference data 11 or the history reference identifier 12 and the history reference index 13 are obtained, and these are supplied to the compressed data storage buffer 6 and recorded. In the compressed data storage buffer 6a,
The non-reference data 11 and the history reference index 13 are second
Are stored in the compressed data storage buffer 6b.

Further, as will be described later in detail, in the decompression processing by executing the decompression processing program 2B, the identifiers 10 and 12 are stored in the first compressed data storage buffer 6a and the identifiers 10 and 12 are not stored in the second compressed data storage buffer 6b. The reference data 11 and the history reference index 13 are stored respectively. First, the identifier is read from the first compressed data storage buffer 6a, and the contents (“1” for the non-reference identifier 10 and “for the history reference identifier 12”) are read. 0 "), it is determined whether the data read from the second compressed data storage buffer 6b is the non-reference data 11 or the history reference index 13.

In the following description, the output or reference (judgment) of "1" for the identifier indicates the output or reference (judgment) of the non-reference identifier 52, and the output or reference (judgment) of "0" refers to the history. The output and reference (judgment) of the identifier are shown.

Next, the operation of this embodiment (processing operation of the CPU 1) will be schematically described with reference to FIG. Here, FIG. 5B shows the original data string, which is the same as the data string shown in FIG. 5B. Further, FIG. 2A shows compressed data of this original data string. In addition, here, in order to simplify the description, the number of bits of one character is 8 bits (1 byte), and the history reference index is 1
It is 5 bits. However, the present invention is not limited to this. The original data string shown in FIG.
When the compression processing is performed by A, it is determined whether or not there is a partial character string in which the contents of two or more characters of the data are the same in the history data already stored in the history buffer 5, and the first character and the second character If the second character is negative, these become non-reference data 11 respectively, and a non-reference identifier 10 of "1" is generated for each. Then, these non-reference identifiers 10 are sequentially stored in the first compressed data storage buffer 6a, and the non-reference data 11 for the character and the second character are also stored in that order in the second compressed data storage buffer 6b.

Next, since the character string consisting of the third character and the fourth character in FIG. 2 (b) has the same content as the character string consisting of the first character and the second character, On the other hand, a history reference identifier 12 of "0" and a history reference index 13 of 15 bits are generated, the history reference identifier 12 is stored in the first compressed data storage buffer 6a, and the history reference index 13 of 15 bits is stored in the second compressed data. The non-reference identifier 10 and the non-reference data 11 respectively stored in the data storage buffer 6b are sequentially stored, but when the history reference index 13 is generated, the fifth character following the third character and the fourth character is stored. Since the non-reference identifier 10 and the non-reference data 11 always correspond to the character of, the non-reference identifier 11 corresponding to the fifth character is also generated in the same manner and the lowest in the history reference index 13. Added as Tsu DOO, second with a history reference index 13 to 16 bits (= 2 bytes)
Stored in the compressed data storage buffer 6b. Then, for the next fifth character, only the non-reference data 11 is generated and stored in the second compressed data storage buffer 6b.

In this way, when the content of the new data string of two or more characters does not match the partial data string of the history data string, the character-by-character non-reference data 11 is stored in the second compressed data storage buffer 6b. While storing, the non-reference identifier 10 is generated for each non-reference data 11 and is stored in the first compressed data storage buffer 6a, but a new data string of two or more characters is a partial data string of the history data string and its contents. If they match, the history reference identifier 12 is generated and
Stored in the compressed data storage buffer 6a, and the non-reference identifier 10 for the next non-reference data 11 is added to the history reference index 13 to form 2-byte data.
This is stored in the second compressed data storage buffer 6b.

Here, when the contents of a character string of two or more characters match, the history reference index 13 is used because the number of bits of the history reference index 13 is 15 bits, rather than the number of bits of one character. This is because it is large and smaller than the character string of two characters, and if the history reference index 13 is used for one character, the number of bits is rather increased and data compression is not performed.

As described above, in the second compressed data storage buffer 6b, as shown in FIG. 2 (a), when divided by 1 byte, non-reference data 11 is divided by 1 and history reference index 13 is divided by 2. You can get compressed data that is divided into bytes. Second for storing such compressed data
If the address unit of the compressed data storage buffer 6b is 1 byte, each non-reference data 11 can be stored at 1 address, and the history reference index 13 can be stored at 2 addresses. The different non-reference data 11 are not stored at the same time, and the non-reference data 11 and the history reference index 13 are not stored simultaneously at one address.

The first compressed data storage buffer 6a
Also has an address unit of 1 byte, and up to eight identifiers are stored in sequence, one for each address.

When decompressing the compressed data string shown in FIG. 2A by the decompression processing program 2B, the first compressed data storage buffer 6a or the memory transferred from the first compressed data storage buffer 6a in the order in which the respective identifiers are compressed. Stored in the non-reference data 11 and history reference index 1
3 and the like are stored in the second compressed data storage buffer 6b or the memory moved from the second compressed data storage buffer 6b in the order of the compression processing, but here, the identifier is stored in the first compressed data storage buffer 6a and is not referenced. It is assumed that the data 11 and the history reference index 13 are stored in the second compressed data storage buffer 6b, respectively.

Next, the first compressed data storage buffer 6a
One identifier is read from the identifier, and the content of the 1-byte unit data corresponding to this identifier, which is read next from the second compressed data storage buffer 6b, is determined from the content of "1" or "0" or its content. . In the case of FIG. 2A, since the first identifier read is the non-reference identifier 10 of "1", the data read from the second compressed data storage buffer 6b is the non-reference data 11, which is the first character. Is stored in the expanded data storage buffer 7. The same applies to the second character.

The first compressed data storage buffer 6a
The address unit is 1 byte, and therefore, 1 byte of data, that is, 8 identifiers are read from one address. In this embodiment, the eight identifiers are sequentially cut out and processed.

When the identifier read from the first compressed data storage buffer 6a is the history reference identifier 12 of "0", 2 bytes are read from the second compressed data storage buffer 6b. The history reference index 13 to which the non-reference identifier 10 of "1" is added as the least significant bit is read. The 1-bit non-reference identifier 10 and the 15-bit history reference index 13 are separated from the 2-byte data, and the non-reference identifier 10 is retained in the CPU 1 as it is. Further, the reference position and the reference length set as shown in Table 2 above are obtained from the history reference index 13, and based on this, the corresponding portion in the decompressed data stored in the decompressed data storage buffer 7 The data string is read and stored following the data already stored in the decompressed data storage buffer 7. In this case, assuming that the history reference index 13 is shown as a symbol A in FIG. 2A, the first character and the second character already stored in the decompressed data storage buffer 7 are read and 3 each
It is stored in the decompression data storage buffer 7 as the second character and the fourth character. In this way, the history reference index 13 is expanded, and the original third and fourth characters are obtained.

Next, the non-reference data 11 following the history reference index 13 indicated by the symbol A is judged by the non-reference identifier 10 which was obtained and held when the history reference index 13 was read previously, and the fifth Is stored in the decompression data storage buffer 7 as a character. Also, the following code B
The history reference index 13 indicated by is the same as that of the history reference index 13 indicated by the symbol A.

In this way, the same decompressed data as the original data shown in FIG. 2B is obtained in the decompressed data storage buffer 7.

In the decoding by such decompression processing,
When the memory storing compressed data, that is, the address unit of the second compressed data storage buffer 6b is 1 byte, the 1-byte non-reference data 11 can be read by one access, Therefore, the access time can be shortened, and the processing such as cutting and synthesizing the read data as in the above-described conventional technique is not necessary.

Also, the second compressed data storage buffer 6b
When the history reference index 13 is read from, the two addresses may be read consecutively, and the 2-byte data read from these may be simply connected. In this case, it is necessary to separate the 1-bit non-reference identifier 10 and the 15-bit history reference index 13 from the 2-byte data, because the non-reference identifier 10 is the least significant bit of the 2-byte data. It can be obtained by logically ANDing data in which only the least significant bit is “1” and the other bits are “0” in the 2-byte data and extracting the lower 1-byte portion. The history reference index 13 is obtained by right-shifting the data by 1 bit to the least significant bit side, which is a very simple process.

Corresponding to Table 1 above, the access capacity in the case of the example of FIG. 2 in this embodiment is shown in Table 3 below.

[0061]

[Table 3]

The compressed data shown in FIG. 2A is converted into FIG.
When the decompression process is performed as shown in (4), four identifiers are acquired (read) from the first compressed data storage buffer 6a by performing one byte unit access four times. The total access capacity of one compressed data storage buffer 6a is 4 bytes, and three non-reference data 11 are accessed from the second compressed data storage buffer 6b by performing one byte unit access three times. Since the two history reference indexes 13 are acquired (read) by performing the acquisition (reading) and the 2-byte unit access twice, the total access capacity of the second compressed data storage buffer 6b is 7 bytes. It is a byte. Therefore, the first compressed data storage buffer 6
Even if the access capacity in a is added, the conventional 1 shown in Table 1
As compared with 7 bytes, it is possible to perform decoding with a sufficiently small capacity of access, and therefore the time required for access can be greatly shortened.

Next, the operation of this embodiment will be described in more detail. First, the compression processing by the compression processing program 2A will be described with reference to FIGS. 1 and 3. In the following description, the unit of data whose contents are compared is 1 byte, and the 1-byte data is expressed as 1 character, similarly to the above, but it is obvious that the present invention is not limited to this.

When the compression processing program 2A is started,
First, the history buffer 5 is initialized (step 100),
Next, the output destination control flag 8 is set to "1" (step 101). The output destination control flag 8 indicates whether to store the non-reference identifier 10 or the history reference identifier 12 in the first compressed data storage buffer 6a or the second compressed data storage buffer 6b. When it is "1", it is instructed to store it in the first compressed data storage buffer 6a, and when it is "0", it is instructed to store it in the second compressed data storage buffer 6b.

Thereafter, the input data to be encoded in the history buffer 5 is for M characters (where M is an integer greater than 1).
Read (step 102). The reading source is given as a parameter from the management program 2C. Here, the length index of the history reference index 13 (see Table 2 above).
The maximum number of characters that can be expressed by
The character (17 bytes) is read into the history buffer 5. Further, the variable m is set to the value of M (step 103). This variable m indicates the length of the partial data string to be compared.

When the above process is completed, the process proceeds to a series of steps described below, but this process is repeated until there is no character string to be encoded. First, the latest m characters read into the history buffer 5 are compared with the data (history data string) previously read into the history buffer 5 (step 104) to obtain the longest matching character string. This comparison is achieved using standard methods. After this comparison, the matching character length is evaluated (step 105),
If two or more characters match, steps 106 to 115 are executed, otherwise step 116 to step 122 or step 123 are executed.

Here, whether or not there is a match of two or more characters is determined by the history reference index 13 having 15 bits, which is larger than the number of bits of one character (8 bits) and the data of one character is referred to as the history reference index. This is because the number of bits increases and the data compression does not occur, and the data must be at least two characters for data compression.

First, the case where two or more characters match will be described. The output destination control flag 8 is checked (step 106), and if it is "1", the history reference identifier 12 of "0" is stored in the first compressed data storage. Write to the buffer 6a (step 107). If the output destination control flag 8 is "2", write the history reference identifier 12 of "0" to the second compressed data storage buffer 6b (step 108). In either case, the output destination control flag 8 is set to 2 (step 109), and the relative distance between the matching character string and the comparison source character string is represented by 11 bits and the length is represented by a fixed length code of 4 bits. The history reference index 13 is written in the second compressed data storage buffer 6b (step 110).

Then, the length of the matched character string is compared with the length of the uncoded character string that has not been encoded yet (step 111). If the uncoded character string is longer, it matches variable C. The value of the character length is substituted (step 112), and if not, the value of the uncoded character length is substituted into the variable C (step 113). Then, the number of characters to be encoded is newly written in the history buffer 5 as the number of values of the variable C as a history data string (step 114), the value of the variable C is added to the variable m, and the value obtained by subtracting the matching character length is again obtained. The variable m is substituted (step 115).

If there is no match of two or more characters in step 105, the output destination control flag 8 is checked (step 11
6) If this is “1”, the non-reference identifier 1 of “1”
0 is written to the first compressed data storage buffer 6a (step 117), and if the output destination control flag 8 is "2", the non-reference identifier 10 of "1" is written to the second compressed data storage buffer 6b ( Step 118). Then, the output destination control flag 8 is set to 1 (step 11
9), the first 1 of the latest m characters on the history buffer 5
The character is written as the non-reference data 11 in the second compressed data storage buffer 6b (step 120). Then, it is checked whether or not the uncoded character length is larger than 0 (step 121). If it is larger than 0, one character of the data to be coded is read into the history buffer 5 (step 122),
If not, 1 is subtracted from the variable m (step 123).

As described above, steps 115 and 122
When the processes up to 123 are completed, it is checked whether or not the variable m is larger than 0 (step 124). If it is larger than 0, the process returns to step 104. Otherwise, the second compressed data storage buffer 6b stores The 15-bit history reference index 13 with the position index 0 shown in Table 2 above is supplied as the end code (step 12
5) The processing by the compression processing program 2A ends.

The compressed data (including the identifier) stored in the compressed data storage buffer 6b is moved to a storage location according to the purpose by the function of the management program 2C.
For example, when compressing and saving the calculation result, the management program 2C activates the compression processing program 2A with the storage location (not shown in FIG. 1) of the calculation result on the RAM 3 as the read source, and ends the compression processing program 2A. After that, the above contents of the compressed data storage buffer 6 are transferred to a data save location (not shown in FIG. 1) on the RAM 3.

Next, the operation of the decompression processing program 2B will be described with reference to FIGS. The management program 2C is
The two input source addresses of the first input and the second input are given to the decompression processing program 2B. These are the contents of the first compressed data storage buffer 6a and the second compressed data storage buffer 6 in the compression processing program 2A, respectively.
It corresponds to the contents of b. That is, the management program 2C
Decompresses the first compressed data storage buffer 6a or the data to which the contents have been moved as the first input, and the second compressed data storage buffer 6b or the data to which the contents have been moved as the second input. It is given to the processing program 2B.

When the decompression processing program 2B is activated,
First, the identifier acquisition flag 9 is set to the "unacquired" state (step 200). The subsequent processes described below are repeated until all the compressed data have been decoded. The identifier acquisition flag 9 is a flag indicating whether or not the CPU 1 (FIG. 1) has already acquired the next identifier, and when it is in the “unacquired” state, it has not been acquired yet and is in the “acquired” state. In the case of 1), the states already taken in and held are shown. In the latter case,
The CPU 1 then uses the retained identifier to execute the second
It is determined whether the data fetched from the input is non-reference data 11 or history reference index 13.

First, the identifier acquisition flag 9 is checked (step 201), and if it is set to the "unacquired" state, the identifier is fetched from the first input (step 202). Then, it is judged whether or not the content of this identifier is "0" (step 203), and if the history reference identifier 12 is "0", steps 204 to 209.
Otherwise (that is, if it is the non-reference identifier 10 and "1"), steps 212 to 214 are executed respectively.

Therefore, the case where the content of the identifier is "0" will be described. 2 bytes (2 characters) of data are fetched from the second input (step 204), and the 16th to 6th bits of the data are read. Cut out the bit as the position index of the history reference index 13 (step 2
05), the next 4 bits from the 5th bit to the 2nd bit are cut out as the length index of the history reference index 13 (step 206), and the last 1st bit (that is, the least significant bit) is set to the second bit. Non-reference data 11 or history reference index 13 that should be imported from
(Step 207).

Then, the identifier acquisition flag 9 is set to the "acquired" state (step 208), and it is checked whether or not the position index of the history reference index 13 is 0 (step 209).
If so, it is determined that the compression data has ended, and the processing by the decompression processing program 2B is ended. However, if this position index is not 0, the position index and length index of the history reference index 13 from the decompression data storage buffer 7 Capture the matching string represented (step 2
10), the matching character string is added to the end of the data stored in the decompressed data storage buffer 7 and written (step 211), and the process returns to step 201.

If it is determined in step 203 that the identifier is not "0", 1-byte data is extracted from the second input (step 212), and this is stored in the decompression data storage buffer 7 as one character. It is additionally written at the end of the existing character string and written (step 213). Then, the identifier acquisition flag 9 is set to the “acquired” state (step 214) and the process returns to step 201.

Next, taking the data shown in FIG. 2 as an example, the processing by the compression processing program 2A will be described with reference to FIGS. However, such data is sufficiently longer than 18 bytes.

In FIG. 3, when the compression processing program 2A is started, a series of processing from step 100 to step 103 shown in FIG. 3 is performed, and then step 10
At 4, the partial data strings are compared. As for the data of the first character of the first byte in FIG. 2B, the result of the comparison in step 104 is that there is no data read before the latest m characters in the history buffer 5, so there is no matching data, Go to step 116. At this time, since the output destination control flag 8 is set to 1 in step 101, the non-reference identifier 10 of "1" is output to the first compressed data storage buffer 6a (step 117) and the second compressed data is stored. The byte data corresponding to the first character is written in the storage buffer 6b as the non-reference data 11 (step 120). Here, since the original data to be compressed has a sufficient length, the judgment in step 121 is always "y", and one character, that is, the first character is read into the history buffer 5 (step 122) and step 12
Return to step 104 via 4, the second character,
That is, the processing of the data of the second byte is started.

Also for the second character, step 10
The determination of 4 indicates that there is no matching data, so step 116
Move to Here, since the output destination control flag 8 is set to 1 in the process of step 119 for the data of the first character, the process proceeds to step 117, and the non-reference identifier of "1" is stored in the first compressed data storage buffer 6a. 10 is written. Then, in step 120, the byte data corresponding to the second character is written as the non-reference data 11 in the second compressed data storage buffer 6b. Similar to the above,
The judgment in step 121 is “y”, and the history buffer 5
The second character is written in (step 122), and the process returns to step 104 via step 124 to process the data of the third character.

Since the data of the third character and the data of the fourth character match the first character and the second character, respectively, the comparison result of step 104 indicates that two or more characters match.
Go to step 106. Here, since the output destination control flag 8 is set to 1 in step 119 in the above processing of the data of the second character, the process proceeds to step 107 and the history reference identifier of "0" is stored in the first compressed data storage buffer 6a. 12 is written and the output destination control flag 8 is set to 2 (step 109). The history reference index 13 representing the position and length of the matched partial data string is the second
Is written in the compressed data storage buffer 6b (step 110). This is the symbol A in FIG. In this case, since the length of 2 bytes (that is, character,) from 2 bytes before the current processing data (that is, the data of the third character) is referred to, the position index of 2 in Table 2 and 0 The 15-bit code A combined with the length index of is written.

Since it is determined in the next step 111 that the data length is sufficiently long, the matching character string length of 2 is set in the variable C (step 112), and the third character and the fourth character are stored in the history buffer 5. It is additionally written as new history data (step 114). Then, although the value of the variable m is updated (step 115), the value of the variable C is the same as the value of the variable C to be added and the number of matching characters to be subtracted is the same. Then, via step 124, step 104
Return to and process the data of the fifth character.

For the data of the fifth byte (that is, the character data), the determination in step 104 indicates that there is no matching data, so the process proceeds to step 116. At this time,
Since the output destination control flag 8 is set to 2 in step 109 in the processing of the data of the third character and the fourth character,
The non-reference identifier 10 of "1" is written in the second compressed data storage buffer 6b (step 118), whereby the one-bit non-reference identifier 10 is added to the above-mentioned 15-bit history reference index 13 (code A). When added, it becomes 16-bit (2-byte) data. Then, the byte data corresponding to the character is supplied to the second compressed data storage buffer 6b (step 120). Then, similarly to the above, the determination in step 121 is "y", and one character is newly read into the history buffer 5 (step 122),
The process returns to step 104 via step 124 to move to processing the data of the sixth character.

Since the contents of the data of the 6th to 8th characters match the contents of the 2nd to 4th characters, the comparison result of step 104 shows that two or more characters match, and the routine proceeds to step 106. At this time, since the output destination control flag 8 is set to 1 in step 119 in the processing of the fifth character data, the history reference identifier 12 of "0" is written in the first compressed data storage buffer 6a. (Step 107). Then, the output destination control flag 8 is set to 2 (step 1
09), the history reference index 13 representing the position and length of the matched partial data string is output to the second compressed data storage buffer 6b (step 110). This is Figure 2
It is the code B in (a). In this case, since the length of 3 characters (3 bytes) from 4 characters (4 bytes) before the current processing data is referred to, the history reference index 13 has a position index of 4 and a length index of 1. Next, since it is determined in step 111 that the data length is sufficiently long, the number of characters of the matching character string is set to the variable C (step 112), and the 6th to 8th three characters are written in the history buffer 5 (step 114). ). And step 11
Although the value of the variable m is updated by 5, the value of the variable m remains unchanged because the value of the variable C to be added and the number of matching characters to be subtracted are the same. After that, the process returns to step 104 via step 124, and the processing of the data after the ninth character is performed.

As a result of the above processing flow, FIG.
The compressed data as shown in (a) is the first compressed data storage buffer 6a and the second compressed data storage buffer 6b, respectively.
Can be obtained.

Next, a process for generating the decompressed data (original data) shown in FIG. 2B from the compressed data shown in FIG. 2A will be described with reference to FIGS. 1 and 4.

Here, the series of identifiers are stored in the first compressed data storage means 6a in FIG. 1, and the series of non-reference data 11 and history reference index 13 are stored in the second compressed data storage means 6b. Assuming that data is stored, the decompression processing program 2B is activated with the former as the first input and the latter as the second input.

Therefore, first, the identifier acquisition flag 9 is set to the "unacquired" state in step 200, and as a result of the determination in step 201, the process proceeds to step 202 and the identifier is read from the first compressed data storage means 6a. . Figure 2
In the example of (a), since the first identifier is the non-reference identifier 10 of "1", as a result of the determination in step 203, the process moves to step 212 and the first non-reference is made from the second compressed data storage means 6b. The data 11 is read and written as the first character in the expanded data storage buffer 7 (step 213). Then, the identifier acquisition flag 9 is set to the "unacquired" state (step 214), and the process returns to step 201 to proceed to the expansion processing of the next code.

In the next code decompression process, step 214
Since the identifier acquisition flag 9 has been set to the “unacquired” state in step 1, the result of the determination in step 201 is similar to the above.
Moving to step 202, the first compressed data storage means 6
Read the identifier from a. In FIG. 2A, the second identifier is also the non-reference identifier 10 of “1”, and as a result of the determination in step 203, the process moves to step 212 and the second compressed data storage means 6b is used to store the second identifier. Non-reference data 1
1 is read and this is written in the decompression data storage buffer 7 as the second character (step 213). Then, the identifier acquisition flag 9 is set to the "unacquired" state (step 214), and the process returns to step 201 to move to the next code decompression process.

Further, in the next code decompression process, since the identifier acquisition flag 9 is set to the "unacquired" state in step 214 as described above, the result of the judgment in step 201 is First move to 202
The identifier is read from the compressed data storage means 6a. Figure 2
In (a), since the third identifier is the history reference identifier 12 of "0", as a result of the determination in step 203, the process shifts to step 204 and the 2-byte data is read from the second compressed data storage means 6b. . In the example of FIG. 2A, the part indicated by the symbol A and the following 1 of the non-reference identifier 10
The bits are read together and steps 205-207
A history reference index 13 having a position index of 2 and a length index of 0 and a non-reference identifier 10 of "0" (this is the identifier of the next fourth process) are obtained. Then, the identifier acquisition flag 9 is set to the "acquired" state (step 208). In the next determination in step 209, since the position index is not 0 as described above, the process moves to step 210, and the length index of 0 indicates that the last 2 of the data in the expanded data storage buffer 7 is
2 bytes of data before the byte (that is, characters and characters in the range shown as "reference range of A" in FIG. 2B)
Are added to the end of the data in the decompressed data storage buffer 7 as history copy data. Then, the process returns to step 201, and proceeds to the decompression process of the next code.

In the processing of the next code, the identifier acquisition flag 9 is "acquired" in step 208 in the processing one time before.
Since the state is set, the process proceeds to step 203 as a result of the determination in step 201. In the example of FIG. 2A,
Since the fourth identifier acquired in step 207 in the process one time before is the non-reference identifier 10 of “0”, as a result of the determination in step 203, the process moves to step 212 and the second compressed data storage means 6b The non-reference data 11 is read from the decompressed data storage buffer 7 as the fifth character.
(Step 213). Then, in step 214, the identifier acquisition flag 9 is set to the “unacquired” state, the process returns to step 201, and the process for expanding the next code is started.

In the next decompression process, the identifier acquisition flag 9 is set to the "unacquired" state, so step 201
As a result of the determination, the process proceeds to step 202 and the identifier is read from the first compressed data storage means 6a. In the example of FIG. 2A, the fifth identifier is the history reference identifier 12 of “0”.
Therefore, as a result of the determination in step 203, step 2
In step 04, the 2-byte data is read from the second compressed data storage means 6b. In the example of FIG. 2A, the code B
1 of the non-reference identifier 10 adjacent to the part indicated by
The bits are read together. And step 20
In steps 5 to 207, the history reference index 13 with the position index 4 and the length index 1 and the non-reference identifier 10 with "1" are obtained. Next, the identifier acquisition flag 9 is set to the “acquired” state, and the position index is not 0 in the determination of step 209.
0, and 3 bytes from the last 4 bytes before the end of the data of the decompressed data storage buffer 7 indicated by the history reference index 13 (non-reference in the range indicated as “reference range of B” in FIG. 2A) The character which is the data 11 and the character which is the history copy data are fetched and added as the sixth, seventh and eighth characters to the end of the data of the decompression data storage buffer. Then, return to step 201,
Further, the process proceeds to the next code decompression process.

As described above, in this embodiment, when decoding the compressed data, the non-reference data 11 and the history reference index 13 can be accessed and read in byte units from the memory. Also, since the identifier is a 1-bit code, it does not extend over a plurality of bytes as in the case of cutting out a code of a plurality of bits and can be easily read. Therefore, high-speed decompression processing can be realized.

In the above description, the input / output unit is 1
Although the byte or 1 bit is used, the encoding and decoding method according to the present invention can be applied to any number of bits as long as it is a memory boundary that can be accessed at high speed. The number of bits of the identifier may be 1 bit or more.
In this case, the history reference index may be composed of the number of bits given by (memory boundary × n) − (number of bits of identifier) (1).

Further, for example, as in the case of the data with high redundancy described above, the position reference index is 12 bits, the length index is 4 bits, and the history reference index has a 16-bit structure which is twice as large as the non-reference data. In this case, it is not necessary to add the identifier of the next character string to the history reference index as described above.

Further, as shown in FIG. 1, in the second compressed data storage buffer 6b, data whose history cannot be referred to, in other words, non-redundant data in the input data are recorded in the order of appearance. Therefore, when compressing data consisting of character strings that do not include any redundancy, only the non-reference identifiers 10 are stored in the first compressed data storage buffer 6a in the same number as the number of compressed data, and in the second compressed data storage buffer 6a. The input data itself is stored in the compressed data storage buffer 6b.

[0098]

As described above, according to the present invention,
Two types of memory access for decoding the code, 1-bit access and 1-character unit access, can be performed at extremely high speed, and the history itself during decompression processing is decompressed data itself. , The history buffer is unnecessary, and the processing is simplified and speeded up.

[Brief description of drawings]

FIG. 1 is a block diagram showing an embodiment of an encoding and decoding system according to the present invention.

FIG. 2 is a diagram showing a specific example of compressed data and decompressed data (original data) in the embodiment shown in FIG.

FIG. 3 is a flowchart showing a flow of a compression processing program in FIG.

4 is a flowchart showing a flow of a decompression processing program in FIG.

FIG. 5 is a diagram showing a specific example of compressed data and decompressed data (original data) in a conventional encoding and decoding method.

[Explanation of symbols]

 1 arithmetic processing unit 2 read-only memory 2A compression processing program 2B decompression processing program 2C management program 2D arithmetic processing program 2E arithmetic processing data 3 occasional writing / reading memory 4 system bus 5 history buffer 6 compressed data storage buffer 6a first compressed data storage Buffer 6b Second compressed data storage buffer 7 Decompression data storage buffer 8 Output destination control flag 9 Identifier acquisition flag 10 Non-reference identifier 11 Non-reference data 12 History reference identifier 13 History reference index

Claims (5)

[Claims] 1. A sequentially input character string is stored in a memory, a partial character string that appears repeatedly a plurality of times is searched in the stored character string, and a partial character string of the same content that appears after the second time is searched. Is converted into a code indicating the first partial character string of the same content and compressed, and an uncompressed partial character string and an identifier are generated for each code, and the uncompressed partial character string and the partial character string are specified. A data coding method, wherein data in which codes are arranged in an input order and data in which the identifiers are arranged in a generation order are separately output. 2. A history buffer for accumulating sequentially input character strings, compressed data storage means for storing in one character data boundary units, decompressed data storage means for storing in one character data boundary units, and The character string input to is compared with the character string in the history buffer, and when there is a character string that matches two or more characters, the history reference identifier and the newly input character string in the history buffer that match A history reference index indicating the position and length of a partial character string in the character string is generated and additionally stored in the compressed data storage means, and when there is no character string that matches two or more characters, the newly input character string The process of generating the non-reference identifier by adding the first character of the non-reference data to the non-reference data and additionally storing the non-reference data and the non-reference identifier in the compressed data storage means is repeated. Then, compression processing means for obtaining compressed data consisting of a history reference identifier, a non-reference identifier, a history reference index, and non-reference data in the compressed data storage means, and an identifier of the compressed data, and the captured identifier Is a non-reference identifier, the data corresponding to one piece of the non-reference data is fetched from the compressed data and additionally stored in the decompressed data storage means as one character data, and the identifier fetched from the compressed data is the history reference identifier. At some time, data of one history reference index is fetched from the compressed data, and based on the content, a partial character designated by the history reference index in the character string already stored in the decompressed data storage means. Data encoding and decoding having decompression processing means for taking in a column and additionally storing it in the decompressed data storage means In the method, the compressed data storage means comprises first and second compressed data storage means, and the compression processing means stores the history reference identifier and non-reference identifier in the first compressed data storage means. A data encoding and decoding method, wherein the history reference index and non-reference data are stored in the second compressed data storage means. 3. The compression processing means according to claim 2, wherein the second compressed data storage means generates an identifier generated for a partial character string following the partial character string converted into the history reference index, A data encoding and decoding method, wherein the data length of the history reference index added to the history reference index is stored, and the data length of the history reference index added with the identifier is an integral multiple of the data length of the non-reference data. 4. The method according to claim 2, wherein an instruction to output the identifier to the first compressed data storage means is issued in the first state, and an identifier is output to the second compressed data storage means in the second state. Is provided, and an identifier acquisition flag indicating whether the identifier is “acquired” or “not acquired” is provided, and the compression processing means sets the output destination control flag to the first when the compression processing is started. When there is no partial character string that matches the input character string in the character string on the history buffer during compression processing, the non-reference is made according to the state of the output destination control flag. After storing the identifier in the first or second compressed data storage means, the output destination control flag is set to the first state, and a character string input in the character string on the history buffer during compression processing. Is a substring that matches two or more characters with When the output destination control flag is set, the history reference identifier is stored in the first or second compressed data storage means according to the state of the output destination control flag, and then the output destination control flag is set to the second state. The processing means has a holding means for holding the identifier fetched from the first or second compressed data storage means, and when the decompression processing is started, the identifier acquisition flag is set to “not acquired”.
When the identifier acquisition flag is in the “unacquired” state, the identifier is fetched from the first compressed data storage means and held in the holding means, and when the identifier is a non-reference identifier, the second 1 byte is taken from the compressed data storage means as the decoded data, stored in the decompressed data storage means, the identifier acquisition flag is set to the “unacquired” state, and the identifier held in the holding means is the history reference identifier. Is held, the identifier separated from the history reference index fetched from the second compressed data storage means is held in the holding means, the identifier acquisition flag is set to the “acquired” state, and the identifier acquisition flag is set. Is in the “acquired” state, the second pressure depending on the content of the identifier held by the holding means. Data encoding and decoding method of the data storage means and performs acquisition of data. 5. The decompression processing means according to claim 2, 3 or 4, wherein the decompression data storage means decompresses a partial data string based on a position and a length designated by the history reference index fetched from the compressed data. Data encoding and decoding method, characterized in that the data is captured and stored continuously at the end of the data string in the decompressed data storage means.