JPH08265167A - Data compression device - Google Patents

Abstract

(57) [Abstract] [Purpose] The objective is to reduce the size and size of the data compression device. Configuration: The control unit 102 determines whether or not the input character stored in the input register 101 is the first character of the partial character string, and according to the determination result, each matching position pointer 10
The maximum match sequence is detected by comparing the characters read from the dictionary memory 103 with the input characters using the comparison circuit 106 while changing the addresses held in 9 to 112. The match length of the maximum match sequence is the match length counter 11
The match length and the match position output from the subtractor 116 are output from the code output unit 115 together with the match flag. In addition, the control unit 102
While changing the write address of the input pointer 113, the input character is written in the dictionary memory 103 as needed.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a technique for inputting data and compressing it.

[0002]

2. Description of the Related Art In recent years, the amount of data to be handled has rapidly increased in various fields such as computers and communications. Since the cost of storing data and the cost of communication such as telephone charges are increasing with the increase in the amount of data, the redundancy included in the data string is removed in order to suppress such costs. Therefore, data compression technology for compressing it has been widely used. Data compression technology is used for file archiver, distributed file system,
It is a technology that has already played a very important role in the fields of data communication, voice / image communication, computer networks, etc., and its importance is expected to increase in the future.

In the data compression method, noise-containing compression having distortion (depending on the presence or absence of distortion when decoding is performed to restore the compressed data string (compressed data string) to the original data string (input data string)) Lossy coding) and noiseless compression without distortion (reversible coding). Normally, noisy compression is
It is used for data that can tolerate some distortion such as images and sounds, while noiseless compression is used for data that does not allow distortion, such as files (eg programs) and documents.

The Lempel-Ziv method (hereinafter referred to as the LZ method) is widely used today as noiseless compression. The LZ method is a kind of so-called adaptive coding method in which a character string is read and its statistical properties are extracted for coding. The definition of the character here is the minimum processing unit of the input data string to be encoded.

FIG. 5 is a block diagram showing the configuration of a conventional data compression apparatus 500 which adopts the LZ method. A conventional data compression apparatus 500 will be described with reference to FIG.

As shown in FIG. 5, this data compression device 500 has an input data string (character string) IW input from the outside.
Input memory 501, a dictionary memory 502 in which encoded partial character strings in the input memory 501 are sequentially stored, and a character read from the input memory 501 is read from the dictionary memory 502. A comparison circuit 503 for comparing with a character, a control unit 504 for controlling the entire apparatus 500, a code memory 505 in which a code word generated by the control unit 504 is stored, a flag register 506, a code memory 505, and a flag. Output memory 507 used to output the codeword stored in register 506
Composed of and.

In the above structure, the character string stored in the dictionary memory 502 is used as a dictionary. Control unit 50
4 changes the addresses for reading characters in the input memory 501 and the dictionary memory 502, and compares the characters read from the memories 501 and 502 by using the comparison circuit 503 to compare whether or not the characters match. , Input memory 5
A partial character string (match sequence) in the dictionary memory 502 that matches the partial character string that is the target of encoding 01 is searched.

The search for the matching sequence (partial character string) by the control unit 504 is performed as follows, for example. First, the character matching the first character of the partial character string to be encoded at the present time is sequentially searched from the character stored in the dictionary memory 502 in the earliest, and the character matching the first character is searched. locate. When a character that matches the first character is found, the address where that character is stored (hereinafter referred to as the matching position) is stored, and then the dictionary memory 502
The character following the found character of No. and the character following the first character of the partial character string of the input memory 501 are sequentially compared,
When they match, the number of characters compared (match length) is counted.
This counting is continuously performed until it is compared that the two characters do not match, and the counted value (match length) is stored in association with the already stored start address. As a result, the extraction of one matching series is completed, such matching series extraction is repeated, and the one with the largest matching length is extracted as the maximum matching series from the extracted matching series.

