JPH07135471A - Data compressor and data expander - Google Patents

Abstract

PURPOSE:To obtain a data compressor and a data expander in which a data string received sequentially is processed in real time and data are compressed/ expanded while keeping a high compression rate at all times. CONSTITUTION:The data compressor includes a data buffer 10, a dictionary buffer 12, a buffer update section 14, a coincidence length coding section 16, a position coding section 20, a sequence coding section 24 and a table update section 28. The coincidence length coding section 16 checks a character string in the data buffer 10 from the head and compares the character string with that in a dictionary, and encodes and outputs the coincident length. When a coincident character string is in existence in the dictionary, the position coding section 20 encodes an address in the dictionary and provides a coded address as an output. When no coincident character string is in existence in the dictionary, the sequence coding section 24 applies coding of a shorter bit length to a head character with a higher frequency of incidence.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention compresses data stored in a digital storage device such as a magnetic disk or IC memory in a general computer system, or expands data read from these digital storage devices. The present invention relates to a data compression device and a data decompression device.

[0002]

2. Description of the Related Art In recent years, the processing contents of computer systems have been diversified with the increase in speed and performance of microprocessors, and the amount of data to be handled has also increased rapidly. Particularly in recent years, image processing for still images and moving images has become popular, and the amount of data to be handled when performing such image processing becomes enormous compared to conventional character data. Therefore, when storing this huge amount of image data in, for example, a hard disk device, a method is known in which data is compressed as a pre-process and the compressed data is stored in the hard disk device. When reading data, the compressed and stored data is read and then expanded, and the expanded data is sent to a personal computer (personal computer).

FIG. 17 is a diagram showing a general system configuration when data is stored in a compressed form in a hard disk device or a memory card. FIG. 1A shows a case where a data compression device 104 and a data decompression device 106 are provided in a hard disk device 102 connected to a personal computer 100. In this case, the non-compressed data is sent from the personal computer 100 to the hard disk device 102, and the compressed data is stored after being compressed by the compression device 104. When reading data, first, the read compressed data is expanded by the expansion device 106 in the hard disk device 102 and then output to the personal computer 100.

Further, FIG. 1B shows the compression device 104.
Also, a configuration in which the expansion device 106 is provided in the personal computer 100 is shown.

Further, in FIG. 1C, a memory card 10 is used as a storage device instead of the hard disk device 102.
8 is shown. In this case, the compression device 104 compresses the data before storing the data in the memory card 108 mounted on the personal computer 100. In addition, the compressed data read from the memory card 108 is expanded by the expansion device 106.

FIG. 18 shows a personal computer 100 and a printer 11.
It is a figure which shows the structure which stores compressed data in the printer buffer 112 provided between 0. In FIG. 1A, the compression device 104 is provided in the personal computer 100, and the decompression device 106 is provided in the printer buffer 112. Further, FIG. 2B shows that both the compression device 104 and the decompression device 106 are provided in the printer buffer 112. As shown in these figures, since the print data of the personal computer 100 is stored in the printer buffer 112 after being compressed by the compression device 104, a larger amount of print data than the actual storage capacity can be stored.

By the way, various methods have been proposed for performing the above-described data compression and decompression, for example, a method using a Huffman code, a dynamic dictionary method,
A typical example is slide dictionary method.

The method using the Huffman code is a conversion code in which the appearance frequency of each character or character string in all data strings to be compressed is counted in advance, and the bit length becomes shorter as the appearance frequency increases. A table is created in advance and input data is encoded according to this conversion code table. According to this method, an optimum conversion code table can be created for any input data string, and there is an advantage that efficient encoding, that is, data compression with a high compression rate becomes possible.

In the dynamic dictionary method, a dedicated code is assigned to an input data string and the data strings are sequentially registered in a dictionary format. As the data in the dictionary increases as the processing progresses,
This is called the dynamic dictionary method. When the character string in the input data string exists in the dictionary, the corresponding code in the dictionary and the code corresponding to the next character of this character string are Is output. If it does not exist, the raw data for one character is output together with the flag indicating that it does not exist. Since it is a method of finding a redundant component in the repeatability of a character string, it is possible to obtain a high compression rate, and further, it is possible to adopt a one-pass configuration capable of sequentially processing an input data string.

The slide dictionary method is to perform dictionary registration using a data string that has already been processed. Since the registered contents of the dictionary are deleted in order from the oldest one, the dictionary size can be limited and there is an advantage that the dictionary can be easily managed. A dictionary search is performed on the input data string, and if a matching character string exists in the dictionary, data that encodes the position and the matching length is output following the match flag. If it does not exist, the next 1
Output raw data for characters. Similar to the dynamic dictionary method of, it is a method of finding an upper long component in the repeatability of a character string, and is characterized in that a high compression rate is always obtained and it can be processed in one pass. An example of using this slide dictionary method is "data compression device and method" disclosed in Japanese Patent Application Laid-Open No. 3-68219.

[0011]

The various compression methods described above have various problems. That is, in the method using the Huffman code, as a preprocessing for data compression, the frequency of appearance of each character in the input data string is counted, and the conversion having a higher frequency of occurrence is associated with a code having a shorter bit length. Since it is necessary to create a code table, it is impossible to process sequentially input data strings in one pass, and there is a problem that real-time processing is impossible because two-pass processing is always performed. In addition, when there are several data groups, different conversion code tables must be created for each data group, so including this conversion code table poses the problem that a high compression rate cannot be obtained. It was

In the dynamic dictionary method and the slide dictionary method, when the corresponding character does not exist in the dictionary, the mismatch flag or the like and the raw data of the next character are output. When there is no data to be input, there is a problem that a code output having a bit length longer than the input original data exists. Furthermore, in the dynamic dictionary method, in order to make the dictionary size finite, the method of updating the dictionary becomes complicated. For example, when trying to update from the one with the lowest access frequency, the access frequency also needs to be held as information. Also, when trying to update from the oldest, it becomes necessary to create a dictionary by associating character strings with data registration times.

Therefore, the present invention was created in view of the above circumstances, and it is possible to process sequentially input data strings in real time, and even if there is no corresponding data in the dictionary. An object of the present invention is to provide a data compression device and a data decompression device that can perform data compression while always maintaining a high compression rate.

[0014]

