CN106849956B - Compression method, decompression method, apparatus and data processing system - Google Patents

Abstract

The application discloses a compression method, a decompression method, a device and a data processing system, and belongs to the field of data processing. The decompression method comprises the following steps: reading a code segment with the code length of a x N + b from compressed data according to the x clock period to obtain (a x N + b)/a sub-code segments; decompressing the (a x N + b)/a sub-code segments concurrently to obtain (a x N + b)/a characters; and determining target decompression data of the x clock period from the (a × N + b)/a characters according to the variable length coding table and the code segment read in the x clock period. The method and the device have the advantages that the plurality of subcode segments are decompressed concurrently to obtain a plurality of characters, and then the target decompressed data of the x-th clock period is determined from the plurality of characters. The next code word is decompressed according to the length of the code word without waiting for the completion of the decompression of the code word, and the decompression speed is high.

Description

Compression method, decompression method, apparatus and data processing system

technical field

The present application relates to the field of data processing, and in particular, to a compression method, a decompression method, an apparatus and a data processing system.

Background technique

Variable Length Coding (English: Variable Length Coding) is an encoding method used when compressing data. In this encoding method, the characters in the data to be compressed can be encoded by code words with different lengths (the code words are binary codes of several bits). Usually, the characters with higher occurrence probability are represented by shorter codewords (such as 01), and the characters with lower probability of occurrence are represented by longer codewords (such as 111001), and the difference between the characters and the codewords is Correspondence can be recorded in the variable-length coding table.

At present, the data obtained by compressing data using variable-length encoding is called compressed data encapsulation. The compressed data encapsulation may include: compressed data and variable-length encoding tables, etc. When decompressing the compressed data encapsulation, the The data is encapsulated and parsed to obtain a variable-length coding table, and then starting from the first bit of the compressed data, the compressed data is sequentially decoded according to the variable-length coding table to obtain decompressed data.

Since the length of each codeword in the compressed data in the above-mentioned compressed data package is unknown before decompression, when the compressed data is decompressed, the starting position of the next codeword can only be determined after a codeword is decompressed. Therefore, it is necessary to decompress one codeword after another according to the sequence of the compressed data, and the decompression speed is low.

SUMMARY OF THE INVENTION

In order to solve the problem of low decompression speed during decompression, embodiments of the present invention provide a compression method, a decompression method, an apparatus, and a data processing system. The technical solution is as follows:

The decompression method provided by the embodiment of the present invention may be executed by a decompression engine, and the decompression engine may be set on a processor of an x86 architecture (English: The X86 architecture) or an advanced reduced instruction set processor (English: Advanced RISC Machines; abbreviation: ARM) ) architecture processor.

In a first aspect, an embodiment of the present invention provides a decompression method, which includes:

The decompression engine reads the code segment with a code length of a*N+b from the compressed data according to the xth clock cycle, and obtains (a*N+b)/a subcode segments; wherein, x is greater than or equal to 1. Integer; (a*N+b)/the code length of each subcode segment in a subcode segment is c, (a*N+b)/a subcode segment includes the first subcode segment, and the start of the first subcode segment The start bit coincides with the start bit of the code segment read in the xth clock cycle, and the code length of the interval between the start bits of two adjacent subcode segments in (a*N+b)/a subcode segments is a -1, the N is an integer greater than 0.

The decompression engine decompresses (a*N+b)/a subcode segments concurrently based on the variable-length encoding table to obtain (a*N+b)/a characters, wherein the decompression engine decompresses each subcode segment can get a character.

The variable-length encoding table may include multiple codewords, each of (a*N+b)/a characters corresponds to one codeword in the variable-length encoding table; at least two codewords in the multiple codewords correspond to The code lengths are different, the code length corresponding to the code word with the longest corresponding code length among the multiple code words is c, the code length corresponding to the code word with the shortest corresponding code length among the multiple code words is a, and a is a plurality of codes The greatest common divisor of the code length corresponding to each codeword in the word, where a is an integer greater than or equal to 2, c is an integer greater than a, and the difference between c and a is b.

The decompression engine determines the target decompression data of the xth clock cycle from (a*N+b)/a characters according to the variable-length encoding table and the code segment read in the xth clock cycle, where the target decompression data of the xth clock cycle In the decompressed data, the position of the last symbol of the code word corresponding to one of the two adjacent valid characters in the code segment read in the xth clock cycle and the start of the code word corresponding to the other valid character. The symbols are located adjacent to each other in the code segment read at the xth clock cycle. The target decompressed data for the xth clock cycle includes a plurality of valid characters arranged in a specific order.

In the decompression method provided by the embodiment of the present invention, when decompressing compressed data, by concurrently decompressing (a*N+b)/a subcode segments, (a*N+b)/a subcode segments are obtained. character, and then determine the target decompressed data of the xth clock cycle from (a*N+b)/a characters according to the variable-length encoding table and the code segment read at the xth clock cycle. There is no need to wait for a codeword to be decompressed before decompressing the next codeword according to the length of the codeword. When decompressing, you can start decompressing from multiple locations at the same time, and the decompression speed is high.

Optionally, the last b bits of the code segment with a code length of a*N+b read in the xth clock cycle are in phase with the first b bits of the code segment with a code length of a*N+b read in the x+1th clock cycle. coincide.

In the decompression method provided by the embodiment of the present invention, when the decompression engine reads two adjacent clock cycles, the first b bits of the next clock cycle are the last b bits of the previous clock cycle, so as to avoid omission during decompression Uncompressed code segment.

Optionally, when x is equal to 1, the decompression engine determines the xth clock cycle from (a*N+b)/a characters according to the variable-length encoding table and the code segment read in the xth clock cycle. The target decompressed data, including:

The decompression engine determines the target decompression data of the xth clock cycle from (a*N+b)/a characters, and the start code element and the codeword corresponding to the first valid character in the target decompression data of the xth clock cycle. The start symbols of the code segment read in the xth clock cycle coincide.

In the decompression method provided by the embodiment of the present invention, when x is equal to 1, the target decompressed data in the first clock cycle is determined by the position of the start symbol of the target decompressed data.

Optionally, when x is an integer greater than or equal to 2, the decompression engine determines from (a*N+b)/a characters according to the variable-length encoding table and the code segment read in the xth clock cycle. Target decompressed data for the xth clock cycle, including:

The decompression engine determines c/a groups of candidate decompression data from (a*N+b)/a characters; each group of candidate decompression data includes multiple characters, and in each adjacent two characters, the code corresponding to one character The position of the last symbol of the word in the code segment read in the xth clock cycle is adjacent to the position of the start symbol of the codeword corresponding to another character in the code segment read in the xth clock cycle; The positions of the start symbols of the code words corresponding to the first characters in each group of candidate decompressed data are different in the code segment read in the xth clock cycle, and the first characters in each group of candidate decompressed data correspond to The starting symbol of the codeword is the W*a-th symbol in the code segment read in the xth clock cycle, where W is an integer greater than or equal to 0 and less than or equal to b/a.

The decompression engine determines the target decompression data of the xth clock cycle from the candidate decompression data of the c/a group; in the compressed data, the last symbol of the codeword corresponding to the last character in the target decompression data of the x-1th clock cycle The starting symbol of the code word corresponding to the first character in the target decompressed data of the xth clock cycle is adjacent to the start symbol, and the target decompression data of the x-1th clock cycle refers to the code read in the x-1th clock cycle. The target decompressed data corresponding to the segment.