The control unit 504 performs encoding based on the result of this search. Specifically, when the length of the maximum matching sequence found as described above is equal to or greater than a predetermined number, the matching flag is set to "1" and stored in the flag register 506, and the maximum matching sequence is stored. The matching position and the matching length are stored in the code memory 505. On the contrary, when the length of the maximum matching sequence is less than the predetermined number, including the case where the character matching the first character of the partial character string to be encoded is not found in the dictionary memory 502, the matching flag is set to "0". "" Is set and stored in the flag register 506, and the data (for example, ASCII code) representing the first character is stored in the code memory 505 as it is.

As described above, the control unit 504 divides the character string of the input memory 501 into partial character strings and sequentially performs the encoding, and also the input memory 501 and the dictionary memory 5
The contents (character string) stored in 02 are updated. Specifically, for example, when encoding of a partial character string in the input memory 501 is completed, the partial character string of which the encoding is completed is newly registered in the dictionary memory 502, and the input memory 501
In this case, the input data string IW is newly written for the number of characters of this partial character string.

The control unit 504 also includes a flag register 5
When the match flag of the number of bits is stored in 06, the contents stored in the flag register 506 and the code memory 505 are stored in the output memory 507. After that, the code word stored in the output memory 507 is compressed and outputted as a compressed code.
To the outside.

By repeating the above operation, the input data string (character string) IW is compressed. Output memory 5
The compressed code output OW that is output from 07 at any time is output to, for example, a magnetic storage device, and is stored on the magnetic disk here.

For decoding the compressed code output (code word) OW, the character string decoded in the past is used as a dictionary. When the value of the match flag is "0", the character represented by the code word and its value are When the value is "1", the partial character string is extracted from the decoded character string stored as a dictionary according to the code word and copied.

[0014]

However, since the above-described conventional data compression apparatus 500 searches for the maximum matching sequence by repeating the extraction of the matching sequence, the character string to be encoded is stored. I had to go. The character string to be encoded is stored in the input memory 501, but there is a problem that the apparatus 500 is upsized due to the provision of such a memory.

The data compression device is connected to, for example, a bus of a computer and is used to compress data to be stored in the main storage device or an external storage device. For this reason, LSI (Large Scale Inte
grated circuit) is desired. A data compression device having a small scale has been desired so that the LSI can be easily made and the cost can be suppressed.

An object of the present invention is to reduce the size of a data compression device and reduce its cost.

[0017]

A data compression apparatus according to the present invention comprises a storage means for storing a character string input in the past, and refers to the character string stored in the storage means to repeatedly input a part. The following means are provided on the premise that the amount of data representing a character string is compressed by detecting the character string.

First, the character discriminating means discriminates whether or not the input character is the first character of the partial character string. When the character discriminating means discriminates the inputted character as the leading character, the coincident position storing means stores the address of the storing means in which the character coincident with the inputted character is stored as the coincident position.

The reading means stores each time a character following the character judged by the character judging means as the first character is inputted, the address is stored in the memory means while sequentially changing the address from the matching position in accordance with the input of the character. Read the character.

The comparing means compares whether or not the input character and the character read from the storing means by the reading means match, and the writing means, each time a character is input, compares the input character with the input character. Write in the storage means at any time.

The counting means counts the number of times the character judging means judges the inputted character as the first character and then compares the characters when the comparing means agree with each other, thereby calculating the length of the partial character string stored in the storing means. Is counted.

The code generation means, when the comparison result of the comparison means becomes inconsistent after the character discriminating means discriminates the inputted character as the leading character, the code generating means stores the code word representing the partial character string stored in the storing means. It is generated from the matching position and the number of characters counted by the counting means.

