JP3425142B2 - Data compression method, data decompression method, data compression device, and data decompression device - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a data compression method, a data decompression method, a data compression device and a data decompression device. In recent years, various types of data such as character codes, vector information, and images have been handled by computers, and the amount of data handled has been increasing rapidly. Along with this, when dealing with a large amount of data, by omitting redundant parts in the data and compressing the data amount,
BACKGROUND OF THE INVENTION Reduction of storage capacity and fast transmission are being carried out. Universal coding has been proposed as a method of compressing various data by one method.

Here, the field of the present invention is not limited to compression of character codes, but can be applied to various data. In the following, the word used in information theory is followed, and one word unit of data is called a character. , A string in which data is connected to arbitrary words is called a character string.

[0003]

2. Description of the Related Art As a method for compressing text data, a file, etc., a dictionary type coding method that uses the similarity of data series and a stochastic statistical coding method (statistical coding) that uses the appearance frequency of a data string. There is. Among them, a typical method of probability statistical coding is the above-mentioned universal coding.

Furthermore, there is a coding called arithmetic coding. This arithmetic coding is to generate a code adapted to the appearance probability of each character while calculating without using a code table. When the appearance frequency of the character of the information source is known, the maximum It is said that it can be compressed efficiently.
There are value arithmetic coding and multi-value arithmetic coding of three or more values. The method of multilevel arithmetic coding will be described below.

In the multi-value arithmetic coding, first, a number line of 0 ≦ P <1 (hereinafter, described as [0,1]) is divided by the number of occurrences of character events (hereinafter, referred to as symbols). Here, the width of each section is taken to be proportional to the ratio of the appearance frequencies of the symbols, and the sections are arranged in descending order of appearance frequency. Then, the section corresponding to the symbol that appears is selected, and in the next symbol, the selected section is further divided into sections corresponding to the total number of symbols, and the section of the corresponding symbol is selected. Subdivide.

Regarding the above processing, FIG. 70 (a) and FIG.
A specific description will be given with reference to a diagram for explaining the principle of multilevel arithmetic coding shown in 0 (b). Here, FIG. 70A is a diagram showing an example of symbols and appearance frequencies, and FIG. 70B is a diagram showing an example of section division of symbols. Then, the description will be advanced by taking the case of dividing the section of the character string “abe” as an example.

First, the number line [0, 1) is converted into FIG.
It is divided into five sections of characters a, b, c, d and e as shown by. Then, the section [0, 0.2) of the first appearing symbol "a" is selected, and the selected section [0, 0.
2) is further divided into 5 sections of all symbols a to e.

Next, the section [0.04, 0.06) of the second appearing symbol "b" is selected, and this section [0.0
4, 0.06) is further divided into five sections of all symbols a to e. Thus, by selecting the section of the symbol "e" that appears third, the character string "abe"
The section [0.05, 0.06) of is obtained. In this way, by repeating the above-described processing for all input data, the section of the character string to be encoded can be determined, and any point in the finally determined section of the character string can be binary-coded. What is displayed is output as a compression code.

The name "arithmetic coding" comes from the fact that a code word is represented by a numerical value below the decimal point of a binary number like [0.11011 ...] And can be calculated. In addition, as a method of dividing the section according to the appearance frequency as described above, a static encoding method that divides the section according to a preset appearance frequency regardless of the actual appearance frequency of the character string.
(static), a quasi-adaptive coding method (semi-
adaptive), or an adaptive coding method that recalculates the frequency each time a character appears and resets the interval for each character (adaptiv
e) There is.

By the way, a method for compressing data in byte (character) units by using the above-described multi-valued arithmetic coding for file compression is described in, for example, the following two documents. "Arithmetic Coding for Data Compression," Commu
n. of ACM, Vol.30, No.6 PP.520 −540 (1986) "An Adatpive Dependency Source Model for Data Co
mpression Scheme, "Commun. of ACM, Vol.32 No.1 PP.
77-83 Here, the literature discloses a specific algorithm of multi-valued arithmetic coding. In addition, the multi-value arithmetic coding in this document is one of the methods called entropy coding that encodes and compresses in units of one character, and multi-value arithmetic coding the appearance probability of the target character The appearance probability is sequentially updated every time the character appears, and is dynamically adapted to various data for encoding. Further, in this multi-valued arithmetic coding, the processing shown in detail in the flowchart of FIG. 71A is performed.

On the other hand, the method of the literature gives a method of obtaining a high compression rate by expressing the character of interest with a conditional probability using the immediately preceding character, and multi-value arithmetic coding of the conditional probability to give a method for obtaining each conditional probability. Are sequentially updated and are dynamically adapted to various data for encoding. Also in this multi-valued arithmetic coding, the processing as shown in the flowchart of FIG. 71 (b) is performed.

Here, instead of multi-valued arithmetic coding, dynamic Huffman coding ("Variation a Theme by Huffman", IEEE Trans. Info) is a modification of Huffman coding.
rm.Theory, Vol.24, No.6 1978, or "Design and
Analysis of Dynamic Huffman Codes ", Journal of AC
M, Vol.34, No.4 1987) can be considered, but this dynamic Huffman coding is less efficient than multi-valued arithmetic coding and takes a long time to process. The method of dynamic Huffman coding of probabilities is not used in practice.

FIG. 72 is a diagram showing an example of this multilevel arithmetic coding / decoding algorithm. In addition to the arithmetic coding, there is a method called a Splay-Tree coding method (see, for example, the document "Application of Spla").
y Tree to Data Compression "by DOUGLAS W. JONES Commu
n.of ACM, Vol31 No.8 P996-1007).

In this splay coding method, FIG.
Using a tree-structure code table as shown in (a) (hereinafter referred to as a code tree), symbols are registered at the ends (generally called leaves or leaves) of the code tree, and the vertices of the code tree (generally called leaves) are registered. The distance from the root (or root) to the leaf where the input data is stored is output as a code word.

More specifically, the code word is assigned "1" when descending from the root to the leaf, when branching to the right, and "0" when branching to the left. That is,
In the example of FIG. 73A, the code of the symbol A is [1011
0], and the code of the symbol B becomes [001]. When the code length is changed (the code is updated), the coded leaf is replaced with another leaf or a contact (called a node or a node) on the code tree.

FIG. 73 (b) shows an example of the above code update. As shown in FIG. 73 (b), the codes of the symbols A, B, C, and D are initially stored in the leaves of the code tree in the input data. Then, first, by changing the nodes of the symbol A and the symbol C, and further changing the nodes of the upper node D and the symbol E of the symbol A, as shown in FIG. 73 (b), the code of the symbol A is [10110 ] To [110] and the code is updated.

Here, the above description is for the case where the appearance probability of each character is dynamically variable-length coded, but in order to further increase the compression rate, the dependency relationship between the input signal and the immediately preceding character is used. It is performed by dynamically variable-length coding the conditional occurrence probability that incorporates. This method is a probabilistic statistic type encoding that uses the probabilistic statistic property of data, and as shown in FIG. 74, a context collection process 511 and a dynamic variable length encoding process 5
It is composed of two steps of 12 and.

Then, as shown in FIG. 75 (a), contextual contexts of character strings are collected from the input data by context collection, and a context tree structure as shown in FIG. 75 (b) is created.
Dynamic conditional variable length coding with conditional probabilities. here,
The conditional probability described above is obtained by counting the number of appearances each time a character string that passes through the characters of each node appears on the context tree having a tree structure as shown in FIG. 75 (b).

By the way, there are mainly the following two methods of context collection for obtaining conditional probabilities. In the following, the number of characters in the condition (context) will be referred to as the degree (reference "Data Compression Using Adaptive Coding and Part").
ial String Matching "JOHN G. CLEARY et al. IEEE Vol.COM
-32, No. 4 APRIL 1984 P396-402). (1) Fixed Order Context Collection Method This method is a method of setting the condition of conditional probability to a fixed number of characters.

For example, in the quadratic context, the contexts of the characters connected to the preceding two characters are collected, and the conditional probability p (y | x1,
x2) is encoded. However, y is the coded character of interest, x
1 and x2 are the first character and the second character immediately before, respectively. (2) Blending context collection method In the fixed-order context collection method described above, if the immediately preceding condition character string is difficult to come out, the estimation of the conditional probability becomes inaccurate,
On the contrary, when the immediately preceding conditional character string is likely to appear, the estimation of the conditional probability becomes accurate, and there is a possibility that the order can be further increased.

Generally, a higher compression ratio is obtained for data in which the correlation between characters is larger as the higher-order context is used, but conversely, the compression ratio is reduced for data in which the correlation is smaller as the higher-order context is used. become worse. The solution to this is the context Bl
ending (mixed order). This method is a method of adapting the order of the context to the input data such that the order is raised when it is easy to appear without fixing the immediately preceding order, and the order is kept low when it is difficult to come out.

[0022]

However, in the stochastic statistic coding method using the arithmetic coding for the dynamic variable length code, every time data is input, the accumulation of all the data input up to that time is accumulated. Since the frequency is recalculated and the number line of [0, 1) is redivided, a complicated and large amount of arithmetic processing is required, and there is a problem that the processing cannot be speeded up.

The present invention was devised in view of such a problem, and by applying spray coding instead of interval calculation of arithmetic codes and registering new data in a code tree in this spray coding, Enables high-speed code registration processing and speeds up data compression / decompression processing.
An object of the present invention is to provide a data compression method, a data decompression method, a data compression device, and a data decompression device.

[0024]

Therefore, in the data compression method of the present invention, the following steps are taken in the data compression method in which the input data is encoded and compressed according to the history that has appeared in the past. It is characterized (Claim 1). (1) A context collection process that holds a combination of input data and a context consisting of n continuous data. (2) Code tree holding process for holding an independent code tree for each context. (3) When the data corresponding to the context of the context collection process appears, the branch of the node as the branch point from the root meaning the vertex of the code tree to the leaf as the point where the data on the code tree is stored. A code output process for outputting a code defined as unique data corresponding to the code. (4) A code length changing process of rearranging a leaf of data and a leaf or node of other data after the process in the code output process.

Furthermore, the data compression method of the present invention is characterized in that the following steps are taken in the data compression method of encoding and compressing the input data according to the history that has appeared in the past (claim 2). ). (1) A context collection process that holds a combination of input data and a context consisting of n continuous data. (2) Code tree holding process for holding an independent code tree for each context. (3) When the data corresponding to the context of the context collection process appears, the branch of the node as the branch point from the root meaning the vertex of the code tree to the leaf as the point where the data on the code tree is stored. A code output process for outputting a code defined as unique data corresponding to the code. (4) A code length changing process of rearranging a leaf of data and a leaf or node of other data after the process in the code output process. (5) A context discriminating process for discriminating whether or not the combination of the input data and the context is held in the context collecting process. (6) An escape code holding process of holding a leaf, in which an escape code defined as data indicating that data has not been registered in advance, is registered in the code tree. (7) When the combination of the input data and the context is a combination that is not held in the history of the context collection process, an escape code is output and the context of the data is acquired until the combination held in the context collection process is obtained. The process of repeating the process of shortening.

Further, the data compression method of the present invention is characterized in that the following steps are taken in the data compression method of encoding and compressing the input data according to the history of appearance in the past (claim 3). ). (1) A context collection process that holds a combination of input data and a context consisting of n continuous data. (2) Code tree holding process for holding an independent code tree for each context. (3) When data corresponding to the context of the context collection process appears, a node branches as a branch point from a root meaning a vertex of a code tree to a leaf as a point where data on the code tree is stored. A code output process for outputting a code defined as unique data corresponding to the code. (4) A code length changing process of rearranging a leaf of data and a leaf or node of other data after the process in the code output process. (5) A context discriminating process for discriminating whether or not the combination of the input data and the context is held in the context collecting process. (6) An escape code holding process of holding a leaf, in which an escape code defined as data indicating that data has not been registered in advance, is registered in the code tree. (7) A new context registration process for newly registering a combination of input data and a context in the context collection process when the combination of the input data and the context is not held in the history of the context collection process. (8) A code tree new registration process of newly registering data in a code tree corresponding to the context when the combination of the input data and the context is a combination not held in the history of the context collection process. (9) When the combination of the input data and the context is a combination that is not held in the history of the context collection process, the code of the escape code is output, and at the same time, the combination of the input data and the context is registered in the history. The process of registering data in the code tree corresponding to the context and repeating the process of shortening the context of the data until the combination held in the context collection process is obtained.

Further, the data compression method of the present invention is characterized in that the following steps are taken in the data compression method of encoding and compressing the input data according to the history that has appeared in the past (claim 4). ). (1) A context collection process that holds a combination of input data and a context consisting of n continuous data. (2) Code tree holding process for holding an independent code tree for each context. (3) When the data corresponding to the context of the context collection process appears, the branch of the node as the branch point from the root meaning the vertex of the code tree to the leaf as the point where the data on the code tree is stored. A code output process for outputting a code defined as unique data corresponding to the code. (4) A code length changing process of rearranging a leaf of data and a leaf or node of other data after the process in the code output process. (5) A context discriminating process for discriminating whether or not the combination of the input data and the context is held in the context collecting process. (6) An escape code holding process of holding a leaf, in which an escape code defined as data indicating that data has not been registered in advance, is registered in the code tree. (7) A new context registration process for newly registering a combination of input data and a context in the context collection process when the combination of the input data and the context is not held in the history of the context collection process. (8) A code tree new registration process of newly registering data in a code tree corresponding to the context when the combination of the input data and the context is a combination not held in the history of the context collection process. (9) In the context new registration process and the code tree new registration process, a process of registering only the combination of the context and the data immediately before determined to be in the history.

On the other hand, the data restoration method of the present invention is characterized in that the following steps are taken in the data restoration method for restoring the coded data obtained by coding the input data according to the history of the past input data. (Claim 5). (1) A context collection process that retains a history of combinations of decoded data and contexts. (2) Code tree holding process for holding independent code trees depending on the context. (3) A code tree determination process of determining a code tree of data from the context of the data decoded up to immediately before. (4) A decoding process of decoding data from the code of the code tree and the code of the data determined in the code tree determination process. (5) A code length changing process in which, after the decoding in the decoding process, the same means as that on the encoding side is used to recombine between leaves as data storage points on the code tree or between leaves and nodes as branch points of the code tree.

The data restoration method of the present invention is characterized in that the following steps are taken in the data restoration method for restoring coded data obtained by coding input data according to the history of past input data. (Claim 6). (1) A context collection process that retains a history of combinations of decoded data and contexts. (2) Code tree holding process for holding independent code trees depending on the context. (3) A code tree determination process of determining a code tree of data from the context of the data decoded up to immediately before. (4) A decoding process of decoding data from the code of the code tree and the code of the data determined in the code tree determination process. (5) A code length changing process in which, after the decoding in the decoding process, the same means as that on the encoding side is used to recombine between leaves as data storage points on the code tree or between leaves and nodes as branch points of the code tree. (6) In the code tree, an escape code defined as data indicating data unregistered is registered in advance for each code tree according to each context, and when the escape code is decoded at the time of decoding, other than the escape code is decoded. Up to the process of shortening the length of the context.

Furthermore, the data restoration method of the present invention is characterized in that the following steps are taken in the data restoration method for restoring coded data obtained by coding input data according to the history of past input data. (Claim 7). (1) A context collection process that retains a history of combinations of decoded data and contexts. (2) Code tree holding process for holding independent code trees depending on the context. (3) A code tree determination process of determining a code tree of data from the context of the data decoded up to immediately before. (4) A decoding process of decoding data from the code of the code tree and the code of the data determined in the code tree determination process. (5) A code length changing process in which, after the decoding in the decoding process, the same means as that on the encoding side is used to recombine between leaves as data storage points on the code tree or between leaves and nodes as branch points of the code tree. (6) Context new registration process of newly registering data in the context collection process. (7) Code tree new registration process of newly registering decoded data in a code tree according to the context. (8) When an escape code defined as data indicating unregistered data is decoded, the context new registration process and the code tree new registration process are executed, and the length of the context is shortened until a code other than the escape code is decoded. The process of repeating the process.

The data restoration method of the present invention is characterized in that the following steps are taken in the data restoration method for restoring coded data obtained by coding input data according to the history of past input data. (Claim 8). (1) A context collection process that retains a history of combinations of decoded data and contexts. (2) Code tree holding process for holding independent code trees depending on the context. (3) A code tree determination process of determining a code tree of data from the context of the data decoded up to immediately before. (4) A decoding process of decoding data from the code of the code tree and the code of the data determined in the code tree determination process. (5) A code length changing process in which, after the decoding in the decoding process, the same means as that on the encoding side is used to recombine between leaves as data storage points on the code tree or between leaves and nodes as branch points of the code tree. (6) Context new registration process of newly registering data in the context collection process. (7) Code tree new registration process of newly registering decoded data in a code tree according to the context. (8) In the process until an escape code other than the escape code defined as data indicating unregistered data is decrypted, when even one escape code is decrypted, a new context is registered only in the context immediately before the decryption other than the escape code. Process and process of performing each new registration process in the code tree new registration process.

Further, the configuration of an apparatus for carrying out the data compression method of the present invention according to claim 1 is shown in the principle block diagram of FIG. The data compression apparatus shown in FIG. 1 encodes and compresses input data according to the history of past appearances. Here, 100 is prefix data holding means, 101 is history holding means, 102 is code tree holding means,
103 is a code tree determining means, 104 is a code output means, 10
Reference numeral 5 is a code length changing means, and 106 is a front data updating means.

The prefix data holding means 100 holds the context consisting of n pieces of input data input up to immediately before the input data, and the history holding means 101 holds the combination of the input data and the context. The code tree holding unit 102 holds an independent code tree for each context. Further, the code tree determining means 103 determines a code tree of data from the input data up to immediately before held in the prefix data holding means 100, and the code output means 104 is selected by the code tree determining means 103. The unique data is output according to a branch from a node as a branch point located midway along the leaf in which the data is stored, from the root meaning the apex of the code tree.

Further, the code length changing means 105 is for recombining the encoded leaf with another leaf or node, and the prefix data updating means 106 is for registering data in the prefix data holding means 100. There (above,
Claim 9). The configuration of an apparatus for carrying out the data compression method of the present invention according to claim 2 is shown in the principle block diagram of FIG. The data compression apparatus shown in FIG. 2 also encodes and compresses input data according to the history of past appearances.

Here, 100 is a front data holding means, 1
01 is history holding means, 103 is code tree determining means, 107
Is a code tree determining means. Further, 108 is a context discrimination means, 109 is an escape code output means, 110 is a context change means, 111 is a code output means, and 116 is a control means. The pre-data holding means 100 holds the context consisting of n pieces of input data input just before the input data, and the history holding means 101 holds the combination of the input data and the context. The code tree holding unit 107 holds an independent code tree for each context in which an escape code defined as data indicating unregistered data is registered in advance.

The code tree determining means 103 determines the code tree of the data from the context and the input data, and the context determining means 108 registers the data in the code tree determined by the code tree determining means 103. The escape code output means 109 determines whether or not there is any data in the code tree, and the escape code output means 109 is on the way from the root, which means the vertex of the code tree, to the leaf as the data storage point of the escape code. The escape code is output according to the branch from the node serving as the branch point.

Further, the context changing means 110 shortens the length n of the context when no data is registered in the code tree, and the code output means 111 when the data is registered in the code tree. Is to output the code of the data according to the branch from the node located on the way from the root of the code tree to the leaf of the data. The code length changing means 105 is a means for recombining the coded leaf and another leaf or node, and the prefix data updating means 1 is used.
Reference numeral 06 is for registering the data in the pre-data holding means 100, and when the control means 116 encodes the escape code, it repeats the processing until the data is encoded. ).

The configuration of an apparatus for carrying out the data compression method according to the third aspect of the present invention is shown in the principle block diagram of FIG. The data compression apparatus shown in FIG. 3 also encodes and compresses input data according to the history of past appearances. Here, 100 is a front data holding means,
101 is history holding means, 103 is code tree determining means, and 10
5 is a code length changing means, 106 is a front data updating means, 1
Reference numeral 07 is a code tree holding means, 108 is a context discrimination means, 109
Is an escape code output means, 110 is a context changing means,
111 is a code output means, 112 is a history registration means, 113
Is a code registration means, and 116 is a control means.

The prefix data holding means 100 holds the context consisting of n pieces of input data input up to immediately before the input data, and the history holding means 101 holds the combination of the input data and the context. The code tree holding unit 107 holds an independent code tree for each context in which an escape code defined as data indicating data unregistered is registered in advance.

The code tree determining means 103 determines the code tree of the data from the context and the input data, and the context determining means 108 registers the data in the code tree determined by the code tree determining means 103. It is to determine whether or not there is. Further, the escape code output means 109
When data is not registered in the code tree, the escape code is output according to the branch from the node as the branch point located between the root that means the vertex of the code tree and the leaf as the data storage point of the escape code. Is.

Further, the history registration means 112 registers the combination of the data and the context in the history holding means 101 when the data is not registered in the code tree, and the code registration means 113 stores the data in the code tree. When the data is not registered, the data is newly registered in the code tree, and the context changing unit 110 shortens the context length n when the data is not registered in the code tree.

Further, the code output means 111 outputs the code of the data according to the branch from the node located in the middle of the root of the code tree to the leaf of the data when the data is registered in the code tree. The code length changing unit 105 recombines the encoded leaf and another leaf or node. Further, the prefix data updating means 106 registers the data in the prefix data holding means 100, and when the escape code is encoded, the control means 116 repeats the process until the data is encoded. Yes (above, claim 11).

Further, the configuration of an apparatus for carrying out the data compression method of the present invention according to claim 4 is shown in the principle block diagram of FIG. The data compression apparatus shown in FIG. 4 also encodes and compresses the input data according to the history of past appearances. Here, 100 is prefix data holding means, 101 is history holding means, 103 is code tree determining means,
Reference numeral 105 is a code length changing means, 106 is a prefix data updating means, 107 is a code tree holding means, 108 is a context discriminating means,
109 and 111 are escape code output means, 11
Reference numeral 0 is context changing means, 114 is history registration means, 115 is code registration means, and 117 is control means.

The front data holding means 100 holds the context consisting of n pieces of input data input up to immediately before the input data, and the history holding means 101 holds the combination of the input data and the context. The code tree holding means 107 holds an independent code tree for each context in which an escape code defined as data indicating data unregistered is registered in advance.

The code tree determining means 103 determines the code tree of the data from the context and the input data. The context determining means 108 registers the data in the code tree determined by the code tree determining means 103. It is to determine whether or not there is. Further, the escape code output means 109
When data is not registered in the code tree, the escape code is output according to the branch from the node that is located on the way from the root that means the vertex of the code tree to the leaf that is the data storage point of the escape code. Is.

The context changing means 110 shortens the length n of the context when no data is registered in the code tree. The escape code output means 111 registers data in the code tree. In this case, the code of the data is output according to the branch from the node located on the way from the root of the code tree to the leaf of the data. Further, the history registration means 114 is for registering a combination of data and context in the history holding means 101, the code registration means 115 is for newly registering data in the code tree, and the code length changing means 105 is for , The encoded leaf and another leaf or node are recombined, and the prefix data updating means 106 registers the data in the prefix data holding means 100.

Further, when the escape code is encoded even once at the time of encoding the data, the control means 117 causes the history registration means 114 to store the combination of the context and the data immediately before the data encoding in the history holding means 101. The data is newly registered in the code tree having the escape code that is registered and encoded immediately before the data is encoded (the above is the twelfth aspect).

On the other hand, the configuration of an apparatus for carrying out the data restoration method of the present invention according to claim 5 is shown in the principle block diagram of FIG. The data restoration device shown in FIG. 5 decodes a code that has been encoded according to a history that has appeared in the past. Here, 200 is a front data holding means, 201
Is a history holding unit, 202 is a code tree holding unit, 203 is a code tree determining unit, 204 is a decoding unit, 205 is a code length changing unit, and 206 is a front data updating unit.

The prefix data holding means 200 holds n pieces of data decoded in the past, and the history holding means 201 holds a combination of the decoded data and the context, and holds a code tree. The means 202 holds an independent code tree for each context. Further, the code tree determining means 203 determines a code tree for decoding data from the context held in the prefix data holding means 200, and the decoding means 204 uses the code tree determining means 203 according to the code. The data stored in the leaf as the data storage point reached by scanning the node as the branch point from the root meaning the apex of the selected code tree is output.

Further, the code length changing means 205 recombines the decoded leaf with another leaf or node, and the prefix data updating means 206 registers the decoded data in the prefix data holding means 200. (The above is claim 13). In addition, the configuration of an apparatus for carrying out the data restoration method of the present invention according to claim 6 is shown in FIG.
The principle block diagram of is shown in FIG. The data restoration device shown in FIG. 6 also decodes a code that has been encoded according to a history that has appeared in the past.

Here, 200 is a front data holding means, 2
01 is history holding means, 203 is code tree determining means, and 204
Is a decoding unit, 205 is a code length changing unit, 206 is a prefix data updating unit, 207 is a code tree holding unit, 208 is a context changing unit, and 213 is a control unit. The prefix data holding unit 200 holds n pieces of data decoded in the past, the history holding unit 201 holds a combination of the decoded data and the context, and the code tree holding unit 207. , Holds a code tree in which escape codes defined as data indicating unregistered data are registered in advance.

The code tree determining means 203 determines a code tree for decoding data from the context held in the prefix data holding means 200, and the decoding means 2
Reference numeral 04 is for outputting the data stored in the leaf as the data storage point reached by scanning the node as the branch point from the root that means the vertex of the code tree selected by the code tree determination means 203 according to the code. is there.

Further, the code length changing means 205 recombines the decoded leaf with another leaf or node, and the context changing means 208-rejects the data when the output data is an escape code and sets the context. The prefix data updating means 206 registers the decoded data in the prefix data holding means 200.