In the decompression method provided by the embodiment of the present invention, in the case where x is an integer greater than or equal to 2, firstly obtain possible c/a candidate decompression data of the data read in the xth cycle, and then according to the xth - The target decompression data of 1 clock cycle selects the target decompression data of the xth clock cycle, so that the decompression engine can start to obtain candidate decompression data before the decompression of the data in the previous clock cycle is completed, which improves the speed of decompressing data. In the case where x is equal to 1, the target decompressed data of the x-1th clock cycle is a plurality of valid characters arranged in a specific order obtained by decompressing the code segment read in the first clock cycle.

Optionally, after the decompression engine determines the target decompressed data of the xth clock cycle, the method further includes:

The decompression engine splices the obtained decompressed data of multiple clock cycles according to the compressed data, and obtains the decompressed data corresponding to the compressed data. In the two adjacent clock cycles after splicing, the last character in the target decompressed data of one clock cycle corresponds to The position of the last symbol of the codeword in the compressed data is adjacent to the position of the start symbol of the codeword corresponding to the first character in the target decompressed data of another clock cycle in the compressed data.

In the decompression method provided by the embodiment of the present invention, after obtaining decompressed data of multiple clock cycles, these results are spliced to obtain decompressed data of compressed data, and the decompression speed is high.

In a second aspect, an embodiment of the present invention provides a compression method, where the compression method can be executed by a compression engine, and the method includes:

The compression engine determines the target common divisor of the code length corresponding to each codeword in the variable-length coding table; the variable-length coding table includes multiple codewords, and the target common divisor is an integer greater than or equal to 2. Each character in the data to be compressed Corresponds to a codeword in the variable-length coding table;

The compression engine generates a variable-length encoding table according to each character in the data to be compressed and the common divisor of the target; at least two code words in the variable-length encoding table have different code lengths, and the code corresponding to a character with a higher probability of appearing in the data to be compressed The code length of the word is less than the code length of the code word corresponding to the character with a lower occurrence probability, and the greatest common divisor of the code length of the code word in the variable-length coding table is the target common divisor;

The compression engine compresses the data to be compressed according to the variable-length coding table to obtain compressed data;

The compression engine generates a compressed data package based on the compressed data and the variable-length encoding table.

The compression method provided by the embodiment of the present invention generates a variable-length encoding table according to each character in the data to be compressed and the common divisor of the target, and compresses the data to be compressed according to the variable-length encoding table, so that the decompression engine decompresses the compressed data. When decompression is performed concurrently from multiple locations, it is not necessary to wait for a codeword to be decompressed and then decompress the next codeword according to the length of the codeword, and the decompression speed is high.

Optionally, the decompression engine determines the target common divisor of the code length corresponding to each codeword in the variable-length encoding table, including:

The decompression engine can first determine at least one common divisor, and compress the data to be compressed according to the variable-length coding table corresponding to each common divisor of the at least one common divisor, and the obtained compression rate is smaller than the preset value, wherein according to at least one common divisor Each common divisor in the number can generate a corresponding variable-length coding table;

Afterwards, the decompression engine may determine the target common divisor from the at least one common divisor, and the value of the target common divisor is greater than the value of each common divisor except the target common divisor in the at least one common divisor.

The larger the greatest common divisor a, the higher the decompression speed of the data compressed by the compression method provided by the embodiment of the present invention, but the compression rate may increase when the greatest common divisor becomes larger. In the compression method provided by the embodiment of the present invention, by predetermining at least one common divisor of which the corresponding compression ratio is smaller than the preset value, and selecting the largest common divisor as the target common divisor, it is ensured that the compression ratio and the decompression speed are at a relatively high level. high range.

In a third aspect, an embodiment of the present invention provides a decompression apparatus, where the decompression apparatus includes multiple units, and the multiple units are configured to implement the above-mentioned first aspect or any one of the possible implementation manners of the first aspect. Decompression method.

In a fourth aspect, an embodiment of the present invention provides a compression device, where the compression device includes a plurality of units, and the plurality of units are used to implement the compression method provided by the second aspect or any possible implementation manner of the second aspect .

In a fifth aspect, an embodiment of the present invention provides a data processing system, which includes the decompression device provided in the third aspect and the compression device provided in the fourth aspect, where the compression device is configured to compress the data to be compressed to obtain compressed data; The decompression device is used for decompressing the compressed data.

In a sixth aspect, a decompression device is provided, the decompression device includes: a base plate, a central processing unit (English: Central Processing Unit; CPU for short) and a memory disposed on the base plate, the base plate is connected with a bus interface, the The bus interface may be connected with a decompression engine, where the decompression engine is configured to execute the decompression method provided by the first aspect.

In a seventh aspect, a decompression device is provided, the decompression device includes: a processor chip, a memory connected to the processor chip, and a CPU and a bus interface provided on the processor chip, and the decompression engine can be integrated in the processor. On the chip, and connected to the CPU through a bus interface, the decompression engine is used to execute the decompression method provided by the first aspect.

In an eighth aspect, a compression device is provided, the compression device includes: at least one processor, at least one network interface, memory, and at least one bus, the memory and the network interface are respectively connected to the processor through the bus; the processor is configured to execute The instructions stored in the memory; the processor implements the compression method provided in the second aspect by executing the instructions.

To sum up, in the decompression method provided by the embodiments of the present invention, when decompressing compressed data, by concurrently decompressing (a*N+b)/a subcode segments, (a*N+ b)/a characters, and then determine the target decompressed data of the xth clock cycle from (a*N+b)/a characters according to the variable-length encoding table and the code segment read in the xth clock cycle. There is no need to wait for a codeword to be decompressed before decompressing the next codeword according to the length of the codeword. The problem of low decompression speed in the related art is solved. When decompressing, the decompression can be started from multiple locations at the same time, and the decompression speed is high.

Description of drawings

1A is a structural block diagram of a decompression apparatus provided by an embodiment of the present invention;

1B is a structural block diagram of another decompression apparatus provided by an embodiment of the present invention;

1C is a structural block diagram of a compression apparatus provided by an embodiment of the present invention;

2A is a flowchart of a compression method according to an embodiment of the present invention;

Fig. 2B is a kind of flow chart of determining target common divisor in the embodiment shown in Fig. 2A;

3A is a flowchart of a decompression method according to an embodiment of the present invention;

3B is a schematic diagram of the correspondence between code words and characters in the data read in the xth clock cycle in the embodiment shown in FIG. 3A;

3C is a bar graph of the chip area occupied by the decompression engine in the embodiment shown in FIG. 3A;

4 is a structural block diagram of a compression apparatus provided by an embodiment of the present invention;

5A is a structural block diagram of a decompression apparatus provided by an embodiment of the present invention;

5B is a structural block diagram of a decompression apparatus provided by an embodiment of the present invention;

FIG. 6 is a schematic structural diagram of a data processing system according to an embodiment of the present invention.

Detailed ways

In order to make the purpose, technical solutions and advantages of the present disclosure clearer, the present disclosure will be described in further detail below with reference to the accompanying drawings. Obviously, the described embodiments are only a part of the embodiments of the present disclosure, rather than all the embodiments. .

Please refer to FIG. 1A , which shows a structural block diagram of a decompression device provided by an embodiment of the present invention. The decompression device may include: a base plate 11 , a CPU 12 and a memory 13 disposed on the base plate 11 , and the base plate 11 is connected with A bus interface 14, the bus interface 14 can be connected with a decompression engine 15, the decompression engine 15 can be an expansion card, and the expansion card can be a Field-Programmable Gate Array (English: Field-Programmable Gate Array; abbreviation: FPGA) or an application-specific integrated Circuit (English: Application Specific Integrated Circuit; abbreviation: ASIC). The bus interface 14 may be PCIe (a type of bus interface).