In the above construction, a plurality of coincidence position storing means are provided, and the reading means is provided with each time a character is input.
The characters stored at the addresses sequentially changed from the respective coincidence positions stored in the plurality of coincidence position storage means are read out from the storage means, respectively, and the comparison means, each time the reading means reads out the characters from the storage means, The characters read out from the storage means are sequentially compared with the input characters, and the counting means finds among the characters read out from the storage means by the reading means that the comparison means matches the input characters. In the case where there is no character compared with the character input by the comparison means among the characters read by the read means from the storage means, the code generation means stores it in the storage means. It is desirable to generate a codeword that represents a substring that has

[0024]

Each time a character is input, the data compression apparatus of the present invention determines whether or not the input character corresponds to the first character of the partial character string, and the input character is input according to the result of the determination. Encoding is performed by searching whether or not the character is stored in the dictionary (storage means), and by detecting the partial character string repeatedly input while newly registering the input character in the dictionary.

For example, when it is determined that the input character corresponds to the first character of the partial character string, a plurality of addresses (matching positions) in the dictionary in which the character matching the input character is stored are searched. Each time a character is input, the characters that are input after this input character are compared to see if they match the respective characters read from the addresses that were changed consecutively from each matching position. Among them, the maximum matching sequence and its matching length are determined by counting the number of input characters that are compared and are compared. When the maximum matching sequence is determined, a codeword is generated from the matching position and the matching length to encode the input partial character string corresponding to this maximum matching sequence. While this encoding is performed, the input character is newly registered in the dictionary as needed.

As described above, by searching for the matching position, it is possible to perform encoding at any time according to the input of the character, and it is possible to register the input character at any time in the dictionary. . This avoids the need to store the character string to be encoded and reduces the number of memories and the capacity thereof. Therefore, it is possible to reduce the size of the device and reduce its cost.

[0027]

Embodiments of the present invention will now be described in detail with reference to the drawings. FIG. 1 is a block diagram showing the configuration of a data compression apparatus 100 according to this embodiment.

The input data string ID in this data compression device 100 is an external device (not shown) such as CP.
U), for example, ASCII that represents one character in 8 bits
Input with I code. The input data string ID is input from the external device together with the 1-bit write signal, and when the write signal becomes active, the 1-character input data string ID is input.
Are stored in the input register 101.

In addition to the input register 101, the write signal is
It is input to the control unit 102. The controller 102 controls the device 10
The control of 0 as a whole is performed, and the encoding process (the operation thereof will be described below) is activated each time the write signal becomes active.

Characters stored in the input register 101 (hereinafter referred to as input characters) are the data selector 10
4 and the previous data register 105. Although not particularly shown, the previous data register 105 stores the input character (the character stored in the input register 101) when the write signal input from the control unit 102 becomes active.

The data selector 104 inputs the characters stored in the previous data register 105 and the input register 101, respectively, and outputs one selected according to the select signal from the control unit 102 to the comparison circuit 106. Comparison circuit 1
06 is a character output from the data selector 104,
It compares whether or not the characters read from the dictionary memory 103 match, and outputs the comparison result to the control unit 102.

The dictionary memory 103 in this embodiment has four
It has a storage capacity (dictionary size) of Kbytes and stores characters (coded input) for 4Kbytes input in the past. The read address and the write address of the dictionary memory 103 are designated by each pointer connected to the address selector 107.

The address selector 107 has a dictionary head pointer 108, matching position pointers 109 to 112,
And each pointer of the input pointer 113 is connected. The address selector 107 selects one of these according to a select signal from the control unit 102.

Here, each of the above pointers will be described with reference to FIG. FIG. 2 is a diagram showing an example of an address on the dictionary memory 103 indicated by each pointer. Figure 2 (a)
Indicates that the coded input is a dictionary size (4 Kby in this embodiment).
2 (b), the coded input is larger than the dictionary size, and the hatched portion represents the area in which characters are stored. Also,
P1 to P4 indicate the positions of the addresses designated (held) by the matching position pointers 109 to 112, respectively.