When the escape code is decoded, the control means 213 resets the context by the context changing means 208, and repeats the process until a code other than the escape code is decoded (above, claim 14). Further, the configuration of an apparatus for carrying out the data restoration method of the present invention according to claim 7 is shown in the principle block diagram of FIG. 7. The data restoration device shown in FIG. 7 also decodes a code that has been encoded according to a history that has appeared in the past.

Here, 200 is a front data holding means, 2
01 is history holding means, 203 is code tree determining means, and 204
Is decoding means, 205 is code length changing means, 206 is prefix data updating means, 207 is code tree holding means, 208 is context changing means, 209 is history registration means, 210 is code registration means, and 213 is control means. . Prefix data holding means 20
0 holds n pieces of data decoded in the past, history holding means 201 holds a combination of decoded data and context, and code tree holding means 20
Reference numeral 7 holds a code tree in which escape codes are registered in advance.

The code tree determining means 203 determines the code tree for decoding the data from the context held in the prefix data holding means 200, and the decoding means 2
Reference numeral 04 is for outputting the data stored in the leaf as the data storage point reached by scanning the node as the branch point from the root that means the vertex of the code tree selected by the code tree determination means 203 according to the code. is there.

Further, the code length changing means 205 recombines the decoded leaf with another leaf or node, and the context changing means 208 discards the above data when the output data is the above escape code. It shortens the context. Further, the prefix data updating unit 206 stores the decoded data in the prefix data holding unit 200.
The history registration means 209 registers in the history holding means 201 all the contexts when the escape code is decoded in the data decoding process and the decoded data.

Further, the code registration means 210 registers the code of the data in all code trees corresponding to the context when the escape code is decoded in the data decoding process.
When the escape code is decoded, the control means 213 resets the context by the context changing means 208, and repeats the process until a code other than the escape code is decoded (above, claim 15).

The configuration of an apparatus for carrying out the data restoration method of the present invention according to claim 8 is shown in the principle block diagram of FIG. The data restoration device shown in FIG. 8 also decodes a code that has been encoded according to a history that has appeared in the past. Here, 200 is a front data holding means, 201
Is history holding means, 203 is code tree determining means, 204 is decoding means, 205 is code length changing means, 206 is prefix data updating means, 207 is code tree holding means, 208 is context changing means, and 212 is code registering means. Reference numeral 213 is a control means.

The prefix data holding means 200 holds n pieces of data decoded in the past, and the history holding means 201 holds a combination of the decoded data and the context, and holds a code tree. The means 207 holds a code tree in which an escape code defined as data indicating unregistered data is registered in advance. Also,
The code tree determining means 203 determines a code tree for decoding data from the context held in the prefix data holding means 200, and the decoding means 204 is selected by the code tree determining means 203 according to the code. The data stored in the leaf as the data storage point reached by scanning the node as the branch point from the root meaning the apex of the code tree is output.

Further, the code length changing means 205 recombines the decoded leaf with another leaf or node, and the context changing means 208 rejects the data and outputs the context when the output data is an escape code. The prefix data updating unit 206 registers the decrypted data in the prefix data holding unit 200.

The history registration means 211 registers the context when the escape code was last decoded in the data decoding process and the decoded data in the history holding means 201, and the code registration means 212 stores the data. The code of the data is registered in the code tree corresponding to the context when the escape code is finally decoded in the decoding process of 1.
When the escape code is decoded, 13 resets the context by the context changing means 208, and repeats the process until a code other than the escape code is decoded.
6).

Here, the above-described data compression method of the present invention has the following operation (claim 1). (1) Through the context collection process, it is possible to retain a combination of input data and a context consisting of n continuous data. (2) By the code tree holding process, it is possible to hold an independent code tree for each context. (3) When the data corresponding to the context of the context collection process appears by the code output process, as a branch point from the root that means the vertex of the code tree to the leaf as the point where the data on the code tree is stored. It is possible to output a code defined as unique data according to the branch of the node. (4) By the code length changing process, the leaf of data and the leaf or node of other data can be recombined after the process in the code output process.

Furthermore, the data compression method of the present invention has the following operation (claim 2). (1) Through the context collection process, it is possible to retain a combination of input data and a context consisting of n continuous data. (2) By the code tree holding process, it is possible to hold an independent code tree for each context. (3) When the data corresponding to the context of the context collection process appears by the code output process, as a branch point from the root that means the vertex of the code tree to the leaf as the point where the data on the code tree is stored. It is possible to output a code defined as unique data according to the branch of the node. (4) By the code length changing process, the leaf of data and the leaf or node of other data can be recombined after the process in the code output process. (5) By the context discrimination process, it is possible to discriminate whether or not the combination of the input data and the context is held in the context collection process. (6) By the escape code holding process, it is possible to hold a leaf in which an escape code defined in advance as data indicating that data has not been registered is registered in the code tree. (7) When the combination of the input data and the context is a combination that is not held in the history of the context collection process (1), an escape code is output and until the combination held in the context collection process is obtained, The process of shortening the context of the data can be repeated.

Further, the data compression method of the present invention has the following operation (claim 3). (1) Through the context collection process, it is possible to retain a combination of input data and a context consisting of n continuous data. (2) By the code tree holding process, it is possible to hold an independent code tree for each context. (3) When the data corresponding to the context of the context collection process appears by the code output process, as a branch point from the root that means the vertex of the code tree to the leaf as the point where the data on the code tree is stored. It is possible to output a code defined as unique data according to the branch of the node. (4) By the code length changing process, the leaf of data and the leaf or node of other data can be recombined after the process in the code output process. (5) By the context discrimination process, it is possible to discriminate whether or not the combination of the input data and the context is held in the context collection process. (6) By the escape code holding process, it is possible to hold a leaf in which an escape code defined in advance as data indicating that data has not been registered is registered in the code tree. (7) When the combination of the input data and the context is not held in the history of the context collection process by the new context registration process, the combination of the input data and the context is newly registered in the context collection process. be able to. (8) When the combination of the input data and the context is a combination not held in the history of the context collection process by the code tree new registration process, this data can be newly registered in the code tree corresponding to the context. it can. (9) When the combination of the input data and the context is a combination not held in the history of the context collection process, the code of the escape code is output and at the same time, the combination of the input data and the context is registered in the history. ,
The process of registering the data in the code tree corresponding to the context and shortening the context of the data can be repeated until the combination held in the context collection process is obtained.

Furthermore, the data compression method of the present invention has the following operation (claim 4). (1) Through the context collection process, it is possible to retain a combination of input data and a context consisting of n continuous data. (2) By the code tree holding process, it is possible to hold an independent code tree for each context. (3) When the data corresponding to the context of the context collection process appears by the code output process, as a branch point from the root that means the vertex of the code tree to the leaf as the point where the data on the code tree is stored. It is possible to output a code defined as unique data according to the branch of the node. (4) By the code length changing process, the leaf of data and the leaf or node of other data can be recombined after the process in the code output process. (5) By the context discrimination process, it is possible to discriminate whether or not the combination of the input data and the context is held in the context collection process. (6) By the escape code holding process, it is possible to hold a leaf in which an escape code defined in advance as data indicating that data has not been registered is registered in the code tree. (7) When the combination of the input data and the context is not held in the history of the context collection process by the new context registration process, the combination of the input data and the context is newly registered in the context collection process. be able to. (8) By the code tree new registration process, when the combination of the input data and the context is a combination not held in the history of the context collection process, the data can be newly registered in the code tree corresponding to the context. . (9) In the context new registration process of (7) and the code tree new registration process of (8), only the combination of the context and the data immediately before determined to be in the history can be registered. The data restoration method of the present invention has the following effects (claim 5). (1) The history of the combination of the decoded data and the context can be retained by the context collection process. (2) By the code tree holding process, each independent code tree can be held according to the context. (3) In the code tree determination process, the code tree of data can be determined from the context of the data decoded up to immediately before. (4) By the decoding process, data can be decoded from the code of the code tree and the code of the data determined in the code tree determination process. (5) By the code length changing process, after decoding in the decoding process,
With the same means as the encoding side, it is possible to rearrange between the leaves as the data storage points on the code tree or between the leaves and the nodes as the branch points of the code tree.

Furthermore, the data restoration method of the present invention has the following operation (claim 6). (1) The history of the combination of the decoded data and the context can be retained by the context collection process. (2) By the code tree holding process, each independent code tree can be held according to the context. (3) In the code tree determination process, the code tree of data can be determined from the context of the data decoded up to immediately before. (4) By the decoding process, data can be decoded from the code of the code tree and the code of the data determined in the code tree determination process. (5) By the code length changing process, after decoding in the decoding process,
With the same means as the encoding side, it is possible to rearrange between the leaves as the data storage points on the code tree or between the leaves and the nodes as the branch points of the code tree. (6) In the code tree, an escape code defined as data indicating data unregistered is registered in advance for each code tree according to each context, and when the escape code is decoded at the time of decoding, other than the escape code is decoded. Up to this, the process of shortening the length of the context can be repeated.

Further, the data restoration method of the present invention has the following actions (claim 7). (1) The history of the combination of the decoded data and the context can be retained by the context collection process. (2) By the code tree holding process, each independent code tree can be held according to the context. (3) In the code tree determination process, the code tree of data can be determined from the context of the data decoded up to immediately before. (4) By the decoding process, data can be decoded from the code of the code tree and the code of the data determined in the code tree determination process. (5) By the code length changing process, after decoding in the decoding process,
With the same means as the encoding side, it is possible to rearrange between the leaves as the data storage points on the code tree or between the leaves and the nodes as the branch points of the code tree. (6) By the new context registration process, data can be newly registered in the context collection process. (7) The decoded data can be newly registered in the code tree according to the context by the code tree new registration process. (8) When the escape code defined as the data indicating the unregistered data is decoded, By executing the context new registration process of (6) and the code tree new registration process of (7),
The process of shortening the length of the context can be repeated until anything other than the escape code is decoded.

Furthermore, the data restoration method of the present invention has the following actions (claim 8). (1) The history of the combination of the decoded data and the context can be retained by the context collection process. (2) By the code tree holding process, each independent code tree can be held according to the context. (3) In the code tree determination process, the code tree of data can be determined from the context of the data decoded up to immediately before. (4) By the decoding process, data can be decoded from the code of the code tree and the code of the data determined in the code tree determination process. (5) By the code length changing process, after decoding in the decoding process,
With the same means as the encoding side, it is possible to rearrange between the leaves as the data storage points on the code tree or between the leaves and the nodes as the branch points of the code tree. (6) By the new context registration process, data can be newly registered in the context collection process. (7) In the code tree new registration process, the decoded data can be newly registered in the code tree according to the context. (8) In the process until the escape code other than the one defined as the data indicating that the data is not registered is decrypted, when even one escape code is decrypted, the context new registration is performed only in the context immediately before the decryption other than the escape code. Each new registration process in the process and the code tree new registration process can be performed.

Further, it has the configuration described with reference to FIG.
In the apparatus for carrying out the data compression method of the present invention according to claim 1, that is, in the data compression apparatus which encodes and compresses the input data according to the history that has appeared in the past, the pre-data holding means 100 inputs The history consisting of n pieces of input data inputted up to immediately before the data is held, the history holding means 101 holds a combination of the input data and the context, and the code tree holding means 102 holds an independent code for each context. Hold the tree.

Then, the code tree determining means 103 determines the code tree of the data from the input data until immediately before being held in the prefix data holding means 100, and the code output means 104.
Outputs unique data according to a branch from a node as a branch point located midway along a leaf in which data is stored from a root that means a vertex of the code tree selected by the code tree determining unit 103.

Further, the code length changing means 105 rearranges the coded leaf and another leaf or node,
The pre-data updating means 106 can register the data in the pre-data holding means 100 (claim 9). Next, an apparatus for implementing the data compression method of the present invention having the configuration described with reference to FIG. 2, that is, input data is encoded and compressed according to the history that has appeared in the past. In the data compression apparatus, the pre-data holding means 100 holds the context composed of n pieces of input data input up to immediately before the input data, and the history holding means 10
1 holds a combination of input data and a context, and the code tree holding means 107 holds an independent code tree for each context in which an escape code defined as data indicating data unregistered is registered in advance.

Then, the code tree determining means 103 determines the code tree of the data from the context and the input data, and the context determining means 108 determines whether or not the data is registered in the code tree determined by the code tree determining means 103. The escape code output means 109 determines that a branch point is located on the way from the root that means the top of the code tree to the leaf that is the data storage point of the escape code when no data is registered in the code tree. Output an escape code according to the branch from the node.

Further, the context changing means 110 shortens the length n of the context when no data is registered in the code tree, and the code output means 111 when the data is registered in the code tree. The code of the data is output according to the branch from the node located on the way from the root to the leaf of the data, and the code length changing unit 105 recombines the coded leaf with another leaf or node.

Then, the prefix data updating means 106 registers the data in the prefix data holding means 100, and the control means 1
When 16 encodes the escape code, the process is repeated until the data is encoded.
0). Next, a device for implementing the data compression method of the present invention having the configuration described with reference to FIG. 3, that is, data for encoding and compressing input data according to a history that has appeared in the past. In the compression device, the prefix data holding means 100 holds the context consisting of n pieces of input data input immediately before the input data, and the history holding means 101 holds the combination of the input data and the context. The code tree holding unit 107 holds an independent code tree for each context in which an escape code defined as data indicating unregistered data is registered in advance.

Then, the code tree determining means 103 determines the code tree of the data from the context and the input data, and the context determining means 108 determines whether or not the data is registered in the code tree determined by the code tree determining means 103. When the data is not registered in the code tree, the escape output means 109 is a node as a branch point located between the root meaning the vertex of the code tree and the leaf as the data storage point of the escape code. The escape code is output according to the branch from.

Further, the history registration means 112 registers the combination of the data and the context in the history holding means 101 when the data is not registered in the code tree, and the code registration means 11
3 newly registers the data in the code tree when the data is not registered in the code tree, and the context changing unit 110 shortens the context length n when the data is not registered in the code tree, When the data is registered in the code tree, the code output means 111 outputs the code of the data according to the branch from the node located on the way from the root of the code tree to the leaf of the data.

Then, the code length changing means 105 rearranges the coded leaf and another leaf or node,
The prefix data updating means 106 registers the data in the prefix data holding means 100, and when the control means 116 codes the escape code, the processing is repeated until the data is coded (the above is claim 11). . Next, a device for implementing the data compression method of the present invention having the configuration described with reference to FIG. 4, that is, input data is encoded and compressed according to the history that has appeared in the past. In the data compression device, the front data holding means 100 is
The context consisting of n pieces of input data inputted up to immediately before the input data is held, the history holding means 101 holds the combination of the input data and the context, and the code tree holding means 10
Reference numeral 7 holds an independent code tree for each context in which an escape code defined as data indicating unregistered data is registered in advance.

Then, the code tree determining means 103 determines the code tree of the data from the context and the input data, and the context determining means 108 determines whether or not the data is registered in the code tree determined by the code tree determining means 103. And a node as a branch point located on the way from the root that means the top of the code tree to the leaf as the data storage point of the escape code when no data is registered in the escape code output means 109 and the code tree. The escape code is output according to the branch from.

Further, the context changing means 110 shortens the length n of the context when no data is registered in the code tree, and the escape code output means 111 outputs the code when the data is registered in the code tree. The code of the data is output according to the branch from the node located on the way from the root of the tree to the leaf of the data. And history registration means 11
4 registers a combination of data and context in the history holding unit 101, the code registration unit 115 newly registers the data in the code tree, and the code length changing unit 105 codes the encoded leaf and another leaf or node. And the prefix data updating means 106 stores the data in the prefix data holding means 10
Register to 0.

Furthermore, when the control means 116 encodes the escape code even once when encoding the data,
The history registration means 114 registers the combination of the context and the data immediately before the data encoding in the history holding means 101, and the code registration means 115 stores the data in the code tree having the escape code encoded immediately before the data encoding. Is newly registered (above, claim 12).

On the other hand, having the configuration described with reference to FIG.
In the apparatus for carrying out the data restoration method of the present invention according to claim 5, that is, in the data restoration apparatus which decodes the code coded according to the history that has appeared in the past, the front data holding means 200 is Holds the decoded n pieces of data, the history holding means 201 holds the combination of the decoded data and the context, and the code tree holding means 202 holds the independent code tree for each context.

Then, the code tree determining means 203 determines the code tree for decoding the data from the context held in the prefix data holding means 200, and the decoding means 204 causes the code tree determining means 203 to follow the code. Data stored in a leaf as a data storage point reached by scanning a node as a branch point from the root meaning the vertex of the selected code tree is output.

Further, the code length changing means 205 rearranges the decoded leaf and another leaf or node, and the prefix data updating means 206 registers the decoded data in the prefix data holding means 200 (the above is the case). Item 13). Next, a device for implementing the data restoration method of the present invention having the configuration described with reference to FIG. 6, that is, data for decoding a code coded according to a history that has appeared in the past. In the restoration device, the front data holding means 2
00 holds n pieces of data decoded in the past, history holding means 201 holds a combination of decoded data and context, and code tree holding means 207 is defined as data indicating data unregistered. Holds a code tree in which escape codes are registered in advance.

Then, the code tree determining means 203 determines the code tree for decoding the data from the context held in the prefix data holding means 200, and the decoding means 204 causes the code tree determining means 203 to follow the code. The node stored as a branch point is scanned from the root representing the apex of the selected code tree, and the data stored in the leaf as the data storage point reached is output.

Further, the code length changing means 205 rearranges the decoded leaf and another leaf or node, and the context changing means 208 rejects the data when the output data is an escape code to shorten the context, The prefix data updating unit 206 registers the decrypted data in the prefix data holding unit 200. Then, when the control means 213 decodes the escape code, the context changing means 208 resets the context, and repeats the processing until the code other than the escape code is decoded (the above is claim 14).

Next, having the configuration described with reference to FIG.
In the device for carrying out the data restoration method of the present invention according to claim 7, that is, in the data restoration device for decoding the code encoded according to the history that has appeared in the past, the front data holding means 200 is Holds the decoded n pieces of data, the history holding means 201 holds the combination of the decoded data and the context, and the code tree holding means 207 holds the code tree in which the escape code is registered in advance.

Then, the code tree determining means 203 determines a code tree for decoding the data from the context held in the prefix data holding means 200, and the decoding means 204 causes the code tree determining means 203 to follow the code. Data stored in a leaf as a data storage point reached by scanning a node as a branch point from the root that means the vertex of the selected code tree is output.

Further, the code length changing means 205 rearranges the decoded leaf and another leaf or node, and the context changing means 208 rejects the data and shortens the context when the output data is an escape code. The prefix data updating unit 206 registers the decrypted data in the prefix data holding unit 200. Then, the history registration means 209
However, the history holding unit 20 stores all the contexts when the escape code is decoded in the data decoding process and the decoded data.
1, the code registration unit 210 registers the code of the data in all the code trees corresponding to the context when the escape code is decoded in the data decoding process, and the control unit 213
When the escape code is decrypted, the context is reset by the context changing means 208, and the process is repeated until anything other than the escape code is decrypted (above, claim 15).

Next, having the configuration described with reference to FIG.
In the device for carrying out the data restoration method of the present invention according to claim 8, that is, in the data restoration device for decoding the code encoded according to the history that has appeared in the past, the front data holding means 200 Holds n pieces of decoded data, the history holding means 201 holds the combination of the decoded data and the context, and the code tree holding means 207 stores an escape code defined as data indicating data unregistered in advance. Holds the registered code tree.

Then, the code tree determining means 203 determines a code tree for decoding data from the context held in the prefix data holding means 200, and the decoding means 204 causes the code tree determining means 203 to follow the code. Data stored in a leaf as a data storage point reached by scanning a node as a branch point from the root that means the vertex of the selected code tree is output.

Further, the code length changing means 205 rearranges the decoded leaf and another leaf or node, and the context changing means 208 rejects the data when the output data is an escape code and shortens the context. Then, the prefix data updating unit 206 registers the decrypted data in the prefix data holding unit 200, and the history registration unit 211.
However, the history holding means 201 indicates the context when the escape code was last decoded in the data decoding process and the decoded data.
The code registration means 212 registers the code of the data in the code tree corresponding to the context when the escape code was finally decoded in the data decoding process.

Further, when the control means 213 decodes the escape code, the context changing means 208 resets the context, and repeats the process until a code other than the escape code is decoded (the above-mentioned claim 16).

[0094]

DESCRIPTION OF THE PREFERRED EMBODIMENTS (a) Description of Technology 1 Related to the Present Invention FIG. 15 is a block diagram showing a configuration example of a data compression apparatus and a data decompression apparatus as Technology 1 related to the present invention.
In FIG. 15, reference numeral 1 is a data compression device that encodes and compresses an input character according to the history of past appearances, and 2 is a data decompression device that decompresses the character encoded by the data compression device 1. is there.

Further, the data compressing apparatus 1 corresponds to the context collecting process 11 for collecting the context of the input character string data to create the context tree and the context (context tree) obtained in the context collecting process 11. Then, the splay coding process 12 for creating / updating the code tree corresponding to the splay code while performing the splay coding according to the character string of the input data is performed.

On the other hand, the data decompression device 2 spray-codes the code tree in which the spray code is associated with the context of the decompressed data encoded by the data compression device 1 according to the character string of the decompressed data. Meanwhile, a splay encoding process 21 for creating / updating and a context collecting process 22 for collecting the context (creating a context tree) about the character string as the restored data are performed.

In the following description, the data compression device 1 will be described as the encoding side and the data decompression device 2 will be described as the decompression side. (1) Description of Encoding Side FIGS. 16 (a) and 16 (b) are diagrams showing an example of the context tree created in the context collection process 11. In FIG. 16 (a), the context tree uses the hash method. 16B is a diagram showing an example in which a character string is stored in a memory in a storage structure of a list structure so that it can be searched in a short time. FIG. 16B shows a tree structure dictionary (list) storing the character string in a parent-child relationship. It is the figure shown.

Here, the address in FIG. 16A is 16
In the example of FIG. 16A, the maximum size of the context tree is 4K nodes (4KW). in this way,
If you register all the characters in advance, the first connection to the route
Since the position of the sibling node of the hierarchy is known in advance, it is not necessary to operate the list at the time of searching, and direct access is possible.

On the other hand, in the second and subsequent layers, the addresses of the child node and the right sibling node are stored in advance, and the list is manipulated and accessed until the stored characters are matched in the list format while matching. Further, when the context tree is initialized, addresses up to address 100 are set. At this time, an end of file (EOF) code is registered in address 100 of the first layer, and the memory at addresses 101 and later is stored. Used for new registration.

Next, FIG. 17 is a diagram showing an example of a code tree created in the above-mentioned spray coding process 12. The code tree is basically set at the time of initialization as shown in FIG. 17, similarly to the conventional Splay-Tree coding. Then, corresponding to FIG. 16B, the maximum size is 4K nodes (4K
Up to W), the nodes of the code tree are classified into two: internal nodes (with child nodes) and external nodes (leaf, the end of each code without child nodes).

Further, in the splay coding, in order to access the code tree, Up and Left as shown in FIG. 18 are used.
Three arrays of t and Right are used. Where U
The p array stores the address from each node to the parent node, the Left array stores the address from each node to the left child node, and the Right array stores the address from each node to the right child node. To do.

In the Up array, the internal nodes are first 4
Store in KW (address (hexadecimal) 000-FFF),
The remaining 4KW of external node (address (hexadecimal) 1000)
~ 1FFF). By doing so, the code for each node of the context tree can be calculated as follows: address of code tree = context tree node pointer (number) + 4K,
You can associate with.

The bit width of each array is 1 for Up array.
3 bits, Left, Right array becomes 12 bits. Next, the basic operation for updating the tree of the code tree having the above configuration will be described with reference to FIGS. 19 (a) and 19 (b). FIG. 19A is a diagram showing a basic operation for updating the splay code. As shown in FIG.
When is accessed, the node A and the branch with the node A two steps above are replaced with the node C of the branch in the opposite direction.

Then, for the codes of the characters A to E,
When the character C is accessed, for example, FIG.
As shown in, the code tree is adapted to be recombined. That is, the code tree is updated by repeating the above-described basic operation twice. In this case, the second basic operation updates the length of the parent node of the node updated first time.

As a result, even if the depth of the code tree becomes deep, by repeating this basic operation, the length from the root to the accessed node C (code 0110) is reduced to 1/2 (code 10). Therefore, the code tree from the root to the accessed node can be dynamically recombined to adapt the code table to the input data. In other words, the code update of the splay code is the Move-
It's like doing a To-Front operation on a Binary-Tree.

Further, the process of creating the context tree in the context collecting process 11 and updating / creating the code tree in the spray coding process 12 as described above will be described in detail with reference to process steps E1 to E31 in the flowchart of FIG. I will describe. The input character is K (K is an arbitrary character), and the character input immediately before the character K is input is P (P is an arbitrary character).

First, the context tree, the code tree, and the preceding character P are initialized (step E1). Then, it is checked whether all the characters that have already been input have been input and encoded (step E2). If there are any input characters, the input of the character K and the setting of the length L of the character string to 0 are performed. Perform (step E3). Further, it is checked whether or not there is a child node under the preceding character P in the context tree (step E5), and if there is no child node under the preceding character P, the 0th order code of the input character K is output (step E6). , The input character K is registered as a child node under the character P immediately before the context tree (step E7).

On the other hand, in the code tree, a node for registering the character K and the escape code is created under the immediately preceding character P and the character K is registered (step E8). An example of the algorithm for creating this node is shown in FIGS.
Shown in. Further, the previous character is changed to the input character K (step E16), and the length L'of the previous character string is the maximum character string length L.
It is checked whether it is equal to max (step E24).

If the immediately preceding character string length L'is not equal to the maximum character string length Lmax, it is checked whether the immediately preceding character string is encoded by the primary code and output (step E).
25). Here, if the immediately preceding character string is not encoded by the primary code, the target character string length L is moved to the immediately preceding character string length L '(step E28), and it is checked whether or not the character K is already encoded (step E9). ), If encoded, the process from step E2 described above is repeated (YES route of step E9), and if not encoded, the process from step E3 described above is repeated (NO route of step E9).

