JPH06266532A - Data compression processor - Google Patents

Abstract

(57) [Abstract] [Purpose] To provide a data compression processing device in which a dictionary is configured in the form of a table to speed up a search, and the length of a character string to be collated is not limited. [Arrangement] The appearance character string is stored in an input register, the character string and the pointer are read from the dictionary with the hash value of the appearance character string as an address, and the appearance character string and the pointer are stored.
Store the first character of the appearance character string in the input buffer, read the character based on the pointer from the dictionary and generate the pointer, compare the character read from the input buffer with the first character of the appearance character string, and read the character from the dictionary The column and the appearance character string are compared, the comparison result and the value of the flag register are input, a logical value is output by the operation determination logic, the values of the flag register and the counter are updated by the logical value, and the pointer from the dictionary and the above The difference value with the generation pointer is taken, the first character of the appearance character string, the flag register, the counter, and the value of the difference circuit are edited based on the logical value, and the edited result is output.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a data compression processing device which is used for reducing the amount of data on a storage medium in data processing and reducing the data storage cost and the data communication cost. .

[0002]

2. Description of the Related Art Conventionally, in a compression processing method for registering an appearing character pattern in a dictionary, a dictionary is constructed as a search tree by storing which character follows a certain character.

[0003]

However, in the above-described conventional dictionary-based compression processing, it is necessary to refer to the pointer every time one character is collated to follow the search tree, and it is not possible to increase the speed. There was a problem in collating a character string whose height was higher than. SUMMARY OF THE INVENTION It is an object of the present invention to provide a data compression processing device in which a dictionary is constructed in the form of a table to speed up a search, and the length of a character string to be collated is not limited.

[0004]

In order to achieve the above object, the data compression processing apparatus of the present invention provides an input register for storing an appearance character string, an entry use state flag, a character string and an appearance position of the character string. A dictionary storage unit that has a dictionary having the pointer as an entry, reads the entry with the hash value of the appearance character string as an address, and stores the entry including the appearance character string, and stores the first character of the appearance character string in the input buffer. Then, a character is read based on the pointer of the entry read from the dictionary storage means, and the input buffer means for generating and outputting the pointer is compared with the character read from the input buffer means and the first character of the appearance character string. Then, the result is output, and the character string of the entry read from the dictionary storage means is compared with the appearance character string, and the result is output. A stage, an operation determination logic for outputting a logical value by using the output of the comparing means and the value of the flag register as an input, a flag register and a counter whose value is updated by the logical value, and an entry read from the dictionary storage means. The difference means for obtaining the difference value between the pointer and the pointer generated by the input buffer means, the first character of the appearance character string, the flag register, the counter, and the value of the difference circuit are edited based on the logical value, and the edited result is output. It is equipped with editing means.

[0005]

When the data string is collated, the input data and the data string in the dictionary are collated. This eliminates the need to refer to the pointer for each character for comparison. Further, when collating a data string longer than the data string registered in the dictionary, the comparison is made with the data pointed to by the pointer in the entry, so there is no limit on the length of the data string collation.

[0006]

1 is a block diagram of a compression circuit 5 according to an embodiment of the present invention.
It is explanatory drawing of 0, 1 is an input register of n characters, 2 is m
A character output register, 3 is a hash circuit, 4 is a dictionary registration / readout circuit, 5 is a dictionary, and 3, 4, and 5 constitute a dictionary storage means. 6 is an input buffer registration / readout circuit, 7 is an input buffer, and 6 and 7 constitute an input buffer means. 8 is a comparison circuit, 9 is an editing circuit, 1
0 is an operation determination logic, 11 is a difference circuit, 12 is a 1-bit flag register, 13 is a counter, 14 is an address register that points to an entry in the dictionary, 15 is an OR circuit, 16
Is an address register indicating a write address in the input buffer, 17 is an adder for adding 1, 18 is a selector, 1
9 is an address register indicating an address in the input buffer, 20 is a 1-character register, 21 is a 1-character register, 22 is a 3-character register, 23 is a 3-character register, 24 and 25 are comparators, 26 is a selector , 27 is an address register indicating a read address in the input buffer, and 28 is an adder for adding 1. 900 is the comparator 2
The signal lines C1 and 901 from 5 to the operation decision logic 10 are signal lines C2 and 902 from the comparator 24 to the operation decision logic 10, and the signal lines XC and 903 from the operation decision logic 10 to the counter 13 and the editing circuit 9 are operation. Signal lines XF, 9 from the decision logic 10 to the flag register 12, selector 26 and editing circuit 9
Reference numeral 04 is a signal line XI from the operation decision logic 10 to the editing circuit 9 and the output register 2, and 905 is a signal line F from the flag register 12 to the operation decision logic 10 and the editing circuit 9. Further, in the present embodiment, the width of 22 and 23 is set to 3 characters, but any width of 2 or more may be used, and the width of 1 is 22 or 2
It is sufficient if the width is 3 or more. The compression in the present invention means a code conversion that can be restored.