In order to solve the above-mentioned problems, the invention of claim 1 uses a data string of a predetermined word length located at the end of the sequentially input uncompressed data as processing data. , And a data buffer and a dictionary buffer that store a data string of a predetermined word length located in front of them, respectively, as a dictionary, and for each word that configures the processed data in the data buffer, match each word that configures the dictionary. If there is a match, the match length coding means for outputting the match length code obtained by coding the longest match length, and the match length coding means, if a match is determined, a match is made. Position encoding means for outputting the position code obtained by encoding the position in the dictionary, which has the longest word length in the word sequence, and is present for each word of the uncompressed data. The data buffer has a rank table in which rank codes having shorter bit lengths are associated in the order of higher rate, and the data buffer is searched by searching the rank table when a mismatch is determined by the match length coding means. Rank coding means for outputting a rank code corresponding to the head word of the processed data in the inside, and the head word of the processed data to be coded when the rank coding means performs the coding processing. Table updating means for updating the rank table in consideration of the above, and when the position coding means or the rank coding means performs coding, a part or all of the processed data that has been coded is Buffer updating means for performing processing of transferring to the dictionary in the dictionary buffer and additionally storing the transferred uncompressed data in the data buffer , And if there is a word that matches each word of the processing data in the dictionary, the matching length and its position are encoded respectively, and if there is no matching word, a matching length and processing data indicating that It is characterized in that compressed data is obtained by encoding each of the first word and the first word.

According to a second aspect of the present invention, in the first aspect of the present invention, when the matching length coding means sequentially views each word of the dictionary in the dictionary buffer from the head, the head of each word is different. A top buffer to store the address,
A chain buffer that stores data indicating at which address in the dictionary the same word is stored next when each word of the dictionary in the dictionary buffer is viewed in order from the beginning, The address in the dictionary is specified by searching the top buffer and the chain buffer based on the first word of the processed data in the data buffer.

According to a third aspect of the present invention, in the first aspect of the present invention, the dictionary buffer and the data buffer are composed of a plurality of memory elements whose addresses are continuous with each other, and the buffer updating means is a code. The respective words constituting a part or all of the processed data that have been encoded are stored in a distributed manner in each of the plurality of memory elements, and the match length encoding means simultaneously outputs from each of the plurality of memory elements. The coincidence search is performed by reading data.

According to a fourth aspect of the present invention, a dictionary buffer for storing, as a dictionary, a data string of a predetermined word length located at the end of the uncompressed data obtained by decompressing the compressed data,
A match length decoding unit that decodes the match length code located at the head of the sequentially input compressed data and outputs concrete match length data and the match length code located at the head of the compressed data are matched. In the case shown, the position decoding means for decoding the next position code and outputting the data indicating the storage position in the dictionary and the matching length code positioned at the beginning of the compressed data match. , The storage position in the dictionary is specified based on the data output from the position decoding means, and the storage position is used as a start address to read data from the dictionary by the amount corresponding to the matching length data. The dictionary read control means for outputting uncompressed data and a rank table in which shorter rank codes are associated with each word of the uncompressed data in descending order of existence probability. If the match length code located at the beginning of the compressed data indicates a mismatch, the order of performing decoding of the uncompressed data by searching the order table based on the order code located next A rank decoding means for decoding, a table updating means for updating the rank table in consideration of the decoded uncompressed data when the decoding processing is performed by the rank decoding means, and the position Dictionary decoding means for updating the dictionary so as to include uncompressed data that has been decoded when decoding is performed by the decoding means or the rank decoding means, and a matching length code is provided. It is characterized in that decompressed data is obtained by decoding compressed data in which either one of the position code and the rank code is combined.

[0018]

According to the data compression apparatus of the present invention, the most recent data string having a predetermined word length, which has been already compressed, is stored in the dictionary buffer as a dictionary, and the data string having a predetermined word length to be processed is stored in the data buffer. To store. Then, the data string stored in the data buffer is searched for a match with each word forming the dictionary in the dictionary buffer, and if there is a match, the word length is the largest in the matched word string. A match length code obtained by encoding a long match length and a position code obtained by encoding a position in the dictionary are output as compressed data.

If they do not match, a matching length code indicating that they do not match is associated with the leading word of the processed data by a rank table in which a short rank code is associated with each word in descending order of existence probability. The obtained rank code is output as compressed data.

After the above-mentioned compression processing is completed, each of the data buffer, the dictionary buffer, and the rank table is updated so that data compression is always performed based on the latest information.

According to the first aspect of the present invention, since the dictionary is created by the sequentially input data, the one-pass configuration can be realized and the real-time compression processing can be performed. Further, even if the corresponding data (word) does not exist in the dictionary, the compression process is performed by assigning a shorter code to a data item having a higher appearance probability. Therefore, the encoding process is performed with a bit length shorter than that of the original data. It is possible to perform data compression that always maintains a high compression rate for all input data.

Further, in the invention of claim 2, the above-mentioned matching length coding means is constituted by including a top buffer and a chain buffer. This top buffer stores the start address of each different word when looking at each word in the dictionary in order from the beginning, and when looking at each word in the dictionary in order from the beginning in the chain buffer. Stores data indicating in which address in the dictionary the same word is stored next. Therefore, when each word in the data buffer is searched in the dictionary, by accessing the top buffer and the chain buffer, the corresponding address in the dictionary can be quickly known, and the processing speed can be increased.

According to the third aspect of the present invention, the dictionary buffer and the data buffer are composed of a plurality of memory elements, and the addresses of these memory elements are continuous with each other. Then, when updating the dictionary, each of the words that compose part or all of the uncompressed data that has been encoded is distributed and stored in each of these memory elements. Data is simultaneously read from the memory element. Therefore, the word lengths corresponding to the number of memory elements can be compared at the same time, and the match length determination when the match length is long can be processed at high speed.

The data decompression device according to a fourth aspect of the present invention decodes the data by decompressing the data compressed by the data compression device. If the matching length code located at the beginning of the input compressed data indicates a match, the position code located next to it is decoded to obtain the storage position in the dictionary. Then, the data is decompressed by reading the data from the dictionary by the amount corresponding to the matching length using this storage position as the head address, and uncompressed data is obtained. Further, when the above-mentioned match length code indicates non-match, the data is expanded by searching the rank table having the same contents as the rank table in the data compression apparatus, and uncompressed data is obtained. This rank table is changed each time after it is searched, and is always updated in the same procedure as the rank table in the above-described data compression device.

In the fourth aspect of the invention, the decompression process can be performed in real time as in the case of data compression.

[0026]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described in detail below with reference to the drawings.