As described above, since the dictionary memory 103 stores the characters of 4 Kbytes input in the past, each of the pointers 108 to 113 has 12 bits (2 ¹² = 4).
096).

The dictionary head pointer 108 is used by the control unit 102.
The character string stored in the dictionary memory 103, which is output from, holds the address of the oldest stored character. Therefore, when the encoded input is smaller than the dictionary size (see FIG. 2A), the dictionary head pointer 108
Holds a value indicating the start address of the dictionary memory 103,
If the encoded input is larger than the dictionary size, then FIG.
As shown in (b), the address designated by the dictionary head pointer 108 is not limited to the head address, and the dictionary memory 10
Move over 3 every time a letter is written to it (slide)
To do.

The input pointer 113 holds an address output from the control unit 102 for writing a new character in the dictionary memory 103. Therefore, when the coded input is smaller than the dictionary size (see FIG. 2A), the input pointer 113 holds the address indicating the beginning of the area of the dictionary memory 103 in which no character is written, and the code is When the digitized input is larger than the dictionary size, as shown in FIG. 2B, the address of the character stored in the earliest, that is, the same value as the address held by the dictionary head pointer 108 is stored in the input pointer 113. Retained.

Input pointer 113 (dictionary top pointer 1
The address held in 08) is changed so as to circulate the dictionary memory 103. Therefore, the dictionary memory 10
The character of 4 Kbytes input in the past is always stored in 3.

The matching position pointers 109 to 112 hold addresses for reading characters from the dictionary memory 103, and the control unit 102 determines that the input character stored in the input register 101 is the first character of the partial character string. Address (matching position) where the character that matches the input character is stored
Hold each. Here, in order to simplify the following description, it is assumed that the input character currently stored in the input register 101 is the first character, and when the input character determined to be the first character and the character following the input character are input. As the operation of the control unit 102 is sequentially described, the determination of the type of the input character will be described.

In this embodiment, the search for the matching position is performed while sequentially changing the address from the address indicated by the dictionary head pointer 108. When the coincidence position is held in the coincidence position pointer 109, that is, when the comparison result of the comparison circuit 106 indicates coincidence, the control unit 102 causes the coincidence position pointer 1 at this time.
The value of 09 is stored in the coincidence position pointer 110. After that, the address selector 107
0 is selected, the character read from the dictionary memory 103 is sequentially compared with the input character while the matching position pointer 110 is incremented, and the matching position pointer 110 holds the matching position. After that, the matching positions are held similarly for the other matching position pointers 111 and 112.

To search for a character that matches the input character, all of the matching position pointers 109 to 112 hold the matching position, or all the characters stored in the dictionary memory 103 are referenced, that is, the dictionary head pointer 108. The process ends by referring to the characters up to the address immediately before the input pointer 113 by circulating from the address of. Each of the matching position pointers 109 to 11 depends on the order of holding the matching positions.
The matching positions held by 2 are as shown in FIGS. 2 (a) and 2 (b).

When the control unit 102 finds a character that matches the input character of the input register 101 as a result of this search, it stores the input character in the previous data register 105 and causes the address selector 107 to input the input pointer 11.
3 is selected, and this input character is stored in the address designated by the input pointer 113. Input character dictionary memory 1
When it is stored in 03, the control unit 102 increments the match position pointer holding the match position, the dictionary head pointer 108, and the input pointer 113, and then the control unit 1
02 requests the external device to output characters. The request to output the character to the external device is made by, for example, sending an interrupt signal to that effect to the external device.

On the other hand, when the character matching the input character is not found by the above search, the control unit 102
The match flag in which “0” is set is output to the code output unit 115, and at the same time, the input character is output to the code output unit 115 via the data selector 104. Further, subsequently, the input character is written in the dictionary memory 103, the dictionary head pointer 108 and the input pointer 113 are incremented, and then the output of the next character is requested to the external device. In this case, since the input character at the present time has been encoded, the control unit 102 determines that the character input next from the external device is the first character.