First, n characters of input data sent from the outside enter the input register 1. Input register 1 here
The input method is to shift n characters and shift n characters. For example, the data is ABCDE, and the value of n is 3
Then, ABC is input first, BCD is input next, and CDE is input next. Data exchange between the compression circuit 50 and the outside will be described with reference to FIG. The first three characters of the input data in the input register 1 are sent to the hash circuit 3 and the hash value is calculated. The method of calculating the hash may be arbitrary, but a proper odd value, for example, a remainder of 1023 is usually taken. This hash value is sent to the register 14 of the dictionary registration / readout circuit 4 and used as the entry address of the dictionary 5. The dictionary 5 will be described in detail with reference to FIG.
Is a memory having entries of a flag, a character pattern of three characters, and a pointer to the input buffer 7.

An entry is read from the dictionary 5 using the data in the register 14 as an entry address. However, the reading is performed only when the flag is 1, and when the flag is 0, the reading is not performed. In the read destination of the entry, the character pattern portion of three characters is the register 22, and the pointer portion is the difference circuit 11 and the selector 26.

Before explaining the difference circuit 11 and the selector 26, the register 16 and the adder 17 will be described. The register 16 is a register for storing the write address of the input data to the input buffer 7, and the adder 17
Is an adder for adding 1 to the data in the register 16. The initial value of the register 16 is 0. Details of the difference circuit 11 will be described with reference to FIG. In FIG. 2, 30 is a register, 31 is a register, and 32 is a subtracter for subtracting the data in the register 31 from the data in the register 30.
The data in the register 16 is the register 3 of the difference circuit 11.
0, and of the entries of the dictionary 5, the pointer is sent to the register 31. These data are subtracted by the subtractor 32, and the result (hereinafter referred to as offset) is sent to the editing circuit 9.

A pointer out of the entries of the dictionary 5 is sent to the selector 26, and the data added by the adder 28 is sent. This selection operation is the operation decision logic 10
When the signal sent from is 0, the data sent from the dictionary 5 is selected, and when the signal is 1, the data sent from the adder 28 is selected. The data selected by the selector 26 enters the register 27. This is sent to the adder 28 and the selector 18. In the adder 28, 1 is added,
This result is sent to the selector 26. The data in the register 27 is sent to the selector 18, and the register 16
The data in is sent. The data selection timing of the selector 18 is such that the data sent from the register 27 is selected in the next cycle in which the data is set in the register 27, and the data sent from the register 16 in the next cycle is selected. And sent to the register 19. In the latter cycle, the data added by the adder 17 is set in the register 16, while the OR circuit 15 sets 1
Bit flag “1”, the first 3 characters of input register 1,
The data in the register 16 are combined in this order and stored in the entry address pointed to by the data in the register 14. In the input buffer 7, in the next cycle after the data of the register 27 is stored in the register 19, the register 19
The data whose address is the data in the input buffer 7
The data is read out to the register 20 in the comparison circuit 8. On the other hand, in the next cycle after the data in the register 16 is stored in the register 19, the first character of the input register 1 is stored in the input buffer 7 by using the data in the register 19 as an address. In the comparison circuit 8, the first character of the input register 1 is entered in the register 21, and this is compared with the data read from the input buffer 7 to the register 20 by the comparator 24. The comparison result is sent to the operation decision logic 10 by the signal line 901 (C2). The register 22 stores the pattern of three characters of the entries read from the dictionary 5, the register 23 stores the first three characters of the data in the input register 1, and these are compared by the comparator 25. The comparison result is the operation decision logic 1 by the signal line 900 (C1)
Sent to 0. In the flag register 12, when the signal sent from the operation decision logic 10 via the signal line 903 (XF) is 0, it is set to 0, and when the signal is 1, it is set to 1. The flag in the flag register 12 is the signal line 905.
(F) sends it to the operation decision logic 10 and the editing circuit 9. The counter 13 is updated when the signal 1 is sent from the operation decision logic 10, and the signal is set to 0.
At that time, the counter is initialized and the initial value is 1. Here, when the signal is 0, the initial value is 1 instead of 3.
The reason for this is that after the comparator 25 compares data for three characters, the comparator 24 also compares the second and third characters of the same data and updates the counter each time.