FIG. 1 is a diagram showing the configuration of a data compression apparatus of an embodiment to which the present invention is applied. The data compression apparatus shown in the figure includes a data buffer 10, a dictionary buffer 12, a buffer updating unit 14, a match length coding unit 16, a position coding unit 20, a rank coding unit 24, and a table updating unit 28. It

The data buffer 10 temporarily holds a data string to be processed, and a new data string is input by the amount of data for which the compression processing has been completed, and the contents are sequentially updated. Also, dictionary buffer 1
2 stores the uncompressed data that has been processed as a dictionary, and the old contents are deleted and updated each time a new compression process is performed.

FIG. 2 is a diagram schematically showing the relationship between the data buffer 10 and the dictionary buffer 12 and the input data string. In the same figure, arrow a indicates the direction of the input data string, and shows the case where each word of the input data string is indicated by one-letter alphabet. The input data string is sequentially input and stored in the data buffer 10. Then, the data compression processing is performed in order from the beginning of the data string stored in the data buffer 10, and the data string after the processing is stored in the dictionary buffer 12 next.

Data buffer 10 and dictionary buffer 1
2 has a predetermined capacity (for example, several thousand words), but in FIG. 2, each has a capacity for 16 words for convenience of explanation. Further, since it is necessary to compare the data string stored in the data buffer 10 with the data string stored in the dictionary buffer 12, the data buffer 10 and the dictionary buffer 12 have the same capacity, or the dictionary buffer 12 has a larger capacity. It has a large capacity.

The buffer updating unit 14 is provided in the data buffer 1
0 and the contents of the dictionary buffer 12 are updated. Since the character string stored in the data buffer 10 is encoded in order from the beginning, the encoded data string is transferred to the dictionary buffer 12, and new uncompressed data for that is transferred to the data buffer 10. The process of adding and storing is performed.

The match length coding unit 16 uses the data buffer 1
It is searched whether or not one word or a plurality of words located at the beginning of the data string stored in 0 exists in the dictionary in the dictionary buffer 12, and the match length code corresponding to the match length is output. The matching length code is created by obtaining a matching length code corresponding to the detected matching length on a one-to-one basis based on the matching length code table 18.

FIG. 3 is a diagram showing the detailed contents of the match length code table 18. As shown in the figure, a match length code "00" is assigned in the case of a mismatch, and a match length code having a longer bit length is assigned as the match length becomes longer. However, since the bit length of the match length code does not increase in proportion to the match length, the match length code table 1 is set so that the compression rate increases as the match length increases.
8 has been created.

The position coding unit 20 outputs a position code obtained by coding the position of the matched data in the dictionary when the match length coding unit 16 determines the match. This encoding is performed by searching the position code table 22 to obtain a position code corresponding to the storage position in the dictionary in a one-to-one manner. Further, the storage position in the dictionary is, for example, the data buffer 1 in FIG.
The address closest to the 0 side is set to "1", and relative addresses such as "2", "3", ...

FIG. 4 is a diagram showing a detailed example of the position code table 22 in the position coding unit 20. As shown in the figure, the smaller the relative address value (position), the shorter the bit position code is assigned. If the matching length is the same, the most recently processed data string appears repeatedly. In this case, the compression rate is the highest.

The match length code and the position code shown in FIGS. 3 and 4 are both variable length codes, and special bit data for separating these codes is not inserted. Therefore, the code of the content that can be separated from the content only by the later expansion processing is assigned.

The rank coding unit 24 includes a match length coding unit 16
When the non-coincidence determination is performed by, the rank code corresponding to the first word stored in the data buffer 10 is output. This encoding is performed by searching the rank table 27 for the rank of the leading word and then searching the rank code table 26 in which a word having a higher probability of appearance of each word is associated with a shorter rank code. Done.

FIG. 5 is a diagram showing a detailed example of the rank code table 26 in the rank coding section 24. As shown in the same figure, a shorter code is assigned to a rank having a higher appearance frequency, so that a high compression rate can be obtained even when there is no corresponding character in the dictionary.

The table updating unit 28 includes a rank coding unit 28.
The rank code table 26 is updated. That is, as described above, the rank code table 26 needs to assign shorter codes in the descending order of the frequency of appearance. Therefore, it is necessary to raise the rank of the corresponding character each time encoding is performed. This is performed by the updating unit 28.

Next, the operation of the data compression apparatus of the embodiment having the above-mentioned configuration will be described. As an example, it is assumed that the data string shown in FIG. 2 is input, and the unprocessed data string and the processed data string are stored in the data buffer 10 and the dictionary buffer 12, respectively.

First, the match length encoding unit 16 inputs the data in the dictionary in the dictionary buffer 12 to the data buffer 1
The longest data string that matches the data string stored in 0 is searched. In the specific example shown in FIG. 2, first, it is searched whether or not the leading character “G” stored in the data buffer 10 is present in the dictionary of the dictionary buffer 12. It is searched whether the character "GC" is present. In this way, character strings are searched until no matching character string is found in the dictionary.

By the way, in the case shown in FIG. 2, since the leading character "G" in the data buffer 10 is not in the dictionary of the dictionary buffer 12, the match length is "0". The match length coding unit 16 searches the match length code table 18 whose contents are shown in FIG. 3, reads the match length code “00” corresponding to the match length “0”, and outputs it.

Further, the information indicating the above-mentioned inconsistency is input from the match length coding unit 16 to the rank coding unit 24, and the processing in the rank coding unit 24 is started.

The rank coding unit 24 includes the data buffer 10
The rank of the letter "G" located at the top of the rank table 2
7 and reads the rank code table 2 based on this rank.
By searching for 6, the corresponding rank code is read and output. In this way, when the character corresponding to the dictionary in the dictionary buffer 12 does not exist, the match length code “00” is assigned by the match length code “00” from the match length coding unit 16 to the order coding in correspondence with the first character in the data buffer 10. The order code is sequentially output from the unit 24 as compressed data.

In this way, after the rank coding unit 24 creates the rank code, the table updating unit 28 updates the rank table 27.

FIG. 6 is a diagram for explaining the updating of the order table. As shown in FIG. 9A, for example, when the appearance frequency of the letter “G” is the eighth at the present time, the rank encoding unit 24 causes the rank code “010011” corresponding to this rank “8”. Is read from the rank code table 26 shown in FIG. Following this processing, or in parallel with this processing, the table updating unit 28 performs processing for raising the rank of the character "G". For example, as shown in FIG. 6 (B), the rank is increased by one and the rank table 27 is updated.