Please refer to FIG. 1B , which shows a structural block diagram of another decompression apparatus provided by an embodiment of the present invention. The decompression apparatus may include: a processor chip 16 , a memory 17 connected to the processor chip 16 , and a The CPU 161 and the bus interface 162 on the processor chip 16 and the decompression engine 163 can be integrated on the processor chip 16 and connected to the CPU 161 through the bus interface 162 . The memory 17 may be a double-rate synchronous dynamic random access memory (English: Double Data Rate SDRAM; abbreviation: DDR), and the bus interface 162 may be an advanced extensible interface (English: Advanced eXtensible Interface; abbreviation: AXI).

Please refer to FIG. 1C, which shows a structural block diagram of a compression apparatus provided by an embodiment of the present invention. The compression apparatus 20 may include: at least one processor 21, at least one network interface 22, memory 23, and at least one bus 24, The memory 23 and the network interface 22 are respectively connected to the processor 21 through the bus 24 ; the processor 21 is configured to execute the instructions 231 stored in the memory 23 . The memory 23 may include a high-speed random access memory (English: Random Access Memory; abbreviation: RAM), and may also include a non-volatile memory (English: non-volatile memory), such as at least one disk memory.

FIG. 2A is a flowchart of a compression method according to an embodiment of the present invention. This embodiment is illustrated by applying the compression method to compressing data to be compressed. The compression method may include the following steps:

Step 201: The compression engine obtains the probability distribution of various characters in the data to be compressed.

When using the compression method provided by the embodiment of the present invention, the compression engine may analyze the data to be compressed to obtain the probability distribution of various characters in the data to be compressed. The data to be compressed may be composed of a plurality of different characters, and the occurrence probability of different characters may be different. The probability distribution may include the occurrence probability of each character. For example, the occurrence probability of the character "A" may be 4% ( percent sign), the probability of occurrence of the character "B" can be 6%. Among them, the characters in the data to be compressed refer to the uncompressed characters stored in the storage device. When the storage device stores data, it usually takes binary bits (English: bit) as the unit. According to different encoding methods, each character The number of occupied binary bits is different. For example, in the data to be compressed using the American Standard Code for Information Interchange (English: American Standard Code for Information Interchange; ASCII for short) as the encoding method, each character can occupy 8 binary bits.

The compression engine in this embodiment of the present invention may be integrated into the compression apparatus shown in FIG. 1C through software or hardware.

Step 202: The compression engine determines the target common divisor of the code length corresponding to each codeword in the variable-length coding table.

The variable-length encoding table may include multiple codewords, the target common divisor is an integer greater than or equal to 2, and each character in the data to be compressed corresponds to a codeword in the variable-length encoding table.

The target common divisor is the greatest common divisor of the corresponding code length of each codeword in the encoding table, and the encoding table is subsequently generated by the compression engine. It should be noted that a codeword is composed of several symbols, which are usually represented as several bits of binary data in computer communication. A symbol can be a binary number.

As shown in FIG. 2B , the process for the compression engine to determine the target common divisor may include the following two sub-steps:

Sub-step 2021: The compression engine determines at least one common divisor, and compresses the data to be compressed according to the variable-length coding table corresponding to each common divisor of the at least one common divisor, and the obtained compression ratios are all less than the preset value.

Wherein, according to each common divisor of the at least one common divisor, a corresponding variable-length coding table can be generated.

Sub-step 2021 may include:

1) The compression engine can first preset multiple common divisors, which are integers greater than or equal to 2 and less than S, where S is the number of binary bits occupied by each character in the data to be compressed (this is Because if the common divisor is greater than or equal to the number of binary bits occupied by characters, when the common divisor is the greatest common divisor of the code length of each codeword in the compressed data, the data volume of the compressed data will be larger than the data to be compressed, and it is difficult to for compression purposes). Exemplarily, if the number of bits occupied by characters in the data to be compressed is 8, the common divisor may be preset to 6 numbers from 2 to 7.

2) After setting multiple common divisors, the compression engine can estimate the compression ratio (English: Compression ratio) corresponding to each common divisor of the multiple common divisors. The compression ratio is the sum of the compressed size of the data and the size before compression. Compare. Exemplarily, the size of the data to be compressed before compression is 100 megabytes (English: Megabytes; abbreviation: M), and the size after compression is 10M, and the compression rate is 10%.

When the compression engine estimates the compression ratio of each common divisor, it can sample the data to be compressed to obtain sampled data, and then generate a variable-length encoding table according to each common divisor (for the process of generating the encoding table according to the common divisor, refer to step 203), And compress the sampled data according to each variable-length coding table to obtain the compression ratio corresponding to each common divisor. Wherein, in the coding table generated according to any common divisor of the plurality of common divisors, the correspondence between each character in the sampled data and the code word corresponding to the character is recorded, and at the same time, each character in the variable-length coding table is recorded. The code length of the corresponding codeword is a positive integer multiple of any of the common divisors.

3) Screening out at least one common divisor whose compression ratio is smaller than a preset value from the plurality of common divisors.

The preset value can be preset by the operator. The preset value can be set in consideration of the decompression speed requirement. When the decompression speed requirement is high, a higher preset value can be set, and the decompression speed requirement is low. , you can set a smaller preset value. This is because generally the smaller the compression ratio, the slower the decompression speed will be.

Sub-step 2022, the compression engine determines a target common divisor from at least one common divisor, and the value of the target common divisor is greater than the value of each common divisor except the target common divisor in the at least one common divisor.

The compression engine determines a target common divisor, where the target common divisor refers to a common divisor with the largest value among at least one common divisor whose corresponding compression ratio is smaller than a preset value.

It should be understood that, in the aforementioned "at least one common divisor", if the number of the "at least one common divisor" is 1, that is, the "at least one common divisor" refers to a common divisor, then the common divisor is the target common factor. Only if the number of the "at least one common divisor" is greater than or equal to 2, the target common divisor refers to a common divisor that is greater than the value of each of the at least one common divisor except the target common divisor.

Since in the decompression method corresponding to the compression method provided by the embodiment of the present invention (refer to the embodiment shown in FIG. 3A ), the greater the greatest common divisor of the codewords in the variable-length coding table, the greater the data read by the decompression engine in each clock cycle. The larger the number, the higher the decompression speed. Therefore, considering the decompression speed, the largest common divisor among the common divisors of which the compression ratio is smaller than the preset value can be determined as the target common divisor.

In addition, since the greatest common divisor is larger, the code length of the code word representing the character will be longer, and the data volume of the compressed data used to represent the data to be compressed (the compressed data is composed of code words) will also increase. Therefore, the greater the greatest common divisor, the greater the compression ratio. In the case of considering the compression ratio, the smallest common divisor among the common divisors of which the compression ratio is smaller than the preset value may also be determined as the target common divisor.

Step 203, the compression engine generates a variable-length encoding table according to each character in the data to be compressed and the target common divisor.

The code lengths of at least two code words in the variable-length coding table are different, and the code length of the code word corresponding to the character with a higher occurrence probability in the data to be compressed is smaller than the code length of the code word corresponding to the character with a lower occurrence probability. The greatest common divisor of the code lengths of the codewords in the table is the target common divisor.

The variable-length encoding table is a mapping table that records the correspondence between characters and codewords in the data to be compressed, and the process of generating the variable-length encoding table is the process of determining the correspondence between characters and codewords in the data to be compressed. Wherein, each codeword in the variable-length encoding table corresponds to a character in the data to be compressed, the codeword corresponding to the same character is the same, and the codeword corresponding to different characters is different. For "different characters correspond to different code words", one case is that the number of digits (or "code length") of the code words corresponding to different characters is different; the other case is that although the code words corresponding to different characters have different The number of bits is the same, but the order of arrangement of the binary data in the codeword is different. Referring to Table 1, the code word corresponding to character A is 000, and the code word corresponding to character B is 001, then the code word 000 corresponding to character A and the code word 001 corresponding to character B have the same number of digits, but the binary data in the code word is the same. are arranged in different order. Further referring to Table 1, the code corresponding to the character A is 000, and the character F corresponds to the code 101000, so the number of digits of the code 000 corresponding to the character A and the code 101000 corresponding to the character F are different.