The operation of the editing circuit 9 will be described with reference to FIG. In FIG. 3, 40 is a selector and 41 is an OR circuit. Of the inputs to the editing circuit 9, the data is the flag from the register 12, the counter value from the counter 13, and the input register 1.
The first character of the data in, the offset from the difference circuit 11, and the input signal are from the operation determination logic 10 to the signal line 904 (X
I) and the signal line 903 (X
F) and the signal line 902 (X
This is the signal sent by C). The offset of the difference circuit 11 and the first character of the input register 1 are sent to the selector 40. Then, the signal line 903 (X
When the signal sent by F) is 0, the data sent from the input data 1 is selected, and when the signal is 1, the offset sent from the difference circuit 11 is selected. In the OR circuit 41, the flag sent from the flag register 12, the counter value sent from the counter 13, the data sent from the selector 40, and the data sent from the input register 1 are combined in this order. And the result is sent to the output register 2. First, only when the signal sent by the signal line 904 (XI) is 1, the flag from the flag register 12 and the data from the selector 40 pass through the OR circuit 41 and are sent to the output register 2 and held therein. to continue. The counter value from the counter 13 passes through the OR circuit 41 only when the signal sent by the signal line 902 (XC) is 0, and is sent to the output register 2 and held therein. In addition, the signal line 903 (X
When the signal sent by F) is 0 (XF = 0)
Only the one-character data sent from the input register 2 is sent to the output register 2. In this case, 1 for every character sent
The address on the output register is shifted by character and sent so as to increase.

The operation decision logic 10 is a circuit implemented by combinational logic based on the specifications of FIG. 1 in FIG.
0a represents the input signal and the output signal in the form of a table. In 10a, the first row shows the distinction between the input signal and the output signal, and the second row shows the item number and the signal line. Item No. 1 is an input signal, when F is 0 and C1 is 0, the output signal is 0 for XF, 1 for XC, and 0 for XI. Item No. 2 is an input signal when F is 0 and C1 is 1, and the output signal is XF is 1, XC is 0, and XI is 1. Item No. 3 is an input signal in which F is 1 and C2 is 1, and the output signal is 1 in XF, 1 in XC, and 0 in XI. No. 4 is an input signal, F is 1, C1 is 0, C2
Is 0, XF is 0, XC is 0, XI
Is 1. Item No. 5 is an input signal, when F is 1, C1 is 1, and C2 is 0, the output signal is 1 for XF, 0 for XC, and 1 for XI. In the output register 2, the signal line 90
When the signal sent by 4 (XI) is 1 (X
The output code is output at I = 1). As for the data set in the output register, in the case of compressed data, the flag and the offset are stored first, and then, when the signal 1 is sent by the signal line 904 (XI), the data is output from the editing circuit 9. When the counter value is sent, this is output register 2
Stored in and outputs this ordered pair of flags, counter values, and offsets. Immediately after the output is completed, the flag and the offset or the first character of the input register 1 are stored. In the case of uncompressed data, the flag and the first 1 character of the input register 1 are stored first, and then the first 1 character of the input register 1 is sequentially stored until the uncompressed data is exhausted.
When the counter value is sent from the editing circuit 9 while the signal 1 is sent through the signal line 904 (XI), the counter value is stored in the output register 2, and the flag, the counter value, and the character string are arranged in this order. Outputs a pair of. Immediately after the output is completed, the flag and the offset or the first character of the input register 1 are stored.