When the data compression is performed in this way, the buffer updating unit 14 moves only the character "G" to be processed to the dictionary buffer 12 and the data buffer 1
Update 0 for one character. FIG. 7 is a diagram showing the contents of the data buffer 10 and the dictionary buffer 12 after updating.
FIG. 3A shows a state in which only the first character “G” of the data buffer 10 shown in FIG. 2 has been moved to the dictionary buffer 12.

The above is the data compression when there is no corresponding character in the dictionary in the dictionary buffer 12, but next, the case where the corresponding character string exists in the dictionary will be described.

The match length coding unit 16 next detects whether or not the character or character string located at the head of the data buffer 10 exists in the dictionary of the dictionary buffer 12. Figure 7
In the case shown in (A), the first character "C" is shown in (a) of the figure.
It exists at the relative address “2” of the dictionary buffer 12 as shown in FIG. Similarly, the first two characters "CB" are shown in FIG.
As shown in, the relative address of the dictionary buffer 12 is “9”,
It exists in "10". Similarly, the first character string "CBAD
"ACBEBADFDA" exists at relative addresses "3" to "16" of the dictionary buffer 12. As described above, the character strings in the data buffer 10 are present at a plurality of positions in the dictionary. Among them, the match length “14” shown in (c) is the longest. "1
The matching length code "101001" corresponding to "4" is read from the matching length code table 18 whose contents are shown in FIG. Further, when there is such a matched character or character string, information to that effect is sent to the position encoding unit 20.

The position coding unit 20 includes a match length coding unit 16
The leading position of the longest character string in the dictionary detected by is represented by a relative address, and the position code corresponding to this leading position is read from the position code table 22 shown in FIG. 4 and output. In the case shown in FIG. 7A, the beginning of the matching character string in the dictionary is located at the relative address “16”, and the position encoding unit 20 determines that the relative address “1”.
The position code "0100011" corresponding to "6" is read from the position code table 22 whose contents are shown in FIG.

In this way, when the corresponding character string exists in the dictionary, the match length code corresponding to the match length and the position code corresponding to the storage position of the first character are output as compressed data. . After that, the buffer updating unit 14 updates the dictionary buffer 12 and the data buffer 10.

FIG. 7B shows the data buffer 10 and the dictionary buffer 12 which have been updated in this way.
The content of is shown.

As described above, when the processing by the data compression apparatus of the present embodiment is performed, even if the corresponding character does not exist in the dictionary, the higher the frequency of appearance, the shorter the bit length of the data The compression is performed, and when the corresponding character string exists in the dictionary, the matching length and the storage position of the character string are encoded to perform data compression. Therefore, in any case, the bit length is shorter than that of the original data, and a very high compression rate can be obtained as a whole. For example, the compressed data obtained by the above-described processing is “00”, “010011”, “101001”, “010001”.
There are a total of 21 bits of "00", and the basic data is "GCBADA
15 characters of "CBEBABFDA". If one character is composed of 8 bits, 15 characters are 120 bits, and the overall compression rate is (21/120) × 100 = 1.
It is 7%, which shows that the compression efficiency is very high.

Further, according to the data compression apparatus of this embodiment described above, the input uncompressed data is transferred to the data buffer 1.
Since a series of compression processing is performed by sequentially storing in 0 and the dictionary buffer 12, processing such as creating a dictionary in advance is unnecessary, and compression processing can be performed in real time.

Next, the data decompression performed corresponding to the above-mentioned data compression will be described. For example, compressed data "00", "01001" obtained by the above-mentioned data compression
A case will be described in which "1", "101001", and "01000100" are input, and data restoration, that is, data decompression is performed based on these compressed data.

FIG. 8 is a diagram showing the configuration of the data decompression device of this embodiment.

The data decompression device shown in the figure has a match length decoding unit 30, a position decoding unit 34, a rank decoding unit 38, a table updating unit 42, a dictionary reading control unit 44, a dictionary buffer 46, and a dictionary updating unit 48. It is configured to include.

The match length decoding section 30 outputs the corresponding match length by decoding the match length code located at the beginning of the input compressed data based on the match length code table 32. Further, when the match length code is "00", it indicates a mismatched state in which there is no corresponding character string in the dictionary in the data compression. Therefore, the match length decoding unit 30
When the match length code “00” is input, notifies the order decoding unit 38 that there is no match. On the other hand, if any other matching length code is input, the position decoding unit 34 is notified of the matching.

The match length code table 32 described above, the position code table 36, and the rank code table 4 which will be described later.
0 has the same contents as the match length code table 18, the position code table 22, and the rank code table 26 described above, and the details thereof are as shown in FIGS. 3 to 5.

The position decoding unit 34 includes a match length decoding unit 30.
The position code table 3 is used to decode the position code input subsequently to the match length code when the notification of the match is received from
Based on 6. The position data in the dictionary buffer 46 is output by this decoding process.

The dictionary read control unit 44 includes the position decoding unit 3
Based on the position data output from No. 4, the storage position in the dictionary buffer 46 is specified, and this storage position is used as the start address and the data of the following matching length is output as decompression data.

When the order length decoding unit 38 is notified by the match length decoding unit 30 that there is no match, the order decoding unit 40 responds based on the order length code input following the match length code based on the order decoding table 40. Read the ranking. In addition, the rank decoding unit 38 outputs the character corresponding to the rank read from the rank decoding table as decompression data based on the rank table 41. The table updating unit 42 includes a rank decoding unit 38.
Every time the ranking table 41 is accessed by, the contents of the ranking table 41 are updated.

The dictionary updating unit 48 updates the dictionary buffer 46 every time the expanded data is output from the dictionary reading control unit 44 or the rank decoding unit 38. Specifically, the uncompressed character or character string after decompression is included in the dictionary in the dictionary buffer 46, and the character in the old dictionary is deleted by the amount of the newly included character or character string. Perform processing.

Next, the operation of the data decompression device having the above configuration will be described.

FIG. 9 is a diagram showing an example of the contents of the dictionary buffer 46. 2A corresponds to the state before the compressed data obtained by the above-described compression processing is input, and is the same as the storage content of the dictionary buffer 12 of the data compression apparatus shown in FIG. ing.

When the compressed data is input, the match length decoding unit 30 first separates the variable length match length code located at the head of the match length decoding unit 30 and performs decoding processing based on the match length code table 32. Since the first match length code input is "00", the match length decoding unit 30 reads and outputs the match length "0" corresponding to this match length code as shown in FIG.