When generating a variable-length code table, each character can be assigned a code word with a decreasing length to each character in the order of the probability of occurrence of each character in the data to be compressed, that is, the greater the probability of a character, the Characters correspond to codewords with shorter lengths, so that the data to be compressed can be represented with a smaller amount of data.

Exemplarily, when the target common divisor is 3, the variable-length encoding table can be as shown in Table 1:

Table 1

In Table 1, in the character column, the probability of occurrence of a character corresponding to a codeword with a shorter code length is greater than that of a character corresponding to a codeword with a longer code length. The code length that is located on the same line as the character, represents the code length of the code word corresponding to the character, or represents the number of code elements contained in the code word corresponding to the character, such as the code length 6 that is located on the same line as the character "P". It is the code length of the code word "110010" corresponding to the character "P". The codeword on the same row as the character represents the codeword corresponding to the character, for example, the codeword "110011" on the same row as the character "Q" represents the codeword corresponding to the character "Q". The arrangement order of the characters in the data to be compressed is consistent with the arrangement order of the code words in the compressed data.

The variable-length encoding in the embodiment of the present invention may be an entropy encoding (English: entropy encoding), and entropy encoding is an encoding manner used in lossless compression.

Step 204: The compression engine compresses the data to be compressed according to the variable length coding table to obtain compressed data.

After the variable-length encoding table is obtained, the data to be compressed can be compressed according to the variable-length encoding table to obtain compressed data. Exemplarily, the variable-length coding table is Table 1. After compressing the to-be-compressed data "ABC" according to Table 1, the obtained compressed data is "000 001 010".

Step 205: The compression engine generates a compressed data package based on the compressed data and the variable-length encoding table.

After acquiring the variable-length encoding table and the compressed data, the compression engine generates a compressed data package based on the compressed data and the variable-length encoding table. The compressed data encapsulation may also include other data, such as a check code (English: CHECKSUM) and the like.

Compared with the compression rate of the compression method based on LZ4 (an encoding method), the compression rate of the compression method provided by the embodiment of the present invention is reduced by about 30%.

To sum up, the compression method provided by the embodiment of the present invention generates a variable-length encoding table with the greatest common divisor of the length of the codeword, and compresses the data to be compressed according to the variable-length encoding table, so that the decompression engine is decompressing the compressed data. Data can be decompressed concurrently from multiple locations without waiting for a codeword to be decompressed before decompressing the next codeword according to the length of the codeword, and the decompression speed is high.

3A is a flowchart of a decompression method shown in an embodiment of the present invention. This embodiment is illustrated by applying the decompression method to decompressing the compressed data package generated by the compression method provided by the embodiment shown in FIG. 2A , The decompression method can be implemented by the decompression engine in FIG. 1A or FIG. 1B . The decompression method may include the following steps:

Step 301: The decompression engine analyzes the compressed data encapsulation to obtain a variable-length code table and compressed data.

When using the decompression method provided by the embodiment of the present invention, the decompression engine may first analyze the encapsulation of the compressed data, and obtain the variable-length coding table and the compressed data. The compressed data encapsulation may be the compressed data encapsulation obtained by the compression method provided by the embodiment shown in FIG. 2A , and the compressed data encapsulation may include a variable-length encoding table, compressed data and other data.

This step is optional, that is, the decompression engine can also directly obtain variable-length encoded and compressed data.

Step 302, the decompression engine reads the code segment with the code length a*N+b from the compressed data in each clock cycle according to the generation sequence of the compressed data, and the code length read in the xth clock cycle is a*N+b. The last b bits of the code segment coincide with the first b bits of the code segment whose code length is a*N+b read in the x+1th clock cycle.

After obtaining the variable-length code table, the decompression engine can read the code length from the compressed data in each clock cycle according to the generation sequence of the compressed data (that is, the data generated first is read first, and the data generated last is read later). The code segment of a*N+b (a*N+b is greater than or equal to the code length c of the longest codeword in the compressed data), the code length read in the xth clock cycle is the code segment of a*N+b The last b bits coincide with the first b bits of the code segment with a code length of a*N+b read in the x+1th clock cycle, where N is an integer greater than 0, and a represents the target common divisor mentioned in the above embodiment , the value of N can be preset according to the hardware situation, b is the difference between the code length c of the longest code word in the compressed data and the code length a of the shortest code word (the code length of the shortest code word is equal to the target common divisor a), a *N may represent the decompression speed of the decompression method provided by the embodiment of the present invention, that is, the larger a and N are, the higher the decompression speed of the decompression method provided by the embodiment of the present invention. Exemplarily, when a=3, c=12, b=c-a=9, the decompression engine reads 3N+9 bits of data per clock cycle.

In the compressed data, the values such as the greatest common divisor a of the code length of the code word, the difference between the code length of the longest code word and the code length of the shortest code word in the compressed data, etc., can be known in advance by the decompression engine before decompression. , for example, these values can be written into the decompression engine when the decompression engine is set. Alternatively, values such as the greatest common divisor a of the code length of the code word, the difference between the code length of the longest code word in the compressed data and the code length of the shortest code word b, etc., can also be included in the variable-length encoding table, and the decompression engine can These values are obtained when parsing the variable-length encoding table.

The clock cycle (English: Clock Cycle) is also called the oscillation cycle, and the clock cycle is the unit of time in the computer. In one clock cycle, the CPU completes a basic action.

In step 302, the decompression engine reads a code segment with a fixed code length from the compressed data in each clock cycle, so data can be transmitted to the decompression engine with a stable bandwidth, and the decompression engine has a high utilization rate of the bandwidth. The decompression method provided by the embodiment can be applied to a bandwidth compression scenario, such as an online decompression application of neural network parameters. However, in the related art, since the code length of the codeword decompressed in each clock cycle may be different, the code segment of the code segment read by the decompression engine may be different. The lengths are also different, making it difficult to apply to bandwidth compression scenarios.

In the decompression method provided by the embodiment of the present invention, the decompression engine can adjust the amount of data read in each clock cycle by adjusting the value of N, thereby adjusting the decompression speed.

Since there may be uncompressed multi-bit symbols at the end of the code segment read in the previous clock cycle in two adjacent clock cycles, in order to avoid the omission of these symbols, when the decompression engine reads the code segment in each clock cycle, The last b bits of the code segment read in the previous clock cycle are read repeatedly, because the code length of the entire compressed data is an integer multiple of a, and the maximum number of symbols that may not be decompressed in the previous clock cycle is b ( In the code segment read in the previous clock cycle, when the last codeword is the maximum length c, the number of undecompressed symbols missed in the previous clock cycle is the maximum number b), and the least possible undecompressed code in the previous clock cycle The number of elements is 0. It should be noted that, in fact, the number of uncompressed symbols in the previous clock cycle is the product of an integer in the interval [0, K] and a, where K is equal to b/a.

Step 303: The decompression engine obtains (a*N+b)/a sub-code segments according to the code segment with the code length a*N+b read from the compressed data according to the xth clock cycle.

Among them, x is an integer greater than or equal to 1; the code length of each sub-code segment in (a*N+b)/a sub-code segments is c, and (a*N+b)/a sub-code segments include the first sub-code segment Code segment, the start bit of the first subcode segment coincides with the start bit of the code segment read in the xth clock cycle, and the start of (a*N+b)/a subcode segment of two adjacent subcode segments The code length of the interval between bits is a-1.