FIG. 5 is a system configuration diagram to which an embodiment of the present invention is applied. In the figure, 50 is the compression circuit of FIG. 1, 50 is a storage device, 60 is a storage device, 100 is input data in the storage device 60, and 101 is an output result in the storage device 70. The input data 100 in the storage device 60 is read by the compression circuit 50, is compressed in the compression circuit 50, is output to the storage device 70, and becomes the output result 101.
The input to the compression circuit 50 is performed while shifting by one character in units of n characters. For example, as input data ABC
Considering DE, if n is 3, ABC is input first, then one character is shifted, so BCD is input, and then CDE is input. The output from the compression circuit 50 is generally of variable length. In the case of compressed data, the flag, the counter value, and the offset are output. Normally, the flag and the counter value are combined into one character data, and the offset is the data for one character. The data is output. In the case of uncompressed data, the flag, the counter value, and the character string are output. Normally, the flag and the counter value are combined into one character, so the character string length +
The data of the length of is output. In the present invention, compression means decompressible code conversion, but the length of input data and the length of output data do not necessarily match. That is, the data length may be shortened or lengthened due to the compression. Generally, the resulting data length depends on the data itself.

FIG. 6 shows an output code generated in the editing circuit 9. In the figure, 102 is a non-compressed code and 103 is a compressed code. The structure of the uncompressed code 102 has a flag 0 indicating that it is an uncompressed code, a counter value that indicates the uncompressed length, that is, the number of characters of uncompressed data, and an uncompressed character string at the end. It is attached. Normally, the flag and the counter value are one character, and the uncompressed character string has one or more characters. Therefore, the uncompressed code is data of two or more characters. Generally, the number of characters in an uncompressed character string is indefinite, and the uncompressed code is a variable length code. The structure of the compressed code 103 has a flag 1 indicating that it is a compressed code at the beginning, then a pattern length, that is, a counter value indicating the length of a pattern that matches the current data, and finally from the current data to the previous one. The offset to the pattern that appears in is attached. The compressed code is a fixed length code because there is no undefined part. Normally, the flag and the counter value are one character, and the offset is one character, so the compression code has a length of two characters.

FIG. 7 shows input data 100 and compression result 101.
Is the details. In the input data 100, since the first character up to the sixth character ABCDEF is an uncompressed part, when an uncompressed code is generated according to FIG. 6, first, the uncompressed flag is 0, then the length of the uncompressed part. 6 and the last is uncompressed character ABCDEF, that is, 06ABC
DEF becomes the uncompressed code. Furthermore, input data 100
ABCDE from the 7th character to the 11th character is 5 from the beginning
The exact same data exists for each character. Therefore, this portion can be compressed, and when the compression code is generated according to FIG. 6, first, the compression flag is 1, and then the pattern length. However, this is 5 because the data for 5 characters is the same, and the last. This is the offset, but this is the distance from the 7th character A to the first 1st character A.
Becomes That is, the compressed code is 156. Since the two characters XY remaining in the input data 100 are uncompressed characters, similarly, the uncompressed code 02X
Y is generated. As a result, the compression result 101 is generated for the input data 100.

FIG. 8 shows the details of the dictionary 5. The dictionary is a memory with flags. In the figure, the first column is a use flag. When the use flag is 0, it means that the data in the entry is invalid, and when the use flag is 1, it means that the data in the entry is usable. . A data pattern is registered in the second column, and in this embodiment, a three-character pattern is registered. This is used for matching with input data during hash search. As a result, the collation of data up to 3 characters can be performed only with the pattern data in the dictionary. A pointer to the second character of the pattern data of the second column in the input buffer 7 is registered in the third column. This pointer is used for collation with data of 4 characters or more. This usage will be described later.

FIG. 9 is a diagram for explaining the search / collation processing in the compression circuit 50 of FIG.
Processing of ABCDEF and processing of the next A. In the figure, 100 is input data, 5 is a dictionary, 7 is an input buffer, and 104 is a hash value calculated in the hash circuit 3 of FIG.

The compression process will be described below with reference to FIGS. 1, 7, and 9.