Next, the rank decoding unit 38 reads from the rank table 41 the rank data "8" corresponding to the rank code "010011" input following the above-mentioned matching length code. Then, based on this ranking data, the ranking code table 40
Is accessed to identify the corresponding one character and output it as decompressed data.

The rank table 41 corresponds to the rank table 27 of the compression apparatus described above, and the table updating unit 42 updates the table according to the same procedure. That is, the processing by the rank decoding unit 38 described above is performed by using the rank table 41 having the contents shown in FIG. 6A, and after this processing is finished, the update processing by the table updating unit 42 is performed. The ranking table 41 has the contents shown in FIG.

In this way, the decompression process is performed when the corresponding character does not exist in the dictionary buffer 46. Similarly, when the next compressed data is input, the match length decoding unit 30 causes the match length code “10100
By separating only 1 "and accessing the match length code table 32, the corresponding match length" 14 "is output.

The match length code input to the position decoding unit 34 and the match length decoding unit 30 is not "00", or the match length output from the match length decoding unit 30 is not "0". The process is thereby started. That is,
The position decoding unit 34 separates the position code “101001” input subsequently to the match length code and accesses the position code table 36 to read and output the corresponding position data “16”.

Next, the dictionary read control unit 44 stores the storage position of the dictionary buffer 46 (the start address of the corresponding character string) based on the position data output from the position decoding unit 34.
Is specified, and the character string of the matching length stored starting from this storage position is read in order and output as decompressed data. As explained in the data compression device described above,
The position data output from the position decoding unit 34 indicates the storage position of the head portion of the character string in the dictionary, and is recognized as a relative address from the end of the data.

After the decompression processing is performed by the rank decoding unit 38 in this way, the dictionary updating unit 48 shown in FIG.
The dictionary buffer 46 is updated as shown in FIG. Further, next, the position decoding unit 34 and the dictionary reading control unit 4
After the decompression processing is performed by 4, etc., the dictionary update unit 48 updates the dictionary buffer 46 as shown in FIG. 9C.

Thus, when the compressed data is input,
Decoding of the match length is performed based on the match length code located at the beginning, and it is determined whether the code that is subsequently input based on this match length code is a position code or a rank code, Position coding unit 34 or rank coding unit 3
Processing by 8 is performed. If it is a position code,
Furthermore, the dictionary read control unit 44 causes the dictionary buffer 46
The dictionary in is accessed and the data expansion process is performed. Therefore, in any case, the expansion processing can be performed in real time based on the sequentially input compressed data.

Next, the configuration and operation of the above-described data compression apparatus according to this embodiment will be described.
When specifically performing the data compression processing, it is necessary to quickly search the dictionary in the dictionary buffer. As a device for that purpose, a top buffer and a chain buffer are provided in association with the dictionary buffer so that the character to be searched can be searched quickly.

FIG. 10 is a diagram for explaining the contents of the top buffer and the chain buffer and how to use them. In the figure, when the contents of the dictionary buffer 12 are viewed from the data buffer 10 side, the top buffer 50 is the dictionary buffer 12 in which the corresponding character first appears.
The address of is stored in association with the corresponding character. For example, if the address of the dictionary buffer 12 is set as shown in FIG. 10, the address data "1" of this character is stored in correspondence with the character "A". Similarly, address data "6", "0", ... Is stored corresponding to each of the characters "B", "C", ....

The chain buffer 52 stores chain data indicating at which address the same character is stored next when the contents of the dictionary buffer 12 are viewed from the data buffer 10 side. For example,
Focusing on the character “C”, it is stored at the addresses “0”, “9”, and “e” of the dictionary buffer 12. Therefore, the addresses "0" and "9" of the chain buffer 52 respectively store the addresses "9" and "e" at which the character "C" appears next. Further, some data indicating that the corresponding character does not exist thereafter at the address "e" of the chain buffer 52 corresponding to the end side as viewed from the data buffer 10 side, for example, the same address data as that character or the start address " Since "0" and the like are stored, it is understood that the search for the character string after that is unnecessary.

For example, when searching for the beginning "A" of the character string stored in the data buffer 10 in the dictionary, the top buffer 50 is first accessed to access the address data "1" corresponding to this character "A". Is read. This address data indicates at which address of the dictionary buffer 12 the corresponding character "A" is first stored. Then, by accessing the chain buffer 52 corresponding to this address, the chain data " 5 ”is read. Similarly, the next chain data "a" is read by accessing the chain buffer 52 with the chain data "5" as an address, and the chain data "c" is read in the same manner. In this way, the character "A" corresponds to the addresses "1", "5", "a" of the dictionary buffer 12,
It can be easily understood that the data is stored in each "c". After that, the character string stored with the respective addresses thus read out as the start address is judged to be the same as the character string in the data buffer 10 to find out how many characters match. It is like this.

By the way, in the present embodiment, the matching length judgment of the character string is also performed at high speed by simultaneously comparing a plurality of characters.

FIG. 11 is a diagram showing a schematic configuration of the dictionary buffer 12 in the case of determining the coincidence of four characters at the same time. As shown in the figure, the dictionary buffer 12 is composed of four RAMs 54, 56, 58, 60 capable of parallel reading. These four RAMs 54 to 60 are respectively assigned consecutive addresses, and when updating the dictionary buffer 12, consecutive character strings are stored in different RAMs 54 to 60 on a character-by-character basis. . on the other hand,
When comparing the character string stored in the data buffer 10 and the storage content of the dictionary buffer 12, these four RAMs are used.
54 to 60 can be read at the same time, that is, four characters at the same time, and the read four characters and the four characters in the data buffer 10 can be compared simultaneously. The details of the reading and writing of data from and to the dictionary and the comparison operation of simultaneous four characters will be described later.

FIG. 12 is a diagram showing an example for updating the ranking table 27 of the data compression apparatus or the ranking table 41 of the data expansion apparatus. In the figure, the rank memory 62 is a rank table 27 or a rank table 41.
Is stored. For example, the rank data is stored with the ASCII code of the character whose rank is to be known as an address. Further, the data memory 64 stores the ASCII code of the corresponding character using the rank data as an address.

Consider a case where the rank memory 62 and the data memory 64 are used to read the rank of the character "G" and update the rank.

First, using the ASCII code “47h” corresponding to the letter “G” as an address, the rank data “8” is read from the rank memory 62.