When the next character is newly input from the external device, that is, when a new character is stored in the input register 101, the control unit 102 restarts the encoding process. At this time, the character that matches the immediately preceding input character is set to the dictionary memory 10
If it is not found in 3, the newly input character corresponds to the first character, as described above, and the search for holding the matching position in each of the matching position pointers 109 to 112 is performed again. To do.

On the other hand, for example, each matching position pointer 109-
When the matching position is held in 112 (actually, even if there is only one pointer holding the matching position among these), the incremented matching position pointers 109 to 112 indicate the addresses. The comparison of whether the stored character matches the newly input character is sequentially performed from the character stored at the address designated by the matching position pointer 109. This is performed by sequentially switching the pointers selected by the address selector 107.

As a result of the above comparison, when there is no character that matches the input character among the characters read from the addresses designated by the matching position pointers 109 to 112,
The control unit 102 outputs the coincidence flag of “0” to the code output unit 115 and causes the character of the previous data register 105 to be input to the code output unit 115 via the data selector 104. As a result, the encoding up to the input character has been completed, so the control unit 102 determines this input character as the first character, and performs the above-described matching position search again.

On the contrary, the matching position pointers 109 to 11
If there is a character that matches the input character among the characters read from the address designated by 2, the control unit 102 counts the length (the number of characters) of the matching sequence stored in the dictionary memory 103. The counter 114 is reset (“0” is set). When the match length counter 114 is reset, the input character is subsequently input to the input pointer 11
3 is written to the address indicated by 3, and then the matching position pointer indicating the character that matches the input character, the input pointer 113, and the dictionary head pointer 108 are each incremented, and the character following the current input character is waited for input. .

After the match length counter 114 is reset, the dictionary memory 103 is incremented while incrementing only the match position pointer from which the character matching the input character is read out.
If not all the characters read from the input character match the input character, the match length counter 114 continues to count up until the comparison circuit 106 makes a comparison. While continuing this count-up, after the character comparison by the comparison circuit 106 is completed, the input character is written in the dictionary memory 103.

When all the characters read from the dictionary memory 103 do not match the input characters, or until the preset maximum matching length (described later) is reached, the matching length counter 11
When the next character is input after counting up 4, the control unit 102 determines that the maximum matching sequence of the partial character strings currently being encoded has been determined, and the code output unit 115 displays “ The match flag of "1" is output. Further, the result obtained by subtracting a value obtained by adding 2 to the count value of the match length counter 114 from the output value of the address selector 107 from the subtracter 116 to the code output unit 115 from the match length counter 114 and the count value (match length). Input sequentially. At this time, the address selector 107 is caused to select one of the matching position pointers 109 to 112 that has been incremented to the end. Therefore, the subtraction result of the subtracter 116 becomes the matching position of the maximum matching sequence among the matching sequences starting from the matching positions held in the respective matching position pointers 109 to 112.

When the maximum matching sequence is determined in this way, the characters up to the character input earlier than the input character stored in the input register 101 have been encoded, so the control unit 102 determines Is determined to be the first character. Therefore, after the code output unit 115 inputs the count value of the match length counter 114 and the subtraction result of the subtractor 116, the control unit 102 causes each of the match position pointers 109 to 112 to hold the match position, as described above. Do a search for.

Although not particularly shown, the code output section 115 is composed of, for example, a selector, a shift register, etc., and is controlled by the control section 102. Code output unit 1
Reference numeral 15 performs selector switching, bit shift of the shift register, and the like according to the control of the control unit 102, so that the shift register has a match flag as a code word, and a character (ASCII code), or a character according to the value of the match flag. The match length (count value of the match length counter 114) and the match position (output of the subtractor 116) are sequentially stored. The code word stored in the shift register is cut out in 8-bit units at any time and output to the outside. The compressed code output OD is output by being cut out from this shift register.