In the input data 100, the first character ABC is input to the input register 1 shown in FIG. First, the hash value of the three-character ABC is calculated by the hash circuit 3, and the result (which is 1) is stored in the register 14. Next, the dictionary is looked up with 1 in the register 14 as the entry address of the dictionary 5, but the first entry is not referenced because the flag is 0. Therefore, data transfer to the difference circuit 11, the register 22 and the selector 26 is not performed.
As a result, the data stored in the difference circuit 11 and the register 22 is meaningless data. On the other hand, the data in the register 16 (initial value 0) is sent to the selector 18 and the adder 17. In the selector 18, the data sent from the register 16 enters the register 19. This timing is the timing when data is set in the register 14. The first character A of the input register 1 is stored in the input buffer 7 using the data in the register 19 as the address of the input buffer 7. Further, at the timing when the data is stored in the register 19, the data is added to the register 16 by the adder 17,
It is set in the register 16. This is also the difference circuit 1
1, sent to the OR circuit 15. In the OR fruit color 15, the pair of 1 and 1 sent from ABC and the register 16 is used as the dictionary 5
To the entry 1 based on the data in the register 14. Further, the difference circuit 11 calculates a meaningless difference value and sends it to the editing circuit 9. Further, meaningless data is selected by the selector 26 and sent to the register 27. The data in the register 27 is sent to the selector 18 and the adder 28. The adder 28 performs addition, and the result is the selector 2
Sent to 6. The data sent from the register 27 is sent to the register 19 in the selector 18. Register 1
Using the data of 9 as an address, meaningless data of one character is set in the register 20 from the input buffer. To the register 21, the first character A of the input register 1 is the register 1
4 is stored at the timing when the hash value is set, and the data of the register 20 (not the data set in the register 20 described above but the data set in the register 20 by the input buffer 7 before that), In the next cycle, it is compared by the comparator 24, and the mismatch signal 0 is sent to the operation decision logic 10 by the signal line C2. The three-character data ABC in the input register 1 is stored in the register 23, which is compared with the register 22 by the comparator 25, and the disagreement signal 0 is sent to the operation decision logic 10 by the signal line C1. Also, flag 0 in register 12 is sent to operation decision logic 10. That is, F = 0, C1 = 0, and C2 = 0. As a result, the output of the operation decision logic 10 is XF = 0, XC =
1, XI = 0. The signal generated by the operation decision logic 10 sets the register 12 to 0 and the counter 13 to 1. In the editing circuit 9, only in the case of initial processing, X
Even if I = 0, the flag 0 and the first character A of the input register 1 are sent to the output register 21 and set. Below, BCD ~
The same process is performed on the EFA input, and the flag register becomes 0 and the counter 13 becomes 5. In these cases, XF = 0 and only the first character of the input register 1 is output from the editing circuit 9 to the output register 2.

In the input data 100, the FAB of three characters is input to the input register 1 of FIG. 1 for the sixth input. First, the hash value of the three-character FAB is calculated by the hash circuit 3, and the result (which is 6) is stored in the register 14. Next, the dictionary is looked up using 6 in the register 14 as the entry address of the dictionary 5, but the sixth entry is not referenced because the flag is 0. Therefore, data transfer to the difference circuit 11, the register 22 and the selector 26 is not performed. As a result, the data stored in the difference circuit 11 and the register 22 is meaningless data. On the other hand, the data (5) in the register 16 is the selector 18 and the adder 17
Sent to. In the selector 18, the data sent from the register 16 enters the register 19. This timing is the timing when data is set in the register 14.
The first character F of the input register 1 is stored in the input buffer 7 by using the data in the register 19 as the address of the input buffer 7. At the timing when the data is stored in the register 19, the data in the register 16 is added by the adder 17 and set in the register 16. This is also sent to the difference circuit 11 and the OR circuit 15. In the OR circuit 15, 1
And the pair of FAB and 6 sent from the register 16 are sent to the dictionary 5 and stored in the entry 6 based on the data in the register 14. Further, the difference circuit 11 calculates a meaningless difference value and sends it to the editing circuit 9.