Next, in order to raise the rank of this character “G”, the rank data “7” obtained by subtracting only one from the read rank “8” is written to the same address. In this state, since there are two rank data "7", it is necessary to change the other rank data "7" to "8".

Therefore, the data memory 64 is accessed by using the duplicated rank data “7” as an address, and the corresponding data “54h” (ASCII code of the character T) is read. Then, the read data is once held, and the ASCII code "47h" of the character "G" is written to this address.

Next, the data memory 64 is accessed by using the order data “8” to be lowered as an address, and the data “54h” temporarily held in the above described is stored as the corresponding data.

Finally, the rank memory 62 is accessed using the newly written data “54h” as an address, and new rank data “8”, which is obtained by adding 1 to the rank data “7”, which is the content thereof, is written.

In this way, the ranking table 27 or 41, which is the contents of the ranking memory 62, is searched and updated.

Hereinafter, a specific configuration of the data compression apparatus which has been devised in various ways will be described.

13 and 14 are diagrams showing the detailed structure of the data compression apparatus of this embodiment. A compression control unit 300 shown in the figure controls the entire data compression apparatus.

The non-compressed data string input to this data compression device is first input to the input FIFO 200. The input FIFO 200 is for absorbing the difference between the data input speed and the processing speed, and for example, 51
It has a capacity of 2 words. Register (REG) 202
Is for temporarily holding a character of one word output from the input FIFO 200. The held character is input to the dictionary / data buffer 204, and the top address operation unit 207 is also passed through a multiplexer (MUX) 206. Entered in.

The dictionary / data buffer 204 comprises the data buffer 10 and the dictionary buffer 12 shown in FIG. 1 in one memory. As shown in FIGS. 2 and 7, the data buffer 10 and the dictionary buffer 12 respectively store two consecutively input data strings, and gradually move their boundaries along with the progress of encoding. ing. Therefore, it can be realized by configuring these two buffers 10 and 12 with one memory and providing a pointer indicating the boundary between the two buffers.

The dictionary / data buffer 204 configured in this way is composed of the data buffer 10 and the dictionary buffer 1.
2 has a total capacity, and, for example, when the compression process for three characters is completed, the pointer is advanced by three addresses and a new input is made at three addresses corresponding to the last part of the data buffer 10. Just write the data string.

Further, based on the characters input to the top address calculation unit 207 via the multiplexer 206,
New registration processing for the top buffer 208 or update processing for the chain buffer 220 is performed. That is, as shown in FIG.
Stores the address of the first character that appears in the dictionary buffer. When the dictionary / data buffer 204 is updated by one character, this one character of data is transferred from the data buffer to the dictionary buffer. The newly transferred character is newly registered in the top buffer 50. Further, since the top buffer 50 is updated in this way, the chain buffer 52 is also updated according to the update situation.

In this way, new characters for the number of characters for which the data compression processing has been completed are registered in the dictionary / data buffer 204 via the register 202, and the top buffer 50 and chain buffer 52 are updated. .

Next, under the control of the compression controller 300, one character located at the beginning of the data area of the dictionary / data buffer 204 is read out, and the registers 208 and 21 are read.
Temporarily held at 0. The data for one character held in the register 210 is input to the top address calculation unit 207 via the multiplexer 206, and the dictionary area of the dictionary / data buffer 204 corresponding to this one character by the top buffer 50 and the chain buffer 52. Address calculation is performed. The calculated address is in register 2
After being temporarily stored in 12, the data is input to the dictionary / data buffer 204 via the multiplexer 214. The compression control unit 300 reads the data for one character in the dictionary designated by this address, and the read data is input to the comparator (CMP) 216.

The comparator 216 has the register 20 first.
The data for one character located at the beginning of the data area held in 8 and the data for one character read from a specific address in the dictionary area are compared, and if they match, the count value of the counter 218 is determined. Increase by 1. Comparator 21
When a match is detected by 6, the compression control unit 300
The data area of the dictionary / data buffer 204 and the address of the dictionary area are each shifted by one, and the same processing is repeated until a mismatch is detected by the comparator 216. Therefore, by checking the count value of the counter 218 after the mismatch is detected by the comparator 216, it is possible to know how many characters from the beginning of the character string stored in the data area of the dictionary / data buffer 204 match. .

If a mismatch is detected after the position is once detected by the comparator 216, the compression controller 3
By controlling 00, the address of the chain buffer 52 is designated by the value of the register 212, the address of the dictionary area of the next candidate character is read, and this value is held in the register 212 again. In this way, it is determined how many characters match each address in the dictionary area in which the same character as the character at the beginning of the data area is stored, and the counter 218 holds the maximum value. It is supposed to be done.

Further, in parallel with the operation for obtaining the maximum match length in this way, the address in the corresponding dictionary area is calculated. In other words, both the value output from the chain buffer 52 and the value output from the chain buffer 52 immediately before and held in the register 212 are both subtracted.
20 and the difference is accumulated by the adder 222 and the register 224. Further, the counter 218 has a function of outputting a signal to that effect when the maximum value is detected, and when the signal is output, the content of the register 224 is transferred to the register 226. Therefore, the register 226 holds only the leading address of the dictionary area of the character string having the maximum matching length.

In this way, the match length of the matched character string is output from the counter 218 and the register 2
26 outputs the position (address) in the dictionary area of the dictionary / data buffer 204.

Next, the match length coding section 228 reads out and outputs the match length code corresponding to the match length output from the counter 218 based on the match length code table 18.
The position encoding unit 230 also reads out and outputs the position code corresponding to the position data output from the register 226 based on the position decoding table 22. This output is input to the byte conversion unit 234 via the multiplexer 232, and the byte conversion unit 234 collectively outputs the matching length code, which is a variable length code, and the position code in byte units. This output is once held in the output FIFO 236 and then output to the outside as a compressed data string.

The above-described data compression operation is an operation in the case where the comparator 216 detects a match once and then a mismatch is detected. However, if no match is detected, the following processing is performed. .

If no match is detected by the comparator 216, the counter 218 does not perform the counting operation, so that the counter 218 outputs the count value "0". At this time, the match length coding unit 228 outputs the match length code “00” corresponding to the count value “0”, and the match length code “00” is input to the byte conversion unit 234.

In parallel with this operation, the encoding process of the first character that does not exist in the dictionary is performed. That is, when the character located at the head of the data area of the dictionary / data buffer 204 is output, the register 238 holds this one character. Then, the held character data is input as an address to the rank memory 62 via the multiplexer 240. As shown in FIG. 12, the rank memory 62 outputs the frequency of appearance of this character using the input character data as an address. The output of the rank memory 62 is temporarily held in the register 242 and then input to the rank coding unit 252.