By the way, when the character registered in the child node matches the input character K in step E10, the length L of the character string is increased by 1 (step E1).
7), this character string length L is the preset maximum code length Lm
It is checked whether it is equal to ax (step E18). If they are not equal, it is checked whether all the characters of the input data have been encoded (step E19), and if there is a character that has not been encoded yet, the input character so far is moved to the immediately preceding character P (step E20), Further, one character K is input (step E21), the process returns to step E10, and it is again checked whether the character registered in the child node matches the character K.

If they do not match, it is checked whether or not the length L of the character string is 0 (step E11), YES,
That is, if there is a child node under the preceding character P but the corresponding character K is not yet attached, the escape code under the preceding character P is output, and then the 0th order code of the character K is output (step E12). ). Further, the character K is registered as a sibling node of the child node under the character P immediately before the context tree (step E13), and the escape code under the character P immediately before the code tree is divided into the escape code and the code of the character K. Then, the code of the character K is added (step E14), and the escape code of the code tree and the code length of the 0th-order code K are updated as the spray code (step E15).

As described above, the decompressed character string of the encoded character string can be registered until the predetermined maximum character string length is reached. Then, step E described above
After step 16 and step E24, it is checked again whether or not the immediately preceding character string is output by the primary code (step E25). That is, if the preceding character string is encoded by the primary code and is output, the extension character string in which the leading character of the encoded character (string) is added to the preceding character string is registered in the context tree (step E26).
The code of the encoded extended character string is registered in the code tree (step E27), and the processing from step E28 described above is repeated.

This registration is performed by branching the code of the preceding character and adding the primary code of the character string to which the character K is added. The branch of the character string is regarded as the code of the character string obtained by encoding the escape code, and is branched to create the original character string and the code of the character string to which the character K is added. In this way
As the dictionary registration character string, the character just before the coded character is registered, and the character string following the character just before is coded.

Further, in the above step E18,
When the character string length L is equal to the preset maximum code length Lmax, or in step E11, the character string length L
Is not equal to 0, the primary code corresponding to the reference number of the character (string) of the context tree is output (step E22), and the code length of the primary code output by the code tree is updated as the spray code (step E22). E23) and then the above step E24
Process from.

In the closed loop processing described above, when the combination of the immediately preceding character P and the input character K is already registered in the context tree, the number of registered characters (character string length) is expanded and the character string is incremented. The process for performing registration is shown. If all the input characters have been encoded in the above step E2, it is checked whether there is a child node below the preceding character P of the context tree (step E29). Output the escape code under the letter P (from NO route of step E29 to step E30), and
The 0th-order code of EOF representing d Of File is output (step E31), and the process ends (from NO route of step E29 to step E31).

If there is no child node, 0 of EOF
The next code is output and the process ends. By performing the above processing, in the data compression method that encodes and compresses the character string as the input data according to the history that has appeared in the past, the character string of the input data is collected in the dictionary and registered with a number. In addition, the splay code is encoded and updated corresponding to each character string.

Here, if the input character K is limited to one of the alphabets a, b, and c, the character "abc abc
Taking the case where "ab b" is input as an example, the update / creation of the context tree and the code tree will be described in more detail with reference to FIGS. First, as shown in FIGS. 21 (a) and 21 (b), the characters a, b, and c and the terminal code EOF that is output after all input data are encoded in the context tree and the code tree are
It is registered as a ₁ , b ₂ , c ₃ and EOF ₄ by adding numbers.

By initializing the context tree in this way, any of the first registered characters a, b, and c becomes the preceding character, and when there is no context following the preceding character, an independent single reference number is also set. I will also serve. In the following description, the letter c
Let be the first previous character. On the other hand, FIG. 21 (b)
As shown in, when the node goes down from the root to the lower left, the code tree has a code "0" for the registered character.
Is a binary tree that assigns the code “1” to the registered character when allocating a node and moving the node down to the lower right, so that when encoding, the path traced from the node with the reference number of the corresponding character to the root is stacked. Then, by reversing the path and assigning the codes "0" and "1" depending on whether it is lower left or lower right, the code word corresponding to the reference number of the character can be obtained.

That is, the 0th-order codes of the three characters "a ₁ , b ₂ , c ₃ " are "00 0110 11", respectively. Then, the above-described FIG. 21 (a), the from the state shown in (b), when the first character string "abc" is entered, so assuming a previously registered "c" (c ₃₎ the immediately preceding character As shown in FIG. 22A, a new node is created under the context tree “c” (c ₃ ) and the first character “a ₅ ” in the character string “abc” is not registered. And an escape code (ESC ₆ ) that represents

On the other hand, in the code tree, as shown in FIG. 22 (b), since "a" has already been registered, the node in which "a" is registered and the upper character of "c" which is the immediately preceding character. Replace the node and set this "c" as a new route (primary coding), and then "a" and escape code (ESC).
To register. Furthermore, in the character string "abc", the next b,
By performing the above-described processing for c as well, the context tree and the code tree when b is input are shown in FIG.
As shown in FIGS. 24A and 24B, the context tree and the code tree when c is input are as shown in FIGS.

This process corresponds to the NO route of step E5, step E in the process steps described above with reference to FIG.
This corresponds to the closed loop processing that goes through the YES route of 24 and the NO route of step E25. That is,
In the context tree, when a child node does not exist under the previous character, a node for registering the input character and the escape code is newly created under the previous character and registered.

On the other hand, in the code tree, when the same character as the character registered in the past is input again, the node of the character registered in the past is registered as the character immediately before the input character. By replacing the node with the upper node of the node and moving the node of the character registered in the past to the upper node, the distance from the root is halved to shorten the code length.

[0123] In addition, followed and by the character string "abc" is input, the lower of the "c _9" in the context tree as just before character last of the "c" of the first input string "abc", character tries to register only one character "a" of the string "abc", as shown in FIG. 24 (a), the context tree, "a _5" is registered already lower "c _3" As shown in FIG.
(A), the "b and 1 letter extended character to be registered from one character" a "2 to the character" ab "to the lower" a ₅ "
₁₁ ”is registered.

At this time, in the code tree, as shown in FIG. 25 (b), the node of the escape code (ESC) registered with "a" under "c" is branched to create a new node. Then, decompress one character in the context tree and register "a
b ”is registered. Then, in the character string "abc",
Even when "b" is registered in the context tree, FIG.
As shown in FIG. 26A, since “b ₇ ” is already registered under “a ₁ ”, as shown in FIG. 26A, the characters to be registered are from 1 character “b” to 2 characters “ and one character extension to bc "registers" c ₁₂ "in the lower of the" b ₇ ".

At this time, in the code tree, as shown in FIG. 26 (b), the node of the escape code (ESC) registered with "b" under "a" is branched to create a new node. Then, "b" registered by decompressing one character in the context tree
"c" is registered. Then, even when the last "c" of the next character string "abc" is registered, when the above process is performed, the context tree and the code tree are respectively shown in FIG.
The state shown in (b) is reached (up to this point, "abc ab
c "is already entered).

When the character string "ab" is further input, the context tree first attempts to register one character "a" under the immediately preceding character "c".
_Since "a ₅ " is already registered under ₉ ", the number of registered characters is expanded by one character to be" ab ", and" b "is registered under" a ₅ ". However, as shown in FIG. 27A, since “b ₁₁ ” is already registered under “a ₅ ”, as shown in FIG. 28A, the number of registered characters is further expanded by one character. and as "abb", "b _11"
"B" is registered in the lower order of.

At this time, in the code tree, as shown in FIG. 28B, the node in which "ab" is registered is branched to register "abb". This process corresponds to the closed loop process that goes through the YES route of step E5, the YES route of step E10, and the YES route of step E25 of the process steps described above with reference to FIG.

That is, when a character string is input, the combination of the immediately preceding character and one character in the input character string is
If already registered in the context tree, the number of characters to register is 1
Register only one character that has not been registered after decompressing. At this time, in the code tree, the node of the escape code (ESC) registered together with the immediately preceding character is branched to create a new node, and this character string is registered.

As described above, the characters "abc abc a
When the input of "bb" is completed, the codes assigned to the respective characters are as shown in FIG. As shown in FIG. 29, the first input character “abc” is encoded by one character each, and the corresponding codes are 00,
There are 2 bits of 01 and 10.

Then, the next inputted character string "abc"
The code word corresponding to is 1 bit of 0, 0, 0 respectively due to the relationship with the immediately preceding character. Further, a code is assigned to the next input character string of "ab" of 2 characters, but as shown in FIG. 29, the character string of 2 characters is represented by a code word of only 2 bits.

The last input character "b" is the case where there is no character corresponding to the connection of the immediately preceding characters,
It is represented by 3 bits of a combination of ESC and a code word of one character alone. As described above, according to the data compression method of the related technique 1, the characters (strings) to be compressed are registered by assigning numbers to the context tree of the tree structure, and the code tree corresponding to this context tree is spray-encoded. By creating and updating while performing, the probability model is constructed by finding the appearance frequency of the appearing characters, and the two-step process of assigning a code to each character is performed at the same time, so the speed of data compression processing is greatly improved. There is an effect of doing.

Further, since the above-mentioned probability model is constructed by creating / updating (spraying) the node of the code tree for each character input, the probability model already constructed for each character input is used. There is no need to perform a huge amount of arithmetic processing such as reconstruction, which has the effect of further improving the speed of compression processing. Further, according to the data compression method of the related technique 1, every time the same character as the previously compressed (encoded) character appears, the node of the code tree of the same character registered in the past is set as the upper node. By rearranging (spray processing) to reduce the code length to 1/2, as the same character (string) appears repeatedly, the code of that character (string) can be represented with a smaller number of bits, so the compression effect is significantly improved. effective.

Further, according to the data compression method of the related technique 1, as in the case where the above character string "ab" is encoded,
By encoding a character as a character string of a plurality of characters instead of encoding it as a character unit, the variable-length encoding process can be speeded up, and the encoding unit is a character string. There is also an effect that the coding efficiency is increased and the coding efficiency of the spray coding is significantly improved.

(2) Description of Decompression Side Next, as described above, using the encoded (compressed) data as an input code, the context collection process 21 and the spray code in the data decompression apparatus 2 described above with reference to FIG. The conversion process 22 for restoring data will be described with reference to process steps D1 to D24 in the flowchart of FIG.

The process for restoring this data may be basically the reverse of the encoding process described in the description of the encoding side. That is, first, the context tree and the code tree are initialized, and the preceding character P is initialized to 0 (step D1). The column length L is set to 0 (step D2),
It is checked whether or not there is a child node below the character just before the context tree (step D3).

Here, when there is no child node,
The character K is decoded using the input code as the 0th order code (step D
From the NO route of No. 3, step D4), it is checked whether the decoded character K is an EOF code (step D).
5). If the decoded character K is not an EOF code, the NO route is taken, the decoded character K is output (step D6), and the character K is registered in the context tree (step D).
7). This is performed in the same manner as the processing step E7 at the time of encoding described above with reference to FIG.

Further, similarly to step E8 at the time of encoding, a node of the character K and the escape code is created under the immediately preceding character P of the code tree (step D8), and the immediately preceding character P is set to the character K (step D17). ). Then, the subsequent processing steps D20 to D23 are processing steps E2 at the time of encoding.
The same processing steps as 0 to E23 are taken, and the immediately preceding character string length L ′ is replaced with the target character string length L (step D2
4) and returns to the above-mentioned processing step D2.

By the way, in the above-mentioned processing step D3, when a child node exists immediately below the character P immediately before the context tree, the input code is regarded as a primary code from the code tree and decoded, and the context tree is decoded. The reference number of the character (string) is obtained (from the YES route of step D3 to step D9). further,
It is checked whether the decoded reference number is an escape code (step D10). If it is an escape code,
The YES route is taken, the next character is decoded using the input character as the 0th order code, and the character K is obtained (step D11).

Then, as in step D5 described above, it is checked whether the decoded character K is an EOF code (step D12). If the decoded character K is not an EOF code, the NO route is taken and the character K is set. Output (Step D
13). Furthermore, processing steps E13 to E15 at the time of encoding
Similarly, register the letter K in the context tree (step D1
4) Add the letter K below the immediately preceding letter P (step D1
5) Update the escape length of the code tree and the code length of the 0th-order code K as a splay code (step D16).

Then, the processes from step D17 described above are performed thereafter. In this way, a splay code is assigned to all one character, and when the splay code of one character that is not in the character string in the dictionary in which the character string connected from the preceding character is already collected is decoded, the code is updated. The connected decoded characters from the character immediately before can be registered in the context tree.

If the decoded reference number is not the escape code in the above processing step D10,
Taking the NO route, the character string corresponding to the reference number of the context tree is restored and output (step D18), and the last character of the character (string) is replaced with the immediately preceding character P (step D19).
Then, the processes from step D20 described above are performed thereafter.

In this way, as the dictionary registration character string,
It is possible to register from the immediately preceding character that has been decoded and to decode the character string that continues from this immediately preceding character. If the decoded character K is the EOF code in the processing step D4 or step D12 described above, the YES route is taken and the restoration processing is ended. As described above, the character strings of the restored data are collected in the context tree as the dictionary, numbered and registered, and the splay code is made to correspond to each restored character string to correspond to the dictionary number. The character string is decoded and updated with the spray code, and the decompressed character string of the encoded character string is registered until the predetermined maximum character string length is reached, and the spray code corresponding to this decompressed character string is registered.

As a result, the character K compressed / encoded by the context collection step 11 and the spray encoding step 12 of the data compression apparatus 1 is restored. As described above, according to the data restoration method of the related technique 1, the restored characters (strings) are numbered and registered in the context tree, and a code tree as a code table corresponding to the context tree is constructed. ,
Since a code that matches the code of the coded character is searched in the code table and the character corresponding to the code that matches is output as a decoded character at the same time, the speed of data restoration processing is greatly increased. It has the effect of improving.

Further, since the above-mentioned probabilistic model is constructed by creating / updating (spraying) the node of the code tree for each character restoration, the code table already constructed is constructed for each character restoration. There is no need to perform a huge amount of arithmetic processing of reconstructing the (stochastic model), which has the effect of further improving the speed of the restoration processing. Furthermore, according to the data restoration method of Related Technique 1, every time the same code as the code decoded in the past appears, the node in the code tree of the same code registered in the past is recombined with the upper node ( (Spray processing) By reducing the code length to ½, the code can be represented by a smaller number of bits as the same code repeatedly appears. Therefore, when the same code is repeatedly decoded, the speed of the restoration process is significantly improved. is there.

Further, according to the data restoration method of the related art 1, by decoding the character not as a character-by-character unit but as a character string of a plurality of character units, the spray processing can be speeded up and the decoding unit can be improved. Since "" is a character string, there is also an effect that the information source that can be restored is expanded and the restoration efficiency is greatly improved. In the above example, the method of collecting and encoding / decoding a character string connected from the immediately preceding character as a context has been described, but it is not always necessary to focus on the immediately preceding character and the context from two or more characters before is collected and encoded. It may be decrypted.

In the above example, the context is dynamically collected and the spray processing is performed.
It does not necessarily have to be dynamic, and may be sprayed using a static context previously collected from a representative sample. Further, in the above-described example, the case where all the input data is dynamically variable-length coded (spray coded) has been described. However, after a considerable amount of data is coded, the update operation of the spray coding is stopped. Alternatively, static variable length coding may be performed. In this case, it suffices that an agreement be made in advance for encoding and decoding and synchronization be achieved.

Further, in the above example, the data to be compressed is described as a character or a character string, but the data compression method and the data decompression method of Related Technique 1 are applied to any data such as other image data or audio data. it can. (B) Description of an Embodiment of the Present Invention FIG. 32 is a block diagram showing a configuration example of a data compression apparatus and a data decompression apparatus for implementing a data compression method and a data decompression method according to an embodiment of the present invention. But
In FIG. 32, the data compression device 3 encodes and compresses the input data according to the history that has appeared in the past, and the data decompression device 4 uses the data compression device 3.
Is for decoding the coded code.

Hereinafter, description will be given below with the data compression device 3 as the encoding side and the data decompression device 4 as the decompression side. In addition,
In the following description, the context tree and the code tree have the configurations described above in item (a). (1) Description of Encoding Side FIG. 33 is a block diagram showing an example of the internal configuration of the data compression device 3 described above. As shown in FIG.
A-1 to 100A-n (n is a natural number) is a prefix data holding unit, 101A is a context history holding unit, 102A is a code tree holding unit, 103A is a code tree determining unit, 104A is a coding unit, 1
Reference numeral 05A is a code tree updating unit, and 106A is a context updating unit.

Here, the pre-data holding units (pre-data holding means) 100A-1 to 100A-n are input n just before the input data K (hereinafter sometimes referred to as event K). It holds the context of individual data. A context history holding unit (history holding means) 101A
Holds a combination of the input data K and the context, and is a code tree holding unit (code tree holding means) 102.
A holds an independent code tree for each context,
The code tree determination unit (code tree determination unit) 103A determines a code tree from the data held immediately before held in the prefix data holding units 100A-1 to 100A-n.

Further, the coding section (code output means) 104
A encodes the data K and outputs the data K from the root of the code tree (the vertex of the code tree) selected by the code tree determination unit 103A.
Is output according to a branch from a node (branch point) located midway along the leaf in which is stored. The code tree updating unit (code length changing unit) 105A rearranges the coded leaf and another leaf or node, and the context updating unit (prefix data updating unit) 106A prefixes the data K. The data is stored in the data holding units 100A-1 to 100A-n.

Further, FIG. 34 shows the above-mentioned encoding unit 104A.
FIG. 35 is a block diagram showing an example of the internal configuration of the encoding unit 104A for outputting the data K encoded according to the branch from the node as described above, as shown in FIG.
Includes an upper node discriminating unit 41, a node number managing unit (memory) 42, a position discriminating unit 43, a latch 44, and a stack 45.
Is provided.

Here, the upper node discriminating unit 41 obtains the node number of the upper node from the node number of the root of the code tree and the node number of the leaf of the context tree, and the node number managing unit (memory) 42 The node number of the context tree and the code tree is managed, and the position discriminating unit 43 discriminates the branching state of the node. In addition, the latch 44
Temporarily holds the node number of the leaf, and the stack 45 uses the data K output from the position determination unit 43.
The code is held once, and when the end signal is received, the held code is sequentially output.

With the configuration described above, in the data compression apparatus shown in FIG. 33, the pre-data holding units 100A-1 to 100A are provided.
-N holds the context consisting of n pieces of input data input up to immediately before the input data K, and the context history holding unit 101
A holds a combination of the input data and the context, and the code tree holding unit 102A holds an independent code tree for each context.

Further, the code tree determining unit 103A determines the code tree of the data from the input data up to immediately before held in the prefix data holding units 100A-1 to 100A-n,
The encoding unit 104A selects "0" or "1" according to a branch from a node located along the leaf in which the data K is stored from the root (vertex) of the code tree selected by the code tree determination unit 103A. The code (unique data) represented is output.

Further, the code tree updating unit 105A as the code length changing unit rearranges the coded leaf and another leaf or node, and the prefix data updating unit 106A stores the data K in the prefix data holding unit 100A-. Register to 1.
Here, the above operation will be described in more detail with reference to the processing steps A1 to A6 of the flowchart shown in FIG.

First, the front-end data storage units 100A-1 to 100-1
The context character string P held in 00A-n is initialized (step A1), and the data K to be encoded is input (step A2). The code tree determination unit 103A receives the context P from the context history holding unit 101A that holds the history of contexts held in the prefix data holding units 100A-1 to 100A-n.
Determines the code tree corresponding to, and from the information of the determined code tree and the context history holding unit 101A, codes the leaf node number (ID) holding the data K and the root node number (ID) of the context P. And sends it to the encoding unit 104A.
4A is the event K in the code tree corresponding to the context P.
The code corresponding to the branch of the node from the leaf of (data K) to the root is output (step A3). The processing performed by the encoding unit 104A will be described later in detail with reference to FIG.

After the coding in the coding unit 104A, the coding tree updating unit 105A rearranges the leaf of the event K of the coding tree with another leaf or node (step A
4) The code tree is updated by storing it in the original code tree holding unit 102A. The process performed by the code tree updating unit 105A will be described later in detail with reference to FIG.

Further, the context updating unit 106A rejects the oldest data (data held in the prefix data holding unit 100-n) and registers the input data K as the context in the prefix data holding unit 100A-1. The context string P
Is updated (step A5). Then, it is checked whether all the data have been encoded (step A
6) If not completed, the process from step A2 is repeated, and if completed, the encoding process is completed (YES route of step A6).

Either the node combination (step A4) or the context update (step A5) described above may be performed first, or the processes may be performed in parallel. next,
As described in the processing step A3, the coding processing performed by the coding unit 104A having the configuration described above with reference to FIG. 34 will be described with reference to processing steps B1 to B8 in FIG.

First, the stack 45 (push-down
stack) is initialized (step B1), and the address pointer of the current node L is set to the leaf in the code tree of the context P in which the data K is stored (step B2). And, it was sent in the above step A3,
Node number (ID) of the leaf that holds data K
Is transmitted from the latch 44 to the position discriminating unit 43, and the position discriminating unit 43 provides the node number management unit 42 with information on which of the upper nodes the node having the received node number is located.
Then, it is determined whether the node received from this information is located on the right hand side of the upper node (step B3).

If it is on the right hand side, stack "1" 4
Push (output) to 5 (from YES route of step B3 to step B4), and push (output) “0” to the stack 45 when located on the left hand (from NO route of step B3 to step B5). Further, the node number (ID) of the root of the context P that is the other node number sent in step A3 described above is sent to the upper node discriminating unit 41, and the upper node discriminating unit 41 receives the received node ( Alternatively, it is determined whether or not the leaf is the root (step B6).

If it is the root, an end signal is output (YES route in step B6), and if it is not the root, the node number (ID) management unit 42 is accessed to obtain the higher rank of this node (or leaf). Of the node (U) of the above, the address pointer is moved to the upper node as a new current node L, and the process from step B3 is repeated (from NO route of step B6 to step B7). .

In this way, by repeating the process until the address pointer reaches the root, the stack 45 stores the "path" represented by the numerical value "1" or "0" from the leaf to the root. It And this "route"
On the contrary, by outputting one bit at a time from the lower bit (pop-up output), the "route" from the root to the leaf is output as a code (step B8).

Next, as described above in the processing step A4, FIG. 37 shows the process in which the code tree updating unit 105A rearranges the leaf of the event K with another leaf or node.
The processing steps C1 to C9 will be described in detail. First, the address pointer of the node Z to be rearranged is set in the leaf K (step C1), and the upper node of the node Z is set in the node U0 (step C2).

Then, it is judged whether or not the upper node U0 of K is the root of the code tree (step C3), and if it is the root, the rearrangement is ended (YES route from step C3 to step C9). Set the upper node of node U0 to U1 (NO in step C3
From the root, step C4), it is determined whether the node U0 is located in one of the upper nodes U1 of the node U0 (step C5).

If U0 is to the right of U1, node X
Set the node located on the left hand side of the node U1 to the node (from the YES route of step C5 to step C6), and set the node Z
And node X are replaced (step C8). That is, the left-hand node of the node U1 and the leaf K are recombined. On the other hand, when the node U0 is on the left side of U1, the node located on the right side of the node U1 is set to the node X (from NO route of step C5 to step C7), and the node Z and the node X are replaced (step C8). . That is, the right-hand node of the node U1 and the leaf K are recombined.

Further, when the address pointer of the node Z is set in the node U1 (step C9), the process returns to the above step C2, and in step C3, the upper node of the set address pointer is the root, that is, the address pointer is directly under the root. The process is repeated until the node is determined to be a node. By performing this processing, the distance (code length) from the root of the accessed leaf is halved.

The character string can be encoded by repeating the above processing for all input characters. As described above, according to the data compression apparatus for implementing the data compression method according to the embodiment of the present invention, the character to be encoded is registered by assigning a number to the context tree of the tree structure and registering in the context tree. By creating / updating the corresponding code tree while performing splay coding, the appearance frequency of the appearing characters is obtained, a probabilistic model is constructed, a code is assigned to each character, and a code table is created. Since the two-stage processing of outputting the code of the character to be converted can be performed at the same time, there is an effect that the speed of the compression processing is significantly improved.

Further, as described above, the probability model is constructed by creating / updating the nodes of the code tree (spray processing) every time a character is input, so that the probability that the character has already been constructed every time a character is input. Since a huge amount of calculation processing of reconstructing the model can be omitted, there is an effect that the compression processing speed is further improved. Further, every time the same character that has been compressed (encoded) appears in the past, the node of the code tree of the same character registered in the past is recombined with the upper node to reduce the code length to ½ ( By the spraying process), as the same character (string) appears repeatedly, the code of the character (string) can be represented by a smaller number of bits, so that the compression effect is significantly improved.

(2) Description of Restoration Side FIG. 38 is a block diagram showing an example of the internal configuration of the data restoration device 4 described above. As shown in FIG.
A-1 to 200A-n (n is a natural number) is a prefix data holding unit, 201A is a context history holding unit, 202A is a code tree holding unit, 203A is a code tree determining unit, 204A is a coding unit, and 2A is a coding tree holding unit.
Reference numeral 05A is a code tree updating unit, and 206A is a context updating unit.

Here, the prefix data holding units (prefix data holding means) 200A-1 to 200A-n hold n pieces of data decoded in the past, and the context history holding unit (history holding means). ) 201A holds a combination of the decoded symbol and context, and the code tree holding unit (code tree holding means) 202A holds an independent code tree for each context.

The code tree determining unit (code tree determining means) 2
03A is a front data holding unit 200A-1 to 200A-
A code tree for decoding a symbol is determined from the context held in n, and the decoding unit (decoding means) 20
4A is a node (branch point) from the root (code tree vertex) of the code tree selected by the code tree determination unit 203A according to the code.
Is output by scanning the symbols stored in the leaf that has arrived.

Further, a code tree updating unit (code length changing means)
205A is a combination of the decoded leaf and another leaf or node, and the context updating unit (prefix data updating unit) 206A registers the decoded symbol in the prefix data holding units 200A-1 to 200A-n. To do. 39 is a block diagram showing an example of the internal configuration of the decoding unit 204A described above. As shown in FIG. 39, the node is scanned from the root of the code tree selected by the code tree determination unit 203A according to the code. To output the symbols stored in the leaf that has reached
Includes a node number management unit (memory) 42 and a latch 44.
A lower node discriminating unit 46 and a leaf / node discriminating unit 47 are provided.

Here, the node number management unit (memory) 42
Is the same as that described above with reference to FIG. 34 in the description on the encoding side, and manages the node numbers of the context tree and the code tree. The lower node discriminating unit 46 also includes a node number management unit 42 for the node number of the code and the root of the code tree.
The node number of the lower node is obtained from the information of
The leaf / node discriminating unit 47 discriminates whether the lower node is a leaf or a node from the information from the lower node discriminating unit 46 and the node number managing unit 42, and the latch 48 temporarily holds the node number of the root. It is a thing.

With the above configuration, the pre-data holding units 200A-1 to 200A-n have decoded n in the past.
The context history holding unit 201A holds each context (data).
Holds a combination of the data K decoded by and the context, and the code tree holding unit 202A holds an independent code tree for each context. Further, the code tree determination unit 203A determines a code tree for decoding the data K from the context held in the prefix data holding units 200A-1 to 200A-n, and the decoding unit 204A has performed coding. Data K stored in a leaf that has arrived by scanning a node (branch point) from the root (vertex) of the code tree selected by the code tree determination unit 203A according to the code of the data K is output.

Further, the code tree updating unit 205A as the code length changing means rearranges the decoded leaf and another leaf or node, and the prefix data updating unit 206A uses the decoded data K as the latest context. Data holding unit 20
Register with 0A-1. Hereinafter, regarding the above-mentioned processing, FIG.
Further details will be described with reference to process steps F1 to F6 of the flowchart shown in FIG.

First, the front data holding sections 200A-1 and 200A-2
The n context character strings P held in 00A-n are initialized (step F1), and the event (data) K to be decoded is input (step F2). The code tree determination unit 203A holds a context history holding unit 201A holding the history of contexts held in the prefix data holding units 200A-1 to 200A-n.
To determine a code tree corresponding to the context P, and send the node number (ID) of the root of the determined code tree and the code of the event K to be decoded to the decoding unit 204A, and the decoding unit 204A in the determined code tree. , And decodes the code by scanning from the root to the leaf in which the event K is stored, according to the code sent (step F3). Note that this decoding unit 204
The process performed by A will be described in detail later with reference to FIG.

After decoding, the code tree updating unit 205A
Updates the code tree by recombining the leaf of the decoded event K with another leaf or node (step F4) and storing it in the original code tree holding unit 202A.
The node rearrangement process performed by the code tree updating unit 205A is performed in the same manner as the processing steps C1 to C9 performed by the code tree updating unit 105A described above with reference to the flowchart of FIG.

Further, the context updating unit 206A rejects the oldest data (data held in the prefix data holding unit 200-n), and uses the decoded event (data) K as the context to prefix data holding unit 200. The context character string P is updated by registering it in -1 (step F5). Then, it is checked whether the decoding is completed for all the data (step F6). If not completed, the processing from step F2 is repeated (NO route of step F6), and if not, the decoding processing is completed (step F6). F6 YES route).