Further, meaningless data is selected by the selector 26 and sent to the register 27. The data in the register 27 is sent to the selector 18 and the adder 28. Addition is performed by the adder 28, and the result is sent to the selector 26. The data sent from the register 27 is sent to the register 19 in the selector 18. Using the data in the register 19 as an address, meaningless data of one character is set in the register 20 from the input buffer 7. The first character F of the input register 1 is stored in the register 21 at the timing when the hash value is set in the register 14, and the data of the register 20 (not the data set in the register 20,
The data which has been set in the register 20 from the input buffer 7 before that) is compared with the comparator 24 in the next cycle, and the mismatch signal 0 is sent to the operation decision logic 10 through the signal line C2. The three-character data FAB in the input register 1 is stored in the register 23, which is compared with the register 22 by the comparator 25, and the disagreement signal 0 is sent to the operation decision logic 10 by the signal line C1. Also, flag 0 in register 12 is sent to operation decision logic 10. That is, F =
0, C1 = 0, C2 = 0. As a result, the output of the operation decision logic 10 becomes XF = 0, XC = 1, and XI = 0. The signal generated by the operation decision logic 10 sets the register 12 to 0 and the counter 13 to 6. In the editing circuit 9, since XF = 0, the head 1 of the input register 1
Only the characters are sent to the output register 2 and set.

In the input data 100, the third three-character ABC is input to the input register 1 of FIG. First, the hash value of the three-character ABC is calculated by the hash circuit 3, and the result (which is set to 1) is stored in the register 14
to go into. Next, the dictionary is looked up with 1 in the register 14 as the entry address of the dictionary 5, and the first entry is referred to because the flag is 1. Therefore, data transfer to the difference circuit 11, register 22, and selector 26 is performed. As a result, 1 is input to the difference circuit 11 and AB is input to the register 22.
Enter C. On the other hand, the data (6) in the register 16 is sent to the selector 18 and the adder 17. In the selector 18, the data sent from the register 16 enters the register 19. This timing is the timing when data is set in the register 14. Using the data in the register 19 as the address of the input buffer 7, the first character A of the input register 1 is stored in the input buffer 7 (at the position next to F).
Further, at the timing when the data is stored in the register 19, the data in the register 16 is added by the adder 17 and set in the register 16. This is also the difference circuit 11,
It is sent to the OR circuit 15. In the OR circuit 15, 1 and AB
The pair of C and 7 sent from the register 16 is sent to the dictionary 5 and stored in the entry 1 based on the data in the register 14. Further, the difference circuit 11 calculates the difference value and sends the result of 6 to the editing circuit 9. In addition, the selector 26
Then, 1 which is the data from the dictionary is selected and sent to the register 27. The data in the register 27 is sent to the selector 18 and the adder 28. Addition is performed by the adder 28, and the result is sent to the selector 26. The data sent from the register 27 is sent to the register 19 in the selector 18. Using the data in the register 19 as an address, one character of data B is set in the register 20 from the input buffer 7,
It is used to compare with the next input character. Register 2
To enter 1, the first character A of input register 1 is register 14
Is stored at the timing when the hash value is set to the data in the register 20 (data stored in the register 20 before the data B) and is compared by the comparator 24 in the next cycle. Sent to the action decision logic 10 by C2. The three-character data ABC in the input register 1 is stored in the register 23, which is compared with the register 22 by the comparator 25, and the coincidence signal 1 is sent to the operation decision logic 10 through the signal line C1. Also, flag 0 in register 12 is sent to operation decision logic 10. That is, F =
0, C1 = 0, C2 = 0. As a result, the output of the operation decision logic 10 becomes XF = 1, XC = 0, and XI = 1. The signal generated by the operation decision logic 10 sets the register 12 to 1 and the counter 13 to 1.

The counter value 6 is sent from the editing circuit 9 to the output register 2 before the counter 13 is initialized to 1. 3 will be described by taking out only the state where data is set in the output register 2, the flags 0 and A are first sent to the output register 2 by the OR circuit 41 and the selector 40 in the editing circuit 9. Hereafter, B, C, D, E,
F is sent to the output register 2 through the OR circuit 41.
Then, during the ABC processing from the 7th character of the input data 100, the counter value that has been sent from the counter 13 and has been ignored so far becomes valid immediately before the update (the counter value is 6), and this is the OR circuit 41. Through output register 2
Sent to. Now the output register 2 has data 06AB
CDEF is set, and this is output as shown in the compression result of FIG. After the data is output from the output register 2, the flag 1 from the register 12 and the offset 6 from the difference circuit 11 are sent from the editing circuit 9 to the output register 2 and set. After that, the processing is performed on the inputs of BCD to DEX, and the counter 13 is updated.