The rank coding section 252 reads the rank code corresponding to the appearance frequency output from the rank memory 62 based on the rank code table 26, and the multiplexer 23
It outputs to the byte conversion part 234 via 2. The byte conversion unit 234 outputs the match length code “00” output from the match length encoding unit 228 and the rank code output from the rank coding unit 252 in byte units, and this output is the output FI.
It is output to the outside as a compressed data string via the FO 236.

The contents of the rank memory 62 are updated each time the rank memory 62 is accessed. In particular,
The update is performed according to the procedures (1) to (2) shown in FIG.
Therefore, the data memory 64 and the register 224 are provided. That is, at the same time as reading the rank from the rank memory 62, a value obtained by subtracting 1 from the read rank is written again in the rank memory 62. next,
The data memory 64 is accessed using the updated rank written in the rank memory 62 as an address, and the register 238
Write the character data stored in. Next, the data memory 64 is accessed again using the rank before the update as an address, and the data stored corresponding to the rank after the update is written to this address. Finally, after the written character data is once held in the register 224, the rank memory 62 is accessed again by this character data to write the rank before update to the corresponding area.
In this way, the order memory 62 and the data memory 64
The content of is changed.

FIG. 15 is a diagram showing the detailed structure of the dictionary area of the dictionary / data buffer 204. The configuration shown in the figure is a detailed configuration for enabling simultaneous reading of characters from the plurality of RAMs shown in FIG.

In the figure, the write signal controller 262 is
It is for inputting alternative write signals WE0 to WE3 to the four RAMs 254, 256, 258, 260. The lower 2 bits of the N-bit write address WA are input to the write signal control unit 262, and one RAM to which the write signals WE0 to WE3 are input each time the address is updated. It is designed to make patrols one by one. Further, the upper N−2 bits of the N-bit write address WA are input to each of the four RAMs 254 to 260, and only the one to which the write signal is input from the write signal control unit 262 is input. Writing is allowed.

Further, the read address control section 264 determines the four RAMs 25 based on the input read address RA.
4 to 260 are simultaneously accessed to read out four character data at the same time. For example, if the input read address RA corresponds to an address in the third RAM 258, the read address i is input to the RAMs 258 and 260 and at the same time the RAM 25 is read.
The read address i + 1 is input to 4,256.
Four RAMs 2 addressed in this way
The read signal SIGRD is input to 54 to 260,
Data for four characters are read at the same time. The read data rearrangement unit 266 performs an operation of rearranging the thus read 4-character data as appropriate. In the example above, R
AM 258, 260, 254, 256 are rearranged in this order and output as read data RD0 to RD3 for four characters.

When the data of 4 characters is read from the dictionary / data buffer 204 in this way, 4
It suffices to use the comparator 216 capable of simultaneously performing the character comparison operation, and also provide the counter 218 with a function of accumulating and adding the outputs of the comparator. Then, when the comparator 216 detects a match in all four characters, the reading and comparison operation of the character data for the next four characters may be continued.
In this manner, the comparator 216 repeats the comparison process until one of the four characters does not match,
It is output from the counter 218 after the matching lengths up to that time are accumulated.

In this way, by reading out data for four characters at the same time and making a comparison, it is possible to perform high-speed processing which is about four times as high as that in the case of reading out and comparing each character.

Next, details of the data decompression device that performs the operation corresponding to the above-described data compression device will be described.

FIG. 16 is a diagram showing the detailed structure of the data decompression device. The decompression control unit 400 shown in the figure controls the entire data decompression device.

The input FIFO 500 temporarily holds the input compressed data string and then outputs it to the bit string converter 502. This bit string conversion unit 502 inputs 1
A match length code, which is a variable length code, is extracted from byte or several bytes of data, and a position code or rank code following this match length code is extracted. The separated match length code is input to the match length decoding unit 504, the position code is input to the position decoding unit 506, and the rank code is input to the rank decoding unit 508.

If the match length is not “0”, the address control unit 510 determines the dictionary based on the match length output from the match length decoding unit 504 and the position data output from the position decoding unit 506. The necessary character data is read from the buffer 512. That is, the start address is designated by the position data output from the position decoding unit 506, and the character data of the matching length stored after this address is read. The read series of character data is
It is input to the output FIFO 516 via the multiplexer 514, temporarily held and then output as an uncompressed data string.

On the other hand, when the match length is "0", the character data is restored based on the rank data output from the rank decoding unit 508. Specifically, this rank data is input as an address to the data memory 520 via the multiplexer 518. The data memory 520 outputs character data corresponding to the order data, the character data is temporarily held in the register 522, and then output as a non-compressed data string via the multiplexer 514 and the output FIFO 516.

A rank memory 524 and a register 526 are provided to update the data memory 520. The rank memory 524 is accessed using the character data once held in the register 522 as an address, and the corresponding rank data is updated. The updated rank data is once held in the register 526 and then input again as an address to the data memory 520 via the multiplexer 518. This time, the updated rank data of the data memory 520 corresponding to the rank is updated. The content is read and held in the register 522, and the content is updated by the character data previously read from the data memory 520. After that, the rank memory 524 is accessed again using the character data held in the register 522 as an address, and the correct rank data of the character data whose rank is lowered is written. In this way, the rank memory 524
And the contents of the data memory 520 are changed.

When the uncompressed data is decompressed in this way, the decompressed data is once held in the register 528 and then input to the dictionary buffer 512, and the expansion buffer 400 updates the dictionary buffer 512. Be seen.

The present invention is not limited to the above embodiments, but various modifications can be made within the scope of the gist of the present invention.

For example, in the above-described embodiment, the case where the rank of the appearance frequency is updated by 1 when the encoding process is performed on the character that does not exist in the dictionary has been described. May be given.

In addition, in the above-described embodiment, one word is used for one word.
Although the description has been made by associating characters with each other, one word may be composed of two or more characters, bit data not directly related to characters may be associated, and the content of the data is not particularly limited.

[0121]

As described above, according to the first aspect of the invention, since the dictionary is created by the sequentially input data, the real-time data compression processing becomes possible. Further, even if there is no corresponding data in the dictionary, the compression process is performed by assigning a shorter code to a data item having a higher appearance probability. Therefore, the encoding process can be performed with a bit length shorter than that of the original data. It is possible to perform data compression that maintains a high compression rate for all input data.