In this case as well, as in the case of the encoding side, either of the processing of changing the nodes (step F4) and the processing of updating the context (step F5) may be performed first.
You may process in parallel. Next, as described in the processing step F3, the decoding unit 204 having the configuration described above with reference to FIG.
The encoding process performed by A will be described with reference to process steps G1 to G7 in the flowchart shown in FIG.

First, the lower node discriminating unit 46 determines the node number (I) of the root sent from the code tree determining unit 203A.
D) is set to the node Z (step G1), and the latch 4
The code (1 bit) of the event K to be decoded, which is also sent from the code tree determination unit 203A via 8 is set to C (step G2). Then, it is checked whether the code of the event K to be decoded set in C matches "1" (step G3), and if it is "1" (Yes), the node Z is detected.
Set the node on the right hand side of node to node Z (step G
From the YES route of 3 to step G4), if it is not "1" (that is, "0"), the node on the left side of the node Z is set to the node Z (from NO route of step G3 to step G5). Further, the lower node discriminating unit 46
Acquires the node number of the node Z from the node number management unit 42 based on the node number of the node set in the node Z, sends this node number to the leaf / node discrimination unit 47, and this leaf / node discrimination unit At 47, the position information of the node Z having the sent node number is acquired from the node number management unit 42, and it is checked whether this node Z is a node or a leaf (step G6).

If node Z is not a leaf (step G
No. 6), the process returns to step G2, and the process is repeated until the leaf in which the event K to be decoded is stored is reached. On the other hand, when the node Z is a leaf (YES route in step G6), it means that the event K to be decoded has been found, so the leaf / node determination unit 47 sends the symbol (event) output signal to the node number management unit 42. The node number management unit 42 that has transmitted and received this signal outputs the event K (symbol) stored in this leaf (step G7) and outputs the end signal of the decoding process.

As a result, the "path" represented by the numerical value "1" or "0" of the code tree created on the encoding side is converted into the event K.
The encoded event K can be decoded by tracing to the leaf in which is stored. As described above, according to the data decompression apparatus for implementing the data decompression method according to the embodiment of the present invention, the decoded characters are registered by assigning the number to the context tree of the tree structure, and the decompressed character is associated with the context tree. By creating / updating the code tree while performing the spray process, the code table is searched for a code that matches the code of the character to be decoded, and the character registered corresponding to the matched code is output as the decoded character. Since the two-stage processing can be performed simultaneously, there is an effect that the speed of the data restoration processing is significantly improved.

As with the encoding side, every time a character is input, a node of the code tree is created / updated (spray processing).
Since it is constructed by, it is not necessary to perform a huge calculation process of reconstructing the already constructed probabilistic model each time a character is input, which has the effect of further improving the speed of the data restoration process. Further, like the encoding side, each time the same code as the code decoded in the past appears, the node of the code tree of the same code registered in the past is recombined with the upper node (spray processing). By reducing the code length to ½, as the same code is repeatedly restored, the code can be represented by a smaller number of bits, which also has the effect of significantly improving the restoration effect. (B-1) Description of First Modification of One Embodiment (1) Description of Encoding Side FIG. 42 shows an internal configuration of a data compression device 3 as a modification of one embodiment of the present invention. And this FIG.
As shown in FIG. 23, in addition to the configuration described above with reference to FIG. 33 in the description of one embodiment, the data compression device 3 according to the present embodiment includes a context determination unit 108A and a context changing unit 110A.
Further, in place of the coding unit 104A and the code tree holding unit 105A described in FIG. 33, a coding unit 104A ′ and a code tree holding unit 107A are respectively provided.

Therefore, in FIG. 42, description of components having the same reference numerals as those already described in FIG. 33 is omitted, and only components different from those in FIG. 33 will be described below. That is, the encoding unit 104A 'serves as a code output means and an escape code output means from a node located on the way from the root of the code tree to the leaf where the escape code is stored when the symbol is not registered in the code tree. When the symbol is registered in the code tree, the escape code is output according to the branch of, and the code of the symbol is output according to the branch from the node located midway from the root of the code tree to the leaf of the symbol.

Further, the encoding unit 104A 'serves as a control means, and when the escape code is encoded, the processing is repeated until the data is encoded. A code tree holding unit (code tree holding means) 107A
Holds an independent code tree for each context in which an escape code (ESC) indicating that a symbol has not been registered is registered in advance. The context discriminator (context discriminator) 108A includes a code tree determiner 103. It is for determining whether or not a symbol is registered in the code tree determined in step S1, and the context changing unit (context changing means) 110A shortens the length of the context when no symbol is registered in the code tree. It is a thing.

With such a configuration different from that of FIG. 33, in the data compression apparatus 3 shown in FIG. 42, the encoding unit 104A 'starts from the root of the code tree when the symbol K is not registered in the code tree. ES according to the branch from the node located on the way to the leaf where the ESC is stored
The code of C is output, and when the symbol K is registered in the code tree, the code of the symbol K is output according to the branch from the node located on the way from the root of the code tree to the leaf of the symbol K.

When the ESC is coded, the data K
The process is repeated until the encoding is performed. Further, the code tree holding unit 107A holds an independent code tree for each context in which an escape code (ESC) indicating that a symbol has not been registered is registered in advance.

The above process will be described in more detail below with reference to process steps H1 to H11 of the flowchart shown in FIG. First, the context changing unit 110A
The context character string P ₀ is initialized from all the contexts stored in the prefix data storage units 200A-1 to 200A-n (step H1), and this context character string P ₀ is set in the context P (step S1). H2), and the data (symbol) K to be encoded is input (step H3).

Further, the context changing unit 110A sends the information of the context P and the data K to the context history holding unit 101A and the code tree determining unit 103A, and the context history holding unit 101A
Information of the context P sent from the context changing unit 110A is
It is sent to the context discrimination unit 108A. Then, the context discrimination unit 108
Based on the received information on the context P, A determines whether or not the event K is registered in this context P (step H4).

Here, when the event K is registered in the context P, the context history holding unit 101A causes the encoding unit 104 to operate.
Instruct A'to encode the escape code (ESC),
The encoding unit 104A 'outputs the code corresponding to the branch of the node from the leaf of the escape code (ESC) to the root in the code tree corresponding to the context P to encode the escape code (NO in step H4). From root to step H5).

Further, the encoding unit 104A 'instructs the code tree updating unit 105A to update the code tree through the code tree determining unit 103A, and the code tree updating unit 105A causes the code tree E to be updated.
The leaf of SC is replaced with another leaf or node (step H6). Then, the order of the context P (the initial state of the code tree is 0th order) is moved to the next lower level (step H
7) Return to step H4, and repeat the process until it is determined that the event K is registered in the context P (Yes).

On the other hand, when the event K is registered in the context P (Yes in step H4), the context history holding unit 101A instructs the encoding unit 104A 'to encode the event K, The coding unit 104A 'outputs the code corresponding to the branch of the node from the leaf of the event K to the root in the code tree corresponding to the context P, and performs coding (from YES root of step H4 to step H8).

Then, the coding unit 104A 'instructs the code tree updating unit 105A through the code tree determining unit 103A to update the code tree, and the code tree updating unit 105A and the leaf of the event K of the code tree and other The leaf or node is recombined (step H9). Furthermore, the context updating unit 106A rejects the oldest data (data held in the prefix data holding unit 100-n) and registers the context of the input data K in the prefix data holding unit 100A-1. Then, the context changing unit 110A updates the context character string P ₀ (step H10).

Then, it is checked whether the coding is completed for all the data (step H11). If not completed (NO route of step H11), the process returns to step H2 until all the data is coded. Step H
If the process after 2 is repeated and the process is completed (YES route of step H11), all the processes for encoding are completed.

For details of the code output processing in steps H5 and H8, refer to the processing steps B1 to B8 described above with reference to FIG. 36 in this embodiment. For details of the node rearrangement processing, also refer to the processing steps C1 to C9 described above with reference to FIG. 37 in the present embodiment.

As described above, according to the data compression apparatus of the first modification of the embodiment of the present invention, the escape code (ESC) indicating that the symbol is not registered is registered in the code tree in advance. , Output as the input data by outputting the code of this escape code while the symbol to be encoded is not included in the pre-registered context (until the context containing the symbol is found and encoded) Since it is not necessary to register all combinations of symbols (contexts) in advance, there is an advantage that the memory used for registering contexts can be significantly reduced.

Then, as described above, the code length of the escape code output while the symbol to be encoded is not included in the pre-registered context is shortened (1/2) by the spray process. Since it is possible to shorten the time until the context in which the symbol is included is detected and encoded, the processing speed of data compression is significantly improved, and the processing load of the data compression device can be significantly reduced.

(2) Explanation of Restoration Side FIG. 44 shows the internal construction of the data restoration device 4 as the first modification of the embodiment of the present invention. As shown in FIG. In the inside of the data restoration device 4 in the present embodiment, a context changing unit 210A is provided in addition to the configuration described in FIG. 38 in the description of the present embodiment, a decoding unit 204A, and a code tree holding unit. Instead of the unit 205A, the decoding unit 204A ′ and the code tree holding unit 20 are respectively provided.
7A is provided.

Therefore, in FIG. 44, description of the components having the same reference numerals as those already described in FIG. 38 is omitted, and components different from the configuration shown in FIG. 38 will be described below. That is, the code tree holding unit (code tree holding means) 207A
Holds a code tree in which escape codes are registered in advance, and a context changing unit (context changing means) 210
A is to reject the input data and shorten the context when the output data is an escape code.

Further, the decoding unit 204A ', as a decoding means, scans a node (branch point) from the root (vertex) of the code tree selected by the code tree determination unit 203A according to the code encoded on the encoding side. Then, the data stored in the leaf that has arrived is output. Further, when the escape code is decoded, the decoding unit 204A 'resets the context as described above when the escape code is decoded, and performs control to repeat the process until data other than the escape code is decoded. It is like this.

With the configuration different from the configuration shown in FIG. 38 as described above, in the data restoration device shown in FIG. 44, the code tree holding unit 207A holds the code tree in which the ESC is registered in advance, and the context changing unit 210A. When the data K output by is ESC, the input data K is rejected and the context is shortened. In addition, the decoding unit 204A ′ outputs the data K stored in the leaf reached by scanning the node from the root of the code tree selected by the code tree determining unit 203A according to the code of the encoded data K, When the ESC is decoded, the context changing unit 210A changes the order of the context and repeats the process until the data K other than the ESC is decoded.

Here, the operation as described above will be described with reference to FIG.
Further details will be described with reference to process steps J1 to J9 of the flowchart shown in FIG. First, the context changing unit 210
A initializes the context character string P ₀ from all the contexts stored in the prefix data storage units 200A-1 to 200A-n (step J1) and sets this context character string P ₀ in the context P. (Step J2).

Then, the context changing unit 110A sets the context P to the context history holding unit 201A and the code tree determining unit 203.
The code tree determining unit 203A selects (determines) a code tree from the received context P (step J3), and sends the determined code tree to the decoding unit 204A '. Decoding unit 204
In A ', the code is decoded by scanning from the root to the leaves in the determined code tree according to the code encoded on the encoding side (step J4). Note that this decoding unit 204
For details of the processing performed by A ′, refer to the processing steps G1 to G7 described above with reference to FIG. 41 in this embodiment.

Then, the decoding section 204A 'checks whether or not the decoded event K is ESC (escape code) (step J5), and if the decoded event K is ESC, changes the context of the ESC signal. It is transmitted to the section 210A (YES route of step J5). Furthermore, this ESC
Upon receiving the signal, the context changing unit 210A changes the order of the context P by moving it to the next lower order (for example, ignoring the oldest data held in the pre-data holding unit 200-n, n-1). The next context P is created) (step J6), this context P is sent to the context history holding unit 201 and the code tree determination means 203, and the process returns to step J3.

That is, the decoding unit 204A 'determines that the ESC
The processing from step J2 is repeated until the event K other than is decoded. On the other hand, when the decrypted event K is not ESC, the leaf of the decrypted event K is recombined with another leaf or node (from NO route of step J5 to step J7). For details of this leaf or node rearrangement processing, refer to the processing steps C1 to C9 in the flowchart described above with reference to FIG. 37 in this embodiment.

Further, the context updating unit 206A rejects the oldest data (data held in the prefix data holding unit 200-n), and stores the decoded event K in the prefix data holding unit 200-1 as the context. Insert and register, context string P
₀ is updated (step J8). Then, it is checked whether the decoding is completed for all the data (step J
9) If not completed, the processes from step J2 are repeated (from NO route of step J9 to step J).
2) If not, the decryption process ends (step J).
9 YES route).

In this case as well, as in the case of the encoding side, either of the processing of changing the nodes (step J7) and the processing of updating the context (step J8) may be performed first.
You may process in parallel. As described above, according to the data restoration device according to the first modified example of the embodiment of the present invention, an escape code (ESC) indicating that a symbol is not registered is registered in the code tree in advance, and the decoding is performed. If the escaped symbol is this escape code, the context is shortened (changed) until the code other than the escape code (that is, the symbol of the symbol to be decoded) is decoded, and the code of the symbol to be decoded is searched. Since it is not necessary to register all combinations (contexts) of symbols appearing as data in the code tree in advance, there is an advantage that the memory used for registering contexts can be significantly reduced.

While the decoded symbol is the escape code as described above, the code length of this escape code is shortened (1/2) by the spray processing to find the context including the symbol to be decoded. Since it is possible to shorten the time until decoding is performed, there is an effect that the speed of the data restoration processing is significantly improved and the processing load of the data restoration device is also greatly reduced. (B-2) Description of Second Modification of One Embodiment (1) Description of Encoding Side FIG. 46 is an internal configuration of a data compression device 3 as a second modification of one embodiment of the present invention. As an example, as shown in FIG. 46, in addition to the configuration described above with reference to FIG. 38 in the description of the first modified example of the present embodiment, the data compression device 3 according to the present embodiment has the same configuration. In addition, a code registration unit 112A is further provided.

Therefore, in FIG. 42, description of the components having the same reference numerals as those already described in FIG. 33 will be omitted. Also,
The code registration unit 112A registers the input data K in the code tree when the data K is not registered in the code tree. With such a configuration, when the input data K is not registered in the code tree, the code registration unit 112A can register the data K in the code tree.

Here, the operation as described above will be described with reference to FIG.
7 will be described with reference to processing steps K1 to K12. Here, as shown in FIG. 47, the processing other than step K8 is the same as in FIG. 4 in the description of the first modified example of the present embodiment.
The processing steps H1 to H described above in the flowchart of FIG.
The process is the same as 11. That is, in this embodiment, in steps K1 to K7, steps H1 to H7 in FIG.
The same processing as H7 is performed, and then step K8
Processing is performed.

That is, when the context discriminating unit 108A discriminates that the event K is not registered in the context tree (NO route of step K4), the code tree updating unit 105A sets the ESC leaf of the code tree to another leaf. Alternatively, the code of the ESC is changed by recombining with the node (step K6), and the context history holding unit 101A stores the current context P in the code registration means 112A.
Then, the context changing unit 110A moves the order of the context P to the next lower order and changes it (step K7), and then the code registration unit 11
2A registers the event K in the code tree (step K8).

Even when it is determined in step K4 that the event K is registered in the context tree, the same processing as steps H8 to H11 in FIG. 43 described above is performed in steps K9 to K12. There is. As described above, according to the data compression device of the second modification of the embodiment of the present invention, as described above, the step K8 is performed.
Other than that, the processing steps are the same as those of the encoding side of the first modified example of the present embodiment in FIG. 43, so that there are the same effects as the encoding side effects of the first modified example of the present embodiment. .

Further, as described above, by taking step 8, the symbols are registered in the code tree while the escape code is coded, and the symbols not previously registered in the code tree are next coded. Since the encoding can be performed at an early stage (higher order), the compression effect is significantly improved as the encoding progresses. (2) Explanation of Restoration Side FIG. 48 shows an example of the internal configuration of the data restoration device 4 as a second modification of the embodiment of the present invention. As shown in FIG. In addition to the configuration described above with reference to FIG. 44 in the description of the restoration side of the first modified example of the present embodiment, a code registration unit 212A is further provided inside the data restoration device 4 in the embodiment. The code registration unit 212A is provided corresponding to the configuration on the encoding side (see FIG. 46).

Therefore, in FIG. 48, description of the components having the same reference numerals as those already described in FIG. 44 will be omitted. The code registration unit 212A registers the code of the decoded data in all the code trees corresponding to the context when the ESC (escape code) is decoded in the decoding process of the data encoded on the compression side. is there.

As a result, in addition to the operation performed by the configuration described above with reference to FIG. 44, when the code registration unit 212A decodes the ESC in the decoding process of the encoded data K, all the codes corresponding to the context are obtained. The code of this decoded data K can be registered in the code tree. The above operation will be described in more detail with reference to the processing steps L1 to L10 of FIG.

As shown in FIG. 49, the processing steps L1 to L4 are the same as the processing steps J1 to J4 described above with reference to FIG. 45 on the restoration side of the first modification of the present embodiment. Processing is performed. Then, in step L4, after the decoding unit 204A decodes the code, the code tree updating unit 205A rearranges the decoded leaf of the event K with another leaf or node (step L5).

Further, if the ESC (escape code) has been previously decoded at this point and the ESC signal from the decoding unit 204A is received, the code tree updating unit 205A determines that all the ESCs have been decoded. The event K is registered in the code tree (step L6). Furthermore, the decrypted event K is ES
It is determined whether it is C (step L7) and the decoded event K
Is an ESC, the ESC signal indicating that the decoded event K is an ESC is transmitted to the context changing unit 210A and the code registering unit 212A, and the context changing unit 210A receiving this ESC signal changes the context P Change the order by moving it to the next lower level (from the YES route of step L7 to step L
8) The process returns to step L3 and is repeated until the event K other than ESC is decoded.

In this way, when the event K decoded by the decoding unit 204A is ESC, the code registration unit 212A creates a new leaf in the code tree and the decoding unit 204 ESC.
When K is decoded for events other than, by storing this event K in all newly created leaves, the symbol can be registered in all code trees in which ESC has been restored.

On the other hand, when the decoded event K is not ESC in the above step L7, the context updating unit 206A rejects the oldest data (data held in the prefix data holding unit 200-n), The decrypted event K is inserted as a context into the pre-data holding unit 200-1 and registered, and the context character string P ₀ is updated (step L9). Then, it is checked whether the decoding is completed for all the data (step L10), and if not completed, the processes from step L2 are repeated (NO route of step L10), and if completed, the decoding process is completed (step L10). YES in step L10
root).

As described above, on the decoding side as well as on the encoding side, when decoding section 204A decodes ESC, code tree registration section 212A newly registers event K in the code tree. As described above, according to the data decompression device according to the second modified example of the embodiment of the present invention, similar to the encoding side, the effects described above on the decompression side in the first modified example of the embodiment are achieved. In addition, when the code of the escape code is decoded, the code of the symbol to be decoded is registered in the code tree, so that the symbol not registered in the code tree can be decoded at an early stage in the next decoding. Therefore, as the decoding process of data such as characters progresses, the restoration effect is greatly improved and the processing load of the data restoration device can be greatly reduced. (B-3) Description of Third Modified Example of Present Embodiment (1) Description of Encoding Side In the third modified example of the present embodiment, the data compression device 3 described above is the second modified example described above. On the other hand, when the data K is encoded, even if the ESC is encoded even once, the context changing unit 110A as the history registration means sets the combination of the context and the data immediately before the encoding of the data. It is registered in the context history holding unit 101A, and the code registration unit 112A
The difference is that data can be newly registered in a code tree having an escape code encoded just before encoding this data.

The above process will be described in more detail below with reference to process steps M1 to M13 shown in FIG. Here, as shown in FIG. 50, step M1
The processes similar to the process steps H1 to H9 of FIG. 43 used in the description of the first modified example of the present embodiment are performed on the processes M1 to M9.

If the event K of the input data is registered in the context P (YES route of step M4),
After the code tree is rearranged in step M9 via step M8, the decoding unit 104 checks whether the event K encoded in step M8 is ESC (step M10). When the encoded event K is ESC, the code registration unit 112A registers the event K in the code tree corresponding to the context P ′ immediately before encoding the event K (from the YES route of step M10 to step M11). The context updating unit 106A registers the context P including the event K in the predata holding unit 100A-1 as the newest context.

Further, from this information, the context changing unit 110A
Inserts the data K into the context character string P ₀ , updates it (step M12), and registers it in the context history holding unit 101A. That is, since the data K is registered in the code tree of the context P '(that is, the last encoded context) immediately before the data K is encoded in step M11, the data K and the data K immediately before the data K are encoded. The context changing unit 106A registers the combination with the context P ′ in the context history holding unit 101A.

On the other hand, if the encoded event K is not ESC (NO route of step M10), step M11
Is skipped and step M12 described above is performed. Furthermore, it is checked whether the encoding of all the data is completed (step M13), and if not completed (NO route of step M13), the process returns to step M2, and the encoding of all the data is completed. The processing is repeated up to, and if the processing is completed, the encoding processing is completed (YES route of step M13).

As described above, according to the data compressing apparatus of the third modification of the embodiment of the present invention, in addition to the effects described above on the encoding side of the second modification of the embodiment, If the pre-registered context does not include a symbol, registering this symbol only in the code tree of the last encoded escape code significantly increases the amount of memory used to register a new context. Therefore, there is an effect that the performance of the data compression device is significantly improved.

Further, each time the same symbol newly registered as described above is input later, the node of the code tree of this symbol is recombined to shorten the code length (spray processing). Since the code length of the code can be shortened only for the symbol having a high appearance frequency, the compression effect of the data compression device is significantly improved.

(2) Explanation of Restoration Side Data Restoration Device 4 According to Third Modification of this Embodiment
Compared to the data restoration device 4 shown in FIG. 48, the context changing unit 210A as the history registration means is a decoding process of the data K encoded on the encoding side, and finally ESC (escape code) is added. The decoded context and the decoded data K are registered in the context history holding unit 201A, and the code registration unit 212
The difference is that A can register the code of the data K in the code tree corresponding to the context when the ESC is finally decoded in the decoding process of the data K.

The above-mentioned processing will be described in more detail with reference to the processing steps N1 to N10 in FIG. Here, as shown in this FIG.
In N5, the same processes as those in steps K1 to K5 of FIG. 49 used in the description of the restoration side of the second modification example are performed.