Step 304, the decompression engine decompresses (a*N+b)/a subcode segments concurrently based on the variable-length encoding table to obtain (a*N+b)/a characters, wherein each subcode is decompressed segment gets one character. When x is equal to 1, step 305 is performed; when x is an integer greater than or equal to 2, step 306 is performed.

In the a*N+b-bit data read in the xth clock cycle, the decompression engine can decompress multiple subcode segments concurrently. The start symbol is the start symbol of each subcode segment.

Wherein, the decompression engine uses the variable-length coding table for multiple sub-code segments starting from the N*ath bit to the (N+K-1)*ath bit in the code segment with a code length of a*N+b. During decompression, if the number of remaining symbols in the code segment whose code length is a*N+b is not enough to c, the decompression engine can use the preset value (the preset The value can be set arbitrarily, such as all 0 or all 1, or alternating 0 and 1, etc.) Fill the code length to c, and then decompress these subcode segments to obtain multiple characters, and then each subcode can be detected. The code length of the corresponding code word in the variable-length encoding table of the character obtained by segment decompression. For example, the code length of the corresponding code word in the variable-length encoding table of the character obtained by decompressing a sub-code segment is greater than that of the sub-code segment before filling. If the code length is longer, the characters obtained by decompressing the sub-code segment can be deleted. After the characters are deleted, there are several undecompressed symbols in the a*N+b bit data.

Exemplarily, the code segment read in the xth clock cycle is "000 001 010 011 100", a=3, c=6, according to the variable-length coding table shown in Table 1, and the sub-code segment "000 001" , "001 010", "010 011", "011 100" and "100000" are decompressed, and the obtained character is the character "A" corresponding to the codeword 000, the character "B" corresponding to the codeword 001, and the codeword 010 The corresponding character "C", the character "D" corresponding to the codeword 011, and the character "E" corresponding to the codeword "100". Among them, "100 000" is a sub-code segment filled with 6 bits. The code length of the code word corresponding to the character "E" obtained by decompressing the 6-bit sub-code segment is 3, which is not greater than the length of "100 000" before filling. Therefore, the character "E" may not be deleted.

It should be noted that there is a one-to-one correspondence between the codewords in the compressed data and the characters in the target decompressed data obtained by decompressing the compressed data. The Kth codeword in the compressed data corresponds to the Kth character in the target decompressed data. If the start bit of a codeword is determined, the codeword can be determined (read at least a from the start bit) Bit symbols, up to c bit symbols, can obtain a codeword represented by these symbols from the variable-length coding table). In the prior art, the code lengths of each codeword in the compressed data are not all the same. Before decompressing a codeword according to the order in the compressed data, the decompression engine cannot know the code length of the codeword, and thus cannot know the next codeword. The start bit of the codeword. However, since the code length of the code word in the compressed data in the decompression method provided by the embodiment of the present invention has the greatest common divisor a, the start bit of the code word corresponding to each character in the decompressed data is included in (a*N+ b) In the start bit of each sub-code segment in the/a sub-code segments, it can be called the code word corresponding to each character in the target decompressed data obtained by decompressing the compressed data (from the variable-length coding table, we can know that each character The starting bit of the code word corresponding to the character) is the correct starting bit in the starting bits of (a*N+b)/a sub-code segments (the correct starting bit is the order of the bit in the entire compressed data) Determined, if the start bit of the code word corresponding to the first character in the decompressed data is the first bit of the entire compressed data, then the first bit in the entire compressed data is the code word corresponding to the first character in the decompressed data. The correct start bit), and the other bits except the correct start bit among the start bits of (a*N+b)/a subcode segments are called error start bits. In step 304, among the multiple characters obtained by decompressing (a*N+b)/a subcode segments concurrently, the valid characters obtained by decompressing from the correct start position and the invalid characters obtained by decompressing from the wrong start position are included. .

Step 305, when x is equal to 1, the decompression engine determines the target decompression data of the xth clock cycle from (a*N+b)/a characters, and the first valid character in the target decompression data of the xth clock cycle corresponds to The start symbol of the codeword of , and the start symbol of the code segment read in the xth clock cycle coincide.

Among them, in the target decompressed data of the xth clock cycle, the position of the last symbol of the code word corresponding to one valid character in each adjacent two valid characters in the code segment read in the xth clock cycle and the other valid character The starting symbols of the code words corresponding to the characters are located adjacent to each other in the code segment read in the xth clock cycle. The target decompressed data for the xth clock cycle includes a plurality of valid characters arranged in a specific order.

After the decompression engine obtains (a*N+b)/a characters, it knows the code length of the codeword corresponding to each of the (a*N+b)/a characters. Because these multiple characters include invalid characters obtained from decompression from the wrong start bit, multiple valid characters can be selected for splicing to obtain the target decompressed data of the xth clock cycle, and the selection basis can be determined first. The code length read in the xth clock cycle is the correct start bit of the first code word in the code segment of a*N+b, and then the second code word is determined according to the correct start bit and the code length of the first code word. The correct start bit of each codeword (the correct start bit of the second codeword is the next bit of the last bit of the first codeword), and so on, the decompression engine can obtain the code corresponding to each valid character The correct start bit of the word, and then multiple valid characters can be selected, and the multiple valid characters are the order of the code words corresponding to each valid character in the a*N+b bit data read in the xth clock cycle. Splicing is performed sequentially, and the target decompressed data of the data read in the xth clock cycle is obtained.

When x=1, the start bit of the code segment with the code length a*N+b read in the xth clock cycle is the start bit of the compressed data, and the start bit is the code read in the xth clock cycle The correct start bit of the first codeword in a code segment of length a*N+b.

Exemplarily, as shown in FIG. 3B , it reads the first 24-bit symbols in the code segment whose code length is a*N+b in the xth clock cycle. The code length and the character corresponding to each code word, that is, the code word composed of 0 to 5 bits with a code length of 6 corresponds to character A, and the code word composed of 3 to 8 bits with a code length of 6 corresponds to character B, and 6 to 14 bits. The code word formed with the code length of 9 corresponds to the character C, the code word formed by 9 to 14 bits is the corresponding character D of the code length 6, the code word formed by the 12 to 23 bits is the corresponding character E of the code length of 12, and 15 to 17 The code word with the code length of 3 corresponding to the character F, wherein the code length of the code word and the character corresponding to the code word can be as shown in Table 2:

Table 2

In Table 2, the top-down sequence of each character, and the sequence of the start bit of the codeword corresponding to each character in the code segment with the code length a*N+b read in the xth clock cycle are: consistent. The way to determine a valid character from the 24-bit symbol shown in FIG. 3B and a plurality of characters corresponding to the 24-bit symbol may be: taking the start bit of the 24-bit symbol as the start bit of the first codeword (The start bit is the correct start bit of the code word corresponding to the first valid character), it is determined that the code length of the first code word is 6, and the character corresponding to the first code word is A. The code length of each codeword is 6, so the correct start bit of the second codeword is the 6th bit of the 24-bit symbol (the first 0 to 5 bits are occupied by the first codeword), and the 24-bit The character corresponding to the code word whose 6th bit of the code element is the starting position is C, so the character C can be used as the second valid character. Since the code length of the code word corresponding to the second valid character is 9, the third The correct start bit of a codeword is the 15th bit of the 24-bit symbol (the first 0 to 14 bits are occupied by the first codeword and the second codeword), and the codeword with the 15th bit as the starting position The corresponding character is F, so the decompressed data obtained is A C F.

Step 306: When x is an integer greater than or equal to 2, the decompression engine determines c/a groups of candidate decompressed data from (a*N+b)/a characters.