According to the second aspect of the present invention, the match length coding means is configured to include the top buffer and the chain buffer, and when each word in the data buffer is searched in the dictionary, these By accessing the top buffer and the chain buffer of, the corresponding address of the dictionary can be quickly known, and the processing speed can be increased.

According to the third aspect of the present invention, the dictionary buffer is composed of a plurality of memory elements, and data is read from these memory elements at the same time. It is possible to compare at the same time, and it is possible to process the match length determination when the match length is long at a high speed.

Further, according to the invention of claim 4, when the matching length code located at the head portion of the input compressed data indicates matching, the position code located next to the matching length code is decoded. Thus, the storage address in the dictionary is obtained, and the address is used as the start address to expand the dictionary by reading the data of the dictionary for the matching length. Further, when the above-mentioned matching length code indicates a mismatch, the data is expanded by searching the rank table. In this way, the data compressed by the data compressing device according to the first to third aspects can be expanded in real time.

[Brief description of drawings]

FIG. 1 is a diagram showing a schematic configuration of a data compression apparatus of an embodiment to which the present invention is applied.

FIG. 2 is a diagram schematically showing a relationship between a data buffer and a dictionary buffer and an input data string.

FIG. 3 is a diagram showing a specific example of a match length code table.

FIG. 4 is a diagram showing a specific example of a position code table.

FIG. 5 is a diagram showing a specific example of a rank code table.

FIG. 6 is a diagram for explaining updating of a ranking table.

FIG. 7 is a diagram for explaining updating of a data buffer and a dictionary buffer.

FIG. 8 is a diagram showing a schematic configuration of a data decompression device according to an embodiment.

FIG. 9 is a diagram showing an example of contents of a dictionary buffer.

FIG. 10 is a diagram for explaining the contents of a top buffer and a chain buffer and how to use them.

FIG. 11 is a diagram showing a schematic configuration of a dictionary buffer in the case of determining a match of four characters simultaneously.

FIG. 12 is a diagram for specifically explaining an update of a ranking table.

FIG. 13 is a diagram showing a detailed configuration of a data compression apparatus according to an embodiment.

FIG. 14 is a diagram showing a detailed configuration of a data compression apparatus according to an embodiment.

FIG. 15 is a diagram showing a detailed configuration of a data area in a dictionary / data buffer according to an embodiment.

FIG. 16 is a diagram showing a detailed configuration of a data decompression device according to an embodiment.

FIG. 17 is an explanatory diagram of a conventional example.

FIG. 18 is an explanatory diagram of a conventional example.

[Explanation of symbols]

 10 data buffer 12 dictionary buffer 14 buffer update unit 16 match length coding unit 18 match length code table 20 position coding unit 22 position code table 24 rank coding unit 26 rank code table 27 rank table 28 table updating unit

Claims (4)

[Claims] 1. Data for storing a data string of a predetermined word length located at the end of the sequentially input uncompressed data as processing data and a data string of a predetermined word length positioned before it as a dictionary, respectively. The buffer and the dictionary buffer, and for each word forming the processing data in the data buffer, it is searched whether or not there is a match with each word forming the dictionary, and a match obtained by encoding the longest match length. When the match length coding means outputs a long code and the match length coding means determines a match, the position in the dictionary of the longest word length in the matched word string is coded. A position table that outputs a position code that outputs a position code, and a rank table that associates a rank code with a shorter bit length with a higher existence probability for each word of uncompressed data. A rank code that has the rank code and outputs a rank code corresponding to the first word of the processed data in the data buffer by searching the rank table when the match length coding means determines a mismatch. Encoding means, table updating means for updating the ranking table in consideration of the first word of the processed data that has been encoded when the encoding processing is performed by the encoding means, and the position When the encoding is performed by the encoding means or the rank encoding means, a part or all of the encoded processing data is transferred to the dictionary in the dictionary buffer, and the transferred data is not compressed. Buffer updating means for performing a process of additionally storing data in the data buffer, and a word matching each word of the processed data in the dictionary In some cases, the match length and its position are encoded respectively, and when there is no matched word, the match length indicating that fact and the first word of the processed data are encoded respectively to obtain compressed data. And a data compression device. 2. The top buffer according to claim 1, wherein the match length encoding means stores a top address for each different word when each word of the dictionary in the dictionary buffer is viewed in order from the top. A chain buffer that stores data indicating at which address in the dictionary the same word is stored next when each word of the dictionary in the dictionary buffer is sequentially viewed from the beginning, A data compression apparatus characterized in that an address in the corresponding dictionary is specified by searching the top buffer and the chain buffer based on the first word of the processed data in the data buffer. 3. The dictionary buffer and the data buffer according to claim 1, wherein the dictionary buffer and the data buffer are composed of a plurality of memory elements whose addresses are continuous with each other, and the buffer updating unit is the processed data that has been encoded. And storing each word constituting a part or all of the plurality of memory elements in a distributed manner in each of the plurality of memory elements, and the coincidence length encoding means reads data from each of the plurality of memory elements at the same time, A data compression device characterized by performing a match search. 4. A dictionary buffer for storing a data string of a predetermined word length, which is located at the end of uncompressed data obtained by decompressing compressed data, as a dictionary, and is located at the beginning of sequentially input compressed data. If the match length decoding means for decoding the match length code that matches and outputs concrete match length data, and the match length code located at the beginning of the compressed data indicate a match, the match length decoding means is positioned next to the match length decoding means. If the position decoding means for decoding the position code and outputting the data indicating the storage position in the dictionary and the matching length code located at the beginning of the compressed data indicate matching, the position decoding is performed. The storage position in the dictionary is specified based on the data output from the means, and the storage position is used as the start address to read the data from the dictionary by the amount corresponding to the matching length data. A dictionary read control means for outputting data, and a rank table in which each word of the uncompressed data is associated with a short rank code in descending order of existence probability, and a matching length located at the beginning of the compressed data. A rank decoding means for performing rank decoding for decoding the non-compressed data by searching the rank table based on the rank code positioned next when the codes indicate disagreement; Table updating means for updating the rank table in consideration of the decoded non-compressed data when the decoding processing is performed by the decoding means, and decoding by the position decoding means or the rank decoding means And a dictionary update means for updating the dictionary so as to include the uncompressed data that has been decoded, when the match length code and the position code and A data decompression device, characterized in that decompressed data is obtained by decoding compressed data combined with either one of the rank codes.