The compressed code output OD output from the code output section 115 will be described with reference to FIG. FIG. 3 is a diagram for explaining the data format of the compression code output OD.

As described above, in this embodiment, the partial character string that matches the input partial character string is the dictionary memory 103.
"1" or "0" depending on whether it is stored in
Is set in the match flag, and as shown in FIG. 3, the data formats of the code words differ from each other depending on the value of the match flag represented by 1 bit.

When "1" is set in the match flag,
The code word is the match flag, a match length of 4 bits, and 1
It consists of a 2-bit match position, and its word length is 17 bits. On the other hand, if "0" is set in the match flag,
The code word is composed of the match flag and a character (non-match character) input with 8 bits, and the word length is 9 bits.

In the present embodiment, since the data format is as described above, the input portion to be encoded is prevented from becoming larger than the original data amount after encoding. When a partial character string that matches two or more characters with the character string is not stored in the dictionary memory 103, the first character of the partial character string is determined as a non-matching character. Therefore, when the match flag is set to "1", the match length is expressed by 4 bits from 2 to 17 characters (maximum match length).

The above is the data compression apparatus 10 according to the present embodiment.
This is a rough compression operation of 0. Next, the above-described compression operation will be described with a specific example. FIG. 4 is a diagram for specifically explaining a compression operation example of the data compression device 100. In the figure, (a) is the input character string 401 input as the input data string ID, and (b) is the input character string 40.
The address on the dictionary memory 103 indicated by each of the pointers 108 to 113 when the seventh character "B" in 1 is input, and FIG. 6C shows the compression output when the input character string 401 is input. The code output OD is shown respectively.

The input character string 401 shown in FIG. 4A is sequentially stored in the input register 101 as the input data string ID, one character at a time from left to right. In the input character string 401, the seventh character “B” is currently stored in the input register 101 as the current input value.

As shown in FIG. 4B, when the seventh character "B" is stored in the input register 101, the input character is written in the dictionary memory 103 at any time. Is the dictionary top pointer 10
Six characters previously input from the address designated by 8 are sequentially stored.

Since the first to fifth characters "AB = 0;" are the types that were input for the first time, the control unit 1
02 cannot retrieve these characters from the dictionary memory 103. Therefore, each of the first to fifth characters is determined to be a non-matching character, and is output from the input register 101 to the code output unit 115 via the data selector 104, whereby a match flag in which “0” is set is set. It is output from the code output unit 115 as a code word (compressed code output OD) including the characters (see FIG. 4C).

On the other hand, the sixth character "B" matches the second input character, and as a result of searching the dictionary memory 103, the second character indicated by P1 in FIG. 4B is written. The present address (match position) is held in the match position pointer 109. When the seventh character “B” is input, the third character read from the address indicated by the incremented coincidence position pointer 109 and this seventh character are compared by the comparison circuit 106.
Since these characters do not match, the sixth character is determined to be a non-matching character. At this time, the sixth character is stored in the previous data register 105, and the sixth character is output to the code output unit 115 via the data selector 104, and the match flag with "0" set is added. Is output.

As described above, since the 7th character does not match the 3rd character, the control unit 102 determines that this 7th character is the first character, and searches the dictionary memory 103 for the matching character. . Since the 7th character matches the 2nd and 6th characters, as a result of this search, the address (matching position) where the 2nd character indicated by P1 in FIG. Match position pointer 109
Further, the address (match position) where the sixth character P2 in FIG. 4B is written is held in the match position pointer 119. Upon completion of this search, the control unit 102 sets the seventh character to the dictionary memory 1
03 at the address indicated by the input pointer 113, incrementing each of the matching position pointers 109 and 110, the dictionary head pointer 108, and the input pointer 113, and then inputting the next character (eighth character “=”). wait.