In the input data 100, EXY of three characters from the eleventh character is input to the input register 1 of FIG. First, the hash value of the three-character EXY is calculated by the hash circuit 3, and the result (which is 1) is stored in the register 14. Next, the dictionary is looked up with 1 in the register 14 as the entry address of the dictionary 5, and the first entry is referred to because the flag is 1. Therefore, the difference circuit 1
1, data transfer to the register 22, the selector 26 is performed. As a result, the difference circuit 11 has seven registers 22
ABC enters. On the other hand, the data (1
0) is sent to the selector 18 and the adder 17. In the selector 18, the data sent from the register 16 enters the register 19. This timing is the timing when data is set in the register 14. The first character E of the input register 1 is stored in the input buffer 7 by using the data in the register 19 as the address of the input buffer 7. The data in the register 16 is added by the adder 17 at the timing when the data is stored in the register 19 and set in the register 16. This is also the difference circuit 11 and the OR circuit 15
Sent to. In the OR circuit 15, the pair of 1 and EXY and 11 sent from the register 16 is sent to the dictionary 5 and stored in the entry 1 based on the data in the register 14.
Further, the difference circuit 11 calculates a difference value and sends the result of 4 to the editing circuit 9. The selector 26 selects the data added by the adder 28 and sends it to the register 27. The data of the register 27 is the selector 18 and the adder 28.
Sent to. Addition is performed by the adder 28, and the result is sent to the selector 26. The data sent from the register 27 is sent to the register 19 in the selector 18. Using the data in the register 19 as an address, one character data F is set in the register 20 from the input buffer 7 and is used for comparison with the next input character. The first character E of the input register 1 is stored in the register 21 at the timing when the hash value is set in the register 14, and the register 20
Data (data E stored in the register 20 before the data F) is compared by the comparator 24 in the next cycle, and the coincidence signal 1 is sent to the operation decision logic 10 by the signal line C2. The register 23 stores the three-character data EXY in the input register 1, and the register 22 and the comparator 25
And the mismatch signal 0 is sent to the operation decision logic 10 through the signal line C1. Also, flag 1 in register 12
Are sent to the motion decision logic 10. That is, F = 1, C
1 = 0 and C2 = 1. This enables the operation decision logic 10
Output becomes XF = 1, XC = 1, and XI = 0. The register 12 is set to 1 by the signal generated by the operation decision logic 10.
, And the counter 13 becomes 5. The editing circuit 9 ignores all the data that has been sent and outputs nothing to the output register 2.

In the input data 100, the two-character XY from the 12th character is input to the input register 1 of FIG.
First, the hash value of the two-character XY is calculated by the hash circuit 3, and the result (which is 1) is stored in the register 14
to go into. Next, the dictionary is looked up with 1 in the register 14 as the entry address of the dictionary 5, and the first entry is referred to because the flag is 1. Therefore, data transfer to the difference circuit 11, register 22, and selector 26 is performed. As a result, 11 is input to the difference circuit 11 and EXY is input to the register 22. On the other hand, the data (1
1) is sent to the selector 18 and the adder 17. In the selector 18, the data sent from the register 16 enters the register 19. This timing is the timing when data is set in the register 14. The first character X of the input register 1 is stored in the input buffer 7 using the data in the register 19 as the address of the input buffer 7. At the timing when the data is stored in the register 19, the data in the register 16 is added by the adder 17,
Is set to. This is also the difference circuit 11 and the OR circuit 1.
Sent to 5. In the OR circuit 15, the pair of 1 and XY and 12 sent from the register 16 is sent to the dictionary 5 and stored in the entry 1 based on the data in the register 14.
Further, the difference circuit 11 calculates a difference value and sends 1 as a result to the editing circuit 9. The selector 26 selects the data added by the adder 28 and sends it to the register 27. The data of the register 27 is the selector 18 and the adder 28.
Sent to. Addition is performed by the adder 28, and the result is sent to the selector 26. The data sent from the register 27 is sent to the register 19 in the selector 18. Using the data in the register 19 as an address, one character of data X is set in the register 20 from the input buffer 7 and is used for comparison with the next input character. The first character X of the input register 1 is stored in the register 21 at the timing when the hash value is set in the register 14, and the register 20
Data (data F stored in the register 20 before the data X) is compared by the comparator 24 in the next cycle, and the disagreement signal 0 is determined by the operation determination logic 10 by the signal line C2.
Sent to. The two-character data XY in the input register 1 is stored in the register 23, and the register 22 and the comparator 25
And the mismatch signal 0 is sent to the operation decision logic 10. Further, the flag 1 in the register 12 is sent to the operation decision logic 10 by the signal line C1. That is, F = 1, C
1 = 0 and C2 = 0. This enables the operation decision logic 10
Output becomes XF = 0, XC = 0, and XI = 1. The signal generated by the operation decision logic 10 causes the register 12 to reach 0.
Is set to 1, and the counter 13 becomes 1. The counter value 5 is sent from the editing circuit 9 to the output register 2 before the counter 13 is initialized to 1.