Among them, each group of candidate decompression data includes multiple characters, and in each adjacent two characters, the position of the last symbol of the code word corresponding to one character in the code segment read in the xth clock cycle and another character The position of the starting symbol of the corresponding codeword in the code segment read in the xth clock cycle is adjacent; the starting symbol of the codeword corresponding to the first character in each two groups of candidate decompressed data is located at the xth The positions in the code segments read by the clock cycle are different, and the start symbol of the code word corresponding to the first character in each group of candidate decompressed data is W* in the code segment read in the xth clock cycle a symbols, W is an integer greater than or equal to 0 and less than or equal to b/a.

When x is an integer greater than or equal to 2, since the data read in the x-1 clock cycle has not been decompressed, it is difficult for the decompression engine to know the number of uncompressed symbols in the data read in the x-1 clock cycle. Therefore, it is difficult for the decompression engine to determine the correct start bit of the first codeword in the code segment whose code length is a*N+b. At this point, the decompression engine can determine all possible correct start bits (all possible correct start bits are the H*a bit in the code segment with a code length of a*N+b read in the xth clock cycle, H takes each integer from 0 to K, K=b/a), and then takes these all possible correct start bits as the correct start bits of the first codeword respectively, and obtains c/ a candidate decompressed data.

Among them, because the first b bits of the code segment read in the xth clock cycle and the last b bits of the code segment read in the x-1th clock cycle are repeated, and the first few bits of the repeated b bits may exist in the A part of the last code word in the code segment read in the x-1 clock cycle, the correct start bit of the first code word in the code segment read in the x-th clock cycle is the code segment read in the x-1 clock cycle The digit next to the last digit of the last codeword in .

Since the greatest common divisor of the code length of the code word in the compressed data is a, the length of the code segment read in the x-1th clock cycle that exists in the first b bits of the code segment read in the xth clock cycle can be 0 to The product of any integer in K and a (when the length is 0*a, it indicates that there is no last bit in the code segment read in the x-1th clock cycle in the first b bits of the code segment read in the xth clock cycle part of the codeword), so the H*a bit in the first b-bit symbols of the code segment read at the xth clock cycle may be the correct start of the first codeword in the code segment read at the xth clock cycle bits, and the number of candidate decompressed data depends on the number of integers from 0 to K, which is equal to K+1=b/a+1=(a+b)/a=c/a, where K+1=b/a+1=(a+b)/a=c/a 1 is added because 0 also counts as an integer from 0 to K.

Exemplarily, c=9, a=3, the first 9 bits of the code segment read in the xth clock cycle is "000 001 010", then the 0th, 3rd and 6th bits are possible correct start bit, the decompression engine can take the 0th bit, the 3rd bit and the 6th bit as the start bit of the code word corresponding to the first character in the three candidate decompressed data, and obtain 3 bits in the manner in step 305 respectively. candidate decompression data.

Step 307: The decompression engine determines the target decompression data of the xth clock cycle from the candidate decompression data of the group c/a.

In the compressed data, the last symbol of the codeword corresponding to the last character in the target decompressed data of the x-1th clock cycle and the start code of the codeword corresponding to the first character in the target decompressed data of the xth clock cycle The elements are adjacent, and the target decompression data of the x-1th clock cycle refers to the target decompression data corresponding to the code segment read in the x-1th clock cycle. In the case where x is equal to 1, the target decompressed data of the x-1th clock cycle is a plurality of valid characters arranged in a specific order obtained by decompressing the code segment read in the first clock cycle.

After the decompression engine obtains the c/a candidate decompressed data of the xth clock cycle, it also completes the decompression of the code segment read in the x-1th clock cycle, and obtains the target decompression data of the x-1th clock cycle. , the decompression engine can determine the correct start bit of the first codeword in the data read in the xth clock cycle according to the target decompression data of the x-1th clock cycle, and select the xth from the c/a candidate decompression data Target decompressed data in clock cycles.

Exemplarily, the decompressed data of the x-1 clock cycle is "ABCD", the corresponding code word is "000 001 010011", and the code segment read in the x-1 clock cycle is "000 001 010 011 101", b =6, a=3, c=9, N=4, a*N+b=15, the code segment read in the xth clock cycle is "011 101000 101001", of which the first 6 bits are the x-1th clock cycle The last 6 bits of the read code segment, the last three bits "101" in the code segment read in the x-1 clock cycle are the first three bits of a 6-bit code word, and the method in step 304 will not check this. The three bits are decompressed, and the three bits of data are the uncompressed code segments. The starting symbols of these three bits of code segments can be determined as the start of the code word corresponding to the first character in the target decompressed data of the xth clock cycle. initial code element.

It should be noted that, in the embodiment of the present invention, the code segments read in each clock cycle are processed concurrently, that is, after the decompression engine reads the code segments in the x-1th clock cycle, the decompression engine processes the code segments in the x-1 clock cycle. When the code segment read at the x-1 clock cycle is decompressed, the decompression engine reads the code segment again at the xth clock cycle, and simultaneously starts to decompress the code segment read at the xth clock cycle. The code segment read at the x-1th clock cycle is read one clock cycle before the code segment read at the xth clock cycle, so the decompression engine performs any of steps 303 to 307 on the code segment read at the xth clock cycle. One process is one step slower than the same process performed by the decompression engine on the code segment read by the x-1 clock cycle. Therefore, in the process of processing the code segment read in the xth clock cycle by the decompression engine, when step 306 is executed, the decompression engine has completed the decompression of the code segment read in the x-1th clock cycle, and obtains the xth -1 clock cycle to target decompressed data.

Through steps 302 to 307, all the data in the compressed data can be decompressed, and the target decompressed data of each clock cycle can be obtained.

Step 308: The decompression engine splices the obtained decompressed data of multiple clock cycles according to the compressed data, and obtains the decompressed data corresponding to the compressed data.

Among them, in the two adjacent clock cycles after splicing, the position of the last symbol of the code word corresponding to the last character in the target decompressed data of one clock cycle in the compressed data and the position of the last symbol in the target decompressed data of another clock cycle The positions of the start symbols of the code words corresponding to one character in the compressed data are adjacent.

As shown in FIG. 3C , it is a bar of the chip area occupied by the decompression engine when the decompression method provided by the embodiment of the present invention is applied, when the decompression method based on Huffman coding is applied, and when the decompression method based on LZ4 is applied. Graph, wherein the vertical axis represents the area of the chip, the area of the chip is in square millimeters, and the chip refers to a chip with a 16 nanometer (nm) process. The bar 31 represents the chip area occupied by the decompression engine when the decompression method based on Huffman coding is applied, and the area is 0.05 square millimeters. The bar 32 represents that the greatest common divisor is 3. When the decompression method provided by the embodiment of the present invention is applied, the chip area occupied by the decompression engine is 0.035 square millimeters. The bar 33 represents that the greatest common divisor is 2. When the decompression method provided by the embodiment of the present invention is applied, the chip area occupied by the decompression engine is 0.025 square millimeters. The bar 34 represents the chip area occupied by the decompression engine when the LZ4-based decompression method is applied, which is 0.16 square millimeters. It can be seen that the decompression method provided by the embodiment of the present invention occupies a smaller chip area than the decompression method in the related art.

In addition, the decompression speed of the decompression method provided by the embodiment of the present invention can reach about 10 times the decompression speed of the compressed data package generated according to Huffman coding, and is basically the same as the decompression speed of the compressed data package generated based on LZ4.