When the eighth character is input, this eighth character is incremented by the matching position pointer 10
Characters read from the address specified by 9, 110,
That is, the third and seventh characters are sequentially compared. The 8th character does not match the 7th character but does match the 3rd character, so the control unit 102 resets the match length counter 114 here, and also inputs this input 8th character. Write to the address designated by the pointer 113.
After that, the matching position pointer 109 and the dictionary head pointer 1
After incrementing 08 and the input pointer 113 respectively, the input of the next character (the ninth character "0") is awaited.

As shown in FIG. 4A, the 9th to 10th characters "0;" match the 4th to 5th characters. Therefore, thereafter, until the eleventh character “C” is input, the control unit 102 increments the coincidence position pointer 109 and detects the character read from the address designated by the coincidence position pointer 109 and the input character. Will be compared sequentially. As a result, the match length counter 114 is counted up until the eleventh character is input, and the count value of the match length counter 114 at the time when the eleventh character is input is "2". Further, assuming that the head address value of the dictionary memory 103 is "0", the value of the coincidence position pointer 109 at this time is "5".

When the eleventh character is input, this character is compared with the character at the address indicated by the matching position pointer 109, that is, the sixth character. As shown in FIG. 4A, since the two do not match, the comparison circuit 106 outputs the result of comparison with the mismatch to the control unit 102. Control unit 1
When the comparison result is input from the comparison circuit 106, 02 determines that the maximum matching sequence has been determined, and subsequently determines whether the matching length of this maximum matching sequence is 2 characters or more, that is, the matching flag is set to "1". It is determined whether or not to generate a code word with "." In this case, the maximum matching sequence is a partial character string having four characters starting from the matching position indicated by P1 in FIG. 4B, and therefore the control unit 102 sends the matching flag set to “1” to the code output unit 115. Output. Further, the code output unit 11
5, the match length counter 114 count value, and the subtracter 1
The 16 subtraction results are sequentially input.

At this time, the control unit 102 causes the address selector 107 to select the coincidence position pointer 109. Therefore, the subtraction result output from the subtractor 116 to the code output unit 115 is a value indicating P1 in FIG.

FIG. 4C shows the compression code output OD when the tenth character up to the input character string 401 is encoded. When the input character string 401 is to be encoded, the compression operation (encoding process) is performed as described above.
As shown in FIG. 4C, six codewords in which the match flag is set to "0" continue, and at the seventh position, the matchword of the codeword is set to "1".

This 7th code word is the 7th-10th 4th
It represents a substring of characters. As described above, the match length is a value obtained by sequentially counting up two characters as "0", and thus the match length at this time is "2". Since the matching position output as the code word is the actual matching position, the matching position at this time is "1" (this is the value when the start address of the dictionary memory 103 is "0"). The compression code output O shown in FIG.
D outputs the code word stored in the shift register of the code output unit 115 by cutting out the code word in units of 8 bits.
It is output from 5 at any time.

As described above, in this embodiment, the matching position of the dictionary memory 103 in which the first character of the partial character string to be encoded is stored is determined, and the character following the first character is input. In addition, since the character stored in the address changed from the matching position corresponding to the input of this character and the newly input character are compared with each other as needed, the encoding is completed. A memory for storing non-printed characters is not needed, and the ratio of the memory in the device can be reduced. As a result, the size and cost of the device can be suppressed, and the LSI can be easily implemented. Therefore, the present invention can be widely applied to a data compression device or the like that is directly connected to a bus of a computer and used. .

Further, in the present embodiment, the code output section 115 is used to output the compressed code output OD as needed.
Therefore, as compared with the conventional data compression device 500 shown in FIG. 5, the number of memories provided is reduced, that is, the input memory 50.
1, since the code memory 505 and the like need not be provided,
There is also an effect that individual control of each part of the device can be simplified.

On the other hand, comparing the two with respect to the processing time required for encoding, how to terminate the extraction of the coincidence sequence
Although it depends on the difference in the maximum matching sequence search method between the two, such as the number of matching position pointers used, the processing time required for data input occupies a small proportion of the total processing time, so basically a large difference occurs in the processing time. do not do.