Only the manner in which the data is set in the output register 2 will be extracted and explained with reference to FIG.
The flag 1 and the offset 6 are sent to the output register 2 by the OR circuit 41 and the selector 40 in the editing circuit 9 by the processing of. Then, the data coming into the editing circuit 9 is continuously ignored until the input data XY is processed, and X
During the processing of Y, the counter value immediately before the update becomes valid (the counter value is 5), and this is sent to the output register 2 through the OR circuit 41. As a result, the data 15 6 is set in the output register 2 and is output as shown in the compression result of FIG. 7 (since XI = 1). After the data is output from the output register 2, the flag 0 from the register 12 and the X from the input register 1 are sent from the editing circuit 9 to the output register 2 and set.

[0027]

As described above, according to the present invention, the dictionary is constructed in the form of a table, and the length of the data string registered in the entry of the dictionary or more can be collated. There is an effect that the collation can be performed and the length of the data string to be collated is not limited.

[Brief description of drawings]

FIG. 1 is a block diagram showing a configuration of a compression circuit according to an embodiment of the present invention.

FIG. 2 is a diagram showing a detailed configuration of a difference circuit in FIG.

3 is a diagram showing a detailed configuration of an editing circuit in FIG.

FIG. 4 is a diagram showing the specifications of the operation decision logic of FIG.

FIG. 5 is a diagram illustrating a usage example of an embodiment of the present invention.

FIG. 6 is a diagram showing a format of an output code.

FIG. 7 is a diagram showing a compression result for input data.

FIG. 8 is a diagram showing a configuration of a dictionary.

FIG. 9 is a diagram illustrating a search and collation process in the compression circuit 50 in FIG.

[Explanation of symbols]

 1 Input Register 2 Output Register 3 Hash Circuit 4 Dictionary Registration / Readout Circuit 5 Dictionary 6 Input Buffer Registration / Readout Circuit 7 Input Buffer 8 Comparison Circuit 9 Editing Circuit 10 Operation Decision Logic 11 Difference Circuit 12 Flag Register 13 Counter 50 Compression Circuit

Claims (1)

[Claims] 1. A data compression processing device for compressing data of a text data string, wherein an input register for storing an appearing character string, an entry usage status flag, a character string, and a pointer indicating an appearance position of the character string are entries. Dictionary storage means for reading an entry with a hash value of the appearing character string as an address and storing an entry including the appearing character string; and storing the first character of the appearing character string in an input buffer, the dictionary The input buffer means for reading out a character based on the entry pointer read out from the storage means and for generating and outputting the pointer is compared with the character read out from the input buffer means and the first character of the appearance character string. And outputs the result and compares the character string of the entry read from the dictionary storage means with the appearance character string. Comparing means for outputting a result and outputting a result, operation decision logic for outputting a logical value with the output of the comparing means and the value of the flag register as input, a flag register and a counter whose value is updated by the logical value, and the dictionary Difference means for taking a difference value between the pointer of the entry read from the storage means and the pointer generated by the input buffer means, the first character of the appearance character string, the flag register, the counter, and the value of the difference circuit A data compression processing apparatus comprising: an editing unit that edits based on a logical value and outputs an edited result.