To sum up, in the decompression method provided by the embodiments of the present invention, when decompressing compressed data, by concurrently decompressing (a*N+b)/a subcode segments, (a*N+ b)/a characters, and then determine the target decompressed data of the xth clock cycle from (a*N+b)/a characters according to the variable-length encoding table and the code segment read in the xth clock cycle. There is no need to wait for a codeword to be decompressed before decompressing the next codeword according to the length of the codeword. The problem of low decompression speed in the related art is solved. When decompressing, you can start decompressing from multiple locations at the same time, and the decompression speed is high.

FIG. 4 is a structural block diagram of a compression apparatus provided by an embodiment of the present invention, and the compression apparatus may become part or all of a terminal or a server. The compression device 400 may include:

The common divisor determination unit 410 is configured to perform step 202 in the above embodiment.

The coding table generating unit 420 is configured to perform step 203 and step 201 in the above embodiment.

The compression unit 430 is configured to perform step 204 in the above embodiment.

The package generation unit 440 is configured to perform step 205 in the above embodiment.

To sum up, the compression device provided by the embodiment of the present invention generates a variable-length encoding table with the greatest common divisor of the length of the codeword, and compresses the data to be compressed according to the variable-length encoding table, so that the decompression engine decompresses the compressed data. Data can be decompressed concurrently from multiple locations without waiting for a codeword to be decompressed before decompressing the next codeword according to the length of the codeword, and the decompression speed is high.

FIG. 5A is a structural block diagram of a decompression apparatus provided by an embodiment of the present invention. The decompression apparatus 500 may include:

The subcode segment determination unit 510 is configured to perform steps 301, 302 and 303 in the above embodiment.

The decompression unit 520 is configured to perform step 304 in the above embodiment.

The decompressed data determination unit 530 is configured to perform steps 305, 306 and 307 in the above embodiment.

Optionally, as shown in FIG. 5B , the decompression apparatus 500 may further include:

The splicing unit 540 is configured to perform step 308 in the above embodiment.

To sum up, in the decompression apparatus provided by the embodiment of the present invention, when decompressing the compressed data, by concurrently decompressing (a*N+b)/a subcode segments, (a*N+ b)/a characters, and then determine the target decompressed data of the xth clock cycle from (a*N+b)/a characters according to the variable-length encoding table and the code segment read in the xth clock cycle. There is no need to wait for a codeword to be decompressed before decompressing the next codeword according to the length of the codeword. The problem of low decompression speed in the related art is solved. When decompressing, you can start decompressing from multiple locations at the same time, and the decompression speed is high.

Referring to FIG. 6, it is a schematic structural diagram of a data processing system provided by an embodiment of the present invention. The data processing system includes a compression device 61 and a decompression device 63. The compression device 61 may be the The device 63 may be the decompression device described in the foregoing embodiments. The compression device 61 is used for compressing the data to be compressed to obtain compressed data; the decompression device 63 is used for decompressing the compressed data. The data processing system can be applied to a terminal or a server. Wherein, the terminal may include a smart phone, a tablet computer, a computer and a laptop computer, and the server may be a server, or a server cluster consisting of several servers, or a cloud computing service center.

In the several embodiments provided in this application, it should be understood that the disclosed apparatus and method may be implemented in other manners. For example, the apparatus embodiments described above are only illustrative. For example, the division of the units is only a logical function division. In actual implementation, there may be other division methods. For example, multiple units or components may be combined or Can be integrated into another system, or some features can be ignored, or not implemented. On the other hand, the shown or discussed mutual coupling or direct coupling or communication connection may be through some interfaces, indirect coupling or communication connection of devices or units, and may be in electrical, mechanical or other forms.

The units described as separate components may or may not be physically separated, and components displayed as units may or may not be physical units, that is, may be located in one place, or may be distributed to multiple network units. Some or all of the units may be selected according to actual needs to achieve the purpose of the solution in this embodiment.

Those of ordinary skill in the art can understand that all or part of the steps of implementing the above embodiments can be completed by hardware, or can be completed by instructing relevant hardware through a program, and the program can be stored in a computer-readable storage medium. The storage medium mentioned may be a read-only memory, a magnetic disk or an optical disk, etc.

The above descriptions are only optional embodiments of the embodiments of the present invention, and are not intended to limit the present application. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present application shall be included in the present application. within the scope of protection.

Claims (15)

1. A method of decompression, the method comprising:

reading a code segment with the code length of a x N + b from compressed data according to the x clock period to obtain (a x N + b)/a sub-code segments; wherein x is an integer greater than or equal to 1; the code length of each sub-code segment in the (a × N + b)/a sub-code segments is c, the (a × N + b)/a sub-code segments include a first sub-code segment, the start bit of the first sub-code segment coincides with the start bit of the code segment read in the x-th clock cycle, the code length of the interval between the start bits of two adjacent sub-code segments in the (a × N + b)/a sub-code segments is a-1, and N is an integer greater than 0;

based on a variable length coding table, decompressing the (a × N + b)/a sub-code segments concurrently to obtain (a × N + b)/a characters, wherein one character can be obtained by decompressing each sub-code segment;

the variable length coding table comprises a plurality of code words, and each character in the (a × N + b)/a characters corresponds to one code word in the variable length coding table; the code lengths corresponding to at least two of the multiple code words are different, the code length corresponding to the code word with the longest code length in the multiple code words is c, the code length corresponding to the code word with the shortest code length in the multiple code words is a, and a is the greatest common divisor of the code lengths corresponding to each of the multiple code words, wherein a is an integer greater than or equal to 2, c is an integer greater than a, and the difference between c and a is b;

and determining target decompressed data of the x clock period from the (a × N + b)/a characters according to the variable length coding table and the code segment read by the x clock period, wherein in the target decompressed data of the x clock period, the position of the last code element of the code word corresponding to one effective character in every two adjacent effective characters in the code segment read by the x clock period is adjacent to the position of the start code element of the code word corresponding to the other effective character in the code segment read by the x clock period.

2. The method of claim 1,

and the rear b bits of the code segment with the code length of a × N + b read in the x clock period coincide with the front b bits of the code segment with the code length of a × N + b read in the x +1 clock period.

3. The method according to claim 1 or 2, wherein in a case that x is equal to 1, the determining, from the (a × N + b)/a characters, the target decompressed data of the xth clock cycle according to the variable length code table and the code segment read in the xth clock cycle includes:

and determining target decompressed data of the x clock period from the (a × N + b)/a characters, wherein a start code element of a code word corresponding to a first effective character in the target decompressed data of the x clock period coincides with a start code element of a code segment read by the x clock period.

4. The method according to claim 1 or 2, wherein, when x is an integer greater than or equal to 2, the determining, from the (a × N + b)/a characters, the target decompressed data of the xth clock cycle according to the variable length coding table and the code segment read in the xth clock cycle includes:

determining c/a group of candidate decompressed data from (a x N + b)/a characters; each group of candidate decompressed data comprises a plurality of characters, and in every two adjacent characters, the position of the last code element of the code word corresponding to one character in the code segment read by the x-th clock cycle is adjacent to the position of the start code element of the code word corresponding to the other character in the code segment read by the x-th clock cycle; the positions of the starting code elements of the code words corresponding to the first character in each two groups of candidate decompressed data in the code segments read in the x clock period are different, the starting code elements of the code words corresponding to the first character in each group of candidate decompressed data are the Wa code elements in the code segments read in the x clock period, and W is an integer which is greater than or equal to 0 and less than or equal to b/a;

determining target decompressed data of the x clock period from the c/a group of candidate decompressed data; in the compressed data, the last bit code element of the code word corresponding to the last character in the target decompressed data of the x-1 clock cycle and the start code element of the code word corresponding to the first character in the target decompressed data of the x-1 clock cycle are adjacent, and the target decompressed data of the x-1 clock cycle refers to the target decompressed data corresponding to the code segment read in the x-1 clock cycle.