In this embodiment, the number of matching position pointers holding the matching position is four, but the number is not limited to this. The smaller the number of matching position pointers, the faster the data compression can be, but the compression ratio (= the amount of data after compression / the amount of data before compression)
Is more likely to occur. Although it depends on the processing speed required for data compression, the type of file to be encoded, and the like, it is desirable to set this number to four or more in order to prevent the compression ratio from increasing.

Further, in the present embodiment, various pointers 108 to 113 for holding each address of the dictionary memory 103 are provided, but for example, the control unit 102 may be made to play the role of these pointers, and the pointers match. Long counter 11
4. The control unit 102 may be caused to play the role of the subtractor 116. As described above, the present invention can be flexibly applied including the data format of the compression code output OD.

[0073]

As described above, according to the present invention,
Each time a character is input, it is determined whether or not the input character corresponds to the first character of the partial character string, and the input character is stored in the dictionary (storage means) according to the determination result. Since the substrings that have been repeatedly input are detected by searching for the presence or absence of the characters, the character strings can be encoded at any time according to the input of characters, and the input characters can be registered in the dictionary at any time. You can As a result, it is possible to avoid the need to store the character string to be encoded, reduce the size of the device, and reduce the cost.

Further, it is possible to prevent the compression ratio from increasing by extracting a plurality of matching positions in the dictionary in which the character matching the character determined to correspond to the first character is stored and performing the above search. be able to.

[Brief description of drawings]

FIG. 1 is a block diagram showing the configuration of a data compression apparatus according to this embodiment.

FIG. 2 is a diagram showing an example of an address on a dictionary memory indicated by each pointer.

FIG. 3 is a diagram illustrating a data format of compressed code output.

FIG. 4 is a diagram for specifically explaining a compression operation example.

FIG. 5 is a block diagram showing a configuration of a conventional data compression device.

[Explanation of symbols]

 100 Data Compressor 101 Input Register 102 Control Unit 103 Dictionary Memory 106 Comparison Circuit 107 Address Selector 108 Dictionary Start Pointer 109-112 Match Position Pointer 113 Input Pointer 114 Match Length Counter 115 Output Control Unit 116 Subtractor

Claims (3)

[Claims] 1. A storage means for storing a character string input in the past is provided, and the character string stored in the storage means is referred to,
A data compression device that compresses the amount of data that represents a character string by detecting repeatedly input partial character strings, and determines whether the input character is the first character of the partial character string. A matching position storage unit that stores, as a matching position, an address of the storage unit in which a character matching the input character is stored when the character determining unit determines the input character as a leading character. Each time a character following the character discriminated by the character discriminating means is inputted as the first character, it is stored in the storage means while sequentially changing the address from the coincident position according to the input of the character. The reading means for reading out the character, the comparing means for comparing the inputted character with the character read out from the storing means, and the character for judging the input character Counting means for counting the length of the partial character string stored in the storage means by counting the number of times that the comparison means has matched after determining that the character is input, and the character determination means is input. After the character is discriminated as the first character, and when the comparison result of the comparison means does not match,
A data compression apparatus comprising: a code generation unit that generates a code word representing a partial character string stored in the storage unit from the coincidence position and the number of characters counted by the counting unit. 2. The data compression apparatus according to claim 1, further comprising a writing unit that writes the input character into the storage unit whenever the character is input. 3. A plurality of the matching position storage means are provided, and the reading means sets an address sequentially changed from each matching position stored in the plurality of matching position storage means each time a character is input. When each of the stored characters is read out from the storage means, and the counting means finds among the characters read out from the storage means by the reading means a character that is compared with the input character by the comparing means. When the reading means reads out from the storage means and there is no character that the comparing means compares with the input character, the code generating means performs the counting once. The data compression apparatus according to claim 1 or 2, wherein a code word representing a partial character string stored in is generated.