Then, on the restoration side of this embodiment, after the leaf of the event K decrypted in step N5 is recombined with another leaf or node, it is checked whether the decrypted event K is ESC (step N6). Decrypted event K
Is ESC, the order of the context P is changed (YES route from step N6 to step N7), and the process returns to step N3 to repeat the process until the event K other than ESC is decoded.

On the other hand, when the decoded event K is not the ESC, the code tree updating unit 205A creates a new leaf only in the code tree obtained by decoding the immediately previous ESC, and the code registration unit 212A.
Registers event K in a new leaf of this code tree (from NO route of step N6 to step N8). Further, the context updating unit 206A discards the oldest data (data held in the prefix data holding unit 200-n), inserts the decoded event K into the prefix data holding unit 200-1 as the context, and Register and update the context string P ₀ (step N
9).

Then, it is checked whether the decoding has been completed for all the data (step N10), and if not completed, the processing from step N2 is repeated (from NO route of step N10 to step N2) and the processing must be completed. If so, the decoding process ends. As described above, according to the data restoration device according to the third modified example of the embodiment of the present invention, in addition to the effect described above on the restoration side of the second modified example of the present embodiment, it is registered in advance. If the context does not include a symbol, the code of this symbol is newly registered only in the code tree of the escape code that was decoded last, so that one or less registration is always required for one symbol. Since it is possible to significantly reduce the memory for managing the node ID used for registering the code of a different symbol, there is an effect that the performance of the data restoration device is significantly improved.

Further, by recombining the symbol newly registered as described above and the node of the code tree of this symbol each time the same symbol is input later, the code length is shortened (spray processing). Only a symbol having a high appearance frequency actually has a code with a short code length, so that the restoration effect of the data restoration device is significantly improved.

(C) Description of Technology 2 Related to the Present Invention Next, technology 2 related to the present invention will be described. First, its principle will be described. FIG. 9 shows the configuration of an apparatus for carrying out the data compression method according to Technique 2 related to the present invention. The data compression apparatus shown in FIG. 9 encodes the input data according to the history of past appearances.

Here, 301 is a code tree holding means, 302
Is a context tree holding unit, 303 is a context registration unit, 304 is a code registration unit, 305 is a context changing unit, 306 is an encoding unit, and 307 is a code updating unit. Code tree holding means 30
Reference numeral 1 holds a code tree in which an escape code defined as data indicating unregistered data is registered in advance, and the context tree holding unit 302 holds a context tree in which a combination of input data and a context is registered. The context registration means 303 is to newly register data in the context tree after encoding the escape code.

Further, the code registration means 304 is for registering new data by branching the leaf as the data storage point of the escape code of the code tree after encoding the escape code, and the context changing means 305. When the combination of the input data and the context is not stored in the context tree, the context is changed. Also, the encoding means 30
Reference numeral 6 is for outputting a code in accordance with input data from the apex of the code tree or branching to a leaf in which escape code is registered, and the code updating means 307 is registered with encoded data and escape code. It replaces a leaf with another leaf or node.

FIG. 10 shows the configuration of an apparatus for carrying out another data compression method according to Technique 2 related to the present invention.
Shown in. The data compression apparatus shown in FIG. 10 also encodes the input data according to the history of past appearances.
The data compression apparatus shown in FIG. 10 has the same code tree holding means 301, context tree holding means 302, context registration means 303, context changing means 305, coding means 306, code updating means 307 as those in FIG. 9 described above. Is equipped with
These explanations are omitted.

Further, 310 is a branch position searching means,
The branch position searching means 310 searches for a leaf having the longest code length on the code tree. Reference numeral 311 is a code registration means. This code registration means 311 is for coding the escape code and then branching the leaf as the data storage point searched by the branch position searching means 110 to newly register the data. is there.

Furthermore, FIG. 1 shows the configuration of an apparatus for carrying out another data compression method according to the technique 2 related to the present invention.
Shown in 1. The data compression apparatus shown in FIG. 11 also encodes the input data according to the history of past appearances. Here, also in the data compression apparatus shown in FIG. 11, the same code tree holding means 3 as that in FIG. 9 described above.
01, context tree holding means 302, context registration means 303, context changing means 305, encoding means 306, code updating means 3
07, and description thereof will be omitted.

Reference numeral 308 is a branch position holding means, and this branch position holding means 308 holds the position of a leaf as a data storage point newly registered in the code tree. Further, 309 is a code registration means, and this code registration means 309 encodes the escape code,
The leaf at the position held by the branch position holding means 308 is branched to newly register the data.

On the other hand, FIG. 12 shows the configuration of an apparatus for carrying out the data restoration method according to the technique 2 related to the present invention. The data decompression device shown in FIG. 12 decodes a code obtained by coding input data according to the history of past input data. Here, 401 is a code tree holding means, 4
02 is a context tree holding means, 403 is a code tree determining means, 40
Reference numeral 4 is a decoding unit, 405 is a context changing unit, 406 is a code updating unit, 407 is a code registration unit, and 408 is a context tree registration unit.

The code tree holding unit 401 holds a code tree in which an escape code defined as data indicating that the data has not been registered is registered in advance, and the context tree holding unit 40.
Reference numeral 2 holds a context tree in which a combination of the decoded data and the context is registered, and the code tree determining means 403.
Is to determine the code tree of the code from the data decoded up to immediately before.

Further, the decoding means 404 decodes the code by scanning from the root meaning the apex of the code tree to the leaf as the data storage point according to the code, and the context changing means 405 determines that the arrived leaf is If it is an escape code, the context is changed, and the code updating means 406 replaces the leaf of the decoded data and escape code with another leaf or a node as a branch point.

When the escape code is decoded, the code registration means 407 newly branches the escape code leaf and registers the decoded data, and the context tree registration means 408 uses the code registration means 407. The registered data is registered in the context tree of the context holding unit 402. Furthermore, FIG. 13 shows the configuration of an apparatus for carrying out another data restoration method according to Technique 2 related to the present invention. The data restoration device shown in FIG. 13 also decodes the code obtained by encoding the input data according to the history of past input data. Here, the data restoration device shown in FIG. Code tree holding means 4 similar to that shown
01, context tree holding means 402, code tree determination means 403,
Decoding means 404, context changing means 405, code updating means 4
06, and the description thereof will be omitted.

Further, 411 is a branch position searching means,
The branch position search means 411 searches the position of the leaf having the longest code length in the code tree. And
Reference numeral 412 is a code registration means, and this code registration means 412
Is to encode the escape code and then branch the leaf searched by the branch position searching means 411 to newly register the data.

Further, 413 is a context tree registration means,
The context tree registration means 413 registers the data registered by the code registration means 412 in the context tree of the context tree holding means 402. Furthermore, FIG. 14 shows the configuration of an apparatus for carrying out the data restoration method according to the technique 2 related to the present invention.
Shown in. The data restoration device shown in FIG. 14 also decodes a code obtained by coding the input data according to the history of the past input data.

Here, also in the data restoration device shown in FIG. 14, the code tree holding means 401, the context tree holding means 402, the code tree determining means 403, the decoding means 404, the context similar to those shown in FIG. The changing means 405 and the code updating means 406 are provided, and the description thereof will be omitted. Further, 409 is a branch position holding unit, and this branch position holding unit 409 holds the position of the leaf newly registered in the code tree.

Further, reference numeral 410 is a code registration means. This code registration means 410 encodes the escape code and then branches the leaf at the position held by the branch position holding means 409 to newly write data. It is to register. Reference numeral 414 is a context tree registration means, and this context tree registration means 414 registers the data registered by the code registration means 410 in the context tree of the context holding means 402.

The data compression method according to the technique 2 related to the present invention has the following effects. (1) By the context tree holding process, it is possible to hold a context tree in which a combination of input data and a context consisting of n pieces of continuous data is registered. (2) By the code tree holding process, it is possible to hold an independent code tree for each context.

(3) In the context tree new registration process, when a combination of input data and context is not held in the context tree holding process, data can be newly registered in the context tree of the context tree holding process. (4) By the code tree new registration process, when the combination of the input data and the context is not held in the context tree holding process, the data can be newly registered in the code tree in the code tree holding process.

(5) By the new registration process, when the combination of the input data and the context is not held in the context tree holding process, the leaf as the data storage point of the code tree in the code tree holding process is obtained by branching. Data can be stored in a new leaf. (6) The context changing process allows the context to be changed when the combination of the input data and the context is not held in the context tree holding process.

(7) By the code output process, the code can be output according to the branch to the input data from the apex of the code tree or the leaf to which the specific code in the code tree is registered. (8) By the process of changing the code length, it is possible to replace a leaf in which a specific code in the input data or the code tree is registered with another leaf or a node defined as a branch point other than the vertex of the code tree.

(9) In the new registration process, the leaf in which the specific code is registered can be branched, and the specific code and the new data can be registered in the two new leaves obtained. Then, the data compression method according to the technique 2 related to the present invention is
It has the following effects. (1) By the code tree holding process, it is possible to hold a code tree in which an escape code defined as data indicating unregistered is registered in advance.

(2) By the context tree holding process, it is possible to hold the context tree in which the combination of the input data and the context consisting of n pieces of continuous data is registered. (3) By the context tree new registration process, when the combination of the input data and the context is not held in the context tree holding process, the data can be newly registered in the context tree of the context tree holding process.

(4) By the code tree new registration process, when the combination of input data and context is not held in the context tree holding process, data can be newly registered in the code tree in the code tree holding process. (5) When the combination of the input data and the context is not held in the context tree holding process by the new registration process, a new leaf obtained by branching the leaf as the data storage point of the code tree in the code tree holding process is obtained. Data can be stored.

(6) By the context changing process, the context can be changed when the combination of the input data and the context is not held in the context tree holding process. (7) By the code output process, the code can be output according to the branch to the input data from the vertex of the code tree or the leaf in which the escape code is registered. (8) By the code length changing process, it is possible to replace a leaf in which input data or escape code is registered with another leaf or a node defined as a branch point other than the vertex of the code tree.

(9) In the new registration process, the leaf in which the escape code is registered can be branched, and the escape code and new data can be registered in the two new leaves obtained. Further, in the above-mentioned new registration process of (5), among the leaves under the same context, the leaf having the longest distance from the root defined as the vertex of the code tree is branched to obtain two new leaves. , It is also possible to register the data stored in the branched leaf and the new data. Of the leaves under the same context, the last registered leaf is branched, and the obtained two new leaves are branched. The data stored in the leaf and the new data can be registered.

On the other hand, the data restoration method according to the technique 2 related to the present invention has the following effects. (1) By the context tree holding process, it is possible to hold the context tree in which the combination of the decoded data and the context is registered. (2) By the code tree holding process, each independent code tree can be held according to the context.

(3) By the code tree determining process, the code tree of the code can be determined from the data decoded up to immediately before. (4) By the decoding process, the code can be decoded by scanning from the root meaning the apex of the code tree to the leaf as the data storage point according to the code. (5) The context can be changed by the context changing process when the leaf that arrived is a specific code in the code tree.

(6) By the process of changing the code length, the leaf of the decoded data and the specific code can be recombined with another leaf or a node as a branch point. (7) By the new registration process, the decoded data can be newly registered in the code tree when the specific code is decoded. (8) By the context tree registration process, the data registered in the new registration process can be registered in the context tree in the context tree holding process.

(9) In the new registration process, new data can be registered by branching the same leaf as the branch selected on the encoding side. Furthermore, the technology 2 related to the present invention
The data restoration method according to the present invention has the following effects. (1) By the code tree holding process, it is possible to hold a code tree in which an escape code defined as data indicating data unregistered is registered in advance.

(2) The context tree holding process can hold the context tree in which the combination of the decoded data and the context is registered. (3) In the code tree determination process, the code tree of the code can be determined from the data decoded up to immediately before. (4) By the decoding process, the code can be decoded by scanning from the root meaning the apex of the code tree to the leaf as the data storage point according to the code.

(5) By the context change process, if the leaf that arrived is an escape code, the context can be changed. (6) Through the process of changing the code length, the leaf of the decoded data and the escape code can be recombined with another leaf or a node as a branch point. (7) By the new registration process, the decoded data can be newly registered in the code tree when the escape code is decoded.

(8) By the context tree registration process, the data registered in the new registration process can be registered in the context tree in the context tree holding process. (9) In the new registration process, the same leaf as the leaf selected for branching on the encoding side can be branched to register new data. Further, the device having the configuration described with reference to FIG.
That is, in the data compression apparatus that encodes the input data according to the history of past appearances, the code tree holding unit 30
Reference numeral 1 holds a code tree in which an escape code defined as data indicating unregistered data is registered in advance, and context tree holding means 302 holds a context tree in which a combination of input data and a context is registered.

Then, the context registration means 303 encodes the escape code, then newly registers the data in the context tree, and the code registration means 304 encodes the escape code and then stores the escape code data of the code tree. The leaf as a point is branched to newly register the data, and the context changing unit 305 changes the context when the combination of the input data and the context is not held in the context tree.

Further, the encoding means 306 outputs a code according to the branch to the input data from the vertex of the code tree or the leaf in which the escape code is registered, and the code updating means 307 outputs the encoded data and escape code. Replaces the leaf registered with the other leaf or node. Furthermore, in the device having the configuration described with reference to FIG. 10, that is, in the data compression device that encodes the input data according to the history that has appeared in the past, the code tree holding unit 301 stores data indicating that the data has not been registered in advance. The code tree in which the defined escape code is registered is held, and the context tree holding unit 302 holds the context tree in which the combination of the input data and the context is registered.

Then, the context registration means 303 encodes the escape code, then newly registers the data in the context tree, and the branch position search means 310 searches the leaf having the longest code length on the code tree. , Code registration means 311 encodes the escape code, and then branch position search means 3
The leaf as the data storage point retrieved in 10 is branched and new data is registered.

Further, the context changing means 305 changes the context when the combination of the input data and the context is not held in the context tree, and the encoding means 306 registers the input data or the escape code from the vertex of the code tree. A code is output in accordance with the branch to a given leaf, and the code updating means 307 replaces the leaf in which the encoded data and the escape code are registered with another leaf or node.

Further, in the device having the configuration described with reference to FIG. 11, that is, in the data compression device that encodes the input data according to the history that has appeared in the past, the code tree holding means 301 indicates that the data has not been registered in advance. A code tree in which an escape code defined as data is registered is held, and a context tree holding unit 302 holds a context tree in which a combination of input data and a context is registered.

Then, after the context registration means 303 encodes the escape code, the data is newly registered in the context tree, and the branch position holding means 308 positions the leaf as a data storage point newly registered in the code tree. And the code registration means 309 encodes the escape code, and then branches the leaf at the position held by the branch position holding means 308 to newly register the data.

Further, the context changing means 305 changes the branch when the combination of the input data and the context is not held in the context tree, and the coding means 306 registers the input data or the escape code from the top of the code tree. The code is output according to the branch to a certain leaf, and the code updating means 30
The leaf in which the data encoded by 7 and the escape code are registered is replaced with another leaf or a node as a branch point.

On the other hand, in the device having the configuration described with reference to FIG. 12, that is, in the data restoration device that decodes the code obtained by coding the input data according to the history of the past input data, the code tree holding means 401 is previously stored. A code tree in which an escape code defined as data indicating unregistered data is registered is held, a context tree in which a combination of the data decoded by the context holding unit 402 and a context is registered, and the code tree determining unit 403 immediately before is held. The code tree of the code is determined from the data decoded up to.

Then, the decoding means 404 decodes the code by scanning from the root meaning the apex of the code tree to the leaf as the data storage point according to the code, and the context changing means 405.
If the leaf reached by is an escape code, change the context. Further, the code updating unit 406 rearranges the decoded data and the escape code leaf with another leaf or a node serving as a branch point, and when the code registration unit 407 decodes the escape code, the escape code leaf is branched and decoded. The newly registered data is newly registered, and the context tree registration unit 408 registers the data registered by the code registration unit 407 in the context tree of the context holding unit 402.

Further, in the device having the configuration described with reference to FIG. 13, that is, in the data decompression device for decoding the code obtained by coding the input data according to the history of the past input data, the code tree holding means 401 is previously stored. A code tree in which an escape code defined as data indicating unregistered data is registered is held, a context tree in which a combination of the data decoded by the context holding unit 402 and a context is registered, and the code tree determining unit 403 immediately before is held. The code tree of the code is determined from the data decoded up to.

[0275] Then, the decoding means 404 decodes the code by scanning from the root meaning the apex of the code tree to the leaf as the data storage point according to the code, and the context changing means 405.
But if the leaf reached is an escape code,
Change context. Further, the leaf of the data and escape code decoded by the code updating means 406 is recombined with another leaf or a node as a branch point, and the branch position searching means 411 searches for the position of the leaf having the longest code length in the code tree, The code registration unit 412 branches the leaf searched by the branch position search unit 411 after encoding the escape code and newly registers the data, and the context tree registration unit 408 context-registers the data registered by the code registration unit 412. It is registered in the context tree of the holding unit 402.

Further, in the device having the configuration described with reference to FIG. 14, that is, in the data restoration device which decodes the code obtained by encoding the input data according to the history of the past input data, the code tree holding means 401 is previously stored. A code tree in which an escape code defined as data indicating unregistered data is registered is held, a context holding unit 402 holds a context tree in which a combination of decoded data and a context is registered, and a code tree determining unit 403 is held. The code tree of the code is determined from the data decoded up to immediately before.

Then, the decoding means 404 decodes the code by scanning from the root which means the vertex of the code tree to the leaf as the data storage point according to the code, and the context changing means 40.
In the case where the leaf that reached 5 is an escape code, the context is changed, the leaf of the data and escape code decoded by the code updating means 406 is recombined with another leaf or a node as a branch point, and the branch position holding means 4
09 holds the position of the leaf newly registered in the code tree.

Further, after the code registration means 410 encodes the escape code, the leaf at the position held by the branch position holding means 409 is branched to newly register the data, and the context tree registration means 408 makes the code. Registration means 410
The data registered in step 3 is registered in the context tree of the context holding unit 402. Therefore, according to the data compression method according to the technique 2 related to the present invention, when the data is such that the above-mentioned specific code is output in a relatively large amount, or the context held in the context tree holding process is sufficiently registered. There is an effect that a high coding rate can be obtained in the initial stage or the like.

If the code length changing process is performed before the above-mentioned code tree new registration process, the code length of the code and the specific code is at least 2 bits, and if the code length changing process is performed after the code tree new registration, Since the code code can be set to a minimum of 1 bit, there is an effect that the coding efficiency is further improved. Further, in the new registration of the code tree, since new data is always registered one by one, only the reproducible symbols are registered in the higher order of the code tree at all times. However, it is possible to prevent the deterioration of the coding efficiency caused by the existence of the data that is not actually used, and this has the effect of significantly improving the coding efficiency after the data is sufficiently registered.

Even if the above-mentioned specific code is an escape code defined as data indicating unregistered in advance, the same effect as the above-described data compression method can be obtained. Further, according to another data compression method of the technique 2 related to the present invention, in the new registration process, among leaves under the same context, the distance from the root defined as the vertex of the code tree is the longest. Branched leaf, got 2
Two new leaves obtained by registering the data stored in the branched leaf and the new data into one new leaf, or branching the last registered leaf among the leaves under the same context. In addition, since it is possible to register the data stored in the branched leaf and the new data, in addition to the effect of the above-mentioned data compression method, the code of the least frequently used data of the appearance frequency is used. The length can be lengthened.

As a result, there is an effect that the reduction of the encoding efficiency due to the extension of the code length by 1 bit can be suppressed to the minimum and the processing speed of the data compression can be greatly improved.
Also, the new data stored in the last registered leaf is
Since it can be approximated as data with a relatively long code length,
Further, there is an effect that the processing speed of data compression is significantly improved.

Further, according to the data restoration method of the technique 2 related to the present invention, similarly to the encoding side, in the process of newly registering the data, the code length of the leaf divided into two is (the leaf before the division). Code length + 1) bits, and the code length of newly registered data and the code length of a specific code can be set to a minimum of 2 bits, which makes it possible to decode a relatively large number of escape codes. In some cases, such as in the early stages when dictionary registration (symbol registration in the code tree) is not sufficient,
This has the effect of significantly improving the data decoding efficiency.

If the code length changing process is performed before the new data registration process, the code length of the decoded data code and escape code is at least 2 bits, and if the code length changing process is performed after the new registration process, The code of the escape code can be set to a minimum of 1 bit, which has the effect of significantly improving the data decoding efficiency. Further, the restoration side can perform the same new registration process as the encoding side, and thus there is an advantage that the data encoded by the encoding side can be accurately decoded.

Also in the above-described data restoration method, even if the specific code is an escape code defined in advance as data indicating unregistered, the same effect as the above-described data restoration method can be obtained. Further, according to another data compression device related to the technique 2 related to the present invention, when the data is such that a relatively large number of escape codes are output, or the context held in the context tree holding means is sufficiently registered. There is an effect that a high coding rate can be obtained in the initial stage or the like.

If the code updating means performs the code updating before the code registering means registers the code, the code length of the code and the specific code is at least 2 bits, and the code updating means performs the code updating after the code registering means registers the code. If the code is updated by, the code of the escape code can be set to a minimum of 1 bit, which has the effect of significantly improving the coding efficiency.

Further, since the new registration of the code by the code registration means is always performed one by one, only the data having reproducibility is registered in the higher order of the code tree, and the code tree is registered. However, it is possible to prevent a decrease in the coding efficiency caused by the existence of data that is not actually used, and this has the effect of significantly improving the coding efficiency after the data is sufficiently registered. Then, such an effect has the effect of dramatically improving the performance of the data compression apparatus.

Further, according to another data compression apparatus related to the technique 2 related to the present invention, in addition to the effect of the above-described data compression apparatus, the code length of the least frequently used data having the lowest appearance frequency is lengthened. As a result, there is an effect that the reduction of the coding efficiency due to the increase of the code length by 1 bit can be minimized and the processing speed of the data compression can be significantly improved, and the performance of the data compression device can be leapt. There is an effect that it improves.

Furthermore, according to still another data compression apparatus related to the technique 2 related to the present invention, in addition to the effect of the data compression apparatus described above, the new data stored in the last registered leaf is relatively coded. Since the data can be approximated as a long data, the processing speed of data compression is significantly improved, and the processing load of the data compression device is significantly reduced.

Further, according to the data restoration device of the technique 2 related to the present invention, when the data is such that the escape code is decoded in a relatively large number, or the context held in the context tree holding means is registered. There is an effect that a high decoding rate can be obtained in an insufficient initial stage. Further, if the code updating means performs the code updating before the code registering means registers the code, the code length of the code and the specific code is at least 2 bits, and the code updating means performs the code updating after the code registering means registers the code. By doing so, the code of the escape code can be set to a minimum of 1 bit, which has the effect of significantly improving the decoding efficiency.

Further, since new codes to be decoded by the code registering means are always registered one by one, only reproducible data is always registered in the high order of the code tree. It is possible to prevent a decrease in the decoding efficiency that occurs due to the existence of data that has been registered in, but is not actually used, and this has the effect of significantly improving the decoding efficiency after the data has been sufficiently registered. Then, such an effect has the effect of dramatically improving the performance of the data restoration device.

Further, according to another data decompression apparatus according to the technique 2 related to the present invention, in addition to the effect of the data decompression apparatus described above, the code length of the least frequently used data having the lowest appearance frequency is lengthened. As a result, there is an effect that the deterioration of the coding efficiency due to the extension of the code length by 1 bit can be minimized and the processing speed of the data recovery can be greatly improved. It also has the effect of improving.

Further, according to still another data restoration device of the technique 2 related to the present invention, in addition to the effect of the above-mentioned data restoration device, the last registered data of the data is stored. Can be done on the reef,
Since the data stored in this last registered leaf can be approximated as data with a relatively long code length, the decrease in decoding efficiency due to the increase of the code length by 1 bit is minimized and the processing speed of data restoration is improved. There is an effect that it can be greatly improved, and further, there is an effect that the performance of the data restoration device is dramatically improved.

Next, the technology 2 related to the present invention (hereinafter, also referred to as related technology 2) will be described more specifically.
That is, the data compression apparatus and the data decompression apparatus according to the related technique 2 are also for implementing the data compression method and the data decompression method of the present invention as shown in FIG. 32, as in the above-described embodiment.

Also in the related technique 2, the description will be made on the assumption that the data compression device is the encoding side and the data decompression device is the decompression side, as in the above-described embodiment. In the following description, the context tree and the code tree have the configurations described above in item (a). (1) Description of Encoding Side FIG. 52 is a diagram showing an example of the internal configuration of a data compression device 3 (see FIG. 32) for implementing the data compression method according to the related technique 2 of the present invention. At 52, 30
1B is a code tree holding unit, 302B is a context tree holding unit, 303
B is a context registration unit, 305B is a context change unit, 306B is an encoding unit, 307B is a code change unit, 321B is a context holding unit, and 322B is a code registration unit.

Here, a code tree holding unit (code tree holding means)
Reference numeral 301B holds a code tree in which an escape code (ESC) (data indicating that data has not been registered) is registered in advance. The context tree holding unit (context tree holding means) 302B is
It holds a context tree in which a combination of a symbol K (input data) and a context is registered. Further, the context registration unit (context registration means) 303B newly registers the symbol K in the context tree after encoding the escape code, and the context holding unit 321B receives the input symbol K.
Is held once.

The code registration unit (code registration means) 322B is
After the escape code is encoded, the leaf (data storage point) of the escape code of the code tree in the code tree holding unit (code tree holding means) 301B is branched to newly register the symbol K. Therefore, the code registration unit 322B has a new node ID generation unit 61, which will be described later with reference to FIG.
A latch 62 and a parent-child information updating unit 63 are provided, and an external node (leaf I) is provided inside the code tree holding unit 301B.
D) holding unit 64, internal node (node ID) holding unit 65,
An ESC-ID holding unit 66 and a code tree management unit 67 are provided.

Also, the context changing unit 305B determines that the symbol K
When the combination of and context is not stored in the context tree, it changes the context. The encoding unit 306B is
The code represented by "1" or "0" is output according to the branch from the vertex of the code tree to the leaf in which the escape code is registered.

The code updating unit 307B replaces the leaf in which the coded symbol K and escape code are registered with another leaf or node. Then, as shown in FIG. 53, in the code registration unit 322B, the new node ID generation unit 61 uses the context tree holding unit 3
02B receives an update signal and two new node IDs (I
D-1 and ID-2 are generated, and the latch 62 temporarily holds the escape code ID (ESC-ID).

Further, the parent-child information updating unit 63 has three pieces of information (ESC-ID) of the upper node ID of the node to be processed, the node ID of the lower node located at the lower right and the node ID of the lower node located at the lower left. , ID-1, ID-
Change the parent-child information by receiving the parent-child information consisting of 2),
It is sent to the code tree holding unit 301B. Furthermore, inside the code tree holding unit 301B, external nodes (leaf I
D) The holding unit 64 holds the leaf ID of the leaf that is the storage point of the code tree data, and the internal node (node ID) holding unit 65 holds the node ID of the node of the code tree. The ESC-ID holding unit 66 holds the escape code of the code tree and the ID of this escape code.

Further, the code tree management unit 67 receives the context ID from the context tree holding unit 302B and uses this context ID as the external node (leaf ID) holding unit 64 and the internal node (node ID).
It is sent to the holding unit 65 and the ESC-ID holding unit 66. With the above configuration, in the data compression device 3 according to the related technique 2 of the present invention, the code tree holding unit 301B holds the code tree in which the escape code is registered in advance, and the context tree holding unit 302B stores the symbol K and the context P. The context tree in which the combination is registered is held, and after the context registration unit 303B encodes the escape code, the symbol K can be newly registered in the context tree.

Furthermore, after the context holding unit 321B once holds the context P and the code registration unit 322B encodes the escape code, the leaf of the escape code of the code tree may be branched to newly register the symbol K. it can. Further, when the context changing unit 305B does not hold the combination of the input symbol K and the context P in the context tree,
The context P can be changed.

Further, the encoding unit 306B outputs a code according to the branch to the input data from the apex of the code tree or the leaf in which the escape code is registered, and the data and the escape code encoded by the code updating unit 307B are registered. One leaf can be replaced with another leaf or node. 57 (a) is a diagram showing an example of the code tree, and FIG. 57 (b) is a diagram showing an example of the context tree. By the way, as shown in FIG. 57 (a), the code tree has ID numbers (0 to 10) at the root and node as internal nodes and at the leaf as external nodes, respectively.

On the other hand, as shown in FIG. 57 (b), the context tree has the ID of the context and the ID number of the symbol registered in the context, and the ID number of the context is the ID of the root of the code tree. The numbers and the ID numbers of the symbols are the same as the leaf ID numbers of the code tree. Here, regarding the above operation,
This will be described in more detail with reference to process steps P1 to P16 showing the operation of the encoding side of the present invention shown in FIGS.

In the following description of the operation, it is assumed that the code tree and the context tree have the configurations as described above.
First, as shown in FIG. 54, when the symbol K is input (step P1), the context P held in the context holding unit 321B is output to the context changing unit 305B (step P2).

Then, in the context changing unit 305B, the context P
When the symbol K is not registered in the context P, the context tree holding unit 302B sends the context change signal to the context changing unit. Output to 305B (step P
3). Upon receiving the context change signal, the context change unit 305B rejects the highest-order character (the leaf having the longest distance from the root of the context tree) and lowers the degree by one to obtain the context P.
02B (step P4).

Then, this process is repeated until the context P in which the symbol K is registered is determined. Next, FIG.
As shown in FIG.
The (number) and the ID of the symbol K (ESC when the symbol K is not registered) are sent to the coding unit 306B (step P5), and the coding unit 306B sends the sent ID to the code tree holding unit 301B. Transfer as it is (Step P
6).

[0307] Then, the code tree holding unit 301B, the ID number of the upper node of the sent ID, and the coding unit 306.
Information indicating whether the ID sent by B is located on the right or the left with respect to the upper node is sent to the encoding unit 306B (step P7). Further, the encoding unit 306B is
I sent from the encoding unit 306B to the upper node
According to the position information of the node having D, for example, "1" is output if it is located on the right, and "0" is output if it is on the left (step P8).

Further, when the ID of the upper node sent together with the above-mentioned position information matches the ID (root ID) of the context P sent from the context holding unit 302B, the encoding process is ended. On the other hand, when they do not match, the ID of the context P is further output to the code changing unit 307B (the same route as in step P6), and the code tree holding unit 30 is further added.
The upper node ID and the position information are obtained from 1B.

Then, the process is repeated until the ID number of the upper node from the code tree holding unit 301B matches the ID of the context P. After this processing is completed, the code changing unit 307
B receives the ID of the context P (= root ID of the code tree) and the leaf ID of the encoded symbol K from the encoding unit 306B (step P9), performs node recombination processing (spray processing), and determines the code length. Update. The node recombining process is performed as described in item (a) and one embodiment of the present invention.

As a result, when the symbol K is previously input and registered in the context P, when the symbol K is further input, the node of the already registered symbol K is recombined with the upper node and the code is changed. The length can be shortened (1/2). By the way, in the above context P, the symbol K
56 is not registered, the context registration unit 310B receives the context P to be registered from the context changing unit 305B (step P10) and the symbol K (step P11), as shown in FIG. The ID of the registered symbol is output to the holding unit 302B (step P12), and the context tree holding unit 302B newly registers the symbol K under the context P.

On the other hand, the code registration unit 322B receives the code tree for registering the code from the code tree holding unit 301B (step P13), and registers the symbol K to be registered and the context tree holding unit 302.
In response to the registered symbol ID from B (step P1
4, 15), the symbol K is newly registered in the code tree and stored again in the code tree holding unit 301B (step P16). Thereby, the symbol K not registered in the context P is registered (encoded).

Here, the code registration unit 322B encodes the escape code and then branches the leaf of the escape code of the code tree in the code tree holding unit 301B to branch to the symbol K.
To newly register (the above-mentioned steps P13 to P1
6) will be described in more detail with reference to FIG. 53, as described above. First, the code tree management unit 67 provided inside the code tree holding unit 301B receives the context ID and sends the context ESC address to the ESC-ID holding unit in the code tree holding unit.

Then, the ESC-ID holding unit 66 uses the ES
While receiving the C address and outputting the ID of the ESC and the symbol (ESC in this case) registered in this ID,
In the code registration unit 322B, the latch 62 latches the ESC-ID and ESC. Further, the new ID generator 61 is
Upon receiving the update signal, two ID numbers (ID-1, ID-
2) is transmitted, and ID-1 stores the code tree holding unit 301B together with the ESC latched as a new ESC-ID.
Stored in the ESC-ID holding unit 66.

Further, in the code tree, in addition to the ID and the symbol, parent-child information representing the position information of the ID is held.
The parent-child information includes three pieces of information, that is, a higher-level node ID of itself, a node ID located at the lower right of the own, and a node ID located at the lower left of the own. The parent-child information updating unit 63
Three IDs (ESC-ID, ID-1, ID-before change)
In response to 2), change the parent-child information. That is, ID-
1, ESC-ID is registered as the higher ID of ID-2,
Also, ESC-ID has ID-1 at the lower right and ID- at the lower left.
Information that 2 is located is registered.

The parent-child information is held in the node ID holding unit 65 of the code tree holding unit 301B together with each ID. on the other hand,
A registration symbol and a new ID (ID-2) are registered in the leaf ID holding unit 64 of the code tree holding unit 301B. By performing the above processing, a new ES is added to the ESC.
The C-ID (ID-1) is registered, the old ESC-ID is stored as a node ID in the node ID holding unit together with parent-child information, and the new ID (ID-2) and the symbol K are stored in the leaf ID holding unit as a new leaf. The processing of holding the symbol K and newly registering the branch of the leaf of the code tree holding unit 301B in which the escape code of the code tree is registered ends.

The operations described with reference to FIGS. 53 to 56 can be summarized as the flow chart shown in FIG. That is, first, 0 is input to the context P ₀ for initialization (step Q1), and the context P ₀ is input to the context P as a variable (step Q2). The context P ₀ is a character (symbol) that has been input / encoded until immediately before,
For example, when the encoding in the present embodiment is a model that uses an nth-order context, the context P ₀ is input by just before.
This means that the encoded (n-1) characters are stored.

Then, when the symbol K is input, it is searched whether or not the symbol K is registered in the context tree of the context P (step Q3). When the symbol K is not registered in the context tree of the context P, the code of ESC (escape code) is output (from NO route of step Q3 to step Q4), and the ESC of the code tree corresponding to the context P is registered. Spraying the existing leaf (step Q
5).

Then, the leaf of the above ESC is branched (step Q6), the ESC and the symbol K are registered in the two new leaves thus obtained (step Q7), and the context P
The symbol K is also registered in the context tree of. Furthermore, after newly registering the symbol K as described above, the oldest character in the context P is rejected, and the context P is changed to a new context P by changing the context P by one (step Q
8).

Then, returning to step Q3, the symbol K
Until it finds that is registered in context P.
Are sequentially changed and the process is repeated. On the other hand, if the symbol K is registered in the context tree of the context P, the code of the symbol K is output (from the YES route of step Q3 to step Q3).
9) The leaf in which the symbol K of the code tree corresponding to this context P is registered is subjected to the spray processing (SPLAY) (step Q10).

Furthermore, after encoding the symbol K, the context P ₀
The symbol K is additionally registered to update the context P ₀ (step Q11). (E.g. by adding the symbol K in the context P _0, rejects the oldest character in the context P _0). And
It is checked whether or not all the characters (symbols) have been encoded (step Q12). If not (NO route of step Q12), the process returns to step Q2 to encode all the characters. The process is repeated until the end.

Further, in the above-described processing in FIG. 58, the ESC leaf spray processing is performed after the ESC and the symbol K are registered. However, this processing order may be reversed, and the processing steps in this case are As shown in FIG. 59. Here, as shown in FIG. 59, in steps R1 to R3 and steps R9 to R12, the same processing as the processing steps Q1 to Q3 and steps Q9 to Q12 of FIG. 58 is performed, respectively.

If the symbol K is not registered in the context P in step R3, the ESC code is output (step R4), the ESC leaf is branched (step R5), and the ESC and the symbol K are added to the new leaf. Is registered (step R6). Then, after performing the registration as described above, the leaf of the ESC is sprayed (step R7).

Further, as in the processing step Q8 of FIG. 58, the context P is changed (step R12), and the step R3 is executed.
The process is repeated until the symbol K is detected at. For example,
When the code tree is in a state where characters (symbols) A to E have already been coded and registered as shown in FIG. 60A, the above-described processing steps R1 to R12 (or the processing in FIG. 58) are performed. In steps Q1 to Q12), when the process is executed with the symbol K as the character F, the leaf of the ESC with the leaf number 6 is branched, and as shown in FIG. The ESC and the letter F are registered in each leaf.

For example, when the context used in the above processing is the third-order context, the symbol K is the 0th-order (initial state).
When encoded with, the information is registered in each of the first-order, second-order, and third-order contexts (hereinafter, the method of registering in all the orders is referred to as the full registration type). 58 and 59.
Steps Q1 to Q12 and steps R1 to R shown in
As described above, reference numeral 12 denotes a step of the process of registering the symbol K in the context of all the orders each time the ESC is coded. However, the coded (registered) order immediately before the symbol K is coded. The processing may be performed so that the symbol K is registered only in one context of the above, and the processing flowchart in this case is as shown in FIG. 61.

That is, in the processing shown in FIG. 61, first,
The context P ₀ is initialized to 0 (step T1), the context P ₀ is input to the context (variable) P, and the context P is input to 0 (step T2). Furthermore, it is searched whether the symbol K is registered in the context P (step T3), and the context P
If the symbol K is not registered in, the processing similar to the above-mentioned steps Q4 and Q5 (see FIG. 58) is performed (from NO route of step T3 to steps T4 and T5).

Then, the context P is input to the context X (step T6), the context P is changed (step T7), and the context P is changed.
The process is repeated until it is detected that the symbol K is registered in. On the other hand, when the symbol K is registered in the context P in the above step T3, the above-mentioned steps Q9 to Q11 (see FIG. 58) or step R9 to.
Processing similar to that of R11 (see FIG. 59) is performed (steps T8 to T10).

After that, the leaf of the ESC of the context X is branched (step T11), and the ESC and the symbol K are respectively registered in the two branched new leaves (step T12). Further, it is checked whether or not all characters (symbols) have been encoded (step T13). If not completed, the processes after step T2 are repeated (NO route of step T13), and if completed. The encoding process ends (YES route 9 in step T13).

By performing the processing in this way, the symbol K is not registered in the contexts P of all orders, but
Registration can be performed only in the context (context X) of the immediately preceding order in which the symbol K is encoded (hereinafter, the method of registering a symbol only in the context of the immediately preceding order is referred to as a sequential registration type). As described above, according to the data compression device of Related Art 2 of the present invention, when the symbol K is not registered in the context P, the code length for branching / registering the escape code (ESC) is set to (the value of the leaf before division). Code length + 1) bits,
By setting the code length of the newly registered code and escape code to a minimum of 2 bits, if the data is such that a relatively large number of escape codes are output, or dictionary registration (symbol registration in the code tree) is not sufficient. There is an effect that a high coding rate can be obtained in the initial stage.

If the spray process is performed before the new registration of the symbol as described above, the code length of the code and the escape code is at least 2 bits, and if the spray process is performed after the new registration, the code of the escape code is minimized. Since it can be set to 1 bit, there is an effect that the coding efficiency is further improved. Furthermore, in the case of the above-described sequential registration type, new registration of symbols in the code tree is always performed one by one, and the same symbol appears twice and three times, so that secondary and tertiary registration is performed. Only the symbols with reproducibility are always registered in the higher order of the code tree, and the coding efficiency of the code tree that occurs because there are symbols that are registered in the code tree but are not actually used Is also prevented, and the coding efficiency after the dictionary is sufficiently registered is greatly improved.

Further, the sequential registration type has an advantage that it uses less memory capacity (dictionary capacity) than the all registration type. (2) Description of Restoration Side FIG. 62 is a diagram showing an internal configuration example of the data restoration device 4 (see FIG. 32) for carrying out the data restoration method according to the related technique 2 of the present invention. At 40
1B is a code tree holding unit, 402B is a context tree holding unit, 403
B is a context changing unit, 404B is a decoding unit, 407B is a code registration unit, 408B is a context registration unit, 409B is a latch, and 42
1B is a context holding unit.

Here, the code tree holding unit (code tree holding means)
401B holds a code tree in which an escape code (ESC) (data indicating that data has not been registered) is registered in advance. The context tree holding unit (context tree holding means) 402B is
It holds a context tree in which a combination of a decoded symbol (data) and a context is registered. Further, the context changing unit 403B searches the context tree held in the context tree holding unit 402B, and changes the context when the leaf that arrived is an escape code, and the decoding unit 404B.
When the symbol K coded on the coding side is input, the code tree holding unit 40 follows the code of the symbol K.
The code of the symbol K is decoded by scanning from the root (vertex) of the code tree held in 1B to the leaf (data storage point).

Further, the code changing unit 406B replaces the leaf of the decoded symbol K and escape code with another leaf or a node as a branch point. Further, the code registration unit (code registration means) 407B also has a function as a code tree determination means, and the symbols K are decoded from the symbols decoded up to immediately before decoding the symbol K.
The code tree in the code tree holding unit 401B in which the code is registered is determined, and when the escape code is decoded, the leaf of the escape code registered in this code tree is branched to create a new leaf, The decoded symbol K is newly registered in this leaf.

Therefore, the code registration unit 407B and the above-described code tree holding unit 401 respectively include the code registration unit 322B and the code tree holding unit 301B (see FIG. 52) on the encoding side.
(See FIG. 53). In addition, the context registration unit 408B is the code registration unit 407.
The symbol K registered in B is registered in the context tree held in the context tree holding unit 402B.
B temporarily holds the symbol K decoded by the decoding unit 404B, and the context holding unit 421B holds the decoded symbol K.

The code tree holding unit 401B described above can hold a code tree in which escape codes have been registered in advance, and the context tree holding unit 402B registers a context in which a combination of the decoded symbol K and context P is registered. It can hold trees. Furthermore, the context changing unit 403
When the leaf that has arrived is an escape code by B, the context can be changed, and the decoding unit 404B scans from the root of the code tree to the leaf according to the code of the encoded symbol K to determine the symbol K. The code can be decoded.

Further, the code changing section 406 which also functions as code tree determining means can determine the code tree in which the code of the symbol K is held from the symbols decoded up to immediately before, and the code tree of the decoded symbol K and the escape code can be determined. A leaf can be recombined with other leaves or nodes. Further, when the escape code is decoded by the code registration unit 407B, a leaf of the escape code can be branched to create a new leaf, and the decoded symbol K can be newly registered in this leaf.

Further, the context registration unit 408B transfers the symbol K registered by the code registration unit 407B to the context tree holding unit 40.
2B context tree, the latch 409B can temporarily hold the symbol K decoded by the decoding unit 204B, and the context change holding unit 421 can hold the decoding unit 2B.
It is possible to hold the symbol K decoded in 04B.

Then, the above-mentioned operation will be described in more detail with reference to the processing steps U1 to U14 showing the operation on the restoration side shown in FIGS. 63 and 64, similarly to the description on the encoding side. First, as shown in FIG. 63, the context holding unit 4
21B holds the symbol (context) decoded up to that point and outputs it to the context changing unit 403B (step U1), and the context changing unit 403B outputs the initially sent context as it is to the context tree holding unit 402B. (Step U2).

Further, the context tree holding unit 402 outputs the context ID sent from the context changing unit 403B, that is, the root ID to the decoding unit 404B (step U3). Here, in the decoding unit 404B, if the code (1 bit) for the route ID sent is, for example, "1", the lower right corner,
If it is "0", the node (or leaf) located at the lower left
Request the ID to the code tree holding unit 401B (step U
4).

Also, the code tree holding unit 401B decodes the node ID of the requested node (or leaf) into the decoding unit 40.
4B (step U5). Then, the decryption unit 40
4B and the code tree holding unit 401B repeat the above processing until the leaf ID of the leaf that is the end of the code tree is obtained.
That is, the decoding unit 404B follows the code tree of the code tree holding unit 401B according to the code encoded on the encoding side until the symbol K to be decoded reaches the registered leaf.

When the target leaf is found, the decoding unit 404B decodes this leaf and the code changing unit 40
6B performs a spray process on the decoded leaf in the same manner as the encoding side to update the code length. Here, when the symbol decoded by this processing is ESC, the decoding unit 4
04B sends this symbol (ESC) to the latch (step U6), and the latch temporarily holds this symbol,
It is sent to the context changing unit 403B (step U7). The context changing unit 403B performs the same context changing process as on the encoding side and performs decoding again.

When the symbol decoded by the decoding unit 404B in the above processing is other than ESC, that is, the symbol K, the decoding unit 404B, as shown in FIG.
The decoded symbol K is sent to the context registration unit 408B via the latch 409B and the context holding unit 421B (steps U8 to U11), and the context registration unit 408B newly registers this symbol K in the context tree holding unit 402B.

The code registration unit 407B receives the root ID of the context P in which the symbol K is registered from the context tree holding unit 407B (step U12), and sends this root ID to the code tree holding unit 401B (step U13). ). In the code tree holding unit 401B, the root ID of the sent context P
The root ID of the code tree having the same root ID as the above is returned to the code registration unit 407B (step U14), and the code registration unit 407B registers the new code of the symbol K in the code tree having this root ID (step U14). Same route as U13).

The code registration unit 407B on the restoration side described above.
The process of registering the symbol K in the code tree holding unit 401B is similar to the process of registering the symbol K in the code tree holding unit 301B by the code registration unit 322B on the encoding side.
Therefore, when the registration process on the encoding side is the full registration type as shown in FIGS. 58 and 59 in the description of the encoding side, the restoration side also registers all the ESCs in all the decoded contexts. In the case of the registration type, and in the case of the sequential registration type as shown in FIG.
It is a sequential registration type in which the symbol K is registered in the context of SC respectively.

Then, similar to the description on the encoding side, the above-mentioned processing on the restoration side can be represented by a flowchart as shown in FIG. That is, the numerical value of the maximum degree is input to the context (variable) P ₀ for initialization (step V1), and this context P ₀ is input to the context P (step V2). That is, when decoding the code, first, the processing is performed using the context of the maximum degree.

Then, in the code tree corresponding to the context P of the maximum degree, the code registered in the leaf is decoded (step V3). Furthermore, it is checked whether the decoded code is a symbol (step V4), and if the decoded code is not a symbol, that is, ESC, the leaf of the decoded ESC is spray-processed as in the encoding side. (From NO route of step V4 to step V
5) The highest-order symbol (oldest symbol) in the context P is rejected, the context is moved to the next lower order to be changed (step V6), and the process returns to step 2. That is, until the symbol (symbol K) other than the ESC is decoded, the context P is changed to the context obtained by subtracting 1 from the highest order, and the context P in which the symbol K is registered is searched.

On the other hand, if the decoded code is a symbol, it means that the symbol K has been decoded, so this symbol K is output (YES route from step V4 to step V7), and this symbol K leaf is coded. The code length of the symbol K is shortened (updated) by performing the spray process in the same manner as the digitization side (step V8). Further, the symbol K is additionally registered in the context P ₀ (step V9), and the ESC is rejected. It should be noted that the process of changing the context P ₀ is the same as that on the encoding side.

Furthermore, regarding the decoded symbol K, the same registration method as that on the encoding side, for example, if the registration method of the symbol K on the encoding side is the full registration type, the ESC leaf is branched according to the full registration type, and a new The symbol K is registered (step V10). Then, it is checked whether the decoding of all the inputted codes has been completed (step V11), and if not completed (NO route of step V11), the process returns to step V2 and the decoding of all the codes is completed. The process is repeated until

As described above, according to the data decompression apparatus of the related technique 2 of the present invention, similarly to the encoding side, in the symbol new registration processing, the leaf already existing on the code tree is divided into two. Then, by setting the code length of this leaf to (the code length of the leaf before division + 1) bits, the code length of the newly registered symbol K and the escape code can be set to a minimum of 2 bits. If the data is such that a relatively large number of codes are decoded,
Alternatively, there is an effect that the data decoding efficiency is significantly improved in the initial stage where the dictionary registration (the registration of the symbol in the code tree) is not sufficient.

If the spray process is performed before the new registration of the symbol as described above, the code length of the decoded symbol and the code length of the escape code are at least 2 bits, and if the spray process is performed after the new registration, the escape code is obtained. Since the code of can be set to 1 bit at the minimum, there is an effect that the decoding efficiency of data is significantly improved. Furthermore, as described above, there is an advantage that the decoding side can perform the correct decoding by performing the same registration processing as the encoding side. (C-1) Description of First Modified Example of Related Technology 2 A data compression apparatus and a data decompression apparatus according to a first modified example of Related Technology 2 are also shown in FIG. It is for implementing a data compression method and a data decompression method.

Further, as in the case of the related technique 2 described above, the data compression device 3 will be described below on the encoding side and the data decompression device 4 will be described on the decompression side. (1) Description of Encoding Side The configuration of the encoding side is as shown in FIG.
The configuration is the same as that described in 2 above.

Further, in the code registration unit 322B shown in FIG. 52 in the related technique 2, in order to register a symbol in the leaf having the longest code length on the code tree held in the code tree holding means 301B, As shown at 66, a new node ID generating unit 61, a latch 62, a parent-child information updating unit 63, and a longest code detecting unit (branch position searching means) 69 are provided, and correspondingly, a code tree holding unit 301B. Is provided with an internal node (node ID) holding unit 65, a code tree management unit 67, and an external node / ESC-ID (leaf ID) holding unit 68.

Inside the code registration unit 322B, the new node ID generation unit 61 has the context tree holding unit 302.
Upon receiving the update signal from B, two new node IDs (ID-
1, ID-2) is generated, and the latch 62 is
The leaf ID detected by the longest code detector 69 is latched. Further, the parent-child information updating unit 63 has three pieces of information (ESC-ID, ID-) of the upper node ID of the processing target node, the node ID of the lower node located at the lower right, and the node ID of the lower node located at the lower left. 1, ID-2)
It receives the parent-child information consisting of, changes the parent-child information, and sends it to the code tree holding unit 301B.

Longest code detecting section (branch position searching means) 69
Is a leaf ID having the longest code length in the code tree obtained from the code tree holding unit 301B.
(ID-0) is detected. In addition, inside the code tree holding unit 301B, the internal node (node ID) holding unit 65 holds the node ID of the code tree, and the external node / ESC-ID (leaf ID) holding unit 68.
Holds the leaf ID of the code tree.

The code tree management unit 67 has a context tree holding unit 302.
Upon receiving the context ID from B, the context ID is stored in the internal node (node ID) holding unit 65 and the external node / ESC-I.
It is sent to the D (leaf ID) holding unit 68. Since the code registration unit 322B and the code tree holding unit 301B have the above-described configurations, the code registration unit 322B searches for the leaf having the longest code length on the code tree held in the code tree holding unit 301B and escapes. After encoding the code, the leaf having the longest code length searched is branched and a symbol K is newly registered.

Further, the above-mentioned processing will be described in detail with reference to the processing steps W1 to W13 of the flowchart shown in FIG. First, in order to search the context including the symbol K, the context (context P) held in the context tree holding unit 302B is selected (steps W1 and W2),
It is checked whether the symbol K is registered in this context P (step W3), and if it is registered, steps Q9 to Q1 described above with reference to FIG. 58 in the description of the third embodiment.
The same process as 2 is performed (steps W9 to W12).

On the other hand, when the symbol K is not registered in the context P, the coding unit 306B outputs the code of ESC (step W4) similarly to the steps Q4 to Q5 of FIG. 58, and the code changing unit 307B. Is the code tree holding unit 301
The leaf of the ESC of the code tree held in B is sprayed (step W5). After that, the code tree holding unit 30
1B uses the ID (root ID) of the context P as the context tree holding unit 3
02B, the node ID of this context P and the parent-child information are sent to the longest code detection unit 69.

The longest code detecting section 69 detects the ID (ID-0) of the leaf X (p) having the longest code length from the parent-child information (step W6). And the detected leaf X
The ID of (p), ID-0, is sent to the leaf ID holding unit 68, and the symbols stored in the ID-0 and ID-0 are latched by the latch 70.

Further, the new node ID generating section 71 generates two new node IDs (ID-1, ID-2), and the parent-child information updating section 63 has three IDs (ID-0, ID-).
1, ID-2), the parent-child information is updated and registered in the node ID holding unit 65 of the code tree holding unit 301B. on the other hand,
In the leaf ID holding unit 68 of the code tree holding unit 301B, the registered symbol K and the new ID (ID-2), and the symbol registered in ID-0 and the ID-1 are respectively registered as new leaves (step W7). .

By performing the above processing, the leaf having the longest code length becomes a node, and two new leaves are registered under this node. Then, the context P is changed (step W8), and the above processing is repeated until it is detected that the symbol K is registered in the context P. As described above, according to the data compression apparatus of the first modification of Related Technique 2 of the present invention, in addition to the effects described above on the encoding side, the code tree of the context P has the longest code length. The leaf X (p) (farthest from the route) is detected, and this leaf X (p) is branched to obtain symbols K and X.
The symbol registered in (p) is newly registered in the code tree. As a result, "longest code length" = "symbol with the lowest frequency of occurrence", it is possible to minimize a decrease in coding efficiency due to a 1-bit increase in code length, and to reduce the processing speed of data compression. And the processing load of the data compression device can be significantly reduced.

(2) Explanation of Restoration Side Data Restoration Device 4 According to First Modification of Related Art 2
62 has the same configuration as that described above with reference to FIG. 62, and further, the code registration unit 40 on the restoration side.
7B and the code tree holding unit 401B have the same internal configurations as the code registration unit 322B and the code tree holding unit 301B on the coding side, respectively (see FIG. 66). Therefore, the code registration unit 407B and the code tree holding unit 401B are equivalent to the code registration unit 322B and the code tree holding unit 301B on the coding side.
Since it has the same configuration as the above, the code registration unit 407B
However, the process of newly registering the code of the decoded symbol in the code tree holding unit 401B is the same as that on the encoding side.

Therefore, the process of decoding the symbol K coded on the coding side may be performed in the same manner as the process (steps V1 to V11) described above with reference to FIG. 65 in the third embodiment. At step V10 in 65, processing steps W7 and W8 (see FIG. 67) on the encoding side may be performed. As described above, according to the data decompression device of the first modification of the related technique 2 of the present invention, as in the encoding side, the code tree of the context P has the longest code length (the distance from the root is The "farthest" leaf X (p) is detected, this leaf X (p) is branched, and the symbols registered in the symbols K and X (p) are newly registered in the code tree. Since “code length” = “symbol with the lowest appearance frequency”, in addition to the effect on the restoration side of the related technique 2 described above, the decrease in the decoding efficiency of data due to the extension of the code length by 1 bit is minimized. Therefore, the processing speed of data decoding can be significantly improved, and the processing load of the data restoration device can be significantly reduced.

Further, as described above, by making the symbol decompression side registration processing the same as the encoding side registration processing, it is possible to accurately decode the code of the symbol encoded by the encoding side. There is an effect that can be. (C-2) Description of Second Modification of Related Technique 2 (1) Description of Encoding Side In this modification, the configuration on the encoding side is similar to that described above with reference to FIG. 52.

In order to register a symbol by branching a leaf newly registered on the code tree held in the code tree holding means 301B, to the code registration unit 322B shown in FIG. In addition, a new node ID generating unit 61, a latch 62, a parent-child information updating unit 63, and a latest registration ID holding unit 70 are provided.
B has an external node (leaf ID) holding unit 64, an internal node (node ID) holding unit 65, an ESC-ID holding unit 66, and a code tree management unit 67.

Here, in the above-mentioned configuration, the same reference numerals as those already described in FIG. 53 or FIG.
The description is omitted. The latest registration ID holding unit (branch position holding means) 70 newly provided in the related technique 2
Holds the ID of the leaf that was last (newly) registered in the code tree held in the code tree holding unit 301B.

Code registration unit 322B and code tree holding unit 3
Since 01B has the above-mentioned configuration, the code registration unit 322B branches the latest leaf in which the symbol is last registered in the code tree held in the code tree holding unit 301B, and this new The symbol K can be newly registered in the created leaf. The above process will be described in more detail below with reference to process steps X1 to X13 in FIG.

In the above process, the latest registered leaf ID registered last is held in the latest registration ID holding unit 70,
New registration is performed by branching the ID. First, in order to search the context including the symbol K, the context (context P) held in the context tree holding unit 302B is selected (steps X1 and X2), and the symbol K is registered in this context P. If it is registered (step X3), if it is registered, the same processing as steps W10 to W13 described above with reference to FIG. 67 in the modification of the third embodiment is performed (YES route of step X3). To step X
10 to X13).

On the other hand, when the symbol K is not registered in the context P, the coding unit 306B outputs the ESC code (step X4) and the code changing unit 307B, similarly to steps W4 to W5 of FIG. Is the code tree holding unit 301
The leaf of the ESC of the code tree held in B is sprayed (step X5). After that, the code tree holding unit 30
1B outputs the ID (root ID) of context P to the latest registration ID holding unit 70 as it is.

In the latest registration ID holding unit 70, this context P
The leaf ID (ID-0) of the latest registered leaf X (p) corresponding to the code tree is the leaf ID of the code tree holding unit 301B.
The data is sent to the holding unit 64, and the ID-0 and the symbol stored in the ID-0 are latched by the latch 62. New ID generator 6
1 generates two new IDs (ID-1, ID-2), and the parent-child information updating unit 63 generates three IDs (ID-0, I
D-1 and ID-2) are received to update the parent-child information to branch the leaf X (p) (step X6), and this information is registered in the node ID holding unit 65 of the code tree holding unit 301B.

On the other hand, the leaf ID of the code tree holding unit 301B
The registered symbol K and the symbol registered in the leaf X (p) are respectively registered in the holding unit 64 as new leaves (steps X7 and X8), and the new registration ID holding unit 70 stores the new ID. Register a certain ID-2. Then, the context P is changed (step X9), and the above processing is repeated until it is detected that the symbol K is registered in the context P.

By performing the above processing, whenever a new symbol K is input, the latest registered leaf registered immediately before the symbol K is input is divided and the symbol K is registered in this leaf. To do. As described above, according to the data compression device of the second modification of the related technique 2,
By newly registering a symbol in the code tree, branching the leaf of the symbol registered immediately before and registering it in this leaf approximates to "symbol of the leaf registered immediately before" = "symbol with a relatively long code length". Therefore, as described above in the first modified example of the third embodiment, the process of detecting the leaf having the longest code length can be omitted, and the processing speed of data compression can be significantly improved. is there.

(2) Description of Restoration Side The construction on the restoration side is the same as the construction described above with reference to FIG. 62, similarly to the coding side, and further, the code registration section 407B and the code tree holding section on the restoration side. Reference numeral 401B denotes a code registration section 322B and a code tree holding section 3 on the encoding side.
It has the same internal configuration as 01B (see FIG. 68).

Therefore, since the code registration unit 407B and the code tree holding unit 401B have the same configurations as the code registration unit 322B and the code tree holding unit 301B on the coding side, the first embodiment of the third embodiment will be described. Similar to the restoration side in the modification, the process of newly registering the code of the symbol decoded by the code registration unit 407B in the code tree holding unit 401B is performed in the same manner as the process on the coding side.

Therefore, also on the main restoration side, the process of decoding the symbol K coded on the coding side is performed in the same manner as the process (steps V1 to V11) described above with reference to FIG. That is, also in the processing step V11 in FIG. 65, steps X6 to X6 in FIG.
Processing similar to that of X8 is performed. As described above, according to the data decompression apparatus of the second modification of Related Technique 2, when a symbol is newly registered in the code tree, the leaf of the previously registered symbol is branched as in the encoding side. By registering in this leaf, it is possible to approximate “symbol of the leaf registered immediately before” = “symbol with a relatively long code length”. Therefore, as described above in the first modification of the third embodiment, It is possible to omit the process of detecting a leaf having a code length, and there is an effect that the processing speed of data decoding is significantly improved.

By thus making the new registration process of the symbol in the code tree the same as the registration process on the encoding side, the decoding process of the symbol encoded on the encoding side can be performed accurately. There is also an effect that can be done. In addition, in the above-mentioned related technique 2 and each modified example, the method described on the encoding side is
In order to switch depending on the data to be encoded or the system, an ID number indicating which method is used is added to the header portion before transmission of the coded data, and the restoration side uses the registration method used from the ID number on the encoding side. May be selected.

[0375]

As described above in detail, according to the data compression method of the present invention as set forth in claim 1, in the data compression method for encoding and compressing the input data according to the history that has appeared in the past, the input data And a context collection process that holds a combination of contexts consisting of n pieces of continuous data up to that point, a code tree holding process that holds a code tree independent for each context, and data corresponding to the context of the context collection process. When it appears, it outputs a code defined as unique data according to the branch of the node as a branch point from the root that means the vertex of the code tree to the leaf as the point where the data on the code tree is stored. Since it has a code output step and a code length changing step of rearranging a leaf of data and a leaf or node of other data after the processing in the code output step, the frequency of input data Then, a two-step process of constructing a probabilistic model, assigning a code to each input data, creating a code table, and outputting the code of the character to be encoded from this code table can be performed at the same time. This has the effect of significantly improving the processing speed. Further, it is possible to omit an enormous amount of arithmetic processing of reconstructing a stochastic model that has already been constructed each time data is input, which has the effect of further increasing the speed of compression processing. Furthermore, as the same data as the input data that has appeared in the past appears repeatedly, the code of the data can be represented by a smaller number of bits, which also has the effect of significantly improving the compression effect in data compression.

Further, according to the data compression method of the present invention described in claim 2, in addition to the steps of the data compression method of the present invention described in claim 1, the combination of the input data and the context is the context. It has a context discriminating process for discriminating whether or not it is held in the collecting process, and an escape code holding process for holding a leaf in which an escape code defined as data indicating data unregistered is registered in a code tree in advance. , When the combination of input data and context is a combination that is not held in the history of the context collection process, an escape code is output and the context of the data is shortened until the combination held in the context collection process is obtained. Is repeated, so that in addition to the effect of the data compression method of the present invention according to claim 1, All combinations of history with pulse may not keep registered in advance, thereby the processing speed of data compression has the effect of greatly improved. Furthermore, it is possible to shorten the time until the combination of the input data and the context is obtained, which has the effect of significantly improving the processing speed of data compression.

According to the data compression method of the present invention as defined in claim 3, in addition to the steps of the data compression method of the present invention as defined in claim 2, the combination of input data and context is contextual. When the combination is not held in the history of the collection process, the combination of the input data and the context is newly registered in the context collection process, and the combination of the input data and the context is the history of the context collection process. If the combination is not stored in the above, the process has a code tree new registration process for newly registering data in the code tree corresponding to the context, and the combination of the input data and the context is stored in the history of the context collection process. When the combination is not held, the escape code code is output and at the same time, the combination of the input data and the context is registered in the history and Is registered in the code tree corresponding to the context, and the process of shortening the context of the data is repeated until the combination held in the context collection process is obtained. Therefore, the present invention according to claim 2 above. In addition to the effect of the data compression method, it is possible to newly register input data that was not previously registered in advance, and the newly registered data can be encoded at an early stage in the next encoding process. This has the effect of significantly improving the data compression effect as the encoding process progresses.

Further, according to the data compression method of the present invention described in claim 4, there are the same steps as those of the data compression method of the present invention described in claim 3, respectively, and the context new registration step and the code are added. In the tree new registration process, since only the combination of the context and the data immediately before determined to be in the history is registered, in addition to the effect of the data compression method of the present invention according to claim 3, It is not necessary to register all the combinations of contexts and data that have been determined not to be in the history of past input data, which has the effect of significantly improving data compression processing. Further, it is possible to give (register) a code only to the data having a high appearance frequency, which has the effect of significantly improving the data compression efficiency.

According to the data restoration method of the present invention as defined in claim 5, in the data restoration method for restoring the coded data obtained by coding the input data according to the history of the past input data, the decoded data and the context are Collection process that retains the history of the combination of codes, code tree retention process that retains each independent code tree according to context, and code tree determination process that determines the code tree of data from the context of the data decoded up to immediately before And a decoding process of decoding data from the code tree and the code of the data determined in the code tree determination process, and a leaf as a data storage point on the code tree by the same means as the encoding side after the decoding process. Since it has a code length changing process of recombining a space or a leaf and a node as a branch point of a code tree, a probability model is constructed by obtaining the appearance frequency of the input data, and the probability model is constructed for each input data. The Create an assignment code table No., it can be processed in two steps of outputting a character to be decoded from this code table at the same time, thereby the speed of the data restoration processing is the effect of greatly improved. Also, it is possible to omit a huge amount of arithmetic processing of reconstructing a stochastic model that has already been constructed each time data is input,
This also has the effect of further increasing the speed of restoration processing. Further, as the code of the same data as the code of the input data that has appeared in the past repeatedly appears, the code of the data can be represented by a smaller number of bits, which also has the effect of significantly improving the restoration effect in the data restoration. .

Further, according to the data restoration method of the present invention as set forth in claim 6, each step has the same steps as those of the data restoration method of the present invention as set forth in claim 5, and the code tree has each step. If an escape code, which is defined as data indicating unregistered data, is registered in advance for each code tree according to the context and the escape code is decoded at the time of decoding, the length of the context is shortened until a code other than the escape code is decoded. Since the processing is repeated, in addition to the effect of the data restoration method of the present invention according to claim 5 described above, it is not necessary to previously register all the histories of the combination of the decoded data and the context. This has the effect of significantly improving the processing speed of data restoration. Furthermore, it is possible to shorten the time until the combination of the decoded data and the context is obtained, and this also has the effect of significantly improving the processing speed of data restoration.

According to the data restoration method of the present invention as set forth in claim 7, in addition to each step of the data restoration method of the present invention as set forth in claim 6, a context for newly registering data in the context collection step It has a new registration process and a code tree new registration process for newly registering the decoded data in the code tree according to the context, and when the escape code defined as the data indicating the data unregistered is decoded, the context Since the process of shortening the length of the context is repeated until the process other than the escape code is executed by executing the new registration process and the code tree new registration process, the present invention according to claim 6 above. In addition to the effect of the data restoration method, it is possible to newly register the decrypted data that has not been previously registered in the past, and the newly registered decrypted data also Of it can be decoded at an early stage in the decoding process, thereby restoring the effect of the data as the decoding process progresses there is an effect to greatly improve.

Further, according to the data restoration method of the present invention as defined in claim 8, the data restoration method according to claim 5 has the same steps as those of the data restoration method, and is defined as data indicating unregistered data. When a single escape code is decoded in the process until the code other than the escape code is decoded, each new registration in the context new registration process and code tree new registration process is performed only in the context immediately before decoding the non-escape code. Since the processing is performed, in addition to the effect of the data restoration method of the present invention according to claim 7, it is necessary to register all the combinations of the context and the data determined not to be in the history of the past input data. This has the effect of significantly increasing the processing speed of data restoration. Further, it is possible to give (register) a code only to the data having a high appearance frequency, which has the effect of significantly improving the data restoration efficiency.

According to the data compression apparatus of the present invention as defined in claim 9, in the data compression apparatus which encodes and compresses the input data according to the history that has appeared in the past, the input data is input just before the input data. Prefix data holding means for holding a context consisting of n pieces of input data, history holding means for holding a combination of input data and context, code tree holding means for holding an independent code tree for each context, and Data is stored from a code tree determining unit that determines the code tree of data from the input data until immediately before being held in the unit data holding unit, and a root that means the vertex of the code tree selected by the code tree determining unit. Code output means for outputting unique data according to a branch from a node as a branch point located along the leaf, and the encoded leaf and another leaf or node Since it is composed of a code length changing means for rearranging and a prefix data updating means for registering data in the prefix data holding means, each input data is constructed by constructing a probability model by calculating the appearance frequency of the input data. A two-step process of assigning a code to a code table and creating a code table from the code table and outputting the code of the data to be coded can be performed at the same time. is there. Further, it is possible to omit an enormous amount of arithmetic processing of reconstructing a stochastic model that has already been constructed each time data is input, which also has the effect of further improving the processing speed of data compression. Also, every time the same data as the coded data in the past appears, the coded leaf and another leaf or node can be recombined to change the code length. The code of data can be represented by a small number of bits, which also has the effect of significantly improving the data compression effect.

Further, according to the data compressing apparatus of the present invention as set forth in claim 10, in the data compressing apparatus which encodes and compresses the input data according to the history that has appeared in the past, the data is inputted just before the input data. Prefix data holding means for holding a context consisting of n pieces of input data, history holding means for holding a combination of the input data and the context, and a context in which an escape code defined as data indicating unregistered data is registered in advance. Code tree holding means for holding an independent code tree for each, code tree determining means for determining the code tree of data from the context and input data, and whether or not data is registered in the code tree determined by the code tree determining means Whether the data is registered in the code tree, the escape code data case from the root that means the vertex of the code tree when the data is not registered. Escape code output means for outputting an escape code in accordance with a branch from a node as a branch point located on the way to a leaf as a point, and a context for shortening the context length n when data is not registered in the code tree Changing means, a code output means for outputting a code of data according to a branch from a node located on the way from the root of the code tree to a leaf of the data when the data is registered in the code tree, and an encoded leaf Code length changing means for recombining other leaves or nodes, prefix data updating means for registering data in the prefix data holding means, and when the escape code is coded, the process is repeated until the data is coded. Since it is configured with a control means, in addition to the effect of the data compression device of the present invention according to claim 9 described above, All combinations of history with force data and the context may be without first pre-registered. Therefore, the processing speed of data compression is significantly improved, and the memory used for registering the context can be significantly reduced, so that the processing load of the data compression apparatus can be significantly reduced.

Further, according to the data compression apparatus of the present invention as set forth in claim 11, in the data compression apparatus which encodes and compresses the input data according to the history that has appeared in the past, the data is input just before the input data. Prefix data holding means for holding a context consisting of n pieces of input data, history holding means for holding a combination of input data and context, and a context in which an escape code defined as data indicating unregistered data is registered in advance. Code tree holding means for holding an independent code tree for each, code tree determining means for determining the code tree of data from the context and input data, and whether or not data is registered in the code tree determined by the code tree determining means The context discriminating means for discriminating whether or not, and when the data is not registered in the code tree, from the root that means the vertex of the code tree to the escape code data storage point Escape output means that outputs an escape code according to the branch from the node as a branch point located up to the leaf of the, and the combination of data and context is registered in the history holding means when the data is not registered in the code tree. History registering means, code registering means for newly registering data in the code tree when no data is registered in the code tree, and context for shortening the context length n when no data is registered in the code tree Changing means, a code output means for outputting a code of data according to a branch from a node located midway from the root of the code tree to a leaf of the data when the data is registered in the code tree, and an encoded leaf A code length changing means for recombining with other leaves or nodes, a prefix data updating means for registering data in the prefix data holding means, and an escape key. When the code is coded, it is configured with a control means for repeating the process until the data is coded. Therefore, in addition to the effect of the data compression device of the present invention according to claim 11, Input data that was not previously registered in the past can be newly registered, and this newly registered data can also be encoded at an early stage in the next encoding process. As the processing progresses, the data compression effect is significantly improved and the processing load of the data compression device can be significantly reduced.

Further, according to the data compression apparatus of the present invention as set forth in claim 12, in the data compression apparatus which encodes and compresses the input data according to the history that has appeared in the past, the data is input just before the input data. Prefix data holding means for holding a context consisting of n pieces of input data, history holding means for holding a combination of the input data and the context, and a context in which an escape code defined as data indicating unregistered data is registered in advance. Code tree holding means for holding an independent code tree for each, code tree determining means for determining the code tree of data from the context and input data, and whether or not data is registered in the code tree determined by the code tree determining means Whether the data is registered in the code tree, the escape code data case from the root that means the vertex of the code tree when the data is not registered. Escape code output means for outputting an escape code in accordance with a branch from a node as a branch point located on the way to a leaf as a point, and a context for shortening the context length n when data is not registered in the code tree Changing means, an escape code output means for outputting a code of data according to a branch from a node located on the way from the root of the code tree to a leaf of the data when the data is registered in the code tree, and a history holding means History registration means for registering a combination of data and context in,
Code registration means for newly registering data in the code tree, code length changing means for rearranging the coded leaf and another leaf or node, and prefix data holding means for registering data in the prefix data holding means. When the escape data updating means to be registered and the escape code is encoded even once at the time of encoding the data, the combination of the context and the data immediately before the encoding of the data is registered in the history holding means by the history registration means, The data according to the present invention as set forth in claim 11, wherein the code tree having an escape code encoded immediately before data encoding is provided with control means for newly registering the data by the code registering means. In addition to the effect of the compression device, it is not necessary to register all the combinations of context and data that are judged not to be in the history of input data in the past, and this enables data The effect of contraction process is further significantly improved. Further, it is possible to give (register) a code only to the data having a high appearance frequency, which has the effect of significantly improving the data compression efficiency. The above-described effects have the effect of dramatically improving the performance of the data compression apparatus.

Further, according to the data restoration apparatus of the present invention as set forth in claim 13, in the data restoration apparatus for decoding the code coded according to the history that has appeared in the past, n pieces of data decoded in the past are held. Is held in the prefix data holding means, the history holding means that holds the combination of the decoded data and the context, the code tree holding means that holds the code tree independent for each context, and the prefix data holding means. Code tree determining means for determining a code tree for decoding data from the context, and data storage reached by scanning a node as a branch point from a root meaning a vertex of the code tree selected by the code tree determining means according to a code Decoding means for outputting the data stored in the leaf as a point, code length changing means for recombining the decoded leaf with another leaf or node, and the decoded data Since it is configured with a prefix data updating means for registering in the prefix data holding means, a probability model is constructed by obtaining the appearance frequency of the input data, a code is assigned to each input data, and a code table is created. The two-stage processing of outputting the character to be decoded from this code table can be performed at the same time, which has the effect of significantly improving the speed of the data restoration processing. In addition, it is possible to omit an enormous amount of arithmetic processing of reconstructing a stochastic model that has already been constructed each time data is input, and this also has the effect of further increasing the speed of restoration processing. Further, as the code of the same data as the code of the input data that has appeared in the past repeatedly appears, the code of the data can be represented by a smaller number of bits, which also has the effect of significantly improving the restoration effect in the data restoration. . The above-described effects have the effect of dramatically improving the performance of the data restoration device.

Further, according to the data restoration apparatus of the present invention as set forth in claim 14, in the data restoration apparatus which decodes the code coded according to the history that has appeared in the past, n pieces of data decoded in the past are held. Pre-data holding means,
History holding means for holding a combination of decoded data and context, code tree holding means for holding a code tree in which an escape code defined as data indicating non-registration of data is held in advance, and pre-data holding means Code tree deciding means for deciding a code tree for decoding data from the specified context, and scanning nodes reaching as branch points from the root which means the vertices of the code tree selected by the code tree deciding means according to the code Decoding means for outputting the data stored in the leaf as the data storage point, code length changing means for recombining the decoded leaf with another leaf or node, and when the output data is an escape code Context changing means for rejecting and shortening the context, and prefix data updating means for registering the decoded data in the prefix data holding means When the escape code is decoded, the context changing means resets the context, and the control means repeats the process until a code other than the escape code is decoded. Therefore, the present invention according to claim 13 above. In addition to the effect of the data restoration device, it is not necessary to register all the history of the combination of the decoded data and the context in advance, which has the effect of significantly improving the processing speed of data restoration. Furthermore, it is possible to shorten the time until the combination of the decoded data and the context is obtained, which has the effect of significantly improving the processing speed of data recovery and also the performance of the data recovery device.

Further, according to the data restoration apparatus of the present invention as set forth in claim 15, in the data restoration apparatus for decoding the code coded according to the history that has appeared in the past, n pieces of data decoded in the past are held. Prefix data holding means, history holding means for holding a combination of decoded data and context, code tree holding means for holding a code tree in which escape codes are registered in advance, and prefix data holding means Code tree determining means for determining the code tree for decoding the data from the existing context, and the data reached by scanning the node as the branch point from the root that means the vertex of the code tree selected by the code tree determining means according to the code Decoding means for outputting data stored in a leaf as a storage point and code length change for rearranging the decoded leaf and another leaf or node Stage, when the output data is an escape code, context changing means for rejecting the data and shortening the context, preposition data updating means for registering the decoded data in the predata holding means, and data decoding processing History registration means for registering all the context and the decoded data when the escape code is decoded in the history holding means,
When the escape code is decoded in the data decoding process, the code registration means that registers the code of the data in all the code trees corresponding to the context, and when the escape code is decoded, the context is reset by the context changing means, and the escape is executed. Since it is configured to include a control unit that repeats the process until a code other than the code is decoded, in addition to the effect of the data restoration device of the present invention described in claim 14, it has not been registered in advance in the past. It is possible to newly register the decrypted data that has been registered, and this newly registered decrypted data can be decrypted at an early stage in the next decryption process.
As a result, as the decoding process progresses, the data restoration effect is greatly improved and the performance of the data restoration device is also greatly improved.

Further, according to the data restoration apparatus of the present invention as set forth in claim 16, in the data restoration apparatus which decodes the code coded according to the history that has appeared in the past, n pieces of data decoded in the past are held. Pre-data holding means,
History holding means for holding a combination of decoded data and context, code tree holding means for holding a code tree in which an escape code defined as data indicating non-registration of data is held in advance, and pre-data holding means Code tree deciding means for deciding a code tree for decoding data from the specified context, and scanning nodes reaching as branch points from the root which means the vertices of the code tree selected by the code tree deciding means according to the code Decoding means for outputting the data stored in the leaf as the data storage point, code length changing means for recombining the decoded leaf with another leaf or node, and when the output data is an escape code Context changing means for rejecting and shortening the context, and prefix data updating means for registering the decoded data in the prefix data holding means Corresponding to the context when the escape code was last decoded in the data decoding process and the history registration unit that registers the decoded data in the history holding unit, and the context when the last escape code was decoded in the data decoding process Code registration means for registering the code of the data in the code tree,
When the escape code is decrypted, the context is reset by the context changing means, and the control means that repeats the process until the other than the escape code is decrypted is configured.
In addition to the effect of the data restoration device of the present invention according to claim 15, it is not necessary to register all the combinations of contexts and data that are determined not to be in the history of past input data,
This has the effect of significantly improving the data restoration process. Furthermore, it is possible to give (register) a code only to the data that actually appears frequently, which has the effect of greatly improving the data recovery efficiency and also the performance of the data recovery device.

[Brief description of drawings]

FIG. 1 is a principle block diagram of the present invention.

FIG. 2 is a principle block diagram of the present invention.

FIG. 3 is a block diagram of the principle of the present invention.

FIG. 4 is a principle block diagram of the present invention.

FIG. 5 is a principle block diagram of the present invention.

FIG. 6 is a principle block diagram of the present invention.

FIG. 7 is a principle block diagram of the present invention.

FIG. 8 is a principle block diagram of the present invention.

FIG. 9 is a block diagram illustrating a technique related to the present invention.

FIG. 10 is a block diagram illustrating a technique related to the present invention.

FIG. 11 is a block diagram illustrating a technique related to the present invention.

FIG. 12 is a block diagram illustrating a technique related to the present invention.

FIG. 13 is a block diagram illustrating a technique related to the present invention.

FIG. 14 is a block diagram illustrating a technique related to the present invention.

FIG. 15 is a block diagram showing a configuration of a data compression device and a data decompression device according to Technology 1 related to the present invention.

FIG. 16A is a diagram showing an example of a storage format of a context tree. (B) is a figure which shows the parent-child relationship of a dictionary.

FIG. 17 is a diagram for explaining an initial state of a code tree.

FIG. 18 is a diagram showing an example of an array that stores a code tree.

19A and 19B are diagrams for explaining an example of a basic operation for updating the code of the splay code and an example of updating the code of the splay code, respectively.

FIG. 20 is a flowchart for explaining a coding procedure according to Related Technique 1.

21A and 21B are diagrams for explaining a procedure for updating a context tree and a code tree according to Related Technique 1.

22 (a) and 22 (b) are diagrams for explaining a procedure for updating a context tree and a code tree according to Related Technique 1.

23 (a) and 23 (b) are diagrams for explaining a procedure for updating a context tree and a code tree according to Related Technique 1. FIG.

24 (a) and 24 (b) are diagrams for explaining a procedure for updating a context tree and a code tree according to Related Technique 1.

25 (a) and 25 (b) are diagrams for explaining a procedure for updating a context tree and a code tree according to Related Technique 1.

26 (a) and 26 (b) are diagrams for explaining a procedure for updating a context tree and a code tree according to Related Technique 1.

27A and 27B are diagrams for explaining a procedure for updating a context tree and a code tree according to Related Technique 1.

28 (a) and 28 (b) are diagrams for explaining a procedure for updating a context tree and a code tree according to Related Technique 1.

[Fig. 29] Fig. 29 is a diagram for describing an example after encoding of a character string according to Related Technique 1.

30 (a) and 30 (b) are diagrams showing an algorithm of a procedure for creating a context tree.

FIG. 31 is a flowchart for explaining a decoding procedure according to Related Technique 1.

FIG. 32 is a block diagram showing a configuration of a data compression device and a data decompression device according to an embodiment of the present invention.

FIG. 33 is a block diagram showing a configuration of a data compression device according to the present embodiment.

FIG. 34 is a block diagram showing a configuration of an encoding unit according to the present embodiment.

[Fig. 35] Fig. 35 is a flowchart for explaining a coding procedure according to the present embodiment.

FIG. 36 is a flowchart for explaining a code output procedure according to the present embodiment.

[Fig. 37] Fig. 37 is a flowchart for explaining a code tree rearrangement procedure according to the present embodiment.

FIG. 38 is a block diagram for explaining the configuration of the data restoration device according to the present embodiment.

[Fig. 39] Fig. 39 is a block diagram for describing the configuration of a decoding unit according to the present embodiment.

FIG. 40 is a flow chart for explaining a decoding procedure according to the present embodiment.

FIG. 41 is a flowchart for explaining a decoding procedure according to the present embodiment.

FIG. 42 is a block diagram for explaining a configuration of a data compression device according to a first modification of the present embodiment.

[Fig. 43] Fig. 43 is a flowchart for describing an encoding procedure according to a first modified example of the present embodiment.

FIG. 44 is a block diagram illustrating a configuration of a data restoration device according to a first modification of the present embodiment.

FIG. 45 is a flowchart for explaining a decoding procedure according to the first modified example of the present embodiment.

FIG. 46 is a block diagram for explaining the configuration of a data compression device according to a second modification of the present embodiment.

[Fig. 47] Fig. 47 is a flowchart for describing a coding procedure according to a second modification of the present embodiment.

FIG. 48 is a block diagram for explaining a configuration of a data restoration device according to a second modification of the present embodiment.

[Fig. 49] Fig. 49 is a flowchart for explaining a decoding procedure according to the second modification of the present embodiment.

[Fig. 50] Fig. 50 is a flowchart for describing an encoding procedure according to a third modification of the present embodiment.

FIG. 51 is a flowchart for explaining a decoding procedure according to the third modification of the present embodiment.

[Fig. 52] Fig. 52 is a block diagram for explaining the configuration of a data compression device according to technology 2 related to the present invention.

[Fig. 53] Fig. 53 is a block diagram for describing a configuration of a code registration unit and a code tree holding unit according to Related Technique 2.

FIG. 54 is a diagram for explaining the operation of the data compression device according to Related Technique 2;

FIG. 55 is a diagram for explaining the operation of the data compression device according to the related technique 2.

FIG. 56 is a diagram for explaining the operation of the data compression device according to Related Technique 2;

57 (a) and (b) are diagrams showing an example of a code tree and a context tree, respectively.

[Fig. 58] Fig. 58 is a flowchart for describing an encoding procedure according to Related Technique 2.

[Fig. 59] Fig. 59 is a flowchart for describing an encoding procedure according to Related Technique 2.

60 (a) and 60 (b) are diagrams showing a state of newly registering a code according to Related Technique 2.

[Fig. 61] Fig. 61 is a flowchart for explaining another encoding procedure according to Related Technique 2.

[Fig. 62] Fig. 62 is a block diagram for explaining the configuration of a data restoration device according to Related Technique 2.

FIG. 63 is a diagram for explaining the operation of the data restoration device according to Related Technique 2;

FIG. 64 is a diagram for explaining the operation of the data restoration device according to Related Technique 2;

[Fig. 65] Fig. 65 is a flowchart for describing a decoding procedure according to Related Technique 2.

[Fig. 66] Fig. 66 is a block diagram for describing a configuration of a code registration unit and a code tree holding unit according to a first modification of Related Technique 2.

[Fig. 67] Fig. 67 is a flowchart for describing an encoding procedure according to a first modified example of the related art 2.

[Fig. 68] Fig. 68 is a block diagram for describing a configuration example of a code registration unit and a code tree holding unit according to a second modification of Related Technique 2.

[Fig. 69] Fig. 69 is a flowchart for describing an encoding procedure according to a second modified example of related art 2.

FIGS. 70 (a) and 70 (b) are diagrams for explaining the principle of multilevel arithmetic encoding.

71 (a) and 71 (b) are flowcharts showing a procedure of conventional multi-valued arithmetic coding for compressing in character units.

[Fig. 72] Fig. 72 is a diagram illustrating an example of an algorithm for multilevel arithmetic encoding.

73 (a) and 73 (b) are diagrams for explaining the principle of spray encoding.

[Fig. 74] Fig. 74 is a diagram for describing the principle of probability statistical coding.

75 (a) and (b) are diagrams showing an example of registration of a context tree.

[Explanation of symbols]

1, 3 Data compression device 2, 4 Data decompression device 11, 22 Context collection process 12, 21 Spray coding process 41 Upper node discriminating unit 42 Node number management unit (memory) 43 Position discriminating unit 44, 48 Latch 45 Stack 46 Lower Node discriminating unit 47 Leaf / node discriminating unit 61 New node ID generating unit 62 Latch 63 Parent-child information updating unit 64 External node (leaf ID) holding unit 65 Internal node (node ID) holding unit 66 ESC-ID holding unit 67 Code tree management Unit 68 External node / ESC-ID (leaf ID) storage unit 69 Longest code detection unit (branch position search unit) 70 Latest registered ID storage unit (branch position storage unit) 100, 200 Prefix data storage unit 100A-1 to 100A -N, 200A-1 to 200A
-N prefix data holding unit 101, 201 history holding unit 101A, 201A context history holding unit 102, 202, 107, 207, 301, 401 code tree holding unit 102A, 202A, 107A, 207A, 301B,
401B code tree holding unit 103, 203, 403 code tree determining unit 103A, 203A code tree determining unit 104 code output unit 104A, 104A ', 306B coding unit 105, 205 code length changing unit 105A, 205A code tree updating unit 106, 206 Prefix Data Updating Means 106A, 206A Context Updating Unit 108 Context Discriminating Unit 108A Context Discriminating Unit 109 Escape Code Outputting Units 110, 208, 305, 405 Context Changing Units 110A, 210A, 305B, 403B Context Changing Unit 111 Code Outputting Unit 112 , 209 History registration means 113, 114, 115, 212, 304, 309, 3
11, 407, 410, 412 Code registration means 112A, 212A, 322B, 407B Code registration section 116, 117, 213 Control means 204, 404 Decoding means 204A, 204A ', 404B Decoding section 303 Context registration means 303B, 408B Context registration section 302, 402 Context tree holding means 302B, 402B Context tree holding section 306 Encoding means 307, 406 Code updating means 406B Code changing sections 308, 409 Branch position holding means 310, 411 Branch position searching means 321B, 421B Context holding section 408, 413, 414 Context tree registration means 409B Latch 511 Context collection 512 Dynamic variable length coding

─────────────────────────────────────────────────── ─── Continuation of the front page (56) Reference JP-A-5-218881 (JP, A) JP-A-6-149537 (JP, A) JP-A-6-315089 (JP, A) JP-A-7- 336237 (JP, A) (58) Fields investigated (Int.Cl. ⁷ , DB name) H03M 7/40 G06F 5/00

Claims (16)

(57) [Claims] 1. A data compression method for encoding and compressing input data according to a history that has appeared in the past, and a context collection process for holding a combination of input data and a context consisting of n pieces of continuous data until then. And a code tree holding process for holding an independent code tree for each context, and when data corresponding to the context of the context collection process appears, the above-mentioned code tree from the root meaning the vertex of the code tree A code output process that outputs a code defined as unique data according to the branch of a node as a branch point to a leaf as a point where data is stored, and the above data after the process in the above code output process And a code length changing process for rearranging a leaf of another data and a leaf of another data or a node. 2. A data compression method for encoding and compressing input data according to a history that has appeared in the past, and a context collecting step of retaining a combination of the input data and a context consisting of n pieces of continuous data until then. And a code tree holding process for holding an independent code tree for each context, and when data corresponding to the context of the context collection process appears, the above-mentioned code tree from the root meaning the vertex of the code tree A code output process that outputs a code defined as unique data according to the branch of a node as a branch point to a leaf as a point where data is stored, and the above data after the process in the above code output process The process of changing the code length for changing the leaf of the above and the leaf or node of other data, and the combination of the above input data and the context A context discriminating process for discriminating whether or not the data is held in the process, and an escape code holding process for holding a leaf in which an escape code defined as data indicating unregistered data is registered in the code tree in advance, When the combination of the input data and the context of is a combination that is not held in the history of the context collection process, the escape code is output, and the data is stored until the combination held in the context collection process is obtained. Characterized by repeating the process of shortening the context of
Data compression method. 3. A data compression method for encoding and compressing input data according to a history that has appeared in the past, and a context collection process for holding a combination of input data and a context consisting of n pieces of data continuous up to that point. And a code tree holding process for holding an independent code tree for each context, and when data corresponding to the context of the context collection process appears, the above-mentioned code tree from the root meaning the vertex of the code tree A code output process that outputs a code defined as unique data according to the branch of a node as a branch point to a leaf as a point where data is stored, and the above data after the process in the above code output process The code length changing process for changing the leaf of the above and the leaf or node of other data, and the combination of the above input data and the context are held in the above context collecting process. In addition to having a context discrimination process for discriminating whether or not to hold, and an escape code holding process for holding a leaf in which an escape code defined as data indicating unregistered data is registered in the code tree in advance, When the combination with the context is a combination which is not held in the history of the context collection process, the context new registration process of newly registering the combination of the input data and the context in the context collection process, and the input of the above When the combination of the data and the context is a combination not held in the history of the context collection process, a code tree new registration process of newly registering the data in the code tree corresponding to the context, If the combination of the input data and the context of is a combination that is not stored in the history of the context collection process, And simultaneously outputs the sign of Pukodo,
Register the combination of the input data and the context in the history, register the data in the code tree corresponding to the context, and shorten the context of the data until the combination held in the context collection process is obtained. A method for compressing data, characterized in that the processing for repeating is repeated. 4. A data compression method for encoding and compressing input data according to a history that has appeared in the past, and a context collection process for holding a combination of input data and a context consisting of n pieces of continuous data until then. And a code tree holding process for holding an independent code tree for each context, and when data corresponding to the context of the context collection process appears, the above-mentioned code tree from the root meaning the vertex of the code tree A code output process that outputs a code defined as unique data according to the branch of a node as a branch point to a leaf as a point where data is stored, and the above data after the process in the above code output process The code length changing process for changing the leaf of the above and the leaf or node of other data, and the combination of the above input data and the context are held in the above context collecting process. In addition to having a context discrimination process for discriminating whether or not to hold, and an escape code holding process for holding a leaf in which an escape code defined as data indicating unregistered data is registered in the code tree in advance, When the combination with the context is a combination which is not held in the history of the context collection process, the context new registration process of newly registering the combination of the input data and the context in the context collection process, and the input of the above When the combination of the data and the context is a combination not held in the history of the context collection process, a code tree new registration process of newly registering the data in the code tree corresponding to the context, In the process of newly registering the context and the process of newly registering the code tree, a combination of the above-mentioned data with the context immediately before judged to be in the history And registers only, the data compression method. 5. A data recovery method for recovering coded data obtained by coding input data according to a history of past input data, comprising: a context collection process for maintaining a history of combinations of decoded data and context; A code tree holding process for holding each independent code tree, a code tree determining process for determining the code tree of the above data from the context of the data decoded up to immediately before, and a code tree determined in the above code tree determining process. After the decoding process of decoding the data from the code of the data and the decoding of the decoding process, by the same means as the encoding side,
A data restoration method, comprising: a code length changing process of recombining between leaves as data storage points on the code tree or between the leaves and nodes as branch points of the code tree. 6. A data recovery method for recovering coded data obtained by coding input data according to a history of past input data, comprising: a context collection process for maintaining a history of combinations of decoded data and context; A code tree holding process for holding each independent code tree, a code tree determining process for determining the code tree of the above data from the context of the data decoded up to immediately before, and a code tree determined in the above code tree determining process. After the decoding process of decoding the data from the code of the data and the decoding of the decoding process, by the same means as the encoding side,
There is a code length changing process of recombining the leaves as the data storage points on the code tree or the leaf and the node as the branch point of the code tree, and the code tree has the code according to each context. If an escape code, which is defined as data indicating unregistered data, is registered in advance for each tree and the above escape code is decoded at the time of decoding, the process of shortening the context length is repeated until a code other than the above escape code is decoded. A data restoration method characterized by the above. 7. A data restoration method for restoring coded data obtained by coding input data according to a history of past input data, a context collection process for holding a history of a combination of decoded data and a context, and A code tree holding process for holding each independent code tree, a code tree determining process for determining the code tree of the above data from the context of the data decoded up to immediately before, and a code tree determined in the above code tree determining process. After the decoding process of decoding the data from the code of the data and the decoding of the decoding process, by the same means as the encoding side,
Includes a code length changing process of recombining the leaves as the data storage points on the code tree or the leaf and the node as the branch point of the code tree, and a context for newly registering the data in the context collecting process. It has a new registration process and a code tree new registration process for newly registering the decoded data in the above-mentioned code tree according to the context, and when the escape code defined as the data indicating the unregistered data is decoded, A data restoration method, wherein the new registration process and the code tree new registration process are executed, and a process of shortening the length of the context is repeated until a code other than the escape code is decoded. 8. A data recovery method for recovering coded data obtained by coding input data according to a history of past input data, comprising: a context collection process for maintaining a history of combinations of decoded data and context; A code tree holding process for holding each independent code tree, a code tree determining process for determining the code tree of the above data from the context of the data decoded up to immediately before, and a code tree determined in the above code tree determining process. After the decoding process of decoding the data from the code of the data and the decoding of the decoding process, by the same means as the encoding side,
Includes a code length changing process of recombining the leaves as the data storage points on the code tree or the leaf and the node as the branch point of the code tree, and a context for newly registering the data in the context collecting process. It has a new registration process and a code tree new registration process for newly registering the decoded data in the above-mentioned code tree according to the context, until the decoding is performed except for the escape code defined as the data indicating the unregistered data. In the process, when even one of the escape codes is decoded, each new registration process in the context new registration process and the code tree new registration process is performed only in the context immediately before decoding other than the escape code. And how to restore data. 9. A data compression apparatus for encoding and compressing input data according to a history that has appeared in the past, wherein prefix data holding a context consisting of n pieces of input data input up to immediately before the input data. Holding means, history holding means for holding a combination of the input data and the context, code tree holding means for holding an independent code tree for each context, and immediately before being held by the pre-data holding means From the input data up to the code tree determining means for determining the code tree of the data, and from the root meaning the apex of the code tree selected by the code tree determining means along the leaf where the data is stored A code output unit that outputs unique data according to a branch from a node serving as a branch point, and a coded leaf and another leaf or node are recombined A data compression apparatus comprising a code length changing means and a prefix data updating means for registering the data in the prefix data holding means. 10. A data compression device for encoding and compressing input data according to a history of past appearances, wherein prefix data holding a context consisting of n pieces of input data input up to immediately before the input data. Holding means, history holding means for holding the combination of the above input data and context, and code tree holding for holding an independent code tree for each context in which escape codes defined as data indicating unregistered data are registered in advance Means, code tree determining means for determining the code tree of the data from the context and input data, and context determination for determining whether or not the data is registered in the code tree determined by the code tree determining means. And means for storing the data of the escape code from the root that means the vertex of the code tree when the data is not registered in the code tree Escape code output means for outputting an escape code in accordance with a branch from a node as a branch point located on the way to a leaf as a point, and shortening the context length n when the above data is not registered in the above code tree. And a code output means for outputting the code of the data according to a branch from a node located midway from the root of the code tree to the leaf of the data when the data is registered in the code tree. And a code length changing means for recombining the encoded leaf and another leaf or node, a prefix data updating means for registering the data in the prefix data holding means, and a code for changing the escape code Data compression, comprising a control means for repeating the process until the data is encoded. Location. 11. A data compression apparatus for encoding and compressing input data according to a history of past appearances, wherein prefix data holding a context consisting of n pieces of input data input immediately before the input data. Holding means, history holding means for holding the combination of the above input data and context, and code tree holding for holding an independent code tree for each context in which an escape code defined as data indicating unregistered data is registered in advance Means, code tree determining means for determining the code tree of the data from the context and input data, and context determination for determining whether or not the data is registered in the code tree determined by the code tree determining means. Means, and when the data is not registered in the code tree, from the root that means the vertex of the code tree to the data storage point of the escape code Escape code output means for outputting the escape code according to the branch from the node as a branch point located within all the leaves, and the data in the history holding means when the data is not registered in the code tree. And history registration means for registering a combination of contexts, code registration means for newly registering the data in the code tree when the data is not registered in the code tree, and the data for being registered in the code tree. If not, context change means for shortening the context length n; and, if the data is registered in the code tree, branch from a node located on the way from the root of the code tree to the leaf of the data. A code output means for outputting the code of the data according to the above, and a code length change for recombining the coded leaf and another leaf or node And a pre-data updating means for registering the data in the pre-data holding means, and a control means for repeating the process until the data is coded when the escape code is coded. A data compression device characterized by the above. 12. A data compression device for encoding and compressing input data according to a history of past appearances, wherein prefix data holding a context consisting of n pieces of input data input up to immediately before the input data. Holding means, history holding means for holding the combination of the above input data and context, and code tree holding for holding an independent code tree for each context in which escape codes defined as data indicating unregistered data are registered in advance Means, code tree determining means for determining the code tree of the data from the context and input data, and context determination for determining whether or not the data is registered in the code tree determined by the code tree determining means. And means for storing the data of the escape code from the root that means the vertex of the code tree when the data is not registered in the code tree Escape code output means for outputting the escape code according to a branch from a node as a branch point located on the way to a leaf as a point, and a context length n when the data is not registered in the code tree. Context changing means for shortening, and an escape for outputting the code of the data according to a branch from a node located on the way from the root of the code tree to the leaf of the data when the data is registered in the code tree A code output means, a history registration means for registering a combination of the data and the context in the history holding means, a code registration means for newly registering the data in the code tree, and an encoded leaf and another leaf or node. A code length changing means for recombining, a prefix data updating means for registering the data in the prefix data holding means, and the data If the escape code is coded even once when coding the data, the combination of the context and the data immediately before the coding of the data is registered in the history holding means by the history registration means, and the code of the data is coded. A data compression device, comprising a control means for newly registering the data by the code registration means in a code tree having an escape code encoded immediately before conversion. 13. A data decompression device for decoding a code coded according to a history that has appeared in the past, a front data holding means for holding n pieces of data decoded in the past, and the decoded data and the context. A history holding unit that holds a combination, a code tree holding unit that holds an independent code tree for each context, and a code tree for decoding the above data is determined from the context held by the above-mentioned predata holding unit. The data stored in the leaf as the data storage point reached by scanning the node as the branch point from the root that means the vertex of the code tree selected by the code tree determination means according to the code. Decoding means for outputting, code length changing means for recombining the decoded leaf with another leaf or node, and the decoded data are registered in the pre-data holding means. Characterized in that it consists before and a location data updating means for, data restoration device. 14. A data restoration device for decoding a code coded according to a history that has appeared in the past, a front data holding means for holding n pieces of data decoded in the past, and a decoded data and a context. The history holding means for holding the combination, the code tree holding means for holding the code tree in which the escape code defined as the data indicating unregistered data is previously registered, and the context held in the front data holding means Code tree determining means for determining a code tree for decoding data, and data storage reached by scanning a node as a branch point from a root that means a vertex of the code tree selected by the code tree determining means according to a code Decoding means that outputs the data stored in the leaf as a point, and the code that recombines the decoded leaf with another leaf or node. A length changing means, a context changing means for rejecting the data and shortening the context when the output data is the escape code, and a prefix data updating means for registering the decoded data in the prefix data holding means, A data restoration device, comprising: a control means for resetting the context by the context changing means when the escape code is decoded, and repeating the processing until a code other than the escape code is decoded. 15. A data restoration device for decoding a code coded according to a history that has appeared in the past, a pre-data holding means for holding n pieces of data decoded in the past, and the decoded data and the context. A history holding means for holding a combination, a code tree holding means for holding a code tree in which an escape code is registered in advance, and a code tree for decoding the above data is determined from the context held in the prefix data holding means. And a data stored in a leaf as a data storage point which is reached by scanning a node as a branch point from a root that means a vertex of the code tree selected by the code tree determination means according to a code And a code length changing means for rearranging the decoded leaf and another leaf or node, and the output data is When was the cape code,
Context changing means for rejecting the above data and shortening the context, prefix data updating means for registering the decoded data in the prefix data holding means, and all contexts when the escape code is decoded in the decoding process for the data And a code for registering the code of the data in all the code trees corresponding to the context when the escape code is decoded in the decoding process of the data. It is characterized by comprising registration means and control means for resetting the context by the context changing means when the escape code is decoded, and repeating the processing until a code other than the escape code is decoded. Data recovery device. 16. A data decompression device for decoding a code coded according to a history that has appeared in the past, a front data holding means for holding n pieces of data decoded in the past, and the decoded data and the context. The history holding means for holding the combination, the code tree holding means for holding the code tree in which the escape code defined as the data indicating unregistered data is previously registered, and the context held in the front data holding means Code tree determining means for determining a code tree for decoding data, and data storage reached by scanning a node as a branch point from a root that means a vertex of the code tree selected by the code tree determining means according to a code Decoding means that outputs the data stored in the leaf as a point, and the code that recombines the decoded leaf with another leaf or node. A length changing means, a context changing means for rejecting the data and shortening the context when the output data is the escape code, and a prefix data updating means for registering the decoded data in the prefix data holding means. , History registration means for registering the context and the decrypted data when the escape code was last decrypted in the data decryption processing, and the escape code finally decrypted in the data decryption processing Code registration means for registering the code of the data in the code tree corresponding to the time context, and when the escape code is decoded, the context is reset by the context changing means, and processing is performed until a code other than the escape code is decoded. And a control means for repeating the above.