5. The method of claim 1, wherein after determining the target decompressed data for the x-th clock cycle, the method further comprises:

according to the compressed data, splicing the obtained decompressed data in a plurality of clock cycles to obtain the decompressed data corresponding to the compressed data, wherein in two adjacent clock cycles after splicing, the position of the last code element of the code word corresponding to the last character in the target decompressed data in one clock cycle in the compressed data and the position of the start code element of the code word corresponding to the first character in the target decompressed data in the other clock cycle in the compressed data are adjacent.

6. A method of compression, the method comprising:

determining a target common divisor of a code length corresponding to each code word in a variable length coding table; the variable length coding table comprises a plurality of code words, the target common divisor is an integer which is greater than or equal to 2, and each character in the data to be compressed corresponds to one code word in the variable length coding table;

generating the variable length coding table according to each character in the data to be compressed and the target common divisor; the code lengths of at least two code words in the variable length coding table are different, the code length of the code word corresponding to the character with higher occurrence probability in the data to be compressed is smaller than the code length of the code word corresponding to the character with lower occurrence probability, and the maximum common divisor of the code lengths of the code words in the variable length coding table is the target common divisor;

compressing the data to be compressed according to the variable length coding table to obtain compressed data;

generating a compressed data package based on the compressed data and the variable length coding table.

7. The method of claim 6, wherein determining the target common divisor of the code length corresponding to each codeword in the variable length coding table comprises:

determining at least one common divisor, and compressing the data to be compressed according to a variable length coding table corresponding to each common divisor in the at least one common divisor, wherein the obtained compression ratios are all smaller than a preset value, and a corresponding variable length coding table can be generated according to each common divisor in the at least one common divisor;

and determining the target common divisor from the at least one common divisor, wherein the value of the target common divisor is greater than the value of each common divisor of the at least one common divisor except the target common divisor.

8. A decompression apparatus, characterized in that the decompression apparatus comprises:

a sub-code segment determining unit, configured to read a code segment with a code length of a × N + b from compressed data according to an x-th clock cycle, to obtain (a × N + b)/a sub-code segments; wherein x is an integer greater than or equal to 1; the code length of each sub-code segment in the (a × N + b)/a sub-code segments is c, the (a × N + b)/a sub-code segments include a first sub-code segment, the start bit of the first sub-code segment coincides with the start bit of the code segment read in the x-th clock cycle, the code length of the interval between the start bits of two adjacent sub-code segments in the (a × N + b)/a sub-code segments is a-1, and N is an integer greater than 0;

the decompression unit is used for carrying out decompression processing on the (a x N + b)/a sub-code segments concurrently based on a variable length coding table to obtain (a x N + b)/a characters, wherein each sub-code segment can be decompressed to obtain one character; the variable length coding table comprises a plurality of code words, and each character in the (a × N + b)/a characters corresponds to one code word in the variable length coding table; the code lengths corresponding to at least two of the multiple code words are different, the code length corresponding to the code word with the longest code length in the multiple code words is c, the code length corresponding to the code word with the shortest code length in the multiple code words is a, and a is the greatest common divisor of the code lengths corresponding to each of the multiple code words, wherein a is an integer greater than or equal to 2, c is an integer greater than a, and the difference between c and a is b;

and a decompressed data determining unit, configured to determine target decompressed data in an x-th clock cycle from the (a × N + b)/a characters according to the variable length coding table and the code segment read in the x-th clock cycle, where in the target decompressed data in the x-th clock cycle, a position of a last symbol of a code word corresponding to one valid character in every two adjacent valid characters in the code segment read in the x-th clock cycle is adjacent to a position of a start symbol of a code word corresponding to another valid character in the code segment read in the x-th clock cycle.

9. The decompression device according to claim 8,

and the rear b bits of the code segment with the code length of a × N + b read in the x clock period coincide with the front b bits of the code segment with the code length of a × N + b read in the x +1 clock period.

10. The decompression device according to claim 8 or 9, wherein, in case x is equal to 1, the decompressed data determining unit is specifically configured to:

and determining target decompressed data of the x clock period from the (a × N + b)/a characters, wherein a start code element of a code word corresponding to a first effective character in the target decompressed data of the x clock period coincides with a start code element of a code segment read by the x clock period.

11. The decompression device according to claim 8 or 9, wherein the decompressed data determining unit, when x is an integer greater than or equal to 2, specifically includes:

determining c/a group of candidate decompressed data from (a x N + b)/a characters; each group of candidate decompressed data comprises a plurality of characters, and in every two adjacent characters, the position of the last code element of the code word corresponding to one character in the code segment read by the x-th clock cycle is adjacent to the position of the start code element of the code word corresponding to the other character in the code segment read by the x-th clock cycle; the positions of the starting code elements of the code words corresponding to the first character in each two groups of candidate decompressed data in the code segments read in the x clock period are different, the starting code elements of the code words corresponding to the first character in each group of candidate decompressed data are the Wa code elements in the code segments read in the x clock period, and W is an integer which is greater than or equal to 0 and less than or equal to b/a;

determining target decompressed data of the x clock period from the c/a group of candidate decompressed data; in the compressed data, the last bit code element of the code word corresponding to the last character in the target decompressed data of the x-1 clock cycle and the start code element of the code word corresponding to the first character in the target decompressed data of the x-1 clock cycle are adjacent, and the target decompressed data of the x-1 clock cycle refers to the target decompressed data corresponding to the code segment read in the x-1 clock cycle.

12. The decompression device according to claim 8, further comprising:

and the splicing unit is used for splicing the obtained decompressed data in a plurality of clock cycles according to the compressed data to obtain the decompressed data corresponding to the compressed data, and in two adjacent clock cycles after splicing, the position of the last code element of the code word corresponding to the last character in the target decompressed data in one clock cycle in the compressed data and the position of the start code element of the code word corresponding to the first character in the target decompressed data in the other clock cycle in the compressed data are adjacent.

13. A compression device, characterized in that it comprises:

the common divisor determining unit is used for determining a target common divisor of the code length corresponding to each code word in the variable length coding table; the variable length coding table comprises a plurality of code words, the target common divisor is an integer which is greater than or equal to 2, and each character in the data to be compressed corresponds to one code word in the variable length coding table;

the coding table generating unit is used for generating the variable length coding table according to each character in the data to be compressed and the target common divisor; the code lengths of at least two code words in the variable length coding table are different, the code length of the code word corresponding to the character with higher occurrence probability in the data to be compressed is smaller than the code length of the code word corresponding to the character with lower occurrence probability, and the maximum common divisor of the code lengths of the code words in the variable length coding table is the target common divisor;

the compression unit is used for compressing the data to be compressed according to the variable length coding table to obtain compressed data;

and the package generating unit is used for generating a compressed data package based on the compressed data and the variable length coding table.

14. The compression apparatus as claimed in claim 13, wherein the common divisor determination unit is configured to:

determining at least one common divisor, and compressing the data to be compressed according to a variable length coding table corresponding to each common divisor in the at least one common divisor, wherein the obtained compression ratios are all smaller than a preset value, and a corresponding variable length coding table can be generated according to each common divisor in the at least one common divisor;

and determining the target common divisor from the at least one common divisor, wherein the value of the target common divisor is greater than the value of each common divisor of the at least one common divisor except the target common divisor.

15. A data processing system, characterized in that the system comprises compression means and decompression means,

the compression device comprises the compression device of claim 13 or 14, and is used for compressing data to be compressed to obtain compressed data;

the decompression apparatus comprising the decompression apparatus of any of claims 8-12; the decompression device is used for decompressing the compressed data.

Images