Data compressing apparatus and a data decompressing apparatus, a data compressing method and a data decompressing method, and a data compressing or decompressing dictionary creating apparatus and a computer readable recording medium storing a data compressing program or a data decompressing program

(1) Field of the Invention

The present invention relates to a data compressing apparatus and a data decompressing apparatus, a data compressing method and a data decompressing method, a data compressing or decompressing dictionary creating apparatus, and a computer readable recording medium storing a data compressing program or data decompressing program for use when various data such as text data (character codes), image data, etc., is compressed or decompressed.

(2) Description of the Related Art

In recent years, various kinds of data such as character codes, image data, etc., is handled in a computer and a quantity of the data is increasing. Because of this, it is general in the computer that a redundant part in handled data is omitted and compressed so that a storage capacity necessary when the data is managed is decreased, or a transmission rate or transmission efficiency is increased at the time of data communication with a remote place in order to decrease a communication cost.

As data compressing methods, there are, for example, dictionary-based coding in which analogy of inputted data strings is used to code and compress the data strings, and statistical coding in which a frequency of occurrence of inputted data strings is used to code and compress the data strings. Hereinafter, one word of data (one alphabetic character, for example) is referred to as “a character”, whereas a train of an arbitrary number of words of data is referred to as “a character string”.

In concrete, in the former dictionary-based coding, a predetermined number (code) is assigned to a character or a character string occurring in a data string (data file, for example) that is an object of compression to create a dictionary (code table), and an actually inputted character (character string) is coded on the basis of the dictionary. A character (character string) having a higher probability is generally assigned as a longer character string in the dictionary so that a compression ratio is improved.

LZ 77 and LZ 78 (refer to “Introduction to Document Data Compression Algorithm”, Tomohiko Uematsu, CQ Shuppansha, for example) are representatives of the dictionary coding system.

In LZ 77 , characters (character strings) occurring in an inputted data string are stored in a buffer in advance, and a storing position (address) and a length of characters (a character string) in the buffer longest-matching with inputted characters (a character string) that is an object of compression are coded as a code of the inputted character (character string). In LZ 78 , characters (a character string) occurring in an inputted data string in the past are registered in a dictionary, and a register number of characters (a character string) in the dictionary matching with inputted characters (a character string) that is an object of compression is coded as a code of the inputted characters (character strings).

On the other hand, in the latter statistical coding, a frequency of occurrence of each character (character string) occurring in an inputted data string are calculated, and a shorter code is assigned to a character (character string) having a higher probability so as to improve a compression ratio.

Arithmetic coding (refer to “Arithmetic Coding for Data Compression”/IAN H. WITTEN, et al., Communication of the ACM, Vol.130, No.6, P520-540, “An Adaptive Dependency Source Model for Data Compression Scheme”/D. M. Abrahamson, Communication of the ACM, Vol.132, No.1, P77-83) and Haffman coding (refer to “Dynamic Haffman Coding”/Donald E. Knuth, Journal of Algorithms, Vol.6, P163-180) are representatives of statistical coding.

As statistical coding, there is proposed another system, in which inputted characters are coded into a variable-length code on the basis of, not a probability of one character, but a conditional probability in consideration of dependency between an inputted character and a character immediately before the inputted character (hereinafter, referred to as a context) as shown in FIG. 48, for example, in order to accomplish a higher compression effect (hereinafer, such variable-length coding using a conditional probability in consideration of a context is referred as a context modeling).

In concrete, the context modeling collects a context from an inputted data string (original data), successively registers characters that are objects of coding [refer to FIG. 49 ( a )] in a dictionary of a tree structure [hereinafter referred as a context tree, refer to FIG. 49 ( b )] counts occurrences of each character each time a character string is inputted which traces characters registered in respective nodes of the context tree to obtain a conditional probability, and codes the original data on the basis of the obtained probability.

Both of dictionary-based coding and statistical coding are classified into three types as shown in items (1) through (3) below according to a way of considering occurrences of a data string that is an object of compression (hereinafter referred as a data string to be compressed):

(1) static coding: coding a character (character string) in a data string to be compressed according to occurrences set in advance irrespective of actual occurrences of the data string to be compressed;

(2) semi-adaptive coding: coding each character (character string) according to occurrences of each character (character string) obtained by scanning all characters (character strings) in a data string to be compressed before compression; and

(3) adaptive coding: re-counting occurrences of a character (character string) each time the same character (character string) as a character (character string) inputted in the past is inputted, and coding an inputted character (character string) according to the re-counted occurrences.

In static coding, a computer reads a dictionary set irrespectively of occurrences of an actual data string to be compressed from a memory or the like (set a dictionary: Step 1 ), fixedly uses the dictionary read out until inputted characters (character strings) end (until judged YES at Step A 4 ) to code each of the inputted characters (character strings) (Steps A 2 and A 3 , NO route at Step A 4 ), as shown in FIG. 50, for example.

On the other hand, in semi-adaptive coding, the computer successively registers data string (characters/character string) to be compressed in a dictionary (Steps B 1 and B 2 , NO route at Step B 3 ), and assigns a code to each of the characters (character strings) registered in the dictionary according to occurrences of the character (character string) to code the dictionary (from YES route at Step B 3 to Step B 4 ), as shown in FIG. 51 , for example.

The computer then puts back a pointer pointing a character (character string) to be inputted to the head of a data string to be compressed (Step B 5 ), re-inputs the above data string (characters/character strings) to be compressed (Step B 6 ), and codes each of the character (character strings) while referring to the above dictionary (Step B 7 , NO route at Step B 8 ) until coding of all the data strings to be compressed is completed (until judged YES at Step B 8 ).

In adaptive coding, the computer codes inputted a character (or a character string) referring to a dictionary set in advance (Step C 2 ) when a data string (character or character string) to be compressed is inputted (Step C 1 ) similarly to static coding in the beginning, as shown in FIG. 52, for example. After that, the computer re-counts occurrences of a coded character (character string), registers a code according to the obtained occurrences as a new code of the character (character string) in the dictionary (Step C 3 ), and codes each character (character string) while updating the dictionary (NO route at Step C 4 ) until coding of all the data strings to be compressed is completed (until judged YES at Step C 4 ).

Above static coding performs coding fixedly using a dictionary set in advance. Therefore, the static coding can always achieve a constant compression ratio with respect to data strings to be compressed having similar statistics, and perform a high-speed compressing process. On the other hand, semi-adaptive coding and adaptive coding create or update a dictionary according occurrences of an actually inputted data string to be compressed so as to assign a code conforming to the actual data string to be compressed to the data string to be compressed. Therefore, it is possible to achieve a remarkable compression ratio even if a large quantity of data more than several megabytes or data having different statistics is compressed.

Above semi-adaptive coding and adaptive coding can achieve a good compression ratio when a large quantity of data of several megabytes as described above. However, when compressing a small quantity of data of several kilobytes such as text data in a text file, above semi-adaptive coding and adaptive coding cannot assign an appropriate code according to occurrences to each character (character string) since every character (character string) occurs only a few times in a data string (text file) to be compressed.

When a small quantity of data of several kilobytes is compressed, semi-adaptive coding and adaptive coding cannot achieve a high compression ratio.

On the other hand, above static coding can achieve a constant compression ratio irrespective of a data size of a data string to be compressed. However, a code to be assigned to each character (character string) occurring in the data string to be compressed is fixedly one so that a quantity of data having been compressed is possibly larger than a quantity of original data when data having different statistics from codes assigned in advance is compressed.

In the light of the above problems, an object of the present invention is to provide a data compressing technique which can stably achieve a preferable compression ratio for a small quantity of data such as text data in a text file and achieve a high compression ratio for data having different statistics, and a decompressing technique which can decompress compressed data obtained in the above compressing technique.

The present invention therefore provide a data compressing apparatus for coding data to be compressed to compress the same comprising a compressing dictionary storing unit for storing a compressing dictionary usable when the data to be compressed is compressed, a compressing dictionary use or non-use deciding unit for deciding whether the compressing dictionary is to be used or not when the data to be compressed is compressed, and a coding unit for coding the data to be compressed on the basis of the compressing dictionary when the compressing dictionary use or non-use deciding unit decides the compressing dictionary is to be used, whereas not coding but outputting said data to be compressed when the compressing dictionary use or non-use deciding unit decides the compressing dictionary is not to be used.

The present invention also provides a data compressing method for coding data to be compressed to compress the same comprising the steps of a deciding step of deciding whether a compressing dictionary is to be used or not when the data to be compressed is compressed, a coding step of coding the data to be compressed on the basis of the compressing dictionary when decided the compressing dictionary is to be used at the deciding step, and a data outputting step of not coding but outputting the data to be compressed when decided the compressing dictionary is not to be used at the deciding step.

The data compressing apparatus and the data compressing method according to this invention decide whether a compressing dictionary is to be used when data to be compressed is compressed, and code the data to be compressed on the basis of the compressing dictionary, or not code but output the data to be compressed, according to the decision. When a compression ratio is degraded if the coding is performed using a dictionary, data to be compressed is not coded (compressed) so that degradation of the compression ratio can be prevented. Whereby, it is possible to achieve a compression effect above a certain level at any time.

The above data compressing apparatus may have a compressed data dividing unit for dividing the data to be compressed into predetermined character data groups, wherein the coding unit codes the data to be compressed by the character data group obtained by the compressed data dividing unit.

If data to be compressed is divided into predetermined character data groups when the data to be compressed is coded and coded (compressed) by divided character data group, it is possible to code plural character data as a bunch at a time so that the coding process can be largely sped up as compared with a case where data to be compressed is coded by one character data.

If the above data to be compressed is document-form data, the above compressed data dividing unit may have a word dictionary storing unit for storing a word dictionary in which desired words are registered as the character data groups occurring in the document-form data, and a word dividing unit for dividing the data to be compressed into words on the basis of the word registered in the word dictionary in-the word dictionary storing unit.

Whereby, it is possible to divide data to be compressed (document-form data) into data units that are “words” having respective meanings and code the data, so as to limit the number of sorts of codes to be assigned to the data to be compressed. Whereby, a quantity of codes having been coded is decreased and a compression ratio is improved. If data to be compressed is coded by word, a decoding process on the decompressing side becomes easy and can be performed at a high speed.

If the above data to be compressed is document-form data, the above compressed data dividing unit may have a word category dictionary storing unit for storing a word category dictionary in which a desired word as each of the character data groups occurring in the document-form data and category information on the word are registered, and a word dividing unit for dividing the data to be compressed into words on the basis of the words registered in the word category dictionary in the word category dictionary storing unit, and a category information adding unit for adding the category information corresponding to each of the words obtained by the word dividing unit on the basis of the category information registered in the word category dictionary.

In the above case, it is possible to group words according to the category information so that the number of sorts of codes to be assigned to the words is decreased and a code to be assigned to each of the words is shortened. Accordingly, a quantity of codes having been coded is decreased and a compression ratio is improved. On the decompressing side, it is possible to readily specify a word to be decoded according to the above category information, which leads to speeding-up of the decoding process.

The above data compressing apparatus may further have a characteristic extracting unit for extracting character data inherent to the data to be compressed as characteristic data of the data to be compressed, and a compressing inherent dictionary creating unit for assigning a predetermined code to each of the characteristic data extracted by the characteristic extracting unit to create a compressing inherent dictionary inherent to the data to be compressed, wherein the coding unit codes the data to be compressed on the basis of the compressing inherent dictionary created by the compressing inherent dictionary creating unit and the compressing dictionary in the compressing dictionary storing unit.

In the above case, the data to be compressed is coded on the basis of both the compressing inherent dictionary and the compressing dictionary. It is thereby possible to largely decrease a probability of coding data to be compressed not registered in the dictionary, which leads to an improvement of the compression ratio.

The above data compressing apparatus may further have an inherent dictionary information outputting unit for outputting information on the compressing inherent dictionary to a decompressing side for the data to be compressed.

On the decompressing side, it is thereby possible to accurately decode (decompress) compressed data having been coded according to the compressing inherent dictionary originally created on the compressing side.

The above data compressing apparatus may still further have a compressing dictionary updating unit for updating the compressing dictionary on the basis of data to be compressed having been coded in the coding unit, wherein the coding unit codes the data to be compressed on the basis of the compressing dictionary updated by the compressing dictionary updating unit.

Whereby, it is possible to always provide a compressing dictionary suitable for data to be compressed that is an object of the next coding, which leads to a further improvement of the compression ratio.

The above compressing dictionary use or non-use deciding unit may decide whether the compressing dictionary is to be used or not on the basis of data contents type information representing a type of data contents of the data to be compressed.

In the above case, without actually detecting contents of data to be compressed, it is possible to simply decide use or non-use of the compressing dictionary. If content (characteristic) of data to be compressed on the basis of the above data contents type information, it is possible to quickly determine whether use of the compressing dictionary is effective when the data to be compressed is coded so as to decide the compressing dictionary is to be used or not. Accordingly, it is possible to achieve a compression effect above a certain level while speeding up the whole coding process.

The above compressing dictionary use or non-use deciding unit may decide whether the compressing dictionary is to be used or not according to whether specific character data occurs in the data to be compressed or not.

In the above case, it is possible to simply decide whether the compressing dictionary is to be used or not only by actually detecting contents of the data to be compressed and determining whether specific character data occurs in the data to be compressed so that a characteristic of the actual data to be compressed is quickly determined. It is therefore possible to achieve a compression effect above a certain level while improving reliability and a processing speed of the coding process.

The above compressing dictionary use or non-use deciding unit may decide whether the compressing dictionary is to be used or not according to occurrence frequency of specific character data in the data to be compressed.

If it is decided that the compressing dictionary is to be used on data to be compressed having a characteristic that specific character data frequently occurs therein, for example, a shorter code may be assigned to specific character data of a high occurrence frequency using the compressing dictionary. It is therefore possible to certainly achieve a compression effect above a certain level.

The above compressing dictionary use or non-use deciding unit may alternatively decide whether the compressing dictionary is to be used or not according to a quantity of compressed data having been coded by the coding unit.

In the above case, if it is decided that the compressing dictionary is not to be used for data to be compressed having a characteristic that a quantity of compressed data having been coded is larger than a quantity of original data, it is possible to largely decrease a probability of degrading a compression efficiency so that a compression effect above a certain level is ensured.

The above data compressing apparatus may further have a dictionary use or non-use information outputting unit for outputting information on use or non-use of the compressing dictionary decided by the compressing dictionary use or non-use deciding unit to a decompressing side for the data to be compressed.

In the above case, the decompressing side can quickly determine whether inputted compressed data has been coded using the compressing dictionary, which largely contributes to speeding-up of the decoding process.

The present invention further provides a data compressing apparatus for coding data to be compressed to compress the same comprising a compressing dictionary storing unit for storing plural kinds of compressing dictionaries usable when the data to be compressed is compressed, a compressing dictionary selecting unit for selecting a compressing dictionary to be used among the plural kinds of compressing dictionaries on the basis of data contents type information representing a type of data contents of the data to be compressed, and a coding unit for coding the data to be compressed on the basis of the compressing dictionary selected by the compressing dictionary selecting unit.

The present invention also provides a data compressing method for coding data to be compressed to compress the same comprising the steps of a dictionary selecting step of selecting a compressing dictionary to be used among plural kinds of compressing dictionaries on the basis of data contents type information representing a type of data contents of the data to be compressed, and a coding step of coding the data to be compressed on the basis of the compressing dictionary selected at the dictionary selecting step.

According to the data compressing apparatus and the data compressing method of this invention, a compressing dictionary to be used is selected among plural kinds of compressing dictionaries on the basis of the data contents type information representing a type of data contents of data to be compressed, and the data to be compressed is coded on the basis of the selected compressing dictionary. Only by inputting the above data contents type information, it is possible to quickly select and use a compressing dictionary suitable for contents (characteristic) of data to be compressed to code the data to be compressed. It is therefore possible to certainly achieve a high compression effect for data to be compressed having different characteristics while improving the processing speed of the whole compressing process.

The present invention still further provides a data compressing apparatus for coding data to be compressed to compress the same comprising a compressing dictionary storing unit for storing plural kinds of compressing dictionaries usable when the data to be compressed is compressed, a compressing dictionary selecting unit for selecting a compressing dictionary including specific character data of high occurrence frequency in the data to be compressed among the plural kinds of compressing dictionaries, and a coding unit for coding the data to be compressed on the basis of the compressing dictionary selected by the compressing dictionary selecting unit.

The present invention also provides a data compressing method for coding data to be compressed to compress the same comprising the steps of a dictionary selecting step of selecting a compressing dictionary including specific character data of high occurrence frequency in the data to be compressed among plural kinds of compressing dictionaries, and a coding step of coding the data to be compressed on the basis of the compressing dictionary selected at the dictionary selecting step.

According to the data compressing apparatus and the data compressing method of this invention, a compressing dictionary including character data of high occurrence frequency in data to be compressed is used to code the data to be compressed at any time so that a compression effect can be further improved. Since a dictionary is selected depending on whether the dictionary includes character data of high occurrence frequency in data to be compressed, the dictionary selecting process can be sped up, thus the whole coding process can be sped up.

The present invention still further provides a data compressing apparatus for coding data to be compressed to compress the same comprising a compressing dictionary storing unit for storing plural kinds of compressing dictionaries usable when the data to be compressed is compressed, a coding unit for coding the data to be compressed using any one of the plural kinds of compressing dictionaries, and a compressing dictionary selecting unit for selecting a compressing dictionary to be used among the plural kinds of compressing dictionaries according to a quantity of compressed data having been coded by the coding unit.

The present invention also provides a data compressing method of coding data to be compressed to compress the same comprising the steps of a coding step of compressing data to be compressed, and a dictionary selecting step of selecting a compressing dictionary to be used among plural kinds of compressing dictionaries according to a quantity of compressed data coded at the coding step.

According to the data compressing apparatus and the data compressing method of this invention, a compressing dictionary to be used is selected among plural kinds of compressing dictionaries according to a quantity of compressed data that is data to be compressed having been coded. It is therefore possible to select the most suitable compressing dictionary in consideration of a quantity of compressed data having been coded at any time, thus increase a compression effect more certainly.

Each of the above data compressing apparatus may further have a compressed data dividing unit for dividing the data to be compressed into predetermined character data groups, wherein the coding unit codes the data to be compressed by the character data group obtained by the compressed data dividing unit on the basis of the compressing dictionary selected by the compressing dictionary selecting unit.

In the above case, it is possible to code plural character data as a bunch at a time so that the coding (compressing) process after a dictionary is selected can be sped up as compared with a case where data to be compressed is coded by one character data.

If the above data to be compressed is document-form data, the compressed data dividing unit may have a word dictionary storing unit for storing a word dictionary in which desired words as the character data groups occurring in the document-form data are registered, and a word dividing unit for dividing the data to be compressed into words on the basis of the words registered in the word dictionary in the word dictionary storing unit.

In the above case, data to be compressed (document-form data) is divided into data units that are “words” having respective meanings and coded, whereby the number of sorts of codes to be assigned to the data to be compressed is limited. Accordingly, a quantity of codes after the coding process is performed using a selected compressing dictionary is decreased, thus a compression ratio is improved. If the data to be compressed is coded by word, the decompressing process on the decompressing side can be easy and sped up.

If the above data to be compressed is document-form data, the above compressed data dividing unit may alternatively have a word category dictionary storing unit for storing a word category dictionary in which a desired word as each of the character data groups occurring in the document-form data and category information on the word are registered, a word dividing unit for dividing the data to be compressed into words on the basis of the words registered in the word category dictionary in the word category dictionary storing unit, and a category information adding unit for adding the category information corresponding to each of the words obtained by the word dividing unit on the basis of the category information registered in the word category dictionary.

In the above case, words can be groups according to the category information. It is therefore possible to decrease the number of sorts of codes to be assigned to the words and shorten a code to be assigned to each of the words so that a quantity of codes having been coded using a selected compressing dictionary is further decreased, thus a compression ratio is improved. The decompressing side can thereby easily specify a word to be decoded according to the above category information, which leads to speeding-up of the decoding process.

Each of the above data compressing apparatus may further have a characteristic extracting unit for extracting character data inherent to the data to be compressed as characteristic data of the data to be compressed, and a compressing inherent dictionary creating unit for assigning a predetermined code to each of the characteristic data extracted by the characteristic extracting unit to create a compressing inherent dictionary inherent to the data to be compressed, wherein the coding unit codes the data to be compressed on the basis of the compressing inherent dictionary created by the compressing inherent dictionary creating unit and the compressing dictionary selected by the compressing dictionary selecting unit.

In the above case, data to be compressed is coded on the basis of both a compressing inherent dictionary and a compressing dictionary selected as above so that a probability of coding data to be compressed not registered in the dictionary is largely decreased, thus a compression ratio is further improved.

In this case, the above data compressing apparatus may have an inherent dictionary information outputting unit for outputting information on the compressing inherent dictionary to a decompressing side for the data to be compressed.

In the above case, the decompressing side can accurately decode (decompress) compressed data having been coded according to a compressing inherent dictionary originally created on the compressing side.

Each of the data compressing apparatus may further have a compressing dictionary updating unit for updating the compressing dictionary on the basis of data to be compressed having been coded by code in the coding unit, wherein the coding unit codes the data to be compressed on the basis of the compressing dictionary updated by the compressing dictionary updating unit.

In the above case, since the above compressing dictionary selected and used in the coding is updated on the basis of compressed data that is data to be compressed having been coded by code, it is possible to provide a plurality of compressing dictionaries suitable for the data to be compressed that is an object of the next coding as the coding process is proceeded so that a compression ratio is further improved.

In the above case, the above data compressing apparatus may have a selected dictionary information outputting unit for outputting selected dictionary information on the compressing dictionary selected by the compressing dictionary selecting unit to a decompressing side for the data to be compressed.

In this case, the decompressing side can quickly determine whether inputted compressed data has been coded using any one of the plural kinds of compressing dictionaries, which largely contributes to speeding-up of the decoding process.

The present invention still further provides a data decompressing apparatus for decompressing compressed data to decode the same comprising a decompressing dictionary storing unit for storing a decompressing dictionary usable when the compressed data is decompressed, a decompressing dictionary use or non-use deciding unit for deciding whether the decompressing dictionary is to be used or not when the compressed data is decompressed, and a decoding unit for decoding the compressed data on the basis of the decompressing dictionary when the decompressing dictionary use or non-use deciding unit decides the decompressing dictionary is to be used, whereas not decoding but outputting the compressed data when the decompressing dictionary use or non-use deciding unit decides the decompressing dictionary is not to be used.

The present invention also provides a data decompressing method for decoding compressed data to decompress the same comprising the steps of a receiving step of receiving dictionary use or non-use information on whether a decompressing dictionary is to be used or not when the compressed data is decompressed from a compressing side, a deciding step of deciding whether the decompressing dictionary is to be used according to the dictionary use or non-use information received at the receiving step, a decoding step of decoding the compressed data on the basis of the decompressing dictionary when decided the decompressing dictionary is to be used at the deciding step, and a data outputting step of not decoding but outputting the compressed data when decided the decompressing dictionary is not to be used at the deciding step.

According to the data decompressing apparatus and the data decompressing method of this invention, whether a decompressing dictionary is to be used when compressed data is decompressed is determined when the compressed data is decompressed, and the compressed data is decoded on the basis of the decompressing dictionary, or the compressed data is not decoded but outputted, according to a result of the decoding. It is therefore possible to omit unnecessary decoding process depending on a state of compression (including a time of non-compression) of compressed data so that the decoding process is performed very efficiently.

The above decoding unit may decode the compressed data by predetermined character data group on the basis of the decompressing dictionary.

In the above case, plural character data can be decoded as a bunch at a time so that the decoding (decompressing) process is largely sped up as compared with a case where the compressed data is decoded by one character data.

If data to be compressed that is the compressed data before compressed is document-form data, the character data group maybe a desired word in the document-form data, whereby the compressed data is decoded by word unit that is “a word” having own meaning. Thus, the decoding process can be performed at a high speed.

If the compressed data is decoded on the basis of the category information on the above word, a word to be decoded can be readily specified on the basis of the above category information, which leads to further speeding-up of the decoding process.

The above decompressing apparatus may further have a decompressing inherent dictionary storing unit for storing a dictionary having character data inherent to data to be compressed that is the compressed data before compressed as characteristic data of the compressed data, in which a predetermined code is assigned to each of the characteristic data as decompressing dictionary, wherein the decoding unit decodes the compressed data on the basis of the decompressing inherent dictionary in the decompressing inherent dictionary storing unit and the decompressing dictionary in the decompressing dictionary storing unit.

The above data decompressing apparatus decodes compressed data on the basis of both the decompressing inherent dictionary and the decompressing dictionary. Accordingly, it is possible to largely decrease a probability of decoding data to be compressed not registered in the dictionary, thus improve a decoding efficiency.

The above decompressing inherent dictionary storing unit may receive information on a compressing inherent dictionary created by extracting character data inherent to the data to be compressed as characteristic data of the data to be compressed and assigning a predetermined code to each of the characteristic data from a compressing side having generated the compressed data to store the decompressing inherent dictionary.

In the above case, a dictionary having the same contents as an inherent dictionary having been used on the compressing side can be created as the above decompressing inherent dictionary so that compressed data having been coded on the basis of a compressing inherent dictionary originally created on the compressing side can be decoded very accurately.

The above data decompressing apparatus may further have a decompressing dictionary updating unit for updating the decompressing dictionary on the basis of a result of decoding by the decoding unit, wherein the decoding unit decodes the compressed data on the basis of the decompressing dictionary updated by the decompressing dictionary updating unit.

In the above case, it is possible to provide a decompressing dictionary suitable for compressed data that is an object of the next decoding at any time, which leads to an improvement of the decoding efficiency.

The above decompressing dictionary use or non-use deciding unit may decide whether the decompressing dictionary is to be used or not according to information on use or non-use of a compressing dictionary received from a compressing side having generated the compressed data.

In the above case, it is possible to quickly determine whether the inputted compressed data has been coded using a compressing dictionary, which largely contributes to speeding-up of the decoding process.

The present invention still further provides a data decompressing apparatus for decoding compressed data to decompress the same comprising a decompressing dictionary storing unit for storing plural kinds of decompressing dictionaries usable when the compressed data is decompressed, a decompressing dictionary selecting unit for receiving selected dictionary information on a compressing dictionary selected on the basis of data contents type information representing a type of data contents of data to be compressed from a compressing side having generated the compressed data to select a decompressing dictionary to be used among the plural kinds of decompressing dictionaries on the basis of the received selected dictionary information, and a decoding unit for decoding the compressed data on the basis of the decompressing dictionary selected by the decompressing dictionary selecting unit.

The present invention also provides a data decompressing method for decoding compressed data to decompress the same comprising the steps of a receiving step of receiving selected dictionary information on a compressing dictionary selected on the basis of data contents type information representing a type of data contents of data to be compressed from a compressing side having generated the compressed data, a dictionary selecting step of selecting a decompressing dictionary to be used among plural kinds of decompressing dictionaries on the basis of the selected dictionary information received at the receiving step, and a decoding step of decoding the compressed data on the basis of the decompressing dictionary selected at the dictionary selecting step.

According to the data decompressing apparatus and the data decompressing method of this invention, the decompressing side receives the selected dictionary information on a compressing dictionary selected on the basis of the data contents type information representing a type of data contents of data to be compressed from a compressing side, selects a decompressing dictionary to be used among plural kinds of decompressing dictionaries on the basis of the received selected dictionary information, and decodes the compressed data on the basis of the selected decompressing dictionary. It is therefore possible to quickly select a decompressing dictionary having the same contents as a compressing dictionary selected on the basis of the above data contents type information on the compressing side at any time so as to accurately decode (decompress) the compressed data.

The present invention still further provides a decompressing apparatus for decoding compressed data to decompress the same comprising a decompressing dictionary storing unit for storing plural kinds of decompressing dictionaries usable when the compressed data is decompressed, a decompressing dictionary selecting unit for receiving selected dictionary information on a compressing dictionary selected as a compressing dictionary including specific character data of high occurrence frequency in data to be compressed from a compressing side having generated the compressed data to select a decompressing dictionary to be used among the plural kinds of decompressing dictionaries on the basis of the received selected dictionary information, and a decoding unit for decoding the compressed data on the basis of the decompressing dictionary selected by the decompressing dictionary selecting unit.

The present invention also provides a data decompressing method for decoding compressed data to decompress the same comprising the steps of a receiving step of receiving selected dictionary information on a compressing dictionary selected as a compressing dictionary including specific character data of high occurrence frequency in data to be compressed from a compressing side having generated the compressed data, a dictionary selecting step of selecting a decompressing dictionary to be used among plural kinds of decompressing dictionaries on the basis of the selected dictionary information received at the receiving step, and a decoding step of decoding the compressed data on the basis of the decompressing dictionary selected at the dictionary selecting step.

According to the data decompressing apparatus and the data decompressing method of this invention, the decoding side receives the selected dictionary information on a compressing dictionary selected as a compressing dictionary including specific character data of high occurrence frequency from the compressing side, selects a decompressing dictionary to be used among plural kinds of decompressing dictionaries on the basis of the received selected dictionary information, and decodes compressed data on the basis of the decompressing dictionary. It is therefore possible to quickly select a decompressing dictionary having the same contents as a compressing dictionary selected as a compressing dictionary including specific character data of high occurrence frequency on the compressing side, so as to accurately decode (decompress) the compressed data.

The present invention still further provides a data decompressing apparatus for decoding compressed data to decompress the same comprising a decompressing dictionary storing unit for storing plural kinds of dictionaries usable when the compressed data is decompressed, a decompressing dictionary selecting unit for receiving selected dictionary information on a compressing dictionary selected according to a quantity of compressed data having been coded from a compressing side having generated the compressed data to select a decompressing dictionary to be used among the plural kinds of decompressing dictionaries on the basis of the received selected dictionary information, and a decoding unit for decoding the compressed data on the basis of the decompressing dictionary selected by the decompressing dictionary selecting unit.

The present invention also provides a data decompressing method for decoding compressed data to decompress the same comprising the steps of a receiving step of receiving selected dictionary information on a compressing dictionary selected according to a quantity of compressed data having been coded from a compressing side having generated the compressed data, a dictionary selecting step of selecting a decompressing dictionary to be used among plural kinds of decompressing dictionaries on the basis of the selected dictionary information received at the receiving step, and a decoding step of decoding the compressed data on the basis of the decompressing dictionary selected at the dictionary selecting step.

According to the data decompressing apparatus and the data decompressing method of this invention, the decoding side receives the selected dictionary information on a compressing dictionary selected according to a quantity of compressed data having been coded from the compressing side, selects a decompressing dictionary to be used among plural kinds of decompressing dictionaries on the basis of the received selected dictionary information, and decodes compressed data on the basis of the decompressing dictionary. It is therefore possible to quickly select a decompressing dictionary having the same contents as a compressing dictionary selected according to a quantity of compressed data having been coded on the compressing side at any time so as to accurately decode (decompress) the compressed data.

The above decoding unit may decode the compressed data by predetermined character data group on the basis of the decompressing dictionary selected by the decompressing dictionary selecting unit.

In the above case, the compressed data is decoded by plural character data as a bunch at a time so that the decoding (decompressing) process after a dictionary is selected is performed at a higher speed, as compared with a case where the compressed data is decoded by one character data.

If data to be compressed that is the compressed data before compressed is document-form data, the character data group maybe a desired word in the document-form data. In this case, the compressed data can be decoded by word unit that is “a word” having own meaning so that the decoding process can be performed at a high speed.

The above decoding unit may decode the compressed data on the basis of category information on the word.

In the above case, it is possible to readily specify a word to be decoded on the basis of the above category information so that the decoding process is further sped up.

The above decompressing apparatus may further have a decompressing inherent dictionary storing unit for storing a dictionary having character data inherent to data to be compressed that is the compressed data before compressed as characteristic data of the compressed data, in which a predetermined code is assigned to each of the characteristic data as decompressing dictionary, wherein the decoding unit decodes the compressed data on the basis of the decompressing inherent dictionary in the decompressing inherent dictionary storing unit and the decompressing dictionary selected by the decompressing dictionary selecting unit.

Each of the above data decompressing dictionary decodes compressed data on the basis of both an inherent dictionary in which a predetermined code is assigned to each of character (characteristic) data inherent to data to be compressed that is the compressed data before compressed and a decompressing dictionary selected as above. It is therefore possible to largely decrease a probability of data to be compressed not registered in the selected dictionary, thus further improve the decoding efficiency.

The above decompressing inherent decompressing dictionary storing unit may receive information on a compressing inherent dictionary created by extracting character data inherent to the data to be compressed as characteristic data of the data to be compressed and assigning a predetermined code to each of the characteristic data from a compressing side having generated the compressed data to store the decompressing inherent dictionary.

In the above case, a dictionary having the same contents as an inherent dictionary used on the compressing side is generated on the decompressing side, so that data to be compressed having been coded according to the compressing inherent dictionary originally created on the compressing side can be decoded very accurately.

Each of the above data decompressing apparatus may further have a decompressing dictionary updating unit for updating the decompressing dictionary on the basis of a result of decoding by the decoding unit, wherein the decoding unit decodes the compressed data on the basis of the decompressing dictionary updated by the decompressing dictionary updating unit.

In the above case, as the decoding process is proceeded, it is possible to provide plural kinds o decompressing dictionaries suitable for compressed data that is an object of the next decoding, which leads to further improvement of the decoding efficiency.

The present invention still further provides a data compressing or decompressing dictionary creating apparatus for creating a dictionary used when data to be compressed is compressed or compressed data is decompressed comprising an occurrence frequency counting unit for counting an occurrence frequency of each character data occurring in data for creating a dictionary, a high occurrence frequency character data detecting unit for detecting character data whose occurrence frequency is higher than predetermined frequency on the basis of the occurrence frequency of each of the character data counted by the occurrence frequency counting unit, a code assigning unit for assigning a predetermined code to each of the high occurrence frequency character data detected by the high occurrence frequency character data detecting unit, and a dictionary generating unit for combining each of the high occurrence frequency character data with the code and outputting a combination thereof, thereby generating the dictionary.

According to the above data compressing or decompressing dictionary creating apparatus of this invention, a predetermined code is assigned to each of character data whose occurrence frequency is higher than predetermined frequency on the basis of occurrence frequency of each character data occurring in data for creating a dictionary, and the character data of high occurrence frequency is combined with the code and outputted, whereby a data compressing or decompressing dictionary is automatically created. It is therefore possible to omit labor to create the dictionary.

The present invention still further provides a data compressing or decompressing dictionary creating apparatus for creating a dictionary used when data to be compressed is compressed or compressed data is decompressed comprising a data dividing unit for diving data for creating a dictionary into predetermined character data groups, an occurrence frequency counting unit for counting an occurrence frequency of each of the character data groups obtained by the data dividing unit, a high occurrence frequency character data group detecting unit for detecting a character data group whose occurrence frequency is higher than predetermined frequency on the basis of the occurrence frequency of each of the character data groups counted by the occurrence frequency counting unit, a code assigning unit for assigning a predetermined code to the high occurrence frequency character group detected by the high occurrence frequency character group, and a dictionary generating unit for combining the high occurrence frequency character group with the code and outputting a combination thereof, thereby generating the dictionary.

According to the above data compressing or decompressing dictionary creating apparatus of this invention, a predetermined code is assigned to character group whose occurrence frequency is higher than predetermined occurrence frequency on the basis of occurrence frequency of each character data group obtained by dividing data for creating a dictionary, and the high occurrence frequency character data group is combined with the code and outputted, whereby a dictionary suitable for coding and decoding of data by the character data group can be automatically created. It is therefore possible to omit a labor to create the dictionary corresponding to character data groups.

If the data for creating a dictionary is document-form data, the character group may be a desired word in the document-form data. In which case, since a dictionary most suitable for a coding process and a decoding process by data unit that is “a word” having own meaning is created, the coding process for data to be compressed and the decoding process for compressed data are largely sped up.

At this time, the code assigning unit may add category information on the word to the word. In which case, the words can be grouped according to the category information so that the number of sorts of codes to be assigned to the words is decreased, and a code to be assigned to each word is shortened. It is therefore possible to decrease a size of the dictionary.

By using the dictionary, a quantity of codes after the coding process is decreased and a compression ratio is increased on the compressing (coding) side. On the decompressing side, a word to be decoded can be readily specified according to the category information, which leads to speeding-up of the decoding process.

The present invention still further provides a recording medium readable by a computer in which a data compressing program for coding data to be compressed to compress the same is recorded characterized in that the data compressing program makes the computer function as a compressing dictionary storing unit for storing a compressing dictionary usable when the data to be compressed is compressed, a compressing dictionary use or non-use deciding unit for deciding whether the compressing dictionary is to be used or not when the data to be compressed is compressed, and a coding unit for coding the data to be compressed on the basis of the compressing dictionary when the compressing dictionary use or non-use deciding unit decides the compressing dictionary is to be used, whereas not coding but outputting the data to be compressed when the compressing dictionary use or non-use deciding unit decides the compressing dictionary is not to be used.

The present invention still further provides a recording medium readable by a computer in which a data compressing program for coding data to be compressed to compress the same is recorded characterized in that the data compressing program makes the computer function as a compressing dictionary storing unit for storing plural kinds of compressing dictionaries usable when the data to be compressed is compressed, a compressing dictionary selecting unit for selecting a compressing dictionary to be used among the plural kinds of compressing dictionaries on the basis of data contents type information representing a type of data contents of the data to be compressed, and a coding unit of coding the data to be compressed on the basis of the compressing dictionary selected by the compressing dictionary selecting unit.

The present invention still further provides a recording medium readable by a computer in which a data compressing program for coding data to be compressed to compress the same is recorded characterized in that the data compressing program makes the computer function as a compressing dictionary storing unit for storing plural kinds of compressing dictionaries usable when the data to be compressed is compressed, a compressing dictionary selecting unit for selecting a compressing dictionary including specific character data of high occurrence frequency in the data to be compressed among the plural kinds of compressing dictionaries, and a coding unit for coding the data to be compressed on the basis of the compressing dictionary selected by the compressing dictionary selecting unit.

The present invention still further provides a recording medium readable by a computer in which a data compressing program for coding data to be compressed to compress the same is recorded characterized in that the data compressing program makes the computer function as a compressing dictionary storing unit for storing plural kinds of compressing dictionaries usable when the data to be compressed is compressed, a coding unit for coding the data to be compressed using any one of the plural kinds of compressing dictionaries, and a compressing dictionary selecting unit for selecting a compressing dictionary to be used among the plural kinds of compressing dictionaries according to a quantity of compressed data having been coded by the coding unit.

In the above recording medium readable by a computer in which a data compressing program is recorded according to this invention, a program for realizing the above data compressing apparatus (data compressing method) is recorded. Only by reading the program recorded in the recording medium by a computer, the computer may function as the above data compressing apparatus. Therefore, generalization or spread of the above data compressing apparatus is largely expected.

The present invention further provides a recording medium readable by a computer in which a data decompressing program for decoding compressed data to decompress the same characterized in that the data decompressing program makes the computer function as a decompressing dictionary storing unit for storing a decompressing dictionary usable when the compressed data is decompressed, a decompressing dictionary use or non-use deciding unit for deciding whether the decompressing dictionary is to be used or not when the compressed data is decompressed, and a decoding unit for decoding the compressed data on the basis of the compressing dictionary when the decompressing dictionary use or non-use deciding unit decided the decompressing dictionary is to be used, whereas not decoding but outputting the compressed data when the decompressing dictionary use or non-use deciding unit decides the decompressing dictionary is not to be used.

The present invention still further provides a recording medium readable by a computer in which a data decompressing program for decoding compressed data to decompress the same characterized in that the data decompressing program makes the computer function as a decompressing dictionary storing unit for storing plural kinds of decompressing dictionaries usable when the compressed data is decompressed, a decompressing dictionary selecting unit for receiving selected dictionary information on a compressing dictionary selected on the basis of data contents type information representing a type of data contents of data to be compressed from a compressing side having generated the compressed data to select a decompressing dictionary to be used among the plural kinds of decompressing dictionaries on the basis of the received selected dictionary information, and a decoding unit for decoding the compressed data on the basis of the decompressing dictionary selected by the decompressing dictionary selecting unit.

The present invention still further provides a recording medium readable by a computer in which a data decompressing program for decoding compressed data to decompress the same characterized in that the data decompressing program makes the computer function as a decompressing dictionary storing unit for storing plural kinds of decompressing dictionaries usable when the compressed data is decompressed, a decompressing dictionary selecting unit for receiving selected dictionary information on a compressing dictionary selected as a compressing dictionary including specific character data frequently occurring in data to be compressed from a compressing side having generated the compressed data to select a decompressing dictionary to be used among the plural kinds of decompressing dictionaries on the basis of the received selected dictionary information, and a decoding unit for decoding the compressed data on the basis of the decompressing dictionary selected by the decompressing dictionary selecting unit.

The present invention still further provides a recording medium readable by a computer in which a data decompressing program for decoding compressed data to decompress the same characterized in that the data decompressing program makes the computer function as a decompressing dictionary storing unit for storing plural kinds of decompressing dictionaries usable when the compressed data is decompressed, a decompressing dictionary selecting unit for receiving selected dictionary information on a compressing dictionary selected according to a quantity of compressed data having been coded from a compressing side having generated the compressed data to select a decompressing dictionary to be used among the plural kinds of decompressing dictionaries on the basis of the received selected dictionary information, and a decoding unit for decoding the compressed data on the basis of the decompressing dictionary selected by the decompressing dictionary selecting unit.

In the recording medium readable by a computer in which a data decompressing program is recorded according to this invention, a program for realizing the above data decompressing apparatus (data decompressing method) is recorded. Only reading the program recorded in the recording medium by a computer, it is possible to function the computer as the above data decompressing apparatus. Therefore, generalization or spread of the above data decompressing apparatus is largely expected.

FIG. 1 is a block diagram showing a structure of a data compressing apparatus according to a first embodiment of this invention;

FIG. 2 is a block diagram showing a computer system to which the data compressing apparatus and a data decompressing apparatus according to the first embodiment of this invention are applied;

FIG. 3 is a flowchart for illustrating an operation of the data compressing apparatus according to the first embodiment;

FIG. 4 is a flowchart for illustrating an operation (statistical coding) of a coding unit of the data compressing apparatus according to the first embodiment;

FIG. 5 is a flowchart for illustrating an operation (dictionary-based coding) of the coding unit of the data compressing apparatus according to the first embodiment;

FIG. 6 is a block diagram showing a structure of a data decompressing apparatus according to the first embodiment;

FIG. 7 is a flowchart for illustrating an operation of the data decompressing apparatus according to the first embodiment;

FIG. 8 is a flowchart for illustrating an operation (statistical decoding) of a decoding unit of the data decompressing apparatus according to the first embodiment;

FIG. 9 is a flowchart for illustrating an operation (dictionary-based decoding) of the decoding unit of the data decompressing apparatus according to the first embodiment;

FIG. 10 is a block diagram showing a structure of a data compressing apparatus according to a first modification of the first embodiment;

FIGS. 11 through 13 are flowcharts for illustrating operations of the data compressing apparatus according to the first modification of the first embodiment;

FIG. 14 is a block diagram showing a structure a dictionary creating apparatus according to the first modification of the first embodiment;

FIG. 15 is a block diagram showing a structure of a data compressing apparatus according to a second modification of the first embodiment;

FIG. 16 is a block diagram showing a structure of a dictionary creating apparatus according to the second modification of the first embodiment;

FIG. 17 is a block diagram showing a structure of a data compressing apparatus according to a third modification of the first embodiment;

FIG. 18 is a flowchart for illustrating an operation (statistical coding) of a coding unit of the data compressing apparatus according to the third modification of the first embodiment;

FIG. 19 is a flowchart for illustrating an operation (dictionary-based coding) of the data compressing apparatus according to the third modification of the first embodiment;

FIG. 20 is a flowchart for illustrating an operation (statistical decoding) of a coding unit of a data decompressing apparatus according to the third modification of the first embodiment;

FIG. 21 is a flowchart for illustrating an operation (dictionary-based decoding) of the decoding unit of the data decompressing apparatus according to the third modification of the first embodiment;

FIG. 22 is a block diagram showing a structure of a dictionary creating apparatus according to the third modification of the first embodiment;

FIG. 23 is a block diagram showing a structure of a data compressing apparatus according to a fourth modification of the first embodiment;

FIG. 24 is a flowchart for illustrating an operation of the data compressing apparatus according to the fourth modification of the first embodiment;

FIG. 25 is a block diagram showing a structure of a data decompressing apparatus according to the fourth modification of the first embodiment;

FIG. 26 is a flowchart for illustrating an operation of the data decompressing apparatus according to the fourth modification of the first embodiment;

FIG. 27 is a block diagram showing a structure of a data compressing apparatus according to a fifth modification of the first embodiment;

FIG. 28 is a flowchart for illustrating an operation (statistical coding) of a coding unit of the data compressing apparatus according to the fifth modification of the first embodiment;

FIG. 29 is a flowchart for illustrating an operation (dictionary-based coding) of the coding unit of the data compressing apparatus according to the fifth modification of the first embodiment;

FIG. 30 is a block diagram showing a structure of a data decompressing apparatus according to the fifth modification of the first embodiment;

FIG. 31 is a flowchart for illustrating an operation (statistical decoding) of a decoding unit of the data decompressing apparatus according to the fifth modification of the first embodiment;

FIG. 32 is a flowchart for illustrating an operation (dictionary-based coding) of the decoding unit of the data decompressing apparatus according to the fifth modification of the first embodiment;

FIG. 33 is a block diagram showing a structure of a data compressing apparatus according to a second embodiment of this invention;

FIG. 34 is a flowchart for illustrating an operation of the data compressing apparatus according to the second embodiment;

FIG. 35 is a block diagram showing a structure of a data decompressing apparatus according to the second embodiment;

FIG. 36 is a flowchart for illustrating an operation of the data decompressing apparatus according to the second embodiment;

FIG. 37 is a block diagram showing a structure of a data compressing apparatus according to a first modification of the second embodiment;

FIG. 38 is a flowchart for illustrating an operation of the data compressing apparatus according to the first modification of the second embodiment;

FIGS. 39 and 40 are flowcharts for illustrating operations of the data compressing apparatus according to the first modification of the second embodiment;

FIG. 41 is a block diagram showing a structure of a data compressing apparatus according to a second modification of the second embodiment;

FIG. 42 is a block diagram showing a structure of a data compressing apparatus according to a third modification of the second embodiment;

FIG. 43 is a block diagram showing a structure of a data compressing apparatus according to a fourth modification of the second embodiment;

FIG. 44 is a block diagram showing a structure of a data decompressing apparatus according to the fourth modification of the second embodiment;

FIG. 45 is a block diagram showing a structure of a data decompressing apparatus according to a fifth modification of the second embodiment;

FIG. 46 is a block diagram showing a structure of a data decompressing apparatus according to the fifth modification of the second embodiment;

FIG. 47 is a diagram for illustrating an example where the data compressing apparatus according to the first and/or second embodiments is applied;

FIG. 48 is a diagram for illustrating a variable-length coding using a context model;

FIGS. 49 ( a ) and 49 ( b ) are diagrams for illustrating a context model;

FIG. 50 is a flowchart for illustrating a static coding;

FIG. 51 is a flowchart for illustrating a semi-adaptive coding; and

FIG. 52 is a flowchart for illustrating an adaptive coding.

(A) Description of a First Embodiment of the Invention

Hereinafter, description will be made of a first embodiment of this invention with reference to the drawings.

FIG. 2 is a block diagram showing a computer system to which a data compressing apparatus and a data decompressing apparatus according to the first embodiment of this invention are applied. In the system according to this embodiment, each of personal computers 1 and 2 is connected to a certain network 6 such as Internet or the like via a network connecting apparatus 4 such as a modem, a TA (Terminal Adapter) or the like, as shown in FIG. 2 .

Each of the personal computers 1 and 3 has, as shown in FIG. 2, a personal computer main body 21 , a display (display screen) 22 , a keyboard 23 and a mouse (pointing device) 24 , etc. The user can make a desired document or program with an editor in the personal computer 1 or 3 , store the made document data or program data as a document file or a program execute file in a hard disk (storage apparatus) 27 in the main body 21 through a process by a CPU (Central Processing Unit) 26 , or provide the document data or the program data (transfer the file) to another personal computer 3 or 1 over the network 6 .

When the above document data or program data is stored in the hard disk 27 or transferred over the network 6 , it is generally desirable that the data is coded, compressed, and stored/transferred in order to save a memory capacity, or decrease a data transmission quantity or a data transmission time, then the compressed data is decompressed (decoded) when displayed on the display 22 or printed out.

According to this embodiment, a data compressing program or a data decompressing program is stored in, for example, the hard disk 27 , and the CPU 26 operates according to the program, whereby the personal computer 1 or 3 is used as a data compressing apparatus which codes and compresses document data (data to be compressed) or a decompressing apparatus which decodes and decompresses coded and compressed data (compressed data).

The user can make each of the above data compressing program and the data decompressing program using an editor or the like of the personal computer 1 or 3 , or receive the program made in another personal computer 3 or 1 over the network 6 and store it in the hard disk 27 . Alternatively, the user can retain (install) the program in the hard disk 27 by reading the program stored in advance in one of various types of storage medium 28 such as a floppy disk (FD) 28 a , a CD-ROM 28 B, an MO (magneto-optic disk) 28 C and the like by CPU 26 through a disk drive 25 . Whereby, the CPU (computer) 26 can function as a data compressing apparatus or a data decompressing apparatus, which leads to improvement or spread of the data compressing apparatus and the data decompressing apparatus.

Hereinafter, the above data compressing apparatus will be referred to as a compressing side, whereas the data decompressing apparatus will be referred to as a decompressing side. Besides, description will be hereinafter made on an assumption that the personal computer 1 is used as the data compressing apparatus, whereas the personal computer 3 is used as the data decompressing apparatus (that is, the CPU 26 of the personal computer 1 functions as the data compressing apparatus, whereas the CPU 26 of the personal computer 3 functions as the data decompressing apparatus), for the sake of convenience.

(a) Description of the Compressing Side (Data Compressing Apparatus)

FIG. 1 is a block diagram showing a structure of a data compressing apparatus 1 according to the first embodiment of this invention. The data compressing apparatus 1 shown in FIG. 1 has a dictionary storing unit 11 , an initial dictionary use or non-use deciding unit 12 , a dictionary referring unit 13 , a coding unit 14 and a dictionary use or non-use information outputting unit 15 .

The dictionary storing unit (compressing dictionary storing unit) 11 stores a dictionary (compressing dictionary) which can be used when document data inputted as data (strings) to be compressed is compressed. In the dictionary, a predetermined code is assigned to each character of a high probability of occurring in data to be compressed. Incidentally, a storage area for the dictionary storing unit 11 may be secured in the above hard disk 27 or prepared as an exclusive memory area.

The initial dictionary use or non-use deciding unit (compressing dictionary use or non-use deciding unit) 12 decides whether the above compressing dictionary stored in the dictionary storing unit 11 is to be used or not when the above data to be compressed is compressed. Here, the initial dictionary use or non-use deciding unit 12 decides use or non-use of the above compressing dictionary according to contents of the data to be compressed (text file data, execute file data, or the like).

Because of this, the initial dictionary use or non-use deciding unit 12 is inputted a file name (or a header file) of file data inputted as data to be compressed as data contents type information showing a type contents of the data to be compressed. The deciding unit 12 decides whether the compressing dictionary is to be used or not depending on what is an extension (“tex” when the file name is “File1.tex”, or “exe” when the file name is “File2.exe”) generally given to the inputted file name.

In the case where a dictionary for text file data is stored as the above compressing dictionary in the dictionary storing unit 11 , the initial dictionary use or non-use deciding unit 12 decides the dictionary in the dictionary storing unit 11 is to be used when an extension of an inputted file name is “tex” representing a text file, whereas decides the dictionary is not to be used when the extension is other than “tex” (“exe” or the like)

The dictionary referring unit 13 refers to (reads out) the above compressing dictionary stored in the dictionary storing unit 11 when the above initial dictionary use or non-use deciding unit 12 decides use of the compressing dictionary. The coding unit 14 codes the data to be compressed on the basis of the compressing dictionary read out from the dictionary storing unit 11 by the dictionary referring unit 13 when the above deciding unit 12 decides use of the compressing dictionary. When the deciding unit 12 decides non-use of the compressing dictionary, the coding unit 14 outputs the data to be compressed, not coding it.

The dictionary use or non-use information outputting unit 15 outputs information about use or non-use of the compressing dictionary (for example, use: 11, or non-use: 00) decided by the above initial dictionary use or non-use deciding unit 12 . Incidentally, the dictionary use or non-use information outputting unit 15 is provided in order that the decompressing side may readily discriminate whether compressed data that is an object of decompression has been coded using the compressing dictionary or not. Therefore, the dictionary use or non-use information outputting unit 15 is not an essential element for a coding process (can be omitted).

Next, an operation (data compressing method) of the data compressing apparatus 1 having the above structure according to the first embodiment will be described in detail with reference to a flowchart (Steps D 1 through D 7 ) shown in FIG. 3 .

When a file name is inputted to the data compressing apparatus 1 (Step D 1 ), the initial dictionary use or non-use deciding unit 12 determines whether an extension of the inputted file name is an extension “txt” representing a text file or not (deciding step: Step D 2 ). If the extension is “txt” as a result (if judged YES at Step D 2 ), the initial dictionary use or non-use deciding unit 12 decides use of the compressing dictionary, and notifies the dictionary referring unit 13 of it.

When receiving the notification, the dictionary referring unit 13 reads out the compressing dictionary (dictionary for text file data) stored in the dictionary storing unit 11 so that the coding unit 14 can refer to the compression dictionary (set the dictionary: Step D 3 ). When the dictionary is set, the dictionary use or non-use information outputting unit 15 outputs a code (11, for example) representing use of the compressing dictionary as dictionary use or non-use information to the decoding side, which will be described later (Step D 4 ). At this time, the coding unit 14 codes the data to be compressed according to the compressing dictionary set by the dictionary referring unit 13 to compress the same (coding step: Step D 5 ).

In concrete, the coding process is performed in either (1) statistical coding utilizing the context modeling described before or (2) dictionary-based coding.

(1) In the Case of Statistical Coding

The coding unit 14 , as shown in FIG. 4, for example, initializes a parameter t for retrieving a context (character string) X (t−n, t−1) (t=0) (Step D 8 ), and sets a parameter n for retrieving a longest matching character (data) string in the context X (t−n, t−1) to a maximum order (a maximum number of characters consisting of the context) of the context X (t−n, t−1) (Step D 9 ). Wherein, the above t, n and N are natural numbers, and the above X (t−n, t−1) represents a data string {X t−n , X t−n+1 , . . . , X t−1 } (where X t represents one character).

The coding unit 14 determines whether a certain context X (t−n, t−1) exists in the compressing dictionary set as above (Step D 10 ). If the context X does not exist in the compressing dictionary, the coding unit 14 repeats retrieval of the context X (t−n, t−1) while decrementing the parameter n (n=n−1) (descending the order of the context) until detecting the context X (t−n, t−1) (from No route at Step D 10 to Step D 13 ).

If the context X (t−n, t−1) exists in the dictionary, the coding unit 14 further determines whether a context consisting of the context X (t−n, t−1) and an inputted character (data to be compressed) Xt added thereto has already existed in the above compressing dictionary or not (from YES route at Step D 10 to Step D 11 ). If the context does not exist in the compressing dictionary, the coding unit 14 outputs ESC (escape code) following the context X (t−n, t−1) (from NO route at Step D 11 to Step D 12 ), descends the order of the context (Step D 13 ), and repeats the above process until detecting the combination (context) of the context X (t−n, t−1) and the inputted character Xt.

Namely, the coding unit 14 in the probability statistical coding retrieves the context X (t−n, t−1) in the dictionary (context tree) while descending the order of the context X (t−n, t−1) one by one until determining that the context (character string) X (t−n, t−1) that is an object of coding exists in the dictionary, thereby retrieving a character string in the dictionary longest-matching with a character string (t, t+1) that is an object of the coding.

When a combination of the context X (t−n, t−1) and the inputted character Xt is detected (exists in the compressing dictionary), the coding unit 14 outputs a code of the character Xt following the context X (t−n, t−1) (from YES route at Step D 11 to Step D 14 ). After that, the coding unit 14 increments the parameter t (t=t+1: Step D 15 ), and successively codes an inputted character Xt while altering the context X (t−n, t−1) that is an object of the retrieval (NO route at Step D 16 ) until coding of all inputted data is completed (until judged YES at Step D 16 ).

(2) In the Case of Dictionary-based Coding

When dictionary-based coding is applied, the coding unit 14 , as shown in FIG. 5, for example, initializes parameters t and n for altering a character string X (t, t+1) that is an object of retrieval, and the number of extended characters Cn of the character string X (t, t+n) (where t, n, Cn are natural numbers) (t=0, N−1, Cn=0: Steps D 17 and D 18 ). In this case, the above X (t, t+n) represents a data string {X t , X t+1 , . . . , X t+1 } (where X t represents one character), as well.

The coding unit 14 determines whether a character string starting with an inputted character string (data string that is an object of retrieval) X (t, t+n) to be coded exists in the compressing dictionary set as above (Step D 19 ). If the character string exists in the compressing dictionary, the coding unit 14 further determines whether the character string is the same as the character string X (t, t+n) that is an object of retrieval [whether the data string X (t, t+n) exists in the dictionary or not] (from YES route at Step D 19 to Step D 20 ).

If the character string X (t, t+n) that is an object of retrieval itself exists in the dictionary as a result, the coding unit 14 sets the number of extended characters Cn to a value of the above parameter n (Step D 21 ), increments n (n=n+1) (Step D 22 ) to increase (extends) the data string X (t, t+n) that is an object of retrieval by one character, and again determines whether the extended character string X (t, t+n) exists in the dictionary or not.

The coding unit 14 applied dictionary-based coding retrieves the character string X that is an object of coding in the dictionary while extending the character string (t, t+n) one character by one character until it is determined that the character string X (t, t+n) does not exist in the dictionary, thereby retrieving a character string in the dictionary longest-matching with the character string (t, t+n) that is an object of coding.

The coding unit 14 next determines whether the number of extended characters Cn=0 if it is determined that the character string X (t, t+n) does not exist in the dictionary (from NO route at Step D 19 to Step D 23 ). If Cn≠0 as a result, the coding unit 14 outputs a code in the dictionary corresponding to the extended character string X (t, t+Cn) (from NO route at Step D 23 to Step D 24 ). If Cn=0, it means that it is determined that the character string X (t, t+n) exists in the dictionary as the character string X (t, t+n) could not be extended any character so that the coding unit 14 outputs a code representing copy (from YES route at Step D 23 to Step D 25 ), and outputs a character Xt before extended (Step D 26 )

The coding unit 14 increments the parameter t (t=t+Cn+1) (Step D 27 ), thereby successively coding an inputted character string X (t, t+n) while altering the character string X that is an object of retrieval (No route at Step D 28 ) until coding of all inputted data is completed (until judged YES at Step D 28 ).

If an extension of the inputted file name is not the extension “txt” representing a text file at above Step D 2 (if judged NO at Step D 2 ), the initial dictionary use or non-use deciding unit 12 determines that there is a good possibility of a quantity of compressed (coded) data being larger than a quantity of original data if file data (data to be compressed) whose extension is not “txt” is coded using a dictionary for text file data, so as to decide non-use of the compressing dictionary, and notifies the dictionary referring unit 13 of it.

The dictionary referring unit 13 transfers this notification to the dictionary use or non-use information outputting unit 15 and the coding unit 14 . When receiving the notification, the dictionary use or non-use information outputting unit 15 outputs a code representing non-use of the compressing dictionary (00, for example) as dictionary use or non-use information to the decoding side (Step D 6 ). The coding unit 14 does not code the data to be compressed, but copies the data and output it (data outputting step: Step D 7 ).

Namely, the data compressing apparatus 1 (data compressing method) according to the first embodiment determines that a coding using a dictionary for text file data prepared in advance can achieve a good compression ratio if inputted data to be compressed is text file data, and codes the data to be compressed. If the inputted data to be compressed is not text file data, the data compressing apparatus 1 determines that a coding using the above dictionary produces a poor compression ratio so as not to code the data to be compressed.

In the case where a coding using a dictionary produces a poorer compression efficiency, for example, a quantity of compressed data becomes larger than a quantity of original data, the data to be compressed is not coded (compressed) so that degradation of the compression efficiency can be prevented. Therefore, it is possible to ensure a compression efficiency above a certain level.

(b) Description of the Decoding Side (Data Decompressing Apparatus)

FIG. 6 is a block diagram showing a structure of a data decompressing apparatus 3 according to the first embodiment. The data decompressing apparatus 3 shown in FIG. 6 decompresses (decodes) compressed data (codes) compressed in the above-described data compressing apparatus 1 . The data decompressing apparatus 3 has a dictionary storing unit 31 , an initial dictionary use or non-use deciding unit 32 , a dictionary referring unit 33 , and a decoding unit 34 .

The dictionary storing unit (decompressing dictionary storing unit) 31 stores a decompressing dictionary which can be used when compressed data compressed by the data compressing apparatus 1 is decompressed. In the dictionary storing unit 31 , there is stored a dictionary having the same contents as the dictionary stored in the dictionary storing unit 11 of the data compressing apparatus 1 as a decompressing dictionary. A storage area for the dictionary storing unit 31 may be ensured in the hard disk 27 , or prepared as an exclusive memory area.

The initial dictionary use or non-use deciding unit (decompressing dictionary use or non-use deciding unit) 32 decides whether or not the above decompressing dictionary stored in the dictionary storing unit 31 is used when the above compressed data is decompressed. Here, whether or not the decompressing dictionary is used is decided according to received information about use or non-use of the compressing dictionary (use: 11, non-use: 00) outputted from the dictionary use or non-use information outputting unit 15 of the data compressing apparatus 1 .

When the initial dictionary use or non-use deciding unit 32 decides use of the decompressing dictionary, the dictionary referring unit 33 reads out the decompressing dictionary from the dictionary storing unit 31 . When the initial dictionary use or non-use deciding unit 32 decides use of the decompressing dictionary, the decoding unit 34 decodes the compressed data on the basis of the decompressing dictionary read out by the dictionary referring unit 33 . When the initial dictionary use or non-use deciding unit 32 decodes non-use of the decompressing dictionary, the decoding unit 34 does not decode the compressed data, but outputs it.

Next, an operation of the data decompressing apparatus 3 having the above structure according to the first embodiment will be described in detail with reference to flowcharts (Steps E 1 through E 19 ) shown in FIGS. 7 through 9.

As shown in FIG. 7, when receiving dictionary use or non-use information from the data compressing apparatus 1 (receiving step: Step E 1 ), the initial dictionary use or non-use deciding unit 32 in the data decompressing apparatus 3 decides use or non-use of the decompressing dictionary according to the received dictionary use or non-use information (deciding step). If the dictionary use or non-use information is a code (11) representing use of the compressing dictionary, for example, the deciding unit 32 decides use of the decompressing dictionary. If the dictionary use or non-use information is a code (00) representing non-use of the compressing dictionary, the deciding unit 32 decides non-use of the decompressing dictionary.

When the deciding unit 32 decides use of the decompressing dictionary, the dictionary referring unit 33 reads out the decompressing dictionary from the dictionary storing unit 31 (setting the dictionary: Step E 2 ). The decoding unit 34 decodes the compressed data according to the decompressing dictionary set by the dictionary referring unit 33 (decoding step: Step E 3 ).

Here, a decoding system in the decoding unit 34 is decided according to a coding system for the compressed data (coding system having been employed in the coding unit 14 of the data compressing apparatus 1 ).

(1) In the Case Where the Compressing Side Employs Statistical Coding

In this case, the decoding unit 34 , as shown in FIG. 8, for example, initializes the parameter t for retrieving a context (character string) X (t−n, t−1) (step E 4 ), besides setting a parameter n for retrieving a longest-matching character string in the context X (t−n, t−1) to a maximum order (a maximum number of characters consisting of the context) N of the context X (t−n, t−1) (step E 5 ). Wherein, the above t, n and N are natural numbers, and the above X (t−n, t−1) represents a character string {X t−n , X t−n+1 , . . . , X t−1 } (where X t represents one character).

The decoding unit 34 determines whether or not a certain context (t−n, t−1) that is an object of decoding exists in the decompressing dictionary set as above (Step E 6 ). If not, the decoding unit 34 repeats retrieval of the context X (t−n, t−1) while decrementing the parameter n (n=n−1) (descending the order of the context) until detecting the context X (t−n, t−1) (from NO route at Step E 6 to Step E 9 ).

When detecting the context X (t−n, t−1), the decoding unit 34 decodes a longest-matching character x according to a code corresponding to the context X (t−n, t−1) (from YES route at Step E 6 to Step E 7 ), and determines whether the decoded longest-matching character x is ESC or not (escape code) (Step E 8 ) If the decoded character x is ESC as a result (if judged YES at Step E 8 ), the decoding unit 34 repeats retrieval of the context X (t−n, t−1) while decrementing the parameter n until decoding a character other than ESC (from YES route at Step E 8 to Step E 9 ).

If the decoded character is other than ESC, the decoding unit 34 outputs the decoded character x as a decoded character Xt (Xt=x: from NO route at Step E 8 to Step E 10 ). The decoding unit 34 increments the parameter t (t=t+1: Step E 11 ), and successively decoded inputted compressed data while altering the context X (t−n, t−1) that is an object of retrieval (NO route at Step E 12 ) until the decoding is completed (until judged YES at Step E 12 ).

(2) In the Case Where the Compressing Side Employs Dictionary-based Coding

In this case, the decoding unit 34 , as shown in FIG. 9, for example, initializes a parameter t (t=0) (Step E 13 ), then determines whether or not an inputted code (compressed data) is a code representing copy (Step E 14 ).

If the inputted code is not a code representing copy as a result, the decoding unit 34 obtains a character string corresponding to the inputted code from the decompressing dictionary and outputs it as a decoded character string X (t, t+n) (from NO route at Step E 14 to Step E 15 ), and increments the parameter t by n (t=t+n: Step E 16 )

If the inputted code is a code representing copy, the decoding unit 34 outputs the inputted code as a decoded code as it is (from YES route at Step E 14 to Step E 17 ), then increments the parameter t (t=t+n: Step E 18 ).

The decoding unit 34 successively decodes inputted compressed data (NO route at Step E 19 ) until decoding of all compressed data is completed (until judged YES at Step E 19 ).

If the above initial dictionary use or non-use deciding unit 32 decides no-use of the decompressing dictionary, the dictionary referring unit 33 notifies the decoding unit 34 of it. The decoding unit 34 does not decode the compressed data (original data having not been actually compressed on the compressing side), but outputs it as it is (data outputting step).

The data decompressing apparatus 3 (data decompressing method) according to the first embodiment decides whether or not the decompressing dictionary is used according to the dictionary use or non-use information received from the compressing side when decompressing compressed data. According to a result of the decision, the decompressing apparatus 3 decodes the compressed data on the basis of the decompressing dictionary, or does not decode the compressed data but outputs it. It is therefore possible to select decoding or non-decoding of the compressed data.

Accordingly, it is possible to cut unnecessary decoding process depending on a condition of compression of the compressing data (including the time of non-compression) so that the decoding process can be performed very efficiently. The decompressing apparatus 3 can quickly determine whether or not the inputted compressed data has been coded using the dictionary when compressed to decide use or non-use of the decompressing dictionary. This largely contributes to speed-up of the decoding process.

(A1) Description of a First Modification of the First Embodiment

(a) Description of the Compressing Side

FIG. 10 is a block diagram showing a structure of a data compressing apparatus according to a first modification of the first embodiment. In a data compressing apparatus 1 shown in FIG. 10, the initial dictionary use or non-use deciding unit 12 decides use or non-use of the compressing dictionary on the basis of not contents discriminating data such as a file name or the like as described above, but inputted data to be compressed, unlike the compressing apparatus 1 shown in FIG. 1 .

In concrete, the initial dictionary use or non-use deciding unit 12 according to this modification decides use or non-use of the compressing dictionary according to judging conditions {circle around (1)}, {circle around (2)} or {circle around (3)} below, for example:

{circle around (1)} whether all specific characters (strings) of high occurrence frequency in data to be compressed are included in the compressing dictionary;

{circle around (2)} whether a quantity of compressed data is larger than a quantity of original data;

{circle around (3)} whether specific character codes exist in data to be compressed.

If use or non-use of the compressing dictionary is decided according to the above judging conditions {circle around (2)}, the initial dictionary use or non-use deciding unit 12 can receive information on a result of coding by the coding unit 14 , as indicated by a broken line in FIG. 10 .

Next, an operation of the data compressing apparatus 1 according to the first modification will be described for each of the above judging conditions.

(1) In the Case Where Use or Non-use of the Compressing Dictionary is Decided According to the Above Judging Conditions {circle around (1)}

In this case, the initial dictionary use or non-use deciding unit 12 , as shown in FIG. 11, for example, initializes an array (count value) C[ ] for counting (calculating) an occurrence frequency of each characters (character strings) (Step F 1 ). When one character (or one character string) a of data to be compressed is inputted, for example, (Step F 2 ), the initial dictionary use or non-use deciding unit 12 counts up the count value C[a] of the inputted character (character string) a (C[a]=C[a]+1: Step F 3 ).

The initial dictionary use or non-use deciding unit 12 repeats the above process until inputting of all data to be compressed is completed (until judged YES at Step F 4 ), thereby successively counting the occurrence frequency of each character occurring in the data to be compressed (NO route at Step F 4 ). When the inputting of all the data to be compressed is completed, the initial dictionary use or non-use deciding unit 12 refers to a count value C[ ] of each character (character string), and extracts N (a natural number not less than 2) characters (character strings) in high ranks S 1 through S N (provided occurrences of S N−1 >occurrences of S N ) whose count values are large (that is, high occurrence frequency) (from YES route at Step F 4 to Step F 5 ).

The initial dictionary use or non-use deciding unit 12 next refers to the compressing dictionary stored in the dictionary storing unit through the dictionary referring unit 13 to decide whether all the characters (character strings) S 1 through S N extracted as above are included in the compressing dictionary (Step F 6 ). If all the characters (character strings) S 1 through S N are included in the compressing dictionary as a result, the initial dictionary use or non-use deciding unit 12 decides use of the compressing dictionary, and notifies the dictionary referring unit 13 of it. When receiving the notification, the dictionary referring unit 13 reads out the compressing dictionary stored in the dictionary storing unit 11 so that the coding unit 14 can refer to the compressing dictionary (setting the dictionary: from YES route at Step F 6 to Step F 7 ).

When the dictionary is set as above, the dictionary use or non-use information outputting unit 15 outputs a code representing use of the compressing dictionary as the dictionary use or non-use information to the decoding side (Step F 8 ), besides the coding unit 14 codes and compresses the data to be compressed according to the compressing dictionary set by the dictionary referring unit 13 (Step F 9 ). Incidentally, the coding in the coding unit 14 may be performed in either statistical coding or dictionary-based coding described above.

If any one of the above N characters (character strings) S 1 through S N in high ranks frequently occurring is not included in the compressing dictionary (if judged NO at Step F 6 ) the initial dictionary use or non-use deciding unit 12 decides non-use of the compressing dictionary, and notifies the dictionary referring unit 13 of it. The dictionary referring unit 13 transfer the notification to the dictionary use or non-use information outputting unit 15 and the coding unit 14 . When receiving the notification, the dictionary use or non-use information outputting unit 15 outputs a code representing non-use of the compressing dictionary as the dictionary use or non-use information to the decoding side (Step F 10 ) The coding unit 14 does not code the data to be compressed but outputs it (Step F 11 ).

Namely, the above data compressing apparatus 1 makes a decision according to occurrences of specific character data in data to be compressed. Here, the data compressing apparatus 1 decides use of the compressing dictionary for data to be compressed in which specific characters (character strings) S 1 through S N frequently occurring are all included in the compressing dictionary, as above. Therefore, it is possible to assign short codes to specific characters (character strings) S 1 through S N frequently occurring. This produces a compression effect above a certain level.

(2) In the Case Where Use or Non-use of the Compressing Dictionary is Decided According to the Above Judging Conditions {circle around (2)}

In this case, the initial dictionary use or non-use deciding unit 12 , as shown in FIG. 12, for example, accepts an input of a character string X(t, t+n) of a predetermined buffer size from character strings to be compressed (Step F 12 ), decides use of the compressing dictionary for the character string X(t, t+n), and notifies the dictionary referring unit 13 of it. The dictionary referring unit 13 reads out the compressing dictionary from the dictionary storing unit 11 . The coding unit 14 codes the character string X (t, t+n) on the basis of the compressing dictionary (Step F 13 ).

After coding the character string X (t, t+n) the coding unit 14 outputs information about a quantity of data (codes) of the coded compressed data resulting from the coding to the initial dictionary use or non-use deciding unit 12 . When receiving the information, the initial dictionary use or non-use deciding unit 12 determines whether a quantity of the coded data is smaller than the original buffer size (Step F 14 ).

If a quantity of the coded data is smaller than the original buffer size n+1 as a result (if judged YES at Step F 14 ), the initial dictionary use or non-use deciding unit 12 notifies the dictionary use or non-use information outputting unit 15 and the coding unit 14 via the dictionary referring unit 13 of it. The dictionary use or non-use information outputting unit 15 outputs a code representing use of the compressing dictionary to the decoding side. The coding unit 14 outputs a code of the character string X (t, t+n) after that, codes the remaining data to be compressed with reference to the compressing dictionary (Steps F 15 and F 16 ). In this case, a coding system in the coding unit 14 may be statistical coding or dictionary-base coding mentioned above.

If a quantity of the coded data is larger than the original buffer size (if judged NO at Step F 14 ), the initial dictionary use or non-use deciding unit 12 notifies the dictionary use or non-use information outputting unit 15 and the coding unit 14 via the dictionary referring unit 13 of it. The dictionary use or non-use information outputting unit 15 outputs a code representing non-use of the compressing dictionary to the decoding side (Step F 17 ). The coding unit 14 copies the data to be compressed and outputs it (Step F 18 ).

Namely, the above data compressing apparatus 1 decides use or non-use of the compressing dictionary according to a quantity of compressed data which is data to be compressed having been coded. Here, the data compressing apparatus 1 decides non-use of the compressing dictionary for data to be compressed having such a characteristic that a quantity of compressed data after the coding is larger than a quantity of original data (no compressing effect is expected), as above. It is therefore possible to largely decrease a probability of degradation of the compressing efficiency so that a compression effect above a certain level can be ensured more certainly.

(3) In the Case Where Use or Non-use of the Compressing Dictionary is Decided According to the Above Judging Conditions {circle around (3)}

In this case, the initial dictionary use or non-use deciding unit 12 , as shown in FIG. 13, for example, determines whether any one of character codes 0x00 through 0x06 and 0xff as specific character codes (specific character bands) exist in data to be compressed (Step F 19 ) Incidentally, one of the above character codes 0x00 through 0x06 and 0xff do not occur in text file data, in general. Assuming here that dictionary for text file data is stored as the compressing dictionary in the dictionary storing unit 11 .

If the above judgement results in that any one of the above character codes 0x00 through 0x06 and 0xff do not exist in the data to be compressed (if judged NO at Step F 19 ), the initial dictionary use or non-use deciding unit 12 judges that the data to be compressed is very like text file data so as to decide use of the compressing dictionary, and notifies the dictionary referring unit 13 of it.

The dictionary referring unit 13 reads out the compressing dictionary from the dictionary storing unit 11 , besides notifying the dictionary use or non-use information outputting unit 15 of use of the compressing dictionary. The dictionary use or non-use information outputting unit 15 outputs a code representing use of the compressing dictionary as the dictionary use or non-use information to the decoding side (Step F 20 ). The coding unit 14 codes the data to be compressed with reference to the compressing dictionary (for text file data) read out by the dictionary referring unit 13 (Step F 21 ).

If one of the above character codes 0x00 through 0x06 and 0xff exist in the data to be compressed (if judged YES at Step F 19 ), the initial dictionary use or non-use deciding unit 12 determines that the data to be compressed is very likely other than text file data so as to decide non-use of the compressing dictionary, and notifies the dictionary use or non-use information outputting unit 15 and the coding unit 14 via the dictionary referring unit 13 of it.

The dictionary use or non-use information outputting unit 15 outputs a code representing non-use of the compressing dictionary (Step F 22 ) The coding unit 14 does not code but copies the data to be compressed, and outputs it (Step F 23 ).

The above data compressing apparatus 1 can easily decide use or non-use of the compressing dictionary merely by actually inspecting contents of data to be compressed and judging whether specific character data occurs in the data to be compressed. It is therefore possible to quickly judge a characteristic of actual data to be compressed so as to produce a compression effect above a certain level while improving a processing speed.

(b) Description of the Decoding Side

A data decompressing apparatus 3 according to the first modification, that is, a data decompressing apparatus 3 for the data compressing apparatus 1 described above with reference to FIGS. 10 through 13, is configured similarly to that shown in FIG. 6, and its operation (data decompressing method) is similar to that described above with reference to FIGS. 7 through 9. Namely, when receiving a code representing use of the dictionary from the compressing side, the data decompressing apparatus 3 decodes compressed data (codes) using the (decompressing) dictionary. When receiving a code representing non-use of the dictionary, the data decompressing apparatus 3 does not perform the decoding process since the data to be compressed which has not been coded is inputted as it is.

(c) Others

The compressing or decompressing dictionary stored in the above dictionary storing unit 11 or 31 is created by a dictionary creating apparatus 5 A shown in FIG. 14, for example. The dictionary creating apparatus (data compressing or decompressing dictionary creating apparatus) 5 A has, as shown in FIG. 14, an occurrence frequency of character or character string counting unit 51 , a high occurrence frequency character or character string detecting unit 52 , a code assigning unit 53 and a dictionary outputting unit 54 .

The occurrence frequency of character or character string counting unit (occurrence frequency counting unit) 51 counts occurrence frequency of each character or character string in data for creating a dictionary. The high occurrence frequency character or character string detecting unit (high occurrence frequency data detecting unit) 52 detects a character or character string whose occurrence frequency is higher than predetermined times on the basis of occurrence times of each character or character string counting by the occurrence frequency of character or character string counting unit 51 .

The code assigning unit 53 assigns a predetermined code to a character or character string of high occurrence frequency detected by the high occurrence frequency character or character string detecting unit 52 . The dictionary outputting unit (dictionary generating unit) 54 combines the above character or character string of high occurrence frequency with the code and outputs them, thereby generating the above compressing or decompressing dictionary. In a manner of assigning a code by the code assigning unit 53 , a predetermined code may be assigned to a character or character string of high occurrence frequency one-to-one, or a character string of high occurrence frequency may be divided into a context and characters and a predetermined code may be assigned to each of the characters.

The dictionary creating apparatus 5 A having the above structure assigns a predetermined code to character data whose occurrence frequency is higher than predetermined frequency on the basis of occurrence frequency of each character or character string occurring in data for creating a dictionary, combines the character data of high occurrence frequency with the code and output them, thereby automatically generating the data compressing or decompressing dictionary. It is therefore possible to omit labor of creating the dictionary.

(A2) Description of a Second Modification of the First Embodiment

(a) Description of the Compressing Side

FIG. 15 is a block diagram showing a structure of a data compressing apparatus according to a second modification of the first embodiment. A data compressing apparatus 1 shown in FIG. 15 additionally has a compressed data dividing unit 16 , as compared with that shown in FIG. 1 .

The above compressed data dividing unit 16 divides inputted data to be compressed into predetermined data groups. On an assumption that the data to be compressed is text-form data such as text file data or the like, the compressed data dividing unit 16 divides the data to be compressed into word units in the document-form data in a manner such as morphological analysis or the like.

Because of this, the compressed data dividing unit 16 according to this embodiment has, as shown in FIG. 15, a word dictionary storing unit 17 and a word inputting unit 18 . The word dictionary storing unit 17 stores a word dictionary in which desired words occurring in the above document-form data are registered. The word inputting unit (word dividing unit) 18 divides the data to be compressed (document-form data) into word units of on the basis of the words registered in the word dictionary in the word dictionary storing unit 17 , and inputs the word units to the coding unit 14 via the dictionary referring unit 13 .

Namely, the coding unit 14 of this modification codes the data to be compressed by word (character data group) obtained by the word inputting unit 18 of the compressed data dividing unit 16 . For this purpose, a word unit compressing dictionary in which a code is assigned to each of desired words is stored in the dictionary storing unit 11 of this modification. The initial dictionary use or non-use deciding unit 12 decides use or non-use of the compressing dictionary on the basis of contents of the inputted data to be compressed (according to {circle around (1)} whether characters or character strings of high occurrence frequency are all included in the dictionary, {circle around (2)} whether a quantity of compressed data is smaller than a quantity of original data, or {circle around (3)} whether specific characters or character strings are included in the data to be compressed), similarly to the above first modification.

In the data compressing apparatus 1 having the above structure according to the second modification, the word inputting unit 18 divides data to be compressed (document-form data) into words and inputs them to the coding unit 14 when the initial dictionary use or non-use deciding unit 12 decides use of the compressing dictionary so that the coding unit 14 codes a plurality of character data as a bunch at a time.

As compared with a case of coding character by character as a unit, it is possible to largely speed up the coding process. By dividing data into a plurality of groups of data that are called “words” having respective meanings, it is possible to limit the number of sorts of codes to be assigned to data to be compressed so that a quantity of codes after the coding is reduced, thus a compression ratio is improved. Further, if the data to be compressed is coded by word as a unit, the decoding process on the decoding side becomes easier.

A procedure of the coding in the above coding unit 14 corresponds to the flowchart (Steps D 8 through D 16 ) shown in FIG. 4 in which X (t−n, t−1) is replaced with a word or the flowchart (Steps D 17 through D 28 ) shown in FIG. 5 in which X (t, t+n) is replaced with a word.

(b) Description of the Decoding Side

A data compressing apparatus 3 according to the second modification, that is, a data compressing apparatus for the above data compressing apparatus 1 shown in FIG. 15 has a structure similar to that shown in FIG. 6 . In this case, a decompressing (word unit decompressing) dictionary having the same contents as the compressing dictionary stored in the dictionary storing unit 11 on the compressing side is stored in the dictionary storing unit 31 , and the decompressing unit 34 decodes compressed data having been compressed by the data compressing apparatus 1 by word (by predetermined character data group) on the basis of the decompressing dictionary.

The data decompressing apparatus 3 according to the second modification decodes compressed data (codes) by word using the above word unit decompressing dictionary when receiving a code representing use of the dictionary from the compressing side. When receiving a code representing non-use of the dictionary, the data decompressing apparatus 3 does not perform the decoding process since data to be compressed is inputted as it is, not coded.

Namely, an operation of the data decompressing apparatus 3 is similar to the flowchart (Steps El through E 3 ) shown in FIG. 7 . The decompressing process in the decoding unit 34 corresponds to the flowchart (Steps E 4 through E 12 ) shown in FIG. 8 in which X (t−n, t−1) is replaced with a word or the flowchart (Steps E 13 through E 19 ) shown in FIG. 9 in which X (t, t+n) is replaced with a word, depending on a coding system (statistical, or dictionary-based) on the compressing side.

The data decompressing apparatus 3 according to the second modification decodes compressed data by word on the basis of the decompressing dictionary when data to be compressed before compressed is document-form data so as to decode a plurality of character data as a bunch at one time. As compared with a case where the decoding is performed by one character data as a unit, this modification can largely speed up the decoding (decompressing) process. Since compressed data is decoded by data that is “a word” having a meaning, it is possible to perform the decoding process readily and at a high speed.

(c) Others

In the above second modification, the compressing or decompressing dictionary stored in the above dictionary storing unit 11 or 31 is created by a dictionary creating apparatus 5 B shown in FIG. 16, for example. For this purpose, the dictionary creating apparatus (data compressing or decompressing dictionary creating apparatus) 5 B has, as shown in FIG. 16, a word dictionary storing unit 55 , a word segmenting unit 56 , an occurrence frequency of word or word string counting unit 57 , a high occurrence frequency word or word string detecting unit 58 , a code assigning unit 59 and a dictionary outputting unit 60 .

The word dictionary storing unit 55 stores words or word strings which become basis when data (document-form data) for creating a dictionary is segmented (divided) into words. The word segmenting unit (data dividing unit) 56 segments the data for creating a dictionary into words (predetermined character data group) on the basis the word dictionary storing unit 55 . The occurrence frequency of word or word string counting unit (occurrence frequency counting unit) 57 counts occurrence frequency of each word or word string obtained by the word segmenting unit 56 .

The high occurrence frequency word or word string detecting unit (high occurrence frequency character data group detecting unit) 58 detects a word or word string whose occurrence frequency is higher than predetermined frequency on the basis of occurrence frequency of each word or word string counted by the occurrence frequency of word or word string counting unit 57 . The code assigning unit 59 assigns a predetermined code to a word or word string of high occurrence frequency detected by the high occurrence frequency word or word string detecting unit 58 . The dictionary outputting unit (dictionary generating unit) 60 combines the above word or word string of high occurrence frequency with the code and outputs them, thereby generating the above compressing or decompressing dictionary.

The dictionary creating apparatus 5 B having the above structure assigns a predetermined code to a word or word string whose occurrence frequency is higher than predetermined frequency on the basis of occurrence frequency of each word or word string obtained by dividing data for creating a dictionary into words, combines the word or word string of high occurrence frequency with the code, and outputs them, thereby automatically creating a dictionary suitable for coding and decoding by word. This allows to omit labor to create a dictionary corresponding to words.

Since a dictionary most suitable for a coding processor a decoding process by data which is “a word” having own meaning is created, it is possible to largely speed up the coding process for data to be compressed or the decoding process for compressed data.

(A3) Description of a Third Modification of the First Embodiment

(a) Description of the Compressing Side

FIG. 17 is a block diagram showing a data compressing apparatus according to a third embodiment of the first embodiment. A data compressing apparatus 1 shown in FIG. 17 additionally has a compressed data dividing unit 16 A including a word category dictionary storing unit 17 A, a word inputting unit 18 A and a category inputting unit 19 A, as compared with the data compressing apparatus 1 shown in FIG. 1 .

The word category dictionary storing unit 17 A stores a word category dictionary in which each of desired words (character data groups) occurring in data to be compressed (document-form data) and part-of-speech information (noun, verb, adjective, or the like) on the word are stored as category information is registered. The word inputting unit (word dividing unit) 18 A divides data to be compressed into words on the basis of words registered in the word category dictionary in the word category dictionary storing unit 17 A. The category inputting unit (category information adding unit) adds part-of-speed information corresponding to a word obtained by the word inputting unit 18 A on the basis of the above part-of-speed information registered in the word category dictionary 17 A.

Namely, the data compressing apparatus 1 according to the third modification employs a word as a unit of coding of data to be compressed (document-form data) at the time of coding by the coding unit 14 , and adds part-of-speech information to each word so as to divide words that are objects of the coding into groups according to the part-of-speech information. It is therefore possible to decrease the number of sorts of codes to be assigned to words (shorten a code length).

Here, the compressing dictionary in which a predetermined code is assigned to each combination of a desired word and category information on the word is stored in the dictionary storing unit 11 . The coding unit 14 retrieves a category of data to be compressed that is an object of coding with the category information added by the above category inputting unit 19 A as a key to detect a corresponding category group, further retrieves the data to be compressed that is an object of the coding in the group, then outputs codes corresponding to the data to be compressed.

Next, detailed description will be made of an operation of the data compressing apparatus 1 having the above structure according to the third modification with reference to flowcharts (Steps G 1 through G 21 ) shown in FIGS. 18 and 19. Incidentally, a process of deciding use or non-use of the compressing dictionary in the initial dictionary use or non-use deciding unit 12 is similar to that described in the first embodiment or the first modification, description of which is omitted here. Hereinafter, the description will be made of only a coding process in the coding unit 14 after use of the compressing dictionary is decided.

(1) In the Case of Statistical Coding

When statistical coding is employed, the coding unit 14 , as shown in FIG. 18, for example, initializes a parameter t (t=0) for retrieving a category context (category string) S (t−n, t−1) (Step G 1 ), and sets a parameter n for retrieving a longest-matching character string in the context S (t−n, t−1) to a maximum order (a maximum number of characters consisting of the context) N (Step G 2 ). Wherein, each of the above t, n and N are natural numbers, and the above S (t−n, t−1) represents a category string {S t−n , S t−n+1 , . . . , S t−1 } (where, S t represents a category of a word (string) X t ).

The coding unit 14 determines whether a certain context S (t−n, t−1) exists in the compressing dictionary (Step G 3 ). If not, the coding unit 14 repeats retrieval of the context S (t−n, t−1) while decrementing the parameter n (n=n−1) (that is, descending the order of the context) until detecting the context X (t−n, t−1) (from NO route at Step G 3 to Step G 6 ).

If the context S (t−n, t−1) exists in the dictionary, the coding unit 14 further determines whether a combination of the context S (t−n, t−1) and an inputted word (data to be compressed) Xt exists in the above compressing dictionary (Step G 4 ). If not, the coding unit 14 outputs ESC (escape code) following the context S (t−n, t−1) (from NO route at Step G 4 to Step G 5 ), descends the order of the context (Step G 6 ), then repeats the above process until detecting the combination (context) of the context S (t−n, t−1) and the inputted word Xt.

If detecting the combination of the context S (t−n, t−1) and the inputted word Xt [if the combination of the context S (t−n, t−1) and the inputted word Xt exists in the compressing dictionary], the coding unit 14 outputs a code of the word Xt following the context S (t−n, t−1) (from YES route at Step G 4 to Step G 7 ). After that, the coding unit 14 increments the parameter t (t=t+1: Step G 8 ), and successively codes an inputted word Xt while altering the context S (t−n, t−1) that is an object of the retrieval (NO route at Step G 9 ) until the coding of all inputted data is completed (until judged YES at Step G 9 ).

(2) In the Case of Dictionary-based Coding

If the dictionary-base coding is employed, the coding unit 14 , as shown in FIG. 19, for example, initializes parameters t and n for altering a word (string) X (t, t+n) that is an object of retrieval and the number of extended words Cn (where t, n and Cn are natural numbers) of the word (string) X (t, t+n) that is an object of the retrieval (t=0, n=1, Cn=0: Steps G 10 and G 11 ) Wherein, the above X (t, t+n) represents a word string {X t , X t+1 , . . . , X t+1 } (where X t represent one word).

The coding unit 14 determines whether a combination of category context S t−1 and data string starting with inputted word X (t, t+n) exists in the compressing dictionary (Step G 12 ). If the combination exists, the coding unit 14 further determines whether the combination is a category context S t−1 and a word X (t, t+n) that is an object of retrieval itself or not (from YES route at Step G 12 to Step G 13 ).

If the word X (t, t+n) that is an object of the retrieval itself exists in the dictionary as a result, the coding unit 14 sets the number of extended words Cn to a value of the parameter n (Step G 14 ), increments n (n=n+1) (Step G 15 ) to increase (extend) the word string X (t, t+n) that is an object of the retrieval by one word, then again determines whether the extended word string X (t, t+n) exists in the dictionary.

If determining that the word string X (t, t+n) does not exist in the dictionary, the coding unit 14 next determines whether the number of extended words Cn=0 (from NO route at Step G 12 to Step G 16 ). If Cn≠0 as a result, the coding unit 14 outputs a code in the dictionary corresponding to the word string X (t, t+Cn) following the category context S t−1 (from NO route at Step G 16 to Step G 17 ). If Cn=0, the coding unit 14 outputs a code representing copy since the word string X (t, t+n) could not be extended even by one word and does not exist in the dictionary (from YES route at Step G 16 to Step G 18 ), after that, outputs one word Xt before extended (Step G 19 ).

The coding unit 14 increments the parameter t (t=t+Cn+1) (Step G 20 ) to successively code an inputted word X (t, t+n) while altering the word string X (t, t+n) that is an object of the retrieval (NO route at Step G 21 ) until coding of all inputted data is completed (until judged YES at Step G 21 ).

If data to be compressed is document-form data, the data compressing apparatus 1 according to the third modification divides the document-form data into words, and adds category information (part-of-speed information or the like) on a word to each of the obtained words so as to group words according to the category information. The compressing apparatus 1 therefore can reduce the number of sorts of codes to be assigned to respective words, thereby shortening a code to be assigned to each word. It is thereby possible to decrease a quantity of codes after coding, thus improve a compression ratio. Further, it is possible to readily specify a word to be decoded owing to the above category information, as will be described later. This largely contributes to speeding up of the decoding process.

(b) Description of the Decompressing Side

A decompressing apparatus 3 according to the third modification, that is, a data decompressing apparatus 3 for the above data compressing apparatus 1 described above with reference to FIGS. 17 through 19, has a structure similar to that of the data decompressing apparatus 3 shown in FIG. 6 . In this case, the decoding unit 34 decodes having been compressed data compressed by the data compressing apparatus 1 by word (predetermined character data group) on the basis of the above category information.

When receiving a code representing use of the dictionary from the compressing side, the data decompressing apparatus 3 according to the third modification decodes compressed data (codes) by word on the basis of the above category information using the above word unit decompressing dictionary. When receiving a code representing non-use of the dictionary, the data decompressing apparatus 3 does not perform the decoding process since data to be compressed is inputted as it is, not coded.

A decoding system used in the decoding unit 34 of the data decompressing apparatus 3 according to the third modification corresponds to a coding system employed in the above coding unit 14 . If statistical coding is employed in the coding unit 14 , the decoding unit 34 decodes compressed data in the probability statistical decoding system. If dictionary-based coding is employed in the coding unit 14 , the decoding unit 34 decodes compressed data in dictionary-based decoding system. Hereinafter, detailed description will be made of a decoding process by the decoding unit 34 with reference to flowcharts (Steps H 1 through H 16 ) shown in FIGS. 20 and 21.

(1) In the Case That the Compressing Side Employs Statistical Coding

In this case, the decoding unit 34 , as shown in FIG. 20, initializes a parameter t for retrieving a category context (category string) S (t−n, t−1) (Step H 1 ), besides setting a parameter n for retrieving a longest-matching character string in the context X (t−n, t−1) to a maximum order (a maximum number of characters consisting of the context) of the context S (t−n, t−1) (Step H 2 ). Wherein, the above t, n and N are natural numbers, and the above S (t−n, t−1) represents a category string {S t−n , S t−n+1 , . . . , S t−1 } (where S t represents a category of a word (string) X t ).

The decoding unit 34 determines whether a certain context S (t−n, t−1) that is an object of the coding exists in the decompressing dictionary in the dictionary storing unit 31 (Step H 3 ). If not, the decoding unit 34 repeats retrieval of the context S (t−n, t−1) while decrementing the parameter n (n=n−1) until detecting the context S (t−n, t−1) (from NO route at Step H 3 to Step H 6 ).

If detecting the context S (t−n, t−1), the decoding unit 34 decodes a longest-matching word (string) x according to a code corresponding to the context S (t−n, t−1) (from YES route at Step H 3 to Step H 4 ), and determines whether the decoded longest-matching word x is ESC (escape code) (Step H 5 ).

If the decoded word x is ESC as a result (if judged YES at Step H 5 ), the decoding unit 34 repeats retrieval of the context S (t−n, t−1) while decrementing the parameter n (Step H 6 ) until decoding a word other than ESC (until judged NO at Step H 5 ).

If the decoded word x is other than ESC, the decoding unit 34 outputs the decoded word x as a decoded word Xt (Xt=x: from NO route at Step H 5 to Step H 7 ). The decoding unit 34 increments the parameter t (t=t+1: Step H 8 ), and successively decodes inputted compressed data while altering the context X (t−n, t−1) that is an object of the retrieval (NO route at Step H 9 ) until decoding of all compressed data (codes) is completed (until judged YES at Step H 9 ).

( 2 ) In the Case Where the Compressing Side Employs Dictionary-based Coding

In this case, the decoding unit 34 , as shown in FIG. 21, initializes a parameter t (t=0) (Step H 10 ), after that, determines whether an inputted code (compressed data) is a code representing copy (Step H 11 ).

If the inputted code is not a code representing copy as a result, the decoding unit 34 outputs a word corresponding to the inputted code on the basis of the decompressing dictionary in the dictionary storing unit 31 as a decoded word X (t, t+n) following the context S t−1 (from NO route at Step H 11 to Step H 12 ), and increments the parameter t by n (t=t+n: Step H 13 ).

If the inputted code is a code representing copy, the decoding unit 34 outputs the inputted code as it is as a decoded word Xt (from YES route at Step H 11 to Step H 14 ), and increments the parameter t (t=t+1: Step H 15 ).

The decoding unit 34 successively decodes inputted compressed data (NO route at Step H 16 ) until decoding of all compressed data (codes) is completed (until judged YES at Step H 16 ).

If the above initial dictionary use or non-use deciding unit 32 decides non-use of the decompressing dictionary, the dictionary referring unit 33 notifies the decoding unit 34 of it. The decoding unit 34 thereby does not decode compressed data (original data having not been compressed on the compressing side actually) and outputs it as it is.

The data decompressing apparatus 3 according to the third modification decodes compressed data from the compressing side on the basis of category information on words in data to be compressed (document-form data) so as to readily specify words to be decoded. As compared with the above second modification, it is possible to more speed up the decoding process.

(c) Others

In the above third modification, the compressing or decompressing dictionary stored in the above dictionary storing unit 11 or 31 is created by the dictionary creating apparatus 5 C shown in FIG. 22, for example. For this purpose, the dictionary creating apparatus (data compressing or decompressing dictionary creating apparatus) 5 C additionally has, as shown in FIG. 22, a category dictionary storing unit 61 , along with a word dictionary storing unit 55 , a word segmenting unit 56 , an occurrence frequency of word or word string counting unit 57 , a high occurrence frequency word or word string detecting unit 58 , a code assigning unit 59 and a dictionary outputting unit 60 which are similar to those shown in FIG. 16 .

The above category dictionary storing unit 61 stores a category dictionary in which category information (part-of-speech information) to be assigned to a word or word string along with a code when the code is assigned to the word or word string of high occurrence frequency by the code assigning unit 59 for each word or word string is stored. The above code assigning unit 59 adds category information on a word or word string of high occurrence frequency to a code to be assigned to the word or word string of high occurrence frequency on the basis the category dictionary stored in the category dictionary storing unit 61 .

Whereby, the above dictionary creating apparatus 5 C can divide words or word strings in groups according to the above category information. As a result, the number of sorts of codes to be assigned to the above words or word strings is decreased and a code to be assigned to each word is shortened so that a size of the dictionary is reduced. By using the dictionary, a quantity of codes after the process is decreased, thus a compression ratio is improved on the compressing (coding) side, besides a word to be decoded is readily specified according to the category information on the decompressing (decoding) side. Therefore, this largely contributes to speeding-up of the decoding process.

(A4) Description of a Fourth Modification of the First Embodiment

(a) Description of the Compressing Side

FIG. 23 is a block diagram showing a structure of a data compressing apparatus according to a fourth modification of the first embodiment. A data compressing apparatus 1 shown in FIG. 23 additionally has a common dictionary storing unit 11 A, an inherent dictionary storing unit 11 B, a characteristic extracting unit 16 B, an inherent dictionary creating unit 17 B and an inherent dictionary outputting unit 18 B, as compared with the data compressing apparatus 1 shown in FIG. 1 .

The above characteristic extracting unit 16 B extracts characters (character strings) inherent to data to be compressed as characteristic data of the data to be compressed. The inherent dictionary creating unit (compressing inherent dictionary creating unit) 17 B assigns predetermined codes to each of the characteristic data extracted by the characteristic extracting unit 16 B to create an inherent compressing dictionary inherent to the data to be compressed. The created inherent dictionary is stored in the above inherent dictionary storing unit 11 B.

The above inherent dictionary and a common dictionary (compressing dictionary) stored in the common dictionary storing unit (compressing dictionary storing unit) 11 A are merged by the dictionary referring nit 13 , as will be described later. Namely, the coding unit 14 according to this modification codes data to be compressed on the basis of the above compressing inherent dictionary created by the inherent dictionary creating unit 17 B and the common dictionary stored in the common dictionary storing unit 11 A.

The inherent dictionary outputting unit (inherent dictionary information outputting unit) 18 B outputs information on the above inherent dictionary to the decompressing side for the data to be compressed.

Next, detailed description will be made of an operation of the data compressing apparatus 1 having the above structure according to the fourth modification with reference to a flowchart (Steps J 1 through J 6 ) shown in FIG. 24 . Incidentally, a process of deciding use or non-use of the compressing dictionary in the initial dictionary use or non-use deciding unit 12 is similar to that described in the first embodiment or the first modification, description of which is omitted here. Hereinafter, the description will be made of the operation, paying an attention to a coding process in the coding unit 14 after use of the compressing dictionary is decided.

In the data compressing apparatus 1 , the characteristic extracting unit 16 B counts occurrences of each character or character string occurring in data (string) to be compressed (Step J 1 ), and extracts high ranked Np (Np is a natural number) characters or character strings frequently occurring (deleting the remainder: Step J 2 ). The characteristic extracting unit 16 B compares the obtained characters or character strings with characters or character strings in the common dictionary (set dictionary) in the common dictionary storing unit 11 A, and deletes coinciding information (included in the common dictionary to extract the remaining characters or character strings as characteristic data (Step J 3 ).

The characteristic data obtained as above is given to the inherent dictionary creating unit 17 B. The inherent dictionary creating unit 17 B appropriately assigns predetermined codes to the received characteristic data to create the inherent dictionary, and stores it in the inherent dictionary storing unit 11 B (Step J 4 ). The dictionary referring unit 13 merges the inherent dictionary stored as above in the inherent dictionary storing unit 11 B and the common dictionary in the common dictionary storing unit 11 A (Step J 5 ).

Whether the initial dictionary use or non-use deciding unit 12 decides use of the compressing dictionary, the dictionary referring unit 13 outputs information (inherent dictionary information) on the inherent dictionary to the decoding side described later, besides the coding unit 14 successively codes the data to be compressed on the basis of the dictionary (inherent dictionary+common dictionary) merged by the dictionary referring unit 13 (Step J 6 ).

The coding procedure in the coding unit 14 is performed similarly to the first embodiment described above. Namely, either statistical coding (refer to FIG. 4) or dictionary-based coding (refer to FIG. 5) is employable. The process of deciding use or non-use of the compressing dictionary in the initial dictionary use or non-use deciding unit 12 is performed similarly to the first embodiment or the first modification, as well.

Whether the initial dictionary use or non-use deciding unit 12 decides non-use of the dictionary, the coding unit 14 does not code the data to be compressed, but copies it and outputs it as it is.

In the data compressing apparatus 1 according to the fourth modification, the inherent dictionary creating unit 17 B assigns predetermined codes to characters or character strings inherent to data to be compressed to create an inherent dictionary inherent to the data to be compressed, and the coding unit 14 codes the data to be compressed on the basis of a dictionary obtained by merging the inherent dictionary and the common dictionary, so as to largely decrease probability of coding data to be compressed not registered in the dictionary, thus improve a compression ratio.

The above inherent dictionary information is outputted to the decompressing side. Therefore, the decompressing side can certainly decode (decompress) the compressed data coded according to the inherent dictionary originally created on the coding side, as will be described later.

The data compressing apparatus 1 according to the fourth modification codes data to be compressed by character or character string. However, it is alternatively possible to code the data to be compressed by word, or code the data to be compresed by word while adding category information thereto, similarly to the above second and third modifications.

(b) Description of the Decompressing Side

FIG. 25 is a block diagram showing a structure of a data decompressing apparatus 3 according to the fourth modification of the first embodiment. The data decompressing apparatus 3 shown in FIG. 25 corresponds to the decompressing side for the data compressing apparatus 1 described above with reference to FIG. 23, which has a common dictionary storing unit 31 A and an inherent dictionary storing unit 31 B, unlike that according to the first embodiment shown in FIG. 6 .

The common dictionary storing unit 31 A stores a dictionary having the same contents as the common dictionary stored in the common dictionary storing unit 11 A on the compressing side. The inherent dictionary storing unit (decompressing inherent dictionary storing unit) 31 B stores a dictionary having characters or character strings inherent to data to be compressed, which is compressed data before compression, as characteristic data of the data to be compressed, in which a predetermined code is assigned to each character data, as a decompressing inherent dictionary. According to this modification, by receiving the inherent dictionary information outputted from the inherent dictionary outputting unit 18 B on the compressing side, the inherent dictionary storing unit 31 B stores a dictionary having the same contents as the inherent dictionary created by the inherent dictionary creating unit 17 B on the compressing side as the above decompressing dictionary.

The above common dictionary and the inherent dictionary are merged by the dictionary referring unit 33 , similarly to the compressing side, and used in the decoding process in the decoding unit 34 . When the initial dictionary use or non-use deciding unit 32 decides use of the dictionary, the decoding unit 34 decodes compressed data on the basis of the inherent dictionary in the inherent dictionary storing unit 31 B and the common dictionary (decompressing dictionary) in the common dictionary storing unit 31 A merged as above by the dictionary referring unit 33 .

The above initial dictionary use or non-use deciding unit 32 decides use or non-use of the dictionary according to the dictionary use or non-use information from the dictionary use or non-use information outputting unit 15 on the compressing side in this modification, as well.

Hereinafter, detailed description will be made of an operation of the data decompressing apparatus 3 having the above structure according to the fourth modification with reference to a flowchart (Steps J 7 through J 9 ) shown in FIG. 26 .

When the data decompressing apparatus 3 receives inherent dictionary information inputted from the inherent dictionary outputting unit 18 B on the compressing side (Step J 7 ), the inherent dictionary storing unit 31 B stores the information so as to generate an inherent dictionary having the same contents as that on the compressing as a decompressing inherent dictionary. The dictionary referring unit 33 merges the decompressing inherent dictionary and the common dictionary (Step J 8 ).

If the initial dictionary use or non-use deciding unit 32 decides use of the dictionary according to the dictionary use or non-use information received from the dictionary use or non-use information outputting unit 15 on the compressing side in this state, the decoding unit 34 successively decodes compressed data referring to the dictionary (inherent dictionary+common dictionary) merged as above by the dictionary referring unit 33 (Step J 9 ).

Incidentally, if the compressing side (coding unit 14 ) employs statistical coding, statistical decoding (refer to FIG. 8) is employed in the decoding process in the decoding unit 34 . If the compressing side (coding unit 14 ) employs dictionary-based coding, dictionary-based decoding (refer to FIG. 9) is employed, as well as in the first embodiment.

If the initial dictionary use or non-use deciding unit 32 decides non-use of the dictionary, the decoding unit 34 does not decode the compressed data (original data having not been compressed actually), but copies it and output it as it is.

The data decompressing apparatus 3 according to the fourth modification decodes compressed data on the basis of both of the inherent dictionary in the inherent dictionary storing unit 31 B and the common dictionary in the common dictionary storing unit 31 A so as to largely decrease probability of decoding compressed data not registered in the dictionary. This largely improves efficiency of decoding.

At this time, the inherent dictionary storing unit 31 B receives information on the compressing inherent dictionary from the compressing side so as to generate a dictionary having the same contents as the inherent dictionary used on the compressing side as the above decompressing inherent dictionary. It is therefore possible to decode very accurately compressed data having been coded according to the inherent dictionary originally created on the compressing side.

If the compressing side codes data to be compressed by word, or code data to be compressed by word while adding category information thereto, the decompressing side can decode compressed data by word, or decode the compressed data by word on the basis of the category information, as well as in the second and third modifications.

(A5) Description of a Fifth Modification of the First Embodiment

(a) Description of the Compressing Side

FIG. 27 is a block diagram showing a structure of a data compressing apparatus according to a fifth modification of the first embodiment. A data compressing apparatus 1 shown in FIG. 27 additionally has a dictionary updating unit 16 C, as compared with that shown in FIG. 1 .

The dictionary updating unit (compressing dictionary updating unit) 16 C updates a compressing dictionary in the dictionary storing unit 11 on the basis of data to be compressed, coded by code in the coding unit 14 . According to the fifth modification, the coding unit 14 codes the data to be compressed on the basis of the compressing dictionary updated by the dictionary updating unit 16 C.

Next, detailed description will be made of an operation of the data compressing apparatus 1 having the above structure according to the fifth modification. In the fifth modification, a process of deciding use or non-use of the compressing dictionary in the initial dictionary use or non-use deciding unit 12 is similar to that in the first embodiment or the first modification, description of which is omitted here. Hereinafter, the description will be made of a coding process in the coding unit 14 after use of the compressing dictionary is decided.

(1) In the Case of Statistical Coding

If statistical coding is employed, the coding unit 14 initializes, as shown in FIG. 28, for example, a parameter t for retrieving a context (character string) X (t−n, t−1) (t=0) (Step K 1 ), and sets a parameter n for retrieving a longest-matching character string in the context (t−n, t−1) to a maximum number of order (a maximum number of characters consisting of the context) of the context X (t−n, t−1) (Step K 2 ). Wherein, the above t, n and N are natural numbers, and the above X (t−n, t−1) represents a character string {X t−n , X t−n+1 , . . . X t−1 } (where X t represents one character).

The coding unit 14 determines whether a certain context X (t−n, t−1) exists in the compressing dictionary (Step K 3 ). If not, the coding unit 14 repeats retrieval of the context X (t−n, t−1) while decrementing (descending the order) the parameter n (n=n−1) until detecting the context X (t−n, t−1) (from NO route at Step K 3 to Step K 6 ).

If the context X (t−n, t−1) exists in the dictionary, the coding unit 14 further determines whether a context configured with the context X (t−n, t−1) and an inputted character (data to be compressed) Xt added thereto already exists in the above compressing dictionary (from YES route at Step K 3 to Step K 4 ) If not, the coding unit 14 outputs ESC (escape code) following the context (t−n, t−1) (from NO route at Step K 4 to Step K 5 ), and descends the order of the context (Step K 6 ), and repeats the above process until detecting the combination (context) of the context X (t−n, t−1) and the inputted character Xt.

When detecting the combination of the context X (t−n, t−1) and the inputted character Xt (if the combination exists in the compressing dictionary), the coding unit 14 outputs a code of the character Xt following the context x (t−n, t−1) (from YES route at Step K 4 to Step K 7 ). The dictionary updating unit 16 C updates the code of one character Xt following the context X (t−n, t−1) in the compressing dictionary (Step K 8 ).

The dictionary updating unit 16 C then determines whether the parameter n at present is N (n=N?: Step K 9 ). If n≠N, the dictionary updating unit 16 C registers one character Xt whose code has been updated in a position following the context X (t−n, t−1) in the compressing dictionary (from NO route at Step K 9 to Step K 10 ) If n=N, the dictionary updating unit 16 C does not perform the above updating (registering) process (YES route at Step K 9 ).

The coding unit 14 increments the parameter t (t=t+1: Step K 11 ), and successively codes an inputted character Xt while altering the context (t−n, t−1) that is an object of retrieval and updating the compressing dictionary (NO route at Step K 12 ) until coding of all inputted data is completed (until it is judged as YES at Step K 12 ).

(2) In the Case of Dictionary-based Coding

If dictionary-based coding is employed, the coding unit 14 , as shown in FIG. 29, for example, initializes parameters t and n for altering a character string X (t, t+n) that is an object of retrieval and the number of extended characters Cn (where t, n and Cn are natural numbers) of the character string (t, t+1) that is an object of the retrieval (t=0, n=1, Cn=0: Steps K 13 and K 14 ). In this case, the above X (t, t+1) represents a character string {X t , X t+1 , . . . , X t+n } (where X t represents one character).

The coding unit 14 determines whether a character string starting with an inputted character string (character string that is an object of retrieval) X (t, t+n) to be coded exists in the compressing dictionary set as above (Step K 15 ). If the character string exists in the dictionary, the coding unit 14 further determines whether the character string is a character string X (t, t+n) that is an object of retrieval itself [whether the character string X (t, t+n) exists in the dictionary] (from YES route at Step K 15 to Step K 16 ).

If the character string X (t, t+n) that is an object of the retrieval itself exists in the dictionary as a result, the coding unit 14 sets the number of extended characters Cn to a value of the above parameter n (Step K 17 ), increments n (n=n+1) (Step K 18 ) to increase (extend) the character string X (t, t+n) that is an object of retrieval by one character, and again determines whether the extended character string X (t, t+n) exists in the dictionary.

When determining that the character string X (t, t+n) does not exist in the dictionary, the coding unit 14 determines whether the number of extended characters Cn is 0 (from NO route at Step K 15 to Step K 19 ) If Cn≠0 as a result, the coding unit 14 outputs a code in the dictionary corresponding to the extended character string X (t, t+Cn) (from NO route at Step K 19 to Step K 20 ). If Cn =0, the coding unit 14 outputs a code representing copy since it is determined that the character string X (t, t+n) could not be extended even by one character and does not exist in the dictionary (from YES route at Step K 19 to Step K 21 ), and outputs one character Xt before extended (Step K 22 ).

The dictionary updating unit 16 C registers a character string X (t, t+Cn+1) in the dictionary to update it (Step K 23 ). The coding unit 14 increments the parameter t (t=t+Cn+1) (Step K 24 ), and successively codes an inputted character string X (t, t+n) while altering the character string X (t, t+n) that is an object of the retrieval and updating the compressing dictionary (NO route at Step K 25 ) until coding of all inputted data is completed (until judged YES at Step K 25 ).

In the data compressing apparatus 1 according to the fifth modification, since the dictionary updating unit 16 C updates the compressing dictionary in the dictionary storing unit 11 used in coding on the basis of data to be compressed coded by code at that time as above, it is possible to always provide the compressing dictionary suitable for data to be compressed that is an object of the next coding. This further improves a compression ratio.

The data compressing apparatus 1 according to the fifth modification may code data to be compressed by word, or code data to be compressed by word while adding category information thereto, as well as in the above second and third modifications.

(b) Description of the Decompressing Side

FIG. 30 is a block diagram showing a structure of a data decompressing apparatus 3 according to the fifth modification of the first embodiment. The data decompressing apparatus 3 shown in FIG. 30 corresponds to the decoding side for the data compressing apparatus 1 described above with reference to FIG. 27, which additionally has a dictionary updating unit 35 , as compared with that shown in FIG. 6 according to the first embodiment.

The dictionary updating unit (decompressing dictionary updating unit) 35 updates a decompressing dictionary in the dictionary storing unit 31 on the basis of a result of decoding by the decoding unit 34 . According to the fifth modification, when the initial dictionary use or non-use deciding unit 32 decides use of the dictionary, the decoding unit 34 decodes compressed data on the basis of the decompressing dictionary updated by the dictionary updating unit 35 .

Next, detailed description will be made of an operation of the data decompressing apparatus 3 having the above structure according to the fifth modification. Incidentally, a process of deciding use or non-use of the dictionary in the initial dictionary use or non-use deciding unit 32 on the decompressing side is similar to that described in the first embodiment or the first modification, description of which is omitted here. Hereinafter, the description will be made, paying an attention to the decoding process in the decoding unit 34 after use of the dictionary is decided.

(1) In the Case Where the Compressing Side Employs Statistical Coding

In this case, the decoding unit 34 , as shown in FIG. 31, for example, initializes a parameter t for retrieving a context (character string) X (t−n, t−1) (t=0) (Step L 1 ), and sets a parameter n for retrieving a longest-matching character string in the context X (t−n, t−1) to a maximum number of order (a maximum number of characters consisting of the context) N of the context X (t−n, t−1) (Step L 2 ). Wherein, the above t, n and N are natural numbers, and the above X (t−n, t−1) represents a character string {X t−n , X t−n+1 , . . . , X t−1 } (where X t represents one character).

The decoding unit 34 determines whether a certain context X (t−n, t−1) that is an object of decoding exists in the decompressing dictionary set as above (Step L 3 ) If not, the decoding unit 34 repeats retrieval of the context X (t−n, t−1) while decrementing the parameter n (n=n−1) (descending the order of the context) until detecting the context X (t−n, t−1) (from NO route at Step L 3 to Step L 6 ).

When detecting the context X (t−n, t−1), the decoding unit 34 decodes a longest-matching character x according to a code corresponding to the context X (t−n, t−1) (from YES route at Step L 3 to Step L 4 ), and determines whether the decoded longest-matching character x is ESC (escape code) (Step L 5 ). If the decoded character x is ESC as a result (if judged YES at Step L 5 ), the decoding unit 34 repeats retrieval of the context X (t−n, t−1) while decrementing the parameter n (Step L 6 ) until decoding a character other than ESC.

If the decoded character x is other than ESC, the decoding unit 34 outputs the decoded character x as a decoded character Xt (Xt=x: from NO route at Step L 5 to Step L 7 ). The data decompressing apparatus 3 registers the decoded character Xt in a position following the context X (t−n, t−1) by the dictionary updating unit 35 to update the decompressing dictionary (Step L 8 ).

The decoding unit 34 increments the parameter t (t=t+1: Step L 9 ), and successively decodes inputted compressed data while altering the context X (t−n, t−1) that is an object of the retrieval and updating the compressing dictionary (NO route at Step L 10 ) until decoding of all compressed data is completed (until judged YES at Step L 10 ).

(2) In the Case Where the Compressing Side Employs Dictionary-based Coding

In this case, the decoding unit 34 , as shown in FIG. 32, for example, initializes a parameter t (t=0) (Step L 11 ), after that, determines whether an inputted code (compressed data) is a code representing copy (Step L 12 ).

If the inputted code is not a code representing copy as a result, the decoding unit 34 outputs a character string corresponding to the inputted code from the decompressing dictionary as a decoded character string X (t, t+n) (from NO route at Step L 12 to Step L 13 ). If the inputted code is a code representing copy, the decoding unit 34 outputs the inputted code as it is as a decoded character Xt (from YES route at Step L 12 to Step L 14 ), and initializes the parameter n (n=1) (Step L 15 ).

In this state, the dictionary updating unit 35 registers a character string X (t, t+n+1) in the decompressing dictionary to update the dictionary (Step L 16 ). The decoding unit 34 increments the parameter t by n (t=t+n: Step L 17 ), and successively decodes inputted compressed data (NO route at Step L 18 ) until decoding of all compressed data (codes) is completed (until judged YES at Step L 18 ).

The data decompressing apparatus 3 according to the fifth modification updates the decompressing dictionary in the dictionary storing unit 31 on the basis of a result of decoding in the decoding unit 34 so as to always provide the decompressing dictionary suitable for compressed data that is an object of the next decoding. This further improves efficiency of the decoding.

If the compressing side codes data to be compressed by word or codes the data to be compressed by word while adding category information, the decoding side may decode compressed data by word, or decode the compressed data by word on the basis of the category information, as well as in the second and third modifications.

(B) Description of a Second Embodiment of the Invention

FIG. 33 is a block diagram showing a structure of a data compressing apparatus 1 according to a second embodiment of this invention. The data compressing apparatus 1 shown in FIG. 33 has a dictionary storing unit 11 C, a dictionary selecting unit 12 A, a dictionary referring unit 13 A, a coding unit 14 A and a selected dictionary information outputting unit 15 A.

The dictionary storing unit (compressing dictionary storing unit) 11 C stores plural kinds of compressing dictionaries 11 - 1 , 11 - 2 , 11 - 3 , . . . 11 -M (where M is a natural number) which can be used when data (strings) to be compressed is compressed. The dictionary selecting unit (compressing dictionary selecting unit) 12 A selects a compressing dictionary to be used among the above compressing dictionaries 11 -i (where i=1 through M) on the basis of data contents type information (an extension of a text file name, or the like) representing a type of contents of the data to be compressed.

The dictionary referring unit 13 A reads out the dictionary 11 -i selected by the dictionary selecting unit 12 A from the dictionary storing unit 11 C so that the coding unit 14 A refers to it. The coding unit 14 A codes the data to be compressed on the basis of the compressing dictionary 11 -i selected by the compressing dictionary selecting unit 12 A and read out (set) by the dictionary referring unit 13 A.

The selected dictionary information outputting unit 1 SA outputs selected dictionary information on the compressing dictionary 11 -i selected by the above dictionary selecting unit 12 A to the decompressing side for the data to be compressed.

A function of the data compressing apparatus 1 according to the second embodiment is accomplished by, for example, the personal computer 2 (refer to FIG. 2 ). A data compressing program is stored in the hard disk 27 , and the CPU 26 reads the data compressing program to operate, whereby functions of the above units 11 C and 12 A through 15 A are realized.

The user can make the above data compressing program using an editor of the personal computer 1 , or receive the data compressing program made in another personal computer 3 over the network 6 and store it in the hard disk 27 . Alternatively, the CPU 26 reads the data compressing program recorded in advance in one of various storage medium 28 such as the floppy disk (FD) 28 A, the CD-ROM 28 B, the MO (magneto-optic disk) 28 C and the like through the disk drive 25 to store (install) it in the hard disk 27 . In this case, improvement in versatility or spread of the data compressing apparatus 1 can be largely expected.

Next, detailed description will be made of an operation (data compressing method) of the data compressing apparatus 2 having the above structure according to the second embodiment with reference to a flowchart (Step M 1 through M 10 ) shown in FIG. 34 . Hereinafter, it is assumed that a dictionary 11 - 1 for execute file data and a dictionary 11 - 2 for text file data, for example, are stored at least as the compressing dictionaries 11 -i in the dictionary storing unit 11 C, for the sake of convenience.

When a file name is inputted to the data compressing apparatus 1 (Step M 1 ), the dictionary selecting unit 12 A determines whether an extension of the inputted file name is an extension “exe” representing an execute file or an extension “txt” representing a text file (Steps M 2 and M 3 ). If the extension of the inputted file name is “exe”, for example, as a result (if judged YES at Step M 2 ), the dictionary selecting unit 13 A selects the dictionary 11 - 1 for execute file in the dictionary storing unit 11 C as the compressing dictionary to be used (dictionary selecting step), and notifies the dictionary referring unit 13 A of it.

The dictionary referring unit 13 A reads the dictionary 11 - 1 for execute file from the dictionary storing unit 11 C and sets it as the compressing dictionary (Step M 4 ), and notifies the selected dictionary information outputting unit 15 A of it. The selected dictionary information outputting unit 15 A outputs a code 01 representing that the dictionary 11 - 1 for execute file is selected as selected dictionary information to the decompressing side (Step M 5 ). The coding unit 14 A refers to the dictionary 11 - 1 set by the dictionary referring unit 13 A to successively code data (strings) to be compressed (coding step: Step M 8 ).

If the extension of the inputted file name is “txt”, for example, (if judged NO at Step M 2 and judged as YES at Step M 3 ), the dictionary selecting unit 13 A selects the dictionary 11 - 2 for text file in the dictionary storing unit 11 C, and notifies the dictionary referring unit 13 A of it.

The dictionary referring unit 13 A reads out the dictionary 11 - 2 for text file from the dictionary storing unit 11 C and sets it as the compressing dictionary (Step M 6 ), and notifies the selected dictionary information outputting unit 15 A of it. The selected dictionary information outputting unit 15 A outputs a code 10 representing that the dictionary 11 - 2 for text file is selected as the selected dictionary information to the decompressing side (Step M 7 ). The coding unit 14 A refers to the dictionary 11 - 2 set by the dictionary referring unit 13 A to successively code data (strings) to be compressed (Step M 8 ).

A practical procedure of coding in the coding unit 14 A after a dictionary is selected is similar to the first embodiment, where either statistical coding (refer to FIG. 4) or dictionary-based coding (refer to FIG. 5) may be employed.

If the extension of the inputted file is neither “exe” nor “txt” (if judged NO at both of Steps M 2 and M 3 ), the dictionary selecting unit 13 A notifies the selected dictionary information outputting unit 15 A and the coding unit 14 A via the dictionary referring unit 13 A that no dictionary is used here. The selected dictionary information outputting unit 15 A outputs a code 00 representing non-use of the dictionary as the selected dictionary information (Step M 9 ). The coding unit 14 A does not code the data to be compressed, but copies it and output it as it is (Step M 10 ).

The data compressing apparatus 1 according to the second embodiment selects a compressing dictionary 11 -i to be used among plural kinds of compressing dictionaries 11 -i on the basis of an extension (data contents type information) of an inputted file name, and codes data to be compressed on the basis of the selected compressing dictionary 11 -i. It is therefore possible to quickly select and use a dictionary 11 -i most suitable for contents (property) of data to be compressed at any time only by inputting a name of a file that is an object of compressing, so as to code the data to be compressed.

Accordingly, it is possible to certainly achieve a remarkable compression effect for data to be compressed having different properties while improving a processing speed of a whole compressing process.

(b) Description of the Decompressing Side

FIG. 35 is a block diagram showing a structure of a data decompressing apparatus according to the second embodiment. A data decompressing apparatus 3 shown in FIG. 35 corresponds to the decompressing side for the data compressing apparatus 1 described above with reference to FIG. 33, which has a dictionary storing unit 31 C, a dictionary selecting unit 32 A, a dictionary referring unit 33 A and a decoding unit 34 A.

The dictionary storing unit (decompressing dictionary storing unit) 31 C stores plural kinds of dictionaries 31 - 1 , 31 - 2 , 31 - 3 , . . . 31 -M which can be used when compressed data is decompressed. Here, a dictionary for execute file is stored as the decompressing dictionary 31 - 1 , and a dictionary for text file is also stored as the-decompressing dictionary 31 - 2 , for example, correspondingly to the compressing side.

The dictionary selecting unit (decompressing dictionary selecting unit) 32 A receives the selected dictionary information on a compressing dictionary 11 -i (i=1 through M) selected on the basis of an extension (data contents type information representing a type of data contents of the data to be compressed) of a file name on the compressing side as described above, and selects a decompressing dictionary to be used among the plural kinds of decompressing dictionaries on the basis of the received selected dictionary information.

When receiving a code 01 representing that the dictionary 11 - 1 for execute file is selected from the compressing side, the dictionary selecting unit 32 A selects the decompressing dictionary 32 - 1 for execute file. When receiving a code 10 representing that the dictionary for text file is selected from the compressing side, the dictionary selecting unit 32 A selects the decompressing dictionary for text file.

The dictionary referring unit 33 A reads out the dictionary 32 -i selected by the dictionary selecting unit 32 A so that the decoding unit 34 A refers to it. The decoding unit 34 A decodes inputted compressed data on the basis of the decompressing dictionary 31 -i selected by the dictionary selecting unit 32 A and read out (set) by the dictionary referring unit 33 A.

If any dictionary 11 -i has not been selected on the compressing side (when receiving a code 00 representing non-use of the dictionary from the compressing side), the decoding unit 34 A is notified of it via the dictionary referring unit 33 A. The decoding unit 34 A does not decode compressed data [original data which has not been compressed (coded) actually], but copies it and outputs it as it is.

A function of the data decompressing apparatus 3 according to the second embodiment is accomplished by, for example, the personal computer 3 (refer to FIG. 2 ). A data decompressing program is stored in the hard disk 27 , and the CPU 26 reads the data decompressing program to operate, whereby functions of the above units 31 C and 32 A through 34 A are realized.

The user can make the above data decompressing program using an editor or the like of the personal computer 3 , or receive the data decompressing program made in another personal computer 1 over the network 6 and store it in the hard disk 27 . Alternatively, the CPU 26 reads the data decompressing program recorded in advance in one of various storage medium 28 such as the floppy disk (FD) 28 A, the CD-ROM 28 B, the MO (magneto-optic disk) 28 C and the like through the disk drive 25 to store (install) it in the hard disk 27 . In this case, improvement in versatility or spread of the data decompressing apparatus 3 can be largely expected.

Next, detailed description will be made of an operation (data decompressing method) of the data decompressing apparatus 3 having the above structure according to the second embodiment with reference to a flowchart (Step N 1 through N 3 ) shown in FIG. 36 .

When the data decompressing apparatus 3 receives the selected dictionary information from the data compressing apparatus 1 (receiving step: Step N 1 ), the dictionary selecting unit 32 A selects a decompressing dictionary 31 -i to be used on the basis of the received selected dictionary information (dictionary selecting step). If the received selected dictionary information is a code (01) representing a dictionary for execute file, the dictionary selecting unit 32 A selects the decompressing dictionary 31 - 1 . If the received selected dictionary information is a code (10) representing a dictionary for text file, the dictionary selecting unit 32 A selects the decompressing dictionary 31 - 2 .

When the dictionary selecting unit 32 A selects the decompressing dictionary 31 -i, the dictionary referring unit 33 A reads out a corresponding decompressing dictionary 31 -i from the dictionary storing unit 31 C (setting a dictionary: Step N 2 ). The decoding unit 34 A decodes compressed data on the basis of the decompressing dictionary 33 -i set by the dictionary referring unit 33 A (decoding step: Step N 3 ).

A decoding system in the decoding unit 34 A is decided according to a coding system on the compressing side (a coding system employed in the coding unit 14 of the data compressing apparatus 1 ). If the compressing side employs statistical coding, statistical decoding system (refer to FIG. 8) is employed. If the compressing side employs dictionary-based coding, dictionary-based decoding system (refer to FIG. 9) is employed.

The data decompressing apparatus 3 (data decompressing method) according to the second embodiment receives the selected dictionary information on a compressing dictionary 11 -i selected on the basis of an extension of a file name from the compressing side, selects a decompressing dictionary among the plural kinds of decompressing dictionaries 31 -i on the basis of the received selected dictionary information to decode compressed data on the basis of the decompressing dictionary, as above. It is therefore to quickly select a decompressing dictionary 31 -i having the same contents as a compressing dictionary having been selected on the compressing side at any time so as to accurately decompress (decode) the compressed data.

(B1) Description of a First Modification of the Second Embodiment

(a) Description of the Compressing Side

FIG. 37 is a block diagram showing a structure of a data compressing apparatus according to a first modification of the second embodiment. As shown in FIG. 37, a data compressing apparatus 1 according to the first modification has a structure similar to that shown in FIG. 33 . However, the dictionary selecting unit 12 A of the data compressing apparatus 1 according to this modification selects a compressing dictionary 11 -i including specific character data (characters or character strings) frequently occurring in data to be compressed among plural kinds of compressing dictionaries 11 -i.

Next, detailed description will be made of an operation (data compressing method) of the data compressing apparatus 1 according to the first modification.

As shown in FIG. 38, for example, the data compressing apparatus 1 initializes an array (count value) C[ ] for counting characters (character strings) (Step P 1 ). When one character (or character string) a of data to be compressed is inputted (Step 2 ), the dictionary selecting unit 12 A counts up a count value C [a] of the inputted character (character string) a (C[a]=C[a]+1: Step P 3 ).

The dictionary selecting unit 12 A repeats the above process until inputting of all the data to be compressed is completed (until it is judged as YES at Step P 4 ), thereby counting occurrences of a character (character string) occurring in the data to be compressed (NO route at Step P 4 ). When the inputting of all the data to be compressed is completed, the dictionary selecting unit 12 A refers to the count value C[ ] of each character (character string) and the dictionary storing unit 11 C to select a compressing dictionary 11 -i including high-ranked N (N is a natural number not less than 2) characters (character strings) S 1 through S N (provided occurrences of S N−1 >occurrences of S N ) having large count values (that is, frequently occurring) (dictionary selecting step: Step P 5 ).

The dictionary selecting unit 12 A then determines whether the selected dictionary 11 -i is only one (Step P 6 ). If the selected dictionary 11 -i is only one, the dictionary selecting unit 12 a outputs a code of the dictionary 11 -i as the selected dictionary information to the decompressing side via the selected dictionary information outputting unit 15 a (from YES route at Step P 6 to Step P 8 ).

If the selected dictionary is plural, the dictionary selecting unit 12 A selects a dictionary 11 -i in which a code of a character (character string) S 1 most frequently occurring is the shortest among the plural kinds of dictionaries 11 -i (from NO route at Step P 6 to Step P 7 ), and outputs a code of the selected dictionary 11 -i as the selected dictionary information to the decompressing side via the selected dictionary information outputting unit 15 A (Step P 8 ).

If there are plural dictionaries in which a code of the character (character string) S 1 is the same at the above Step P 7 , the dictionary selecting unit 12 A compares lengths of the codes of the characters (character strings) S 2 , S 3 , . . . , and selects a dictionary 11 -i in which lengths of the codes of the characters (character strings) S 2 , S 3 , . . . are shorter.

When the dictionary selecting unit 12 A selects the dictionary 11 -i, the dictionary referring unit 33 A reads out the selected dictionary 11 -i from the dictionary storing unit 11 C to set the dictionary 11 -i. The coding unit 14 A refers to the dictionary 11 -i set by the dictionary referring unit 33 A to successively code the data to be compressed (coding step: Step P 9 ).

In this case, a coding system in the coding unit 14 A may be either statistical coding (refer to FIG. 4) or dictionary-based coding (refer to FIG. 5 ).

The data compressing apparatus 1 (data compressing method) according to the first modification selects a dictionary 11 -i including specific characters (character strings) S 1 through S N frequently occurring in data to be compressed, and codes the data to be compressed on the basis of the dictionary 11 -i, as above. It is therefore possible to code data to be compressed using a dictionary 11 -i including characters (character strings) S 1 through S N frequently occurring in data to be compressed at any time, so as to increase effect of compression.

In this case, a dictionary 11 -i is selected depending on whether the dictionary including a finite number of characters (character strings) S 1 through S N occurring in data to be compressed so that the dictionary selecting process itself is sped up. This largely contributes to speeding-up of the whole coding process.

The dictionary selecting process at the above Step P 7 may be performed as shown at Step P 7 in FIG. 39, for example. Namely, if the dictionary 11 -i selected at Step P 5 is plural (dictionaries D 1 through D M : where M is a natural number not less than 2), the dictionary selecting unit 12 A selects a dictionary D M in which ΣP n ×L mn (where Σ represents a total about n=1 through N) is the smallest when probability of occurrence of a character (character string) S N in the data to be compressed is P n (n=1 through N), and a code length of a character (character string) S N in the dictionary D M is L mn .

In this case, the dictionary selecting unit 12 a selects a dictionary 11 -i in which a total of lengths of codes assigned to characters (character strings) S 1 through S N of high occurrence frequency is the smallest. Therefore, it is possible in this case to achieve a higher compression ratio.

The above dictionary selecting unit 12 A may select a compressing dictionary 11 -i to be used among plural kinds of compressing dictionaries 11 -i according to a quantity of compressed data having been coded by the coding unit 14 A, as indicated by a broken line in FIG. 37 .

An operation (data compressing method) of the data compressing apparatus 1 in this case is as shown in FIG. 40 . Namely, the data compressing apparatus 1 accepts an input of a character string X(t, t+n) for a predetermined buffer size from the data to be compressed (character strings) (Step Q 1 ), and arbitrarily selects a dictionary 11 -i to be used in coding the character string X(t, t+n) among the compressing dictionaries 11 -i by the dictionary selecting unit 12 A. The dictionary selecting unit 13 A reads out a corresponding compressing dictionary 11 -i from the dictionary storing unit 11 C, and the coding unit 14 A codes the character string X(t, t+n) on the basis of the dictionary 11 -i (hereinafeter referred as dictionary A) (Step Q 2 ).

After coding the character string X(t, t+n), the coding unit 14 A outputs information on a quantity of data (codes) of the data to be compressed having been coded as a result of the coding to the dictionary selecting unit 12 A. When receiving the information, the dictionary selecting unit 12 A determines whether a quantity of the data having been coded is smaller than the original buffer size (Step Q 3 ).

If a quantity of the data having been coded is smaller than the original buffer size (if judged YES at Step Q 3 ), the dictionary selecting unit 12 A notifies the selected dictionary information outputting unit 15 A and the coding unit 14 A via the dictionary referring unit 13 A of a code (01, for example) of the selected dictionary A. The selected dictionary information outputting unit 15 A outputs the code (01) of the dictionary A to the decompressing side. The coding unit 14 A outputs a code of the character string, after that, codes the remaining data to be compressed by referring to the same dictionary A (coding step: Steps Q 4 and Q 5 ). In this case, a coding system in the coding unit 14 A may be either statistical coding or dictionary-base coding.

If a quantity of the data having been coded is larger than the original buffer size (if judged NO at Step Q 3 ), the dictionary selecting unit 12 A selects another compressing dictionary 11 -i (hereinafer referred as dictionary B) (dictionary selecting step). The coding unit 14 A codes the data to be compressed by referring to the dictionary B (Step Q 6 ). After coding, the coding unit 14 A outputs information on a quantity of data (codes) of the data to be compressed having been coded as a result of the coding to the dictionary selecting unit 12 A. When receiving the information, the dictionary selecting unit 12 A again determines whether a quantity of the data having been coded is smaller than the original buffer size (Step Q 7 ).

If a quantity of the data having been coded is smaller than the original buffer size as a result (if judged YES at Step Q 7 ), the dictionary selecting unit 12 A notifies the selected dictionary information outputting unit 15 A and the coding unit 14 A via the dictionary referring unit 13 A of a code (10, for example) of the selected dictionary B. The selected dictionary information outputting unit 15 A outputs the code (10) of the dictionary to the decompressing side, and the coding unit 14 A codes the data to be compressed by referring to the same dictionary B (Steps Q 8 and Q 9 ).

If a quantity of the data having been coded is larger than the original buffer size (if judged NO at Step Q 7 ), the dictionary selecting unit 12 A determines that there is no dictionary suitable for the coding, and notifies the selected dictionary information outputting unit 15 A and the coding unit 14 A via the dictionary referring unit 13 A of non-use of dictionary. The selected dictionary information outputting unit 15 A thereby outputs a code (00, for example) representing non-use of dictionary to the decompressing side (Step Q 10 ). The coding unit 14 A does not code the data to be compressed, but copies it and outputs it as it is (Step Q 11 ).

The above data compressing apparatus 1 (data compressing method) selects a compressing dictionary to be used among plural kinds of compressing dictionaries 11 -i according to a quantity of compressed data which is data to be compressed having been coded. It is therefore possible to select the most suitable compressing dictionary 11 -i in consideration of a quantity of compressed data obtained after coding, at anytime. This improves the compression effect of data to be compressed, more certainly.

(b) Description of the Decompressing Side

A data decompressing apparatus 3 according to the first modification, that is, a data decompressing apparatus 3 for the above data compressing apparatus 1 described above with reference to FIGS. 37 through 40, has a structure similar to that according to the second embodiment shown in FIG. 35 . In this case, the dictionary selecting unit 32 A has a function {circle around (1)} or {circle around (2)} below according to the above-described dictionary selecting manner on the compressing side:

{circle around (1)} function of receiving the selected dictionary information on a compressing dictionary 11 -i selected as a compressing dictionary including characters (character strings) S 1 through S N of high occurrence frequency in data to be compressed from the compressing side, and selecting a decompressing dictionary 31 -i to be used among plural kinds of decompressing dictionaries 31 -i on the basis of the received selected dictionary information; and

{circle around (2)} function of receiving the selected dictionary information on a compressing dictionary 11 -i selected according to a quantity of compressed data having been coded, and selecting a decompressing dictionary to be used among plural kinds of decompressing dictionaries 31 -i on the basis of the received selected dictionary information.

The data decompressing apparatus 3 according to the first modification performs the same decoding process conducted after the selected dictionary information is received as the above second embodiment, in which only definition of the selected dictionary information received from the compressing side differs.

Namely, when receiving the selected dictionary information form the compressing side, the dictionary selecting unit 32 A selects a decompressing dictionary 31 -i corresponding to the selected dictionary information, referring to the dictionary storing unit 31 C (dictionary selecting step). The dictionary referring unit 23 reads out the selected dictionary 31 -i, and the decoding unit 34 A successively decodes compressed data, referring to the read dictionary 31 -i (decoding step).

The data decompressing apparatus 3 (data decompressing method) according to the first modification can receive the selected dictionary information on a compressing dictionary 11 -i selected as a compressing dictionary 11 -i including specific characters (character strings) S 1 through S N of high occurrence frequency from the compressing side, select a decompressing dictionary 31 -i to be used among plural kinds of decompressing dictionaries 31 -i on the basis of the received selected dictionary information, and decode compressed data on the basis of the decompressing dictionary 31 -i. It is therefore possible to quickly select a decompressing dictionary 31 -i having the same contents as a compressing dictionary selected as a compressing dictionary 11 -i including specific characters (character strings) S 1 through S N of high occurrence frequency on the compressing side at any time so as to accurately decode (decompress) the compressed data.

Alternatively, the data decompressing apparatus 3 (data decompressing method) according to the first modification can receive the selected dictionary information on a compressing dictionary 11 -i selected according to a quantity of compressed data having been coded from the compressing side, select a decompressing dictionary 31 -i to be used among plural kinds of decompressing dictionaries 31 -i on the basis of the received selected dictionary information, and decode compressed data on the basis of the decompressing dictionary 31 -i. It is therefore possible to quickly select a decompressing dictionary having the same contents as a compressing dictionary 11 -i selected according to a quantity of compressed data having been coded on the compressing side at any time so as to accurately decode (decompress) the compressed data.

(c) Others

The dictionaries 11 -i and 31 -i stored in the respective dictionary storing unit 11 C and 31 C can be automatically created by the dictionary creating apparatus 5 A described before with reference to FIG. 14 .

(B2) Description of a Second Modification of the Second Embodiment

(a) Description of the Compressing Side

FIG. 41 is a block diagram showing a data compressing apparatus according to a second modification of the second embodiment. In a data compressing apparatus 1 shown in FIG. 41, as compared with that shown in FIG. 33, the dictionary selecting unit 12 A selects a compressing dictionary 11 -i on the basis of specific characters (character string) frequently occurring in data to be compressed or a quantity of compressed data having been coded, similarly to the above first modification. The data compressing apparatus 1 has a compressed data dividing unit 16 including a word dictionary storing unit 16 and a word inputting unit 17 similar to those (refer to FIG. 15) described above in the second modification of the first embodiment.

The structure of the data compressing apparatus 1 according to the second modification is of the data compressing apparatus 1 shown in FIG. 37 according to the above first modification to which the compressed data dividing unit 16 described in the second modification of the first embodiment is added, wherein the coding unit 14 A codes data to be compressed (document-form data) by word, similarly to the second modification of the first embodiment.

In this case, each decompressing dictionary 11 -i stored in the dictionary storing unit 11 C has contents in which a predetermined code is assigned to each of desired words in document-form data. The dictionary selecting process in the dictionary selecting unit 12 A is performed, based on, not a character (character string), but a word.

In the data compressing apparatus 1 having the above structure according to the second modification, the word inputting unit 18 divides data to be compressed (document-form data) into words, and outputs the words to the coding unit 14 . The coding unit 14 A can code plural character data as a bunch at a time on the basis of a compressing dictionary 11 -i selected by the dictionary selecting unit 12 A.

As compared with the second embodiment, it is possible to largely speed up the decoding process. By dividing data to be compressed into data that is “words” each having own meaning, it is possible to limit the number of kinds of codes to be assigned to the data to be compressed so that a quantity of codes having been coded is decreased, thus a compression ratio is increased. If data to be compressed is coded by word, the decoding process on the decompressing side becomes easy and can be sped up.

A procedure of coding in the above coding unit 14 A corresponds to the flowchart (Steps D 8 through D 16 ) in FIG. 4 in which X (t−n, t−1) is replaced with one word, or the flowchart (Steps D 17 through D 28 ) in FIG. 5 in which X (t, t+n) is replaced with one word.

(b) Description of the Decompressing Side

A data decompressing apparatus 3 according to the second modification, that is, a data decompressing apparatus 3 for the data compressing apparatus 1 described above with reference to FIG. 41, is configured similarly to that shown in FIG. 35 . In this case, a dictionary 31 -i for decompression (decompressing by word) having the same contents as a compressing dictionary 11 -i stored in the dictionary storing unit 11 C on the compressing side is stored in the dictionary storing unit 11 C. The decoding unit 34 A decodes compressed data by word (by predetermined character data group) on the basis of a decompressing dictionary 31 -i selected by the dictionary selecting unit 32 A.

When the data decompressing apparatus 3 according to the second modification receives the selected dictionary information from the compressing side, the dictionary selecting unit 32 A selects a decompressing dictionary corresponding to the selected dictionary information, and the decoding unit 34 A decodes compressed data (codes) using the decompressing dictionary 31 -i.

The decoding process in the decoding unit 34 corresponds to a coding system on the compressing side (statistical or dictionary-based), where X (t−n, t−1) is replaced with one word in the flowchart (Steps E 4 through E 12 ) in FIG. 8, or X (t, t+n) is replaced with one word in the flowchart (Steps E 13 through E 19 ) in FIG. 9 .

The data decompressing apparatus 3 according to the second modification divides compressed data into words when the compressed data is decompressed on the basis of a decompressing dictionary 31 -i selected by the dictionary selecting unit 12 A to decode the compressed data by word. It is therefore possible to decode plural character data as a bunch at a time. This can largely speed up the decoding (decompressing) process after a dictionary is selected, as compared with the above second embodiment.

(c) Others

The dictionaries 11 -i and 31 -i stored in the respective dictionary storing units 11 C and 31 C can be automatically created by the dictionary creating apparatus 5 B described before with reference to FIG. 16 .

(B3) Description of a Third Modification of the Second Embodiment

(a) Description of the Compressing Side

FIG. 42 is a block diagram showing a third modification of the data compressing apparatus 1 shown in FIG. 33 . In the data compressing apparatus 1 shown in FIG. 42, as compared with that shown in FIG. 33, the dictionary selecting unit 12 A selects a compressing dictionary 11 -i according to specific characters (character strings) frequently occurring in data to be compressed or a quantity of compressed data having been coded, similarly to the above first modification. Further, the data compressing apparatus 1 has a compressed data dividing unit 16 A including a word category dictionary storing unit 17 A, a word inputting unit 18 A and a category inputting unit 19 A similar to those (refer to FIG. 17) described above in the third modification of the first embodiment.

A structure of the data compressing apparatus 1 according to the third modification is of the data compressing apparatus 1 according to the above first modification shown in FIG. 37, to which the compressed data dividing unit 16 A described before in the third modification of the first embodiment is added, where the coding unit 14 A codes data to be compressed (document-form data) by word on the basis of category information (part-of-speech information, or the like) on each word, similarly to the third modification of the first embodiment.

In this case, each of the compressing dictionaries stored in the dictionary storing unit 11 C has contents in which category information and a predetermined codes are assigned to each desired word in document-form data. The dictionary selecting process in the dictionary selecting unit 12 A is performed, based on, not a character (character string), but a word.

In the data compressing apparatus 1 having the above structure according to the third modification, the word inputting unit 18 A of the compressed data dividing unit 16 A divides data to be compressed (document-form data) into words on the basis of the word category dictionary storing unit 17 A, and the category inputting unit 19 A adds the category information on each of the obtained words to divide the words into groups according to the category information.

It is therefore possible to decrease the number of kinds of codes to be assigned to the words and shorten a length of each code to be assigned to the word. If the coding unit 14 A performs the coding process using a compressing dictionary 11 -i selected by the dictionary selecting unit 12 A, a quantity of codes having been subjected to the coding process is further decreased and a compression ratio is largely improved, as compared with the above first modification. In this case, the decompressing side can readily specify a word to be decoded owing to the above category information, leading to an increase of a speed of the decoding process.

In this case, a coding system in the coding unit 14 A may be either statistical coding (refer to FIG. 18) or dictionary-based coding (refer to FIG. 19 ).

(b) Description of the Decompressing Side

A data decompressing apparatus 3 according to the third modification, that is, a data decompressing apparatus 3 for the data compressing apparatus 1 described above with reference to FIG. 42, is configured similarly to that shown in FIG. 35 . In this case, the decoding unit 34 A decodes compressed data compressed in the data compressing apparatus 1 on the basis of the above category information by word (by predetermined character data group).

When the data decompressing apparatus 3 according to the third modification receives the selected dictionary information from the compressing side, the dictionary selecting unit 32 A selects a decompressing dictionary 31 -i corresponding to the selected dictionary information, and the decoding unit 34 A decodes compressed data (codes) by word on the basis of the dictionary 31 -i and the above category information (part-of-speech information, or the like), similarly to the third modification of the first embodiment.

In this case, the decoding system in the decoding unit 34 of the data decompressing apparatus 3 according to the third modification corresponds to a coding system in the above coding unit 14 . If statistical coding is employed in the coding unit 14 , statistical decoding (refer to FIG. 20) is employed, or if dictionary-based coding is employed in the coding unit 14 , dictionary-based decoding is employed to decode compressed data.

In the data decompressing apparatus 3 according to the third modification, the decoding unit 34 A decodes compressed data on the basis of the category information on each word so that a word to be decoded is readily specified on the basis of the above category information, which leads to speeding-up of the compressed data decoding process.

(c) Others

The dictionaries 11 -i and 31 -i stored in the above dictionary storing units 11 C and 31 C, respectively, can be automatically created by the dictionary creating apparatus 5 C described before with reference to FIG. 22 .

(B4) Description of a Fourth Modification of the Second Embodiment

(a) Description of the Decompressing Side

FIG. 43 is a block diagram showing a structure of a data compressing apparatus according to a fourth modification of the second embodiment. A data compressing apparatus 1 shown FIG. 43 additionally has, as compared with that shown in FIG. 33, a common dictionary storing unit 11 C′, along with a inherent dictionary storing unit 11 B, a characteristic extracting unit 16 B, an inherent dictionary creating unit 17 B and an inherent dictionary outputting unit 18 B which are similar to those described in the fourth modification of the first embodiment.

In the data compressing apparatus 1 according to the fourth modification, the coding unit 14 A codes data to be compressed on the basis of an inherent dictionary created by the inherent dictionary creating unit 17 B and a compressing dictionary 11 ′-i (i=1 through M: where M is a natural number not less than 2) in the common dictionary storing unit 11 C′ selected by the dictionary selecting unit 32 A.

In the data compressing apparatus 1 according to the fourth modification, the characteristic extracting unit 16 B and the inherent dictionary creating unit 17 B assign a predetermined code to each inherent character data (characteristic data) of data to be compressed to create a compressing inherent dictionary inherent to the data to be compressed (as to a concrete procedure, refer to FIG. 24 ). The coding unit 14 A codes the data to be compressed on the basis of both of the compressing inherent dictionary and a common dictionary selected by the dictionary selecting unit 12 A.

According to the above data compressing apparatus 1 , it is possible to largely decrease probability of coding data to be compressed not registered in a dictionary, thus improve a compression ratio.

In this case, the inherent dictionary outputting unit 18 B outputs information on the above inherent dictionary to the decompressing side so that the decompressing side, which will be described later, accurately decode (decompress) compressed data having been coded according to the inherent dictionary originally created on the compressing side.

The data compressing apparatus 1 according to the fourth modification may code data to be compressed by word, or code data to be compressed by word while adding the category information, similarly to the above second and third modifications.

(b) Description of the Decompressing Side

FIG. 44 is a block diagram showing a structure of a data decompressing apparatus 3 according to the fourth modification of the second embodiment. A data decompressing apparatus 3 shown in FIG. 44 corresponds to the decompressing side of the data compressing apparatus 1 described above with reference to FIG. 43, which additionally has, as compared with that according to the second embodiment shown in FIG. 35, a common dictionary storing unit 31 a and an inherent dictionary storing unit 31 B.

The common dictionary storing unit 31 A and the inherent dictionary storing unit 31 B are similar to those shown in FIG. 25 . The common dictionary storing unit 31 A store dictionaries 31 ′-i (i=1 through M: where M is a natural number not less than 2) having the same contents as common dictionaries stored in the common dictionary storing unit 11 A on the compressing side. The inherent dictionary storing unit 31 B stores a dictionary having characters or character strings inherent to data to be compressed that is compressed data before compressed as characteristic data of the data to be compressed, in which a predetermined code is assigned to each characteristic data, as a decompressing inherent dictionary. According to this modification, by receiving inherent dictionary information outputted from the inherent dictionary outputting unit 18 B on the compressing side, the inherent dictionary storing unit 31 B stores a dictionary having the same contents as an inherent dictionary created by the inherent dictionary creating unit 17 B on the compressing side as the above decompressing dictionary.

Namely, a structure of the data decompressing apparatus 3 according to the fourth modification is of the data decompressing apparatus 3 according to the second embodiment shown in FIG. 35, to which the common dictionary storing unit 31 A and the inherent dictionary storing unit 31 B described in the fourth modification of the first embodiment are added, where the decoding unit 34 A decodes compressed data on the basis of a decompressing inherent dictionary in the inherent dictionary storing unit 31 B and a common dictionary (decompressing dictionary) 31 ′-i in the common dictionary storing unit 31 A selected by the dictionary selecting unit 32 A.

When the data decompressing apparatus 3 having the above structure according to the fourth modification of the second embodiment receives selected dictionary information from the compressing side, the dictionary selecting unit 32 A selects a common dictionary 31 ′-i corresponding to the selected dictionary information. At this time, the inherent dictionary storing unit 31 B receives inherent dictionary information from the compressing side, thereby storing a compressing inherent dictionary having the same contents as a compressing dictionary 11 ′-i having been used on the compressing side.

In the data decompressing apparatus 3 , the dictionary referring unit 33 A merges (composes) the common dictionary 31 ′-i selected by the dictionary selecting unit 32 A and the inherent dictionary in the inherent dictionary storing unit 31 B. The decoding unit 34 A successively decode compressed data on the basis of the dictionary merged as above.

The data decompressing apparatus 3 according to the fourth modification decodes compressed data on the basis of both an inherent dictionary in the inherent dictionary storing unit 31 B and a common dictionary 31 ′-i selected by the dictionary selecting unit 32 A so as to largely decrease probability of decoding compressed data not registered in the selected dictionary, thus further improve efficiency of the decoding.

According to this modification, the inherent dictionary storing unit 31 B can store an inherent dictionary having the same contents as a compressing dictionary 11 ′-i having been used on the compressing side by receiving the inherent dictionary information from the compressing side. The decoding unit 34 A can thereby decode compressed data having been coded according to an inherent dictionary originally created on the compressing side, very accurately.

If the compressing side codes data to be compressed by word or codes data to be compressed by word while adding the category information, the decompressing side may decode compressed data by word or decode compressed data by word on the basis of the category information, as well as the second and third modifications.

(B5) Description of a Fifth Modification of the Second Embodiment

(a) Description of the Compressing Side

FIG. 45 is a block diagram showing a structure of a data compressing apparatus according to a fifth modification of the second embodiment. In a data compressing apparatus shown in FIG. 45, as compared with that shown in FIG. 33, the dictionary selecting unit 12 A selects a compressing dictionary 11 -i on the basis of specific characters (character strings) frequently occurring in data to be compressed or a quantity of compressed data having been coded, similarly to the above first modification. The data compressing apparatus 1 in FIG. 45 additionally has a dictionary updating unit 16 C similar to that (refer to FIG. 27) described above in the fifth modification of the first embodiment.

The data compressing apparatus 1 according to the fifth modification has the dictionary updating unit 16 C which updates a compressing dictionary 11 -i on the basis of compressed data, which has been coded by word by the coding unit 14 A, whereby the coding unit 14 A codes data to be compressed on the basis of the compressing dictionary 11 -i updated by the dictionary updating unit 16 C.

In the data compressing apparatus 1 having the above structure according to the fifth modification, the dictionary selecting unit 12 A selects a compressing dictionary 11 -i in either manner shown in FIG. 38 or 39 , and the coding unit 14 A codes data to be compressed on the basis of the compressing dictionary 11 -i. At this time, the dictionary updating unit 16 C updates the compressing dictionary 11 -i on the basis of compressed data which has been coded by word by the coding unit 14 A.

As the coding process is proceeded, a plurality of compressing dictionaries suitable for data to be compressed that is an object of the next coding can be prepared. This further improves a compression ratio.

Details of the above processes after a dictionary is selected are similar to those shown in FIGS. 28 and 29, description of which is omitted here. The data compressing apparatus 1 according to the fifth modification may code data to be compressed by word, or code data to be compressed by word while adding category information, as well as the second and third modifications.

(b) Description of the Decompressing Side

FIG. 46 is a block diagram showing a structure of a data decompressing apparatus according to the fifth modification of the second embodiment. A data decompressing apparatus 3 shown in FIG. 46 corresponds to the decompressing side of the data compressing apparatus 1 described above with reference to FIG. 45, which additionally has, as compared with that shown in FIG. 35, a dictionary updating unit 35 similar to that (refer to FIG. 30) described above in the fifth modification of the first embodiment.

The data decompressing apparatus 3 according to the fifth modification has the dictionary updating unit (decompressing dictionary updating unit) 35 which updates a decompressing dictionary 31 -i in the dictionary storing unit 31 C on the basis of a result of decoding by the decoding unit 34 A. The decoding unit 34 A decodes compressed data on the basis of the decompressing dictionary 31 -i updated by the dictionary updating unit 35 .

When the data decompressing apparatus 3 according to the fifth modification receives selected dictionary information from the compressing side, the dictionary selecting unit 32 A selects a decompressing dictionary 31 -i corresponding to the received selected dictionary information in the dictionary storing unit 31 C, and the decoding unit 34 A successively decode compressed data on the basis of the decompressing dictionary 31 -i. At this time, the dictionary updating unit 35 successively updates the decompressing dictionary selected by the dictionary selecting unit 32 A on the basis of a result of decoding by the decoding unit 34 A.

According to the data decompressing apparatus 3 of the fifth modification, the dictionary updating unit 35 updates a decompressing dictionary 31 -i selected by the dictionary selecting unit 32 A on the basis of a result of decoding obtained through the decoding process in the decoding unit 34 A. As the decoding process is proceeded, plural kinds of decompressing dictionaries 31 -i suitable for compressed data that is an object of the next decoding can be prepared, which further improves a decompression efficiency.

Details of the above processes after a dictionary is selected are similar to those shown in FIG. 31 or 32 , description of which is omitted here. If the compressing side codes data to be compressed by word, or codes data to be compressed by word while adding the category information, the decompressing side may decode compressed data by word, or decode compressed data by word on the basis of the category information.

(c) Others

The data compressing apparatus 1 in each of the above embodiments and modifications may be applied to not only compressing (coding) of data to be compressed by file, but also to a case where, as shown in FIG. 47, for example, a file contents change detecting-dividing unit 41 and a compressed file spooling unit 42 divide a file to be compressed and hold the divided files, the data compressing apparatus 1 compresses the files, then a coded file spooling unit 43 and a file archiving unit 44 collect each of the coded files, thereby obtaining file in which different kinds of files are archived.

In each of the embodiments and modification, the data compressing apparatus 1 and the data decompressing apparatus are configured by the personal computer 1 as an apparatus exclusively used for compression and by the personal computer 3 as an apparatus exclusively used for decompression, respectively. However, it is alternatively possible to provide a function of the data compressing apparatus 1 as a data compressing unit and a function of the data decompressing apparatus 3 as a data decompressing unit to the personal computer 1 or 3 so as to configure the personal computer 1 or 3 as a data compressing and decompressing apparatus.

In such case, if the above dictionary storing unit 11 and 31 ( 11 C and 31 C) are commonly used by the data compressing unit and the data decompressing unit, it is possible to largely decrease a memory area for holding (storing) the above compressing dictionary and the decompressing dictionary so as to reduce a size of the apparatus. By commonly using each dictionary, the data decompressing unit can decode compressed data according to the same dictionary as a dictionary used in the data compressing unit so that the compressed data can be more accurately decoded.

Each of the above embodiment has been described by way of an example where data to be compressed is mainly character data such as text file data. However, this invention is not limited to this example, but the data to be compressed may be other data such as image data or the like.

It should be noted that this invention is not limited to the above embodiments, but may be modified in various ways without departing from the scope of this invention.