Nothing Special   »   [go: up one dir, main page]

WO2014147671A1 - 圧縮装置、圧縮方法、伸張装置、伸張方法および情報処理システム - Google Patents

圧縮装置、圧縮方法、伸張装置、伸張方法および情報処理システム Download PDF

Info

Publication number
WO2014147671A1
WO2014147671A1 PCT/JP2013/001976 JP2013001976W WO2014147671A1 WO 2014147671 A1 WO2014147671 A1 WO 2014147671A1 JP 2013001976 W JP2013001976 W JP 2013001976W WO 2014147671 A1 WO2014147671 A1 WO 2014147671A1
Authority
WO
WIPO (PCT)
Prior art keywords
data
compression
delimiter
code
unit
Prior art date
Application number
PCT/JP2013/001976
Other languages
English (en)
French (fr)
Inventor
片岡　正弘
坂井　正徳
貴文 大田
Original Assignee
富士通株式会社
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 富士通株式会社 filed Critical 富士通株式会社
Priority to PCT/JP2013/001976 priority Critical patent/WO2014147671A1/ja
Priority to EP13879073.8A priority patent/EP2978135A4/en
Priority to CN201380074817.7A priority patent/CN105191144B/zh
Priority to KR1020157025611A priority patent/KR101750646B1/ko
Priority to AU2013382910A priority patent/AU2013382910B2/en
Priority to JP2015506367A priority patent/JP6527462B2/ja
Publication of WO2014147671A1 publication Critical patent/WO2014147671A1/ja
Priority to US14/857,553 priority patent/US9509333B2/en

Links

Images

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/10—File systems; File servers
    • G06F16/17—Details of further file system functions
    • G06F16/174—Redundancy elimination performed by the file system
    • G06F16/1744—Redundancy elimination performed by the file system using compression, e.g. sparse files
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F40/00—Handling natural language data
    • G06F40/10—Text processing
    • G06F40/12—Use of codes for handling textual entities
    • G06F40/14—Tree-structured documents
    • G06F40/146—Coding or compression of tree-structured data
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/3068—Precoding preceding compression, e.g. Burrows-Wheeler transformation
    • H03M7/3071—Prediction
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method
    • H03M7/3088—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method employing the use of a dictionary, e.g. LZ78
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/70—Type of the data to be coded, other than image and sound
    • H03M7/705—Unicode

Definitions

  • a space symbol included in a character string constituting a document indicates a word break that is a unit constituting the document.
  • one compression code is assigned to a word including a plurality of characters, while a compression code is also assigned to a space symbol. Since a compression code is assigned to a space symbol as well as a word, the number of compression codes used for compression increases, which causes a reduction in compression rate.
  • An object of one aspect of the present invention is to improve a compression rate in compression of data in which a delimiter between units constituting data is indicated by a symbol.
  • the compression apparatus corresponds to a combination of a first element that is one of elements constituting data and a first delimiter that indicates a delimiter between the elements in the data.
  • a storage unit that stores one compression code in association with the first element, and a compression code that is stored in association with the first element read from the data is acquired from the storage unit.
  • An acquisition unit; and a writing unit that writes the acquired compressed code in a storage area for storing the compressed data of the data.
  • the decompressing device combines a combination of a first element that is one of elements constituting data and a first delimiter that indicates a delimiter between the elements in the data into one A storage unit that stores the compressed code in association with the storage unit; an acquisition unit that acquires the combination corresponding to the compressed code read from the compressed data obtained by compressing the data from the storage unit; And a writing unit for writing both the first element and the first delimiter included in the combination into a storage area for decompressed data obtained by decompressing the compressed data.
  • an information processing system includes a storage device and an information processing device, and the information processing device is a delimiter between the elements in the data and a first element that is one of elements constituting data.
  • a storage unit that stores a conversion dictionary in which a combination of delimiters indicating one compression code is associated, a reception unit that receives compressed data obtained by compressing data from the storage device, and the compressed data
  • a first acquisition unit that acquires the combination corresponding to the compression code read from the conversion dictionary, and both the first element and the delimiter included in the acquired combination.
  • a first writing unit for writing in a first storage area of decompressed data obtained by decompressing data, and performing information processing on the decompressed data written in the first storage area A second acquisition unit that acquires, from the conversion dictionary, the compressed code stored in association with the first element read from the decompressed data subjected to the information processing; A first writing unit that writes the acquired compressed code in a second storage area that stores compressed data of the data, and the compressed data written in the second storage area are transmitted to the storage unit And a transmission unit.
  • the computer-readable storage medium stores one compression code corresponding to a combination of a delimiter indicating a delimiter between elements in data and one data element delimited by the delimiter.
  • Compression dictionary data having a structure including information for compression processing associated with each type of data element, wherein the one compression code is referred to based on the one data element in a compression process by a computer
  • the compressed dictionary data is stored.
  • a computer-readable storage medium includes a combination of a delimiter indicating a delimiter between elements in data and one data element delimited by the delimiter as one compression code corresponding to the combination.
  • the decompression dictionary data having a structure including the decompression processing information associated with each data element type, and in the decompression processing by the computer, the decompression in which the combination is referred to based on the one compression code Store dictionary data.
  • the compression efficiency of document data using space symbols can be improved.
  • FIG. 1 shows an example of a compression dictionary.
  • FIG. 2 shows an example of conversion to a compression code.
  • FIG. 3 shows an example of conversion into decompressed data.
  • FIG. 4 shows an example of the functional block configuration.
  • FIG. 5 shows a processing procedure example of the compression function.
  • FIG. 6 shows an example of a processing procedure for generating a compression dictionary.
  • FIG. 7 shows a processing procedure example of statistical processing.
  • FIG. 8 shows an example of the data structure of the statistical table T1.
  • FIG. 9 shows a processing procedure example of the compressed data generation processing.
  • FIG. 10 shows a processing procedure example of the compressed data generation processing.
  • FIG. 11 shows an example of the data structure of the compression dictionary.
  • FIG. 12 shows a processing procedure example of the decompression function.
  • FIG. 13 shows an example of a processing procedure for decompression dictionary generation.
  • FIG. 14 shows a processing procedure example of the decompressed data generation processing.
  • FIG. 15 shows an example of the data structure of the expansion dictionary.
  • FIG. 16 shows a hardware configuration example of the computer 1.
  • FIG. 17 shows an example of a program configuration that runs on the computer 1.
  • FIG. 18 shows a system configuration example using the computer 1.
  • FIG. 19 shows a system configuration example using the computer 1.
  • FIG. 20 shows an example of the data structure of the compression dictionary.
  • FIG. 21 shows an example of the data structure of the expansion dictionary.
  • FIG. 22 shows an example of a data structure in the csv format.
  • FIG. 23 shows an example of the data structure of the compression dictionary.
  • FIG. 24 shows an example of the data structure of the expansion dictionary.
  • FIG. 1 shows an example of a compression dictionary.
  • the compression dictionary D0 includes a symbol compression dictionary D01 and a symbol string compression dictionary D02.
  • the symbol compression dictionary D01 indicates a correspondence relationship between a character code indicating a symbol such as a character or a number and a compression code.
  • the symbol string compression dictionary D02 indicates a correspondence relationship between a character code string indicating a symbol string such as a word or a tag and a compression code.
  • the compression dictionary D1 includes a symbol compression dictionary D11, a symbol string compression dictionary D12, and a control symbol compression dictionary D13.
  • the symbol compression dictionary D11 indicates a correspondence relationship between a character code indicating a symbol such as a character or a number and a compression code.
  • the symbol string compression dictionary D12 indicates a correspondence relationship between a character code string indicating a combination of a symbol string such as a word or a tag and a space symbol and a compression code.
  • the control symbol compression dictionary D13 indicates a correspondence relationship between a compression code and a character code string indicating a combination of a control symbol and a delimiter to delete the immediately preceding space symbol.
  • the compression code included in the compression dictionary D0 is indicated by “c ′ ()”.
  • c ′ () a symbol or a symbol string corresponding to the compression code is shown in parentheses.
  • the compression code included in the compression dictionary D1 is indicated by “c ()”.
  • c () a symbol or a symbol string corresponding to the compression code is shown in parentheses.
  • a compression code corresponding to “a” is indicated as “compression code c (a)”
  • the compression code corresponding to “about ⁇ ” is indicated as “compression code c (about ⁇ )”.
  • the space symbol is a symbol indicated by 0x20 in the ASCII code system, and is indicated as “ ⁇ ” in the description of the present embodiment.
  • control symbol for deleting the space symbol expanded immediately before is indicated as “[- ⁇ ]”.
  • the compression code c ([- ⁇ ];) corresponds to the combination of the control symbol [- ⁇ ] and the delimiter “;”.
  • the symbol string compression dictionary D02 in the compression dictionary D0 associates a compression code with each symbol string and space symbol
  • the symbol string compression dictionary D12 in the compression dictionary D1 is not a symbol string alone but a symbol string.
  • One compression code is associated with a combination of a space symbol.
  • the compression code in the symbol string compression dictionary D12 and the compression code in the control symbol compression dictionary D13 are combined and encoded. Is done.
  • the compression code registered in the control symbol compression dictionary D13 is used in common for each word registered in the symbol string compression dictionary D12, and a symbol string compression dictionary D12 is provided for each delimiter symbol individually.
  • the data size of the compression dictionary is less likely to increase.
  • Example (1) in FIG. 2 shows an example in which the part “about” in the English example sentence E1 is compressed based on the compression dictionary D0.
  • the compressed code c ′ (about) and the compressed code c ′ ( ⁇ ) corresponding to the word “about” and the symbol “ ⁇ ” included in “about” are used for the compressed data. That is, in the example (1), the compressed data corresponding to the portion “about ⁇ ” in the English example sentence E1 is “c ′ (about) c ′ ( ⁇ )”.
  • Example (2) in FIG. 2 shows an example in which the “about ⁇ ” portion in the English example sentence E1 is compressed based on the compression dictionary D1. Since the word “about” is registered in the symbol string compression dictionary D12, the compressed data corresponding to the portion “about” in the English example sentence E1 is “c (about ⁇ )”.
  • the compressed data of the “about ⁇ ” portion is composed of two compression codes, whereas in the example (2), the compressed code constituting the compressed data of the “about ⁇ ” portion is 1. One.
  • Example (3) in FIG. 2 shows an example in which the “invention.”
  • Portion in the English example sentence E1 is compressed based on the compression dictionary D0.
  • the compressed code c ′ (invention) and the compressed code c ′ (.) Corresponding to each of the word “invention” and the symbol “.” Included in “invention.” are used for the compressed data. That is, in the example (3), the compressed data corresponding to the portion of “invention.”
  • the English example sentence E1 is “c ′ (invention) c ′ (.)”.
  • Example (4) in FIG. 2 shows an example when the “invention.”
  • Portion in the English example sentence E1 is compressed based on the compression dictionary D1.
  • the word “invention ⁇ ” is registered in the symbol string compression dictionary D12. If the last space symbol “ ⁇ ” of the symbol string registered in the symbol string compression dictionary D12 is a delimiter other than a space symbol such as “.”, “,”, “;” And “:”, a space A compression code (“invention ⁇ ”) including the symbol “ ⁇ ” is used for the compressed data. That is, even if the portion to be compressed is “invention.”, The compression code c (invention ⁇ ) is used. In this case, the compression code c ([ ⁇ ].) Registered in the control symbol compression dictionary D13 is further used.
  • the compression code c ([- ⁇ ].) Is a compression code corresponding to a combination of the control symbol [- ⁇ ] and the symbol “.”.
  • the control symbol [- ⁇ ] is a control symbol indicating that the immediately preceding space is cancelled.
  • An empty code in the character code system used by the data to be compressed is assigned to the code indicating the control symbol.
  • Example (4) the compressed data corresponding to the “invention.” Portion in the English example sentence E1 is “c (invention ⁇ ) c ([ ⁇ ].)”. In both the example (3) and the example (4), the number of compression codes constituting the compressed data corresponding to “invention.” Is two.
  • the number of compressed codes included in the compressed data is smaller when the compression dictionary D1 is used than when the compression dictionary D0 is used.
  • the number of compression codes included in the compressed data is the same regardless of whether the compression dictionary D0 or the compression dictionary D1 is used. Therefore, if the combination of the symbol string and the space symbol registered in the symbol string compression dictionary D12 exists in the data to be compressed, the compression code used for the compressed data is more compressed using the compression dictionary D1 than the compression dictionary D0.
  • the number of compression codes in the compression dictionary D1 is larger than the number of compression codes registered in the control symbol compression dictionary D13.
  • the number of compression codes in the control symbol compression dictionary D13 is overwhelmingly smaller than the types of characters. For example, even if compression codes related to exclamation, commas, periods, colons, semicolons, and questions are registered in the control symbol dictionary D13, the number of types of compression codes handled is only increased by six.
  • the compression code length is almost unchanged for the entire compression dictionary. For example, even if the number of types of compression codes included in the compression dictionary is doubled, the compression code length is increased by 1 bit for each compression code.
  • the registration of a space symbol that exists at a frequency similar to the number of words in the compression dictionary in combination with the word has a greater effect than the increase in the compression code length due to the addition of the control symbol compression dictionary D13. Therefore, the compression rate is expected to be improved by compression using the compression dictionary D1.
  • FIG. 3 shows an example of conversion into decompressed data.
  • FIG. 3 shows a process (1) of generating decompressed data corresponding to the compression code “c (invention) c ([ ⁇ ⁇ ].)”, which is an example of the compressed data generated using the compression dictionary D1 in FIG. (5) are illustrated.
  • the storage area A3 is a storage area for storing compressed data.
  • the storage area A5 is a buffer area in which an expansion code corresponding to the compression code stored in the storage area A3 is stored.
  • the storage area A4 is a storage area for storing decompressed data generated based on the decompression code stored in the storage area A5.
  • Step (1) in FIG. 3 shows a state in which compressed data is stored in the storage area A3.
  • the decompression code corresponding to the compression code c (invention ⁇ ) is generated.
  • Step (2) in FIG. 3 is a state in which the decompressed code generated in step (1) is written in the storage area A4.
  • the decompression code corresponding to the compression code c ([ ⁇ ].) Is generated.
  • Step (3) in FIG. 3 shows a state in which the decompression codes “[ ⁇ ]” and “.” Generated in step (2) are written. Control based on the control symbol [- ⁇ ] stored in the storage area A5 is performed on the storage area A4.
  • Step (4) in FIG. 3 shows a state in which control based on the control symbol [- ⁇ ] is performed.
  • the write position to the storage area A4 may be shifted without deleting the space symbol ⁇ in the storage area A4.
  • the symbol following the control symbol in this case “.” Is overwritten at the position where the space symbol was written.
  • the conversion process according to the control symbol [- ⁇ ] is performed.
  • the control symbol [- ⁇ ] inconsistency by generating compressed data using a compression code corresponding to the symbol string registered in the compression dictionary D1 even for a symbol string whose trailing space symbol does not match Is resolved.
  • the number of compression codes used for the compressed data can be reduced while suppressing the increase in the types of compression codes to a small amount, so that the compression rate is improved. Furthermore, when decompressing the compressed data compressed by the above-described compression processing, the number of compression codes to be processed is reduced, so that the decompression speed can be improved.
  • the compression code corresponding to the space symbol is not generated in the compression process, and the space is generated each time a word is generated in the expansion process. It is conceivable to generate symbols automatically.
  • compression code generation processing is performed in character units. Since the compressed data includes a compression code indicating a word and a compression code indicating a symbol such as a character, the determination whether the expansion code corresponding to the compression code is a word or a symbol is generated every time an expansion code is generated. To be done. Further, a mechanism for identifying whether the compression code is a compression code corresponding to a word or a compression code corresponding to a character is required.
  • the decompression process of this embodiment it is only determined whether or not the decompression code is a control symbol. For example, it is realized by performing determination processing between a control symbol written in a register and a register in which an expansion code read from the expansion dictionary is written. Multiple determination processes for one decompression code and creation of an decompression program with a complicated algorithm are avoided. In addition, since it is possible to suppress processing across a plurality of decompression codes, the number of registers to be used can also be suppressed.
  • FIG. 4 shows an example of the functional block configuration.
  • the computer 1 includes a compression unit 11, an expansion unit 12, a generation unit 13, a generation unit 14, and a storage unit 15.
  • the storage unit 15 stores, for example, a compression target file F1, a compression file F2, an expansion file F3, a compression dictionary D2, an expansion dictionary D3, and the like. Further, the storage unit 15 stores a word list L1 used for generating the compression dictionary D2 and the expansion dictionary D3, for example.
  • the word list L1 is a list of word groups to which a compression code is assigned.
  • the storage unit 15 includes storage areas such as storage areas A1, A2, A3, A4, and A5, and is used as a work area for processing of the compression unit 11, the expansion unit 12, the generation unit 13, and the generation unit 14.
  • the compression unit 11 performs a compression process on the file F1 stored in the storage unit 15, and generates a compressed file F2.
  • the decompression unit 12 executes decompression processing of the compressed file F2 stored in the storage unit 15, and generates an decompressed file F3.
  • the generation unit 13 generates a compression dictionary D2 used in the compression process of the compression unit 11.
  • the generation unit 14 generates an expansion dictionary D3 used in the expansion process of the expansion unit 12.
  • the compression unit 11 includes a control unit 111, a search unit 112, a reading unit 113, and a writing unit 114.
  • the control unit 111 controls the search unit 112, the reading unit 113, and the writing unit 114, and executes a compression process for the file F1.
  • the control unit 111 loads the file F1 into the storage area A1.
  • the reading unit 113 reads data from the file F1.
  • the search unit 112 searches the compression dictionary D2 for the data read by the reading unit 113.
  • the writing unit 114 writes a compression code corresponding to the search result of the search unit 112 in the storage area A2.
  • the control unit 111 manages the reading position of the reading unit 113, the writing position of the writing unit 114, and the like.
  • control unit 111 causes the reading unit 113 and the writing unit 114 to execute the symbol or symbol string included in the file F1. Causes sequential processing to be executed. Further, the control unit 111 generates a compressed file F2 based on the compressed data stored in the storage area A2, and stores the compressed file F2 in the storage unit 15.
  • the decompression unit 12 includes a control unit 121, a search unit 122, a reading unit 123, and a writing unit 124.
  • the control unit 121 controls the search unit 122, the reading unit 123, and the writing unit 124, and executes decompression processing of the compressed file F2.
  • the control unit 121 loads the compressed file F2 into the storage area A3.
  • the reading unit 123 reads the compressed code from the compressed file F2.
  • the search unit 122 searches the expansion dictionary D3 for the compressed code read by the reading unit 123.
  • the writing unit 124 writes the decompression code corresponding to the search result of the search unit 122 in the storage area A4.
  • the control unit 121 adjusts the write position where writing by the writing unit 124 is performed by one space symbol (for example, 1 byte). To do.
  • the control unit 121 manages the reading position of the reading unit 123, the writing position of the writing unit 124, and the like. For example, the control unit 121 causes the reading unit 123 and the writing unit 124 to sequentially perform the compression codes included in the compressed file F2. Execute the process.
  • the control unit 121 generates an expanded file F3 based on the expanded data stored in the storage area A4, and stores the expanded file F3 in the storage unit 15.
  • the generation unit 13 includes a control unit 131, a statistics unit 132, an allocation unit 133, and a sorting unit 134.
  • the generation unit 13 generates a compression dictionary D2 in response to an instruction from the compression unit 11.
  • the control unit 131 controls the statistics unit 132, the allocation unit 133, and the sorting unit 134, and generates a compression dictionary D2 used for compression of the file F1.
  • the statistical unit 132 generates statistical information of each character and word by counting the number of appearances of characters and words included in the file F1.
  • the sorting unit 134 sorts each character or word for which statistical information is generated based on the statistical information generated by the statistical unit 132.
  • the generation unit 14 includes a control unit 141, an allocation unit 142, a duplication unit 143, and a sorting unit 144.
  • the generation unit 14 generates an expansion dictionary D3 in response to an instruction from the expansion unit 12.
  • the control unit 141 controls the assigning unit 142, the duplicating unit 143, and the sorting unit 144, and generates an expansion dictionary D3 used for decompressing the compressed file F2.
  • the assigning unit 142 uses the statistical information stored in the storage unit 15 to generate a compressed code corresponding to each character or word.
  • the sorting unit 144 sorts the character information assigned with the compression code according to the value of the compression code.
  • the duplication unit 143 duplicates a character code indicating a character or a word corresponding to the compression code according to the code length of each of the sorted compression codes.
  • the control unit 141 generates the expansion dictionary D3 by placing the character code copied by the copying unit 143 at the offset position corresponding to the compression code generated by the assigning unit 142.
  • the control unit 141 further stores the expansion dictionary D3 in the storage unit 15.
  • FIG. 5 shows a processing procedure example of the compression function.
  • the control unit 111 executes preprocessing for compression processing (S101).
  • the call of the compression function includes designation of the file F1 to be compressed.
  • the control unit 111 secures the storage area A1 and the storage area A2, loads the word list L1 from the storage unit 15, and secures the storage area for the statistical table T1 and the compression dictionary D2.
  • the control unit 111 loads the file F1 into the storage area A1 (S102).
  • the control unit 111 divides the file F1 into blocks, and performs the following compression processing for each block obtained by the division. Subsequently, the control unit 111 instructs the generation unit 13 to generate the compression dictionary D2 (S103).
  • FIG. 6 shows an example of a processing procedure for generating a compression dictionary.
  • the control unit 131 causes the statistical unit 132 to execute statistical processing of the file F1 (S201).
  • FIG. 7 shows an example of a statistical processing procedure.
  • the statistical unit 132 starts statistical processing on the file F1 loaded in the storage area A1.
  • the read position indicates the beginning of the file F1 loaded in the storage area A1.
  • the statistics unit 132 acquires a character code from the reading position of the storage area A1 (S301). In the process of S301, the reading position is advanced by the character code acquired in S301.
  • the statistical unit 132 determines whether or not the character code acquired in S301 is a delimiter (S302).
  • the determination in S302 is made according to whether a character code to be processed as a delimiter is set in advance and the character code acquired in S301 corresponds to one of the preset character codes.
  • the delimiter is, for example, a space symbol (0x20 in ASCII code system), exclamation (0x21 in ASCII code system), comma (0x2C in ASCII code system), period (0x2E in ASCII code system), colon (ASCII code system). 0x3A), semicolon (0x3B in ASCII code system) and question (0x3F in ASCII code system).
  • the determination in S302 may be made according to whether or not the character code acquired in S301 is within a predetermined numerical range (for example, 0x20 to 0x3F).
  • the statistical unit 132 stores the character code acquired in S301 in the buffer (S303). The process proceeds to S309 in which the process of S303 ends.
  • the statistical unit 132 determines whether the character code acquired in S301 is a delimiter (S302: YES). As an example, the determination in S304 may be performed before the determination in S302. In this case, the statistical unit 132 performs the determination of S302 when the condition of S304 is not satisfied, proceeds to the procedure of S305 if the determination condition of S302 is satisfied, and proceeds to the procedure of S303 if the determination condition of S302 is not satisfied.
  • S304 space symbol
  • FIG. 8 shows an example of the statistics table T1.
  • the statistics table T1 stores the number of appearances for each symbol such as letters and numbers, each word included in the word list L1, and each combination of a control symbol and each delimiter.
  • the statistical unit 132 may register a character string delimited by satisfying the determination condition of S302 as a word in the statistical table T1.
  • the statistical unit 132 when there is no corresponding character string in the statistical table T1, the statistical unit 132 newly registers the character string as a word in the statistical table T1.
  • a compression code is assigned to words included in the word list L1 but not included in the file F1.
  • a compression code is assigned to a word that is not included in the word list L1 but is included in the file F1.
  • words that are included in the word list L1 and are not included in the file F1 are suppressed from occupying a storage area by being registered in the statistical table T1.
  • the statistical unit 132 counts combinations of control symbols and delimiters (S306). In S306, the number of appearances for the combination of the control symbol for canceling the space symbol and the delimiter acquired in S301 is incremented. When the process of S306 ends, the statistics unit 132 proceeds to the procedure of S309.
  • the statistical unit 132 determines whether or not the reading position is the end of the file F1 loaded in the storage area A1 (S309). If it is not the end in the determination of S309 (S309: NO), the statistical unit 132 proceeds to the procedure of S301. If the end of the determination in S309 (S309: YES), the statistical unit 132 ends the statistical processing.
  • the control unit 131 returns to the procedure of FIG. 6 and causes the sorting unit 134 to execute the sorting process (S202).
  • the sort unit 134 uses the statistical information (each character) generated by the statistical unit 132 using the character information (symbols such as characters, symbol strings such as words, combinations of control symbols and separators) registered in the statistical table T1. Sort based on the number of occurrences of information). For example, the statistic unit 132 rearranges the character information registered in the statistic table T1 in one of the order of increasing or decreasing number of appearances.
  • the control unit 131 causes the allocating unit 133 to execute allocation of a compression code (S203).
  • the assigning unit 133 assigns a compression code to the character information group rearranged in the order of frequency in S202 based on an algorithm that assigns a shorter compression code to the character information having a higher frequency, such as Huffman coding or arithmetic coding.
  • the control unit 131 causes the sorting unit 134 to sort the set of the character information and the compression code assigned to the character information based on the character information (S204). For example, the sorting unit 134 sorts the character information in ascending order of character codes.
  • the sorting unit 134 arranges the first character code value of the character information in ascending order, and arranges character information having the same first character code value in ascending order of the second character code value.
  • the state rearranged by the process of S204 is the compression dictionary D2 shown in FIG.
  • the control unit 131 When the processing of S204 is completed, the control unit 131 performs index generation processing (S205).
  • the control unit 131 generates an index by associating the character information with information indicating the position (offset) in the character information group in which the character information is sorted in S204. For example, the offset “0x126” is associated with the character “i” in the compression dictionary D2 illustrated in FIG.
  • the search for the compression code corresponding to the word starting with “i” is started from “0x126”.
  • the generation unit 13 ends the generation process of the compression dictionary D2.
  • FIG. 11 shows an example of the data structure of the compression dictionary.
  • the compression dictionary D2 shown in FIG. 11 character information and a compression code are stored in association with each other.
  • the storage position of the set of character information and compression code is indicated by an offset starting from the storage position of the compression dictionary D2.
  • the information of the character information “invent ⁇ ” is stored at the offset 0x0140.
  • the index generated in S205 uses this offset to narrow down the search range.
  • “c ()” indicates a compressed code corresponding to character information in parentheses.
  • the compression dictionary D2 is generated by the generation unit 13, but as another example, the compression dictionary D2 may be stored in the storage unit 15 in advance. In this case, the compression dictionary D2 is used in common for a plurality of files. For example, in the compression dictionary D2 stored in the storage unit 15 in advance, a compression code is assigned based on, for example, statistical information of character information in a previously compressed file or a plurality of files existing in the database.
  • control unit 111 When the generation unit 13 finishes generating the compression dictionary D2, the control unit 111 returns to the procedure of FIG. 5 and executes the compressed data generation processing (S104).
  • FIG. 9 shows a processing procedure example of the compressed data generation processing.
  • the read position is set at the start point of the file F1 loaded in the storage area A1, the write position is set at a predetermined position in the storage area A2, and the buffer is cleared.
  • the reading unit 113 acquires a character code from the reading position (S401).
  • the control unit 111 updates the reading position after obtaining the character code in S401. Further, the control unit 111 stores the character code acquired by the reading unit 113 in S401 in a buffer (S402).
  • the control unit 111 determines whether or not the character code acquired in S401 is a space symbol (S403).
  • the process returns to S401, and the reading unit 113 acquires the character code from the reading position. That is, the procedures of S401 and S402 are repeated until the space symbol is read.
  • the search unit 112 searches the compression dictionary D2 with the character code (or character code string) stored in the buffer (S404).
  • the control unit 111 determines whether matching character information matching the character code (or character code string) stored in the buffer exists in the compression dictionary D2 (S405). The process when the matched character information does not exist in the compression dictionary D2 (S405: NO) will be described later with reference to FIG. If the matching character information exists (S405: YES), the writing unit 114 writes the compression code associated with the matching character information in the compression dictionary D2 at the writing position in the storage area A2 (S406).
  • control unit 111 updates the writing position and deletes (clears) the character code (or character code string) stored in the buffer (S407). Further, the control unit 111 determines whether or not the reading position is the end of the file F1 loaded in the storage area A1 (S408).
  • the process returns to S401, and the output unit 113 acquires the character code from the reading position.
  • the control unit 111 ends the compressed data generation process.
  • FIG. 10 shows a processing procedure example of the compressed data generation processing. If there is no matching character information in the compression dictionary D2 in the processing of S405 (S405: NO), the control unit 111 determines that the character code at the end of the character code (or character code string) delimited by the space symbol is It is determined whether it is a delimiter (S409). That is, it is determined whether or not the character code immediately before the space symbol indicates a delimiter symbol in the character code string stored in the buffer. Whether or not it is a delimiter is determined using the same determination condition as in S302 of FIG.
  • the control unit 111 replaces the end delimiter with a space symbol in the character code string up to the end delimiter in the buffer.
  • a character code string is generated (S410).
  • the search unit 112 searches the compression dictionary D2 for the character code string generated in S410 (S411). Based on the search result of S411, the control unit 111 determines whether there is matching character information that matches the character code string generated in S410 in the compression dictionary D2 (S412).
  • the writing unit 114 writes the compression code associated with the matching character information in the compression dictionary D2 at the writing position of the storage area A2 (S413).
  • the control unit 111 updates the writing position in accordance with the writing by the writing unit 114. Further, the writing unit 114 stores, in the compression dictionary D2, the compression code (control code) associated with the combination of the control symbol and the delimiter symbol and the compression code associated with the space symbol at the write position in the storage area A2. Write (S414).
  • the control unit 111 updates the writing position in accordance with the writing by the writing unit 114.
  • the control unit 111 When there is no matching character information (S412: NO) or when the last character code is not a delimiter (S409: NO), the control unit 111 performs processing for each character code in the buffer (S415). To S418). For each character code, the control unit 111 causes the search unit 112 to search the compression dictionary D2 (S416), and causes the writing unit 114 to write the compression code obtained as a result of the search at the write position (S417). When the processing of S416 and S417 is performed for each character code stored in the buffer, the procedure returns to S407, and the control unit 111 clears the character code string stored in the buffer.
  • the control unit 111 When the above compressed data generation process is completed, the procedure returns to S105 shown in FIG.
  • the control unit 111 generates a compressed file F2 using the compressed data stored in the storage area A2, and stores it in the storage unit 15 (S105).
  • the compressed file F2 includes, for example, a header, compressed data in the storage area A2, and trailer information.
  • the header includes, for example, identification information for identifying the compression algorithm and information such as the data size of each of the header, the compressed data, and the trailer information.
  • the trailer information includes, for example, an expansion dictionary D3 corresponding to the statistical table T1 or the compression dictionary D2. The expansion dictionary D3 will be described later with reference to FIG.
  • the control unit 111 When the process of S105 is completed, the control unit 111 notifies the call destination of the compression function that the compression process has been completed (S106).
  • the notification in S106 includes, for example, information indicating the storage destination of the compressed file F2.
  • FIG. 12 shows an example of the processing procedure of the decompression function.
  • the control unit 121 executes preprocessing for decompression processing (S501).
  • the call of the expansion function includes designation of the compressed file F2 to be expanded.
  • the control unit 111 secures the storage area A3 and the storage area A4, loads the statistical table T1 from the compressed file F2, and further secures a storage area for the expansion dictionary D3.
  • control unit 121 loads the compressed file F2 into the storage area A3 (S502).
  • control unit 111 causes the generation unit 14 to generate an expansion dictionary (S503).
  • FIG. 13 shows an example of a processing procedure for generating a decompression dictionary.
  • the control unit 141 acquires the statistics table T1 from the trailer information of the compressed file F2 loaded in the storage area A3 (S601).
  • the allocation unit 142 allocates a compression code to each character information in the statistical table T1 (S602).
  • a compression code is assigned by the same algorithm as in S203.
  • the sorting unit 144 sorts the character information to which the compression code is assigned according to the value of the compression code (S603).
  • the control unit 141 associates the code length of the assigned compression code with each character information to which the compression code is assigned (S604).
  • the duplicating unit 143 duplicates the character information and the code length information to the number corresponding to the code length associated with the character information (S605). Further, the control unit 141 stores the copied information at a position in the storage area of the expansion dictionary D3 secured in the storage unit 15 and at an offset position based on the compression code (S606). As a result of S606, the expansion dictionary D3 is generated, and the procedure proceeds to S504 in FIG.
  • FIG. 15 shows an example of the data structure of the expansion dictionary.
  • the expansion dictionary D3 has a data structure in which information indicating an expansion code (character information) and a code length is stored at an offset position based on a corresponding compression code.
  • the expansion dictionary D3 in FIG. 15 illustrates a case where the maximum code length of the compression code is 12 bits.
  • the expansion dictionary D3 is used for processing of reading fixed-length data from compressed data subjected to variable-length encoding and extracting an expansion code corresponding to the read fixed-length data.
  • the decompression speed can be increased compared to determining the boundary of the code bit by bit.
  • extra data is read out from the compressed data, so the read position from the compressed data is adjusted based on the code length. Since the expansion dictionary D3 is an expansion dictionary used for such expansion processing, information having the same expansion code and code length is registered in duplicate.
  • control symbol [- ⁇ ]. For example, control symbol [- ⁇ ].
  • the symbol string around ⁇ is also the control symbol [- ⁇ ].
  • the number is duplicated according to the code length of the compression code and stored at the offset position according to the compression code.
  • c (about ⁇ ) is 10-bit data “0110101001”.
  • FIG. 14 shows an example of a processing procedure for decompression data generation processing.
  • the control unit 121 starts a process for generating expanded data corresponding to the compressed data included in the compressed file F2.
  • the read position from the storage area A3 is set to the start point of the compressed data of the compressed file F2
  • the write position to the storage area A4 is set to a predetermined position in the storage area A4, and the storage area A5 (buffer) is cleared. Yes.
  • the writing unit 124 writes the decompression code obtained in S702 to the write position in the storage area A4 (S704).
  • the control unit 121 adjusts the writing position (S705). In S705, the control unit 121 returns the writing position in the storage area A4 by one character code. Subsequent to S705, the writing unit writes the delimiter stored in the storage area A5 in the writing position of the storage area A4 (S706).
  • the control unit 121 updates the reading position from the storage area A3 (S707).
  • the read position from the storage area A3 is updated based on the code length obtained by referring to S702.
  • the read position is advanced by the number of bits indicated by the code length information.
  • the control unit 121 updates the write position in the storage area A4 (S708).
  • the write position in the storage area A4 is updated based on the length of the decompressed code (expanded code length) read in S702.
  • the processing order of S707 and S708 may be switched. *
  • the expansion dictionary D3 may further include information indicating the expansion code length in addition to the expansion code and the code length. In that case, for example, the control unit 121 updates the writing position based on the decompression code length associated with each decompression code in the processing of S708.
  • the control unit 121 When the decompressed data generation process is completed, the control unit 121 creates the decompressed file F3 based on the decompressed data stored in the storage area A4, and stores the created decompressed file F3 in the storage unit 15 (S505). Further, the control unit 121 notifies the callee of the decompression function that the decompression process has been completed (S506).
  • the notification in S506 includes, for example, information indicating the storage destination of the decompressed file F3.
  • FIG. 16 shows a hardware configuration example of the computer 1.
  • the computer 1 includes, for example, a processor 301, a RAM (Random Access Memory) 302, a ROM (Read Only Memory) 303, a drive device 304, a storage medium 305, an input interface (I / F) 306, an input device 307, an output interface (I / F) 308, an output device 309, a communication interface (I / F) 310, a SAN (Storage Area Network) interface (I / F) 311, a bus 312 and the like. Each piece of hardware is connected via a bus 312.
  • a processor 301 includes, for example, a processor 301, a RAM (Random Access Memory) 302, a ROM (Read Only Memory) 303, a drive device 304, a storage medium 305, an input interface (I / F) 306, an input device 307, an output interface (I / F) 308, an output device 309, a communication interface (I / F
  • the RAM 302 is a readable / writable memory device.
  • a semiconductor memory such as SRAM (Static RAM) or DRAM (Dynamic RAM), or a flash memory other than the RAM may be used.
  • the ROM 303 may be a PROM (Programmable ROM).
  • the drive device 304 is a device that performs at least one of reading and writing of information recorded in the storage medium 305.
  • the storage medium 305 stores information written by the drive device 304.
  • the storage medium 305 is a storage medium such as a hard disk, a flash memory such as an SSD (Solid State Drive), a CD (Compact Disc), a DVD (Digital Versatile Disc), or a Blu-ray disc.
  • the computer 1 includes a drive device 304 and a storage medium 305 for each of a plurality of types of storage media.
  • the input interface 306 is connected to the input device 307 and is a circuit that transmits an input signal received from the input device 307 to the processor 301.
  • the output interface 308 is a circuit that is connected to the output device 309 and causes the output device 309 to execute an output in accordance with an instruction from the processor 301.
  • the communication interface 310 is a circuit that controls communication via the network 3.
  • the communication interface 310 is, for example, a network interface card (NIC).
  • the SAN interface 311 is a circuit that controls communication with a storage device connected to the computer 1 via the storage area network 4.
  • the SAN interface 311 is, for example, a host bus adapter (HBA).
  • the processor 301 reads a program stored in the ROM 303 or the storage medium 305 to the RAM 302, and performs at least one process of the compression unit 11, the expansion unit 12, the generation unit 13, and the generation unit 14 according to the procedure of the read program. Do. At that time, the RAM 302 is used as a work area of the processor 301.
  • the function of the storage unit 15 is that the ROM 303 and the storage medium 305 store program files (such as an application program 24, middleware 23, and OS 22 described later) and data files (such as a file F1, a compressed file F2, and an expanded file F3). This is realized by being used as a work area of the processor 301.
  • the program read by the processor 301 will be described with reference to FIG.
  • FIG. 17 shows an example of a program configuration that runs on the computer 1.
  • the application program 24 or the middleware 23 is a program in which the processing procedure of the compression function or decompression function of this embodiment is defined.
  • the application program 24 or the middleware 23 is a program in which the compression dictionary generation or decompression dictionary generation processing procedure of this embodiment is defined.
  • the compression program in which the processing procedure of the compression function is defined and the decompression program in which the processing procedure of the decompression function is defined may be an integrated program or a separate program.
  • the compression dictionary generation program in which the compression dictionary generation procedure is defined may be included in the compression program, or may be a separate program called by the compression program.
  • the expansion dictionary generation program in which the procedure for generating the expansion dictionary is defined may be included in the expansion program, or may be a separate program read by the expansion program.
  • OS Operating System 22
  • At least one of the above-described compression function and expansion function, at least one of the compression program, the expansion program, the compression dictionary generation program, and the expansion dictionary generation program is stored in a storage medium.
  • the storage medium is read by the drive device 304 and installed, the program stored in the storage medium becomes executable.
  • Each processing procedure defined in the installed program is executed by controlling the hardware group 21 (301 to 312) based on the OS 23.
  • the functions of the functional blocks included in the computer 1 shown in FIG. 4 are provided when the processor 301 executes a compression program or an expansion program.
  • the processing procedures shown in FIGS. 5, 6, 7, 9, and 10 are executed by the processor 301 to provide the functions of the functional blocks included in the compression unit 11 and the generation unit 13. 12, 13, and 14 are executed by the processor 301, the functions of the functional blocks included in the decompression unit 12 and the generation unit 14 are provided.
  • the function of the control unit 111 is that the processor 301 accesses the RAM 302 (allocating a storage area, loads a file, etc.) and manages the processing status (reading position, writing position, etc.) in the register. It is provided by making a match determination with the information held in the file.
  • the function of the reading unit 113 is provided by the processor 301 accessing the RAM 302 according to the processing status in the register.
  • the function of the search unit 112 is provided when the processor 301 accesses the RAM 302 and performs collation determination based on the access result.
  • the function of the writing unit 114 is provided by the processor 301 accessing the RAM 302 according to the processing status in the register.
  • the function of the control unit 121 is that the processor 301 accesses the RAM 302 (allocating a storage area, loads a file, etc.), manages the processing status (reading position, writing position, etc.) in the register, and stores it in the register. It is provided by making a match determination with the held information.
  • the function of the reading unit 123 is provided by the processor 301 accessing the RAM 302 according to the processing status in the register.
  • the function of the search unit 122 is provided when the processor 301 accesses the RAM 302 and performs collation determination based on the access result.
  • the function of the writing unit 124 is provided by the processor 301 accessing the RAM 302 according to the processing status in the register.
  • the functional blocks in the generation unit 13 are executed using the hardware group 21 as follows.
  • the function of the control unit 131 is provided when the processor 301 performs area management of the RAM 302 and accesses the RAM 302, and the processor 301 calls a routine according to the routine processing result.
  • the function of the statistical unit 132 is provided by an access process to the RAM 302 by the processor 301 and an arithmetic process according to the result of the access process.
  • the function of the sorting unit 134 is provided by the processor 301 accessing the RAM 302 and the arithmetic processing according to the access result.
  • the function of the allocating unit 133 is provided when the processor 301 performs arithmetic processing based on access to the RAM 302.
  • the functional blocks in the generation unit 14 are executed using the hardware group 21 as follows.
  • the function of the control unit 141 is provided when the processor 301 performs area management of the RAM 302 and accesses the RAM 302, and the processor 301 calls a routine according to the routine processing result.
  • the function of the duplication unit 143 is provided by access processing to the RAM 302 by the processor 301.
  • the function of the sorting unit 144 is provided by the processor 301 accessing the RAM 302 and the arithmetic processing according to the access result.
  • the function of the allocation unit 142 is provided by the processor 301 performing arithmetic processing based on access to the RAM 302.
  • the number of compression codes is suppressed. For this reason, the number of memory accesses required for writing the compressed code is suppressed. Further, since the compression rate is improved, the number of I / Os when storing the compressed file is also suppressed.
  • FIG. 18 shows a system configuration example using the computer 1.
  • the information processing system illustrated in FIG. 18 includes a base station 2, a network 3, a computer 1a, and a computer 1b.
  • the computer 1a is connected to the network 3 connected to the computer 1b by at least one of wireless and wired.
  • the compression unit 11, the decompression unit 12, the generation unit 13, and the generation unit 14 illustrated in FIG. 4 may be included only in the computer 1a, or may be included in both the computer 1a and the computer 1b.
  • the computer 1a may include the compression unit 11 and the generation unit 13, and the computer 1b may include the decompression unit 12 and the generation unit 14.
  • the computer 1b includes the compression unit 11 and the generation unit 13, and the computer 1a
  • the decompression unit 12 and the generation unit 14 may be included.
  • the compressed file F2 generated by the computer 1a is transmitted to the computer 1b by communication via the network 3, and the compressed file F2 is expanded by the computer 1b to generate the expanded file F3.
  • the compressed file F2 may be transmitted to the base station 2 wirelessly and transmitted from the base station 2 to the computer 1b.
  • the compression rate is improved, so that the amount of compressed data communicated is reduced. Thereby, the use of the hardware resources of the system illustrated in FIG. 18 for the communication processing is suppressed.
  • FIG. 19 shows a system configuration example using the computer 1.
  • the information processing system illustrated in FIG. 19 includes a computer 1, a network 3, a client device 6, a storage area network (SAN) 4, and a storage device 5.
  • the computer 1 performs information processing in response to a request from the client device 6. Data subject to information processing is compressed and stored in the storage device 5, for example.
  • the computer 1 acquires and decompresses data to be processed that is compressed and stored in the storage device 5.
  • the computer 1 executes the information processing requested from the client device 6 on the decompressed data, further compresses the data after the information processing, and stores it in the storage device 5.
  • the information processing includes, for example, update processing of data stored in the storage device 5, analysis / analysis processing of data stored in the storage device 5, and the like.
  • a compression process or decompression dictionary may be executed based on In that case, the processing of S103 in FIG. 5 and the processing of S503 in FIG. 12 may simply load the compression dictionary and decompression dictionary that are held.
  • the target of the compression process may be a monitoring message output from the system in addition to the file.
  • the monitoring message sequentially stored in the buffer is compressed by the above-described compression processing and stored as a log file.
  • compression may be performed in units of pages in the database, or compression may be performed in units of a plurality of pages.
  • a common compression dictionary may be used for a plurality of monitoring messages, or a common compression dictionary may be used for a plurality of pages.
  • space symbols are often used, but other delimiters are also used.
  • the compression dictionary D2 When the compression dictionary D2 is used, a symbol string with a delimiter, a delimiter and a space symbol, a compression code corresponding to a combination of the symbol string and the space symbol, a compression code corresponding to a control symbol and a delimiter, Three compression codes, corresponding to the space symbol, are used.
  • a delimiter other than the space symbol is used, a space symbol is often used after the delimiter.
  • a compression dictionary D4 in which compression codes are assigned to combinations of control symbols, delimiters (other than space symbols), and space symbols may be used instead of the compression dictionary D2.
  • FIG. 20 shows an example of the data structure of the compression dictionary.
  • the compression dictionary D4 In the compression dictionary D4, combinations of control symbols and delimiters (other than space symbols) are registered.
  • the compression dictionary D4 shown in FIG. 20 combinations of control symbols, delimiters (other than space symbols), and space symbols are registered.
  • the control symbol counting process of S306 in FIG. 7 it is confirmed whether a space symbol follows a delimiter other than a space symbol. If a space symbol follows, the control symbol, delimiter (other than space symbol), and space symbol If the combination is registered, the compression dictionary D4 of FIG. 20 is generated.
  • FIG. 21 shows an example of the data structure of the expansion dictionary. Also in FIG. 21, combinations of control symbols, delimiters (other than space symbols), and space symbols are registered.
  • the expansion dictionary D5 is generated according to the statistical table. The expansion dictionary D5 is used instead of the expansion dictionary D3.
  • csv code-separated values
  • a comma included in the data string indicates a field delimiter that is an element constituting the csv format data.
  • FIG. 22 shows an example of the data structure in the csv format.
  • the csv format data E1 illustrated in FIG. 22 is data including six fields in each row, and the title of each field is a header row (application number, filing date, inventor, country name, route, name of invention). Shown in Each line delimiter is indicated by a line feed code.
  • the data of the inventor field in the data E1 shows the inventor's last name and first name, and the last name and the first name are separated by a space symbol.
  • FIG. 23 shows an example of the data structure of the compression dictionary.
  • the compression dictionary D6 shown in FIG. 23 combinations of symbol strings and commas are registered. For example, character information in which a comma is added to a word such as “INDEX,” or “INFORMATION,” is registered. While the compression dictionary D6 for registering character information including a comma at the end of the character information is used, a delimiter other than a comma is present after the word in the data E1, and thus a control symbol [- ,] Are used. For example, a combination of a control symbol [ ⁇ ,] and a space symbol ⁇ is registered in the compression dictionary D6.
  • a combination of a control symbol [-,] and a line feed code (the line feed code is shown as [Line feed]) is registered.
  • a compression code corresponding to each registered character information is stored in association with the character information.
  • FIG. 24 shows an example of the data structure of the expansion dictionary.
  • each character information registered in the compression dictionary D6 is duplicated and stored in an offset position corresponding to the corresponding compression code in a number corresponding to the code length of the corresponding compression code. ing. Information indicating the code length of the compression code is also stored in the expansion dictionary D7 in association with each character information.
  • each element of the data is separated by a comma, but a line feed code is used at the line boundary. Therefore, for example, the combination of the control symbol [ ⁇ ,] and the line feed code tends to increase the number of appearances and shorten the code length of the compression code.
  • space symbols may be included when multiple words are included in the field.
  • the data of the inventor field of the data E1 shown in FIG. 22 is “KATAOKA ⁇ MASAHIRO,”
  • the compression code corresponding to this data is c (KATAOKA,) c ([ ⁇ ,] ⁇ ) c (MASAHIRO ,).
  • a combination of a symbol string such as a word and a delimiter symbol such as a space symbol existing immediately before the symbol string may be registered in the compression dictionary.
  • a control symbol for deleting the following space symbol is used.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Audiology, Speech & Language Pathology (AREA)
  • Computational Linguistics (AREA)
  • General Health & Medical Sciences (AREA)
  • Health & Medical Sciences (AREA)
  • Artificial Intelligence (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)

Abstract

　一側面によれば、データを構成する単位間の区切りが記号により示されるデータの圧縮において圧縮率を向上させることを目的とする。　圧縮装置が、データを構成する要素のうちの１つである第１の要素と、前記データにおいて前記要素間の区切りを示す第１の区切り記号との組み合わせに対応する１つの圧縮符号を、前記第１の要素と対応付けて記憶する記憶部と、前記データから読み出された前記第１の要素と対応付けて記憶された前記圧縮符号を、前記記憶部から取得する取得部と、取得した前記圧縮符号を、前記データの圧縮データを格納する格納領域に書き込む書込部と、を含む。

Description

圧縮装置、圧縮方法、伸張装置、伸張方法および情報処理システム
　データの圧縮技術または伸張技術の少なくとも一方に関する。
　ハフマン符号化や算術圧縮などの可変長圧縮符号を用いた圧縮アルゴリズムによれば、圧縮対象データ内の文字コードに対応する圧縮符号を用いて圧縮データが生成される。また、ハフマン符号化などの圧縮アルゴリズムを利用して、文字コードの組み合わせである単語に対応づけられた圧縮符号を割り当てて圧縮データの生成を行なう圧縮技術がある（例えば、特許文献１など参照）。
特開２０１０－９３４１４号公報
解決しようとする課題
　特定の言語（例えば、英語やドイツ語など）においては、文書を構成する文字列の中に含まれるスペース記号により、文書を構成する単位である単語の区切りが示される。上述の圧縮アルゴリズムでは、複数の文字を含む単語に対して１つの圧縮符号が割り当てられる一方、スペース記号に対しても圧縮符号が割り当てられる。単語と同等にスペース記号にも圧縮符号が割り当てられるため、圧縮に用いられる圧縮符号数が多くなり、圧縮率が低下する要因となる。
　本発明の一側面によれば、データを構成する単位間の区切りが記号により示されるデータの圧縮において圧縮率を向上させることを目的とする。
　一態様によれば、圧縮装置は、データを構成する要素のうちの１つである第１の要素と、前記データにおいて前記要素間の区切りを示す第１の区切り記号との組み合わせに対応する１つの圧縮符号を、前記第１の要素と対応付けて記憶する記憶部と、前記データから読み出された前記第１の要素と対応付けて記憶された前記圧縮符号を、前記記憶部から取得する取得部と、取得した前記圧縮符号を、前記データの圧縮データを格納する格納領域に書き込む書込部と、を含む。
　一態様によれば、伸張装置は、データを構成する要素のうちの１つである第１の要素と、前記データにおいて前記要素間の区切りを示す第１の区切り記号との組み合わせを、１つの圧縮符号と対応付けて記憶する記憶部と、前記データを圧縮して得られる圧縮データから読み出された前記圧縮符号に対応する前記組み合わせを、前記記憶部から取得する取得部と、取得した前記組み合わせに含まれる前記第１の要素及び前記第１の区切り記号の双方を、前記圧縮データを伸張して得られる伸張データの格納領域に書き込む書込部と、を含む。
　一態様によれば、情報処理システムは、記憶装置と情報処理装置を含み、情報処理装置は、データを構成する要素のうちの１つである第１の要素と前記データにおいて前記要素間の区切りを示す区切り記号の組み合わせと、１つの圧縮符号とが対応付けられた変換辞書を記憶する記憶部と、前記記憶装置から、データを圧縮して得られる圧縮データを受ける受信部と、前記圧縮データから読み出された前記圧縮符号に対応する前記組み合わせを、前記変換辞書から取得する第１の取得部と、取得した前記組み合わせに含まれる前記第１の要素及び前記区切り記号の双方を、前記圧縮データを伸張して得られる伸張データの第１の格納領域に書き込む第１の書込部と、前記第１の格納領域に書き込まれた前記伸長データに対して情報処理を行なう処理部と、前記情報処理が行なわれた前記伸長データから読み出された前記第１の要素に対応付けて記憶された前記圧縮符号を、前記変換辞書から取得する第２の取得部と、取得した前記圧縮符号を、前記データの圧縮データを格納する第２の格納領域に書き込む第１の書込部と、前記第２の格納領域に書き込まれた圧縮データを、前記記憶部に送信する送信部と、を含む。
　一態様によれば、コンピュータ読み取り可能な記憶媒体は、データにおいて要素間の区切りを示す区切り記号と、前記区切り記号によって区切られる１つのデータ要素との組み合わせに対応する１つの圧縮符号を前記データ要素に対応づけた圧縮処理用情報を、前記データ要素の種類ごとに含む構造を有する圧縮辞書データであって、コンピュータによる圧縮処理において、前記１つのデータ要素に基づいて前記１つの圧縮符号が参照される前記圧縮辞書データ、を記憶する。
　一態様によれば、コンピュータ読み取り可能な記憶媒体は、データにおいて要素間の区切りを示す区切り記号と、前記区切り記号によって区切られる１つのデータ要素との組み合わせを、前記組み合わせに対応する１つの圧縮符号と対応づけた伸長処理用情報を、前記データ要素の種類ごとに含む構造を有する伸長辞書データであって、コンピュータによる伸張処理において、前記１つの圧縮符号に基づいて前記組み合わせが参照される前記伸張辞書データ、を記憶する。
　一側面によれば、スペース記号が用いられる文書データの圧縮効率を向上できる。
図１は、圧縮辞書の例を示す。 図２は、圧縮符号への変換例を示す。 図３は、伸張データへの変換例を示す。 図４は、機能ブロックの構成例を示す。 図５は、圧縮機能の処理手順例を示す。 図６は、圧縮辞書生成の処理手順例を示す。 図７は、統計処理の処理手順例を示す。 図８は、統計テーブルＴ１のデータ構造の例を示す。 図９は、圧縮データ生成処理の処理手順例を示す。 図１０は、圧縮データ生成処理の処理手順例を示す。 図１１は、圧縮辞書のデータ構造例を示す。 図１２は、伸張機能の処理手順例を示す。 図１３は、伸張辞書生成の処理手順例を示す。 図１４は、伸張データ生成処理の処理手順例を示す。 図１５は、伸張辞書のデータ構造例を示す。 図１６は、コンピュータ１のハードウェア構成例を示す。 図１７は、コンピュータ１で動作するプログラム構成例を示す。 図１８は、コンピュータ１を用いたシステム構成例を示す。 図１９は、コンピュータ１を用いたシステム構成例を示す。 図２０は、圧縮辞書のデータ構造例を示す。 図２１は、伸張辞書のデータ構造例を示す。 図２２は、ｃｓｖ形式のデータ構造の例を示す。 図２３は、圧縮辞書のデータ構造例を示す。 図２４は、伸張辞書のデータ構造例を示す。
　以下に実施の形態が示される。
［圧縮符号の例］
　図１は、圧縮辞書の例を示す。圧縮辞書Ｄ０は、記号圧縮辞書Ｄ０１および記号列圧縮辞書Ｄ０２を含む。記号圧縮辞書Ｄ０１は、文字や数字などの記号を示す文字コードと圧縮符号との対応関係を示す。記号列圧縮辞書Ｄ０２は、単語やタグなどの記号列を示す文字コード列と圧縮符号との対応関係を示す。圧縮辞書Ｄ１は、記号圧縮辞書Ｄ１１、記号列圧縮辞書Ｄ１２および制御記号圧縮辞書Ｄ１３を含む。記号圧縮辞書Ｄ１１は、文字や数字などの記号を示す文字コードと、圧縮符号との対応関係を示す。記号列圧縮辞書Ｄ１２は、単語やタグなどの記号列およびスペース記号の組み合わせを示す文字コード列と圧縮符号との対応関係を示す。制御記号圧縮辞書Ｄ１３は、直前のスペース記号を削除する旨の制御記号および区切り記号の組み合わせを示す文字コード列と、圧縮符号との対応関係を示す。
　図１に例示される圧縮辞書Ｄ０および圧縮辞書Ｄ１には、圧縮符号と、圧縮符号と対応付けられた記号または記号列とが対応付けて登録されている。圧縮辞書Ｄ０や圧縮辞書Ｄ１に登録された記号または記号列のうち、圧縮対象のデータから読み出された記号または記号列と一致する記号または記号列に対応する圧縮符号が読み出される。
　本実施の形態において、圧縮辞書Ｄ０に含まれる圧縮符号は「ｃ´（）」で示される。圧縮符号を「ｃ´（）」と示す場合には、丸括弧内に圧縮符号に対応する記号または記号列が示される。また、圧縮辞書Ｄ１に含まれる圧縮符号は「ｃ（）」で示される。圧縮符号ｃ（）においても、丸括弧内に圧縮符号に対応する記号または記号列が示される。例えば、「ａ」に対応する圧縮符号は「圧縮符号ｃ（ａ）」などと示され、「ａｂｏｕｔ△」に対応する圧縮符号は「圧縮符号ｃ（ａｂｏｕｔ△）」などと示される。スペース記号は、ＡＳＣＩＩコード系において０ｘ２０で示される記号であり、本実施の形態の説明においては「△」と示される。
　また、詳細は後述されるが、直前に伸張されたスペース記号を削除する旨の制御記号は、「［－△］」と示される。例えば、制御記号［－△］および区切り記号「；」の組み合わせには、圧縮符号ｃ（［－△］；）が対応する。
　圧縮辞書Ｄ０内の記号列圧縮辞書Ｄ０２は、記号列とスペース記号のそれぞれに対して圧縮符号を対応付けるのに対し、圧縮辞書Ｄ１内の記号列圧縮辞書Ｄ１２は、記号列単体ではなく、記号列とスペース記号との組み合わせに対して１つの圧縮符号を対応付ける。圧縮辞書Ｄ１を用いて圧縮が行なわれる場合には、圧縮対象のデータ内に存在する記号列とスペース記号との組み合わせは、記号列圧縮辞書Ｄ１２に登録された組み合わせに対応する圧縮符号により符号化される。
　一方で、記号列と、スペース記号以外の区切り記号（カンマやコロンなど）との組み合わせは、記号列圧縮辞書Ｄ１１内に登録されていない。圧縮対象のデータ内には、スペース記号が後続する記号列だけでなく、スペース記号以外の区切りが後続する記号列も存在しうる。カンマやコロンなどのスペース記号と異なる区切り記号それぞれについて記号列圧縮辞書Ｄ１２が設けられると、圧縮符号の種類が増大し、その結果、圧縮辞書のデータサイズが増大する。そこで、スペース記号を削除する旨を示す制御記号が各単語に対して共通で用いられる。圧縮辞書Ｄ１内の制御記号圧縮辞書Ｄ１３において、制御記号と区切り記号との組み合わせが、１つの圧縮符号と対応づけられる。圧縮対象のデータ内の記号列とスペース記号以外の区切り記号との組み合わせに対しては、記号列圧縮辞書Ｄ１２内の圧縮符号と、制御記号圧縮辞書Ｄ１３内の圧縮符号とが組み合わされて符号化される。制御記号圧縮辞書Ｄ１３に登録される圧縮符号が、記号列圧縮辞書Ｄ１２に登録される各単語に対して共通して用いられており、各区切り記号に対して個別に記号列圧縮辞書Ｄ１２を設けるよりも圧縮辞書のデータサイズが増大しにくい。
　図２は、圧縮符号への変換例を示す。図２には、英語例文Ｅ１「Ｈｅ△ｓｐｅｎｔ△ｍｕｃｈ△ｔｉｍｅ△ｆｏｒ△ｔａｌｋｉｎｇ△ａｂｏｕｔ△ｈｉｓ△ｉｎｖｅｎｔｉｏｎ．」が示される。図２の例において、英語例文Ｅ１は、記憶領域Ａ１に格納された状態である。英語例文Ｅ１中の「ａｂｏｕｔ△」および「ｉｎｖｅｎｔｉｏｎ．」のそれぞれの部分について、圧縮符号の例（１）～（４）が示される。圧縮符号の例（１）および例（３）は、圧縮辞書Ｄ０に含まれる圧縮符号が用いられた例であり、圧縮符号の例（２）および例（４）は、圧縮辞書Ｄ１に含まれる圧縮符号が用いられた例である。
　図２の例（１）は、英語例文Ｅ１中の「ａｂｏｕｔ△」の部分が圧縮辞書Ｄ０に基づいて圧縮された場合の例を示す。「ａｂｏｕｔ△」に含まれる単語「ａｂｏｕｔ」および記号「△」のそれぞれに対応する圧縮符号ｃ´（ａｂｏｕｔ）および圧縮符号ｃ´（△）が圧縮データに用いられる。すなわち、例（１）において、英語例文Ｅ１中の「ａｂｏｕｔ△」の部分に対応する圧縮データは、「ｃ´（ａｂｏｕｔ）ｃ´（△）」となる。
　図２の例（２）は、英語例文Ｅ１中の「ａｂｏｕｔ△」の部分が圧縮辞書Ｄ１に基づいて圧縮された場合の例を示す。記号列圧縮辞書Ｄ１２に単語「ａｂｏｕｔ△」が登録されているので、英語例文Ｅ１中の「ａｂｏｕｔ△」の部分に対応する圧縮データは、「ｃ（ａｂｏｕｔ△）」となる。例（１）においては「ａｂｏｕｔ△」の部分の圧縮データが２つの圧縮符号で構成されるのに対し、例（２）においては「ａｂｏｕｔ△」の部分の圧縮データを構成する圧縮符号は１つである。
　図２の例（３）は、英語例文Ｅ１中の「ｉｎｖｅｎｔｉｏｎ．」の部分が圧縮辞書Ｄ０に基づいて圧縮された場合の例を示す。「ｉｎｖｅｎｔｉｏｎ．」に含まれる単語「ｉｎｖｅｎｔｉｏｎ」および記号「．」のそれぞれに対応する圧縮符号ｃ´（ｉｎｖｅｎｔｉｏｎ）および圧縮符号ｃ´（．）が圧縮データに用いられる。すなわち、例（３）においては英語例文Ｅ１中の「ｉｎｖｅｎｔｉｏｎ．」の部分に対応する圧縮データは、「ｃ´（ｉｎｖｅｎｔｉｏｎ）ｃ´（．）」となる。
　図２の例（４）は、英語例文Ｅ１中の「ｉｎｖｅｎｔｉｏｎ．」の部分が圧縮辞書Ｄ１に基づいて圧縮された場合の例を示す。記号列圧縮辞書Ｄ１２に、単語「ｉｎｖｅｎｔｉｏｎ△」が登録されている。記号列圧縮辞書Ｄ１２に登録された記号列の最後のスペース記号「△」が「．」、「，」、「；」および「：」などのスペース記号以外の区切り記号である場合には、スペース記号「△」を含む圧縮符号（「ｉｎｖｅｎｔｉｏｎ△」）が圧縮データに用いられる。すなわち、圧縮対象の部分が「ｉｎｖｅｎｔｉｏｎ．」であっても、圧縮符号ｃ（ｉｎｖｅｎｔｉｏｎ△）が用いられる。この場合には、さらに、制御記号圧縮辞書Ｄ１３に登録された圧縮符号ｃ（［－△］．）が用いられる。圧縮符号ｃ（［－△］．）は、制御記号［－△］と記号「．」との組み合わせに対応する圧縮符号である。制御記号［－△］は、直前のスペースを打ち消す旨を示す制御記号である。制御記号を示すコードには、圧縮対象のデータが使用する文字コード系における空きコードが割り当てられる。
　例（４）においては英語例文Ｅ１中の「ｉｎｖｅｎｔｉｏｎ．」の部分に対応する圧縮データは、「ｃ（ｉｎｖｅｎｔｉｏｎ△）ｃ（［－△］．）」となる。例（３）においても例（４）においても「ｉｎｖｅｎｔｉｏｎ．」に対応する圧縮データを構成する圧縮符号の数は２つである。
　圧縮対象のデータ内でスペース記号が使用される場合には圧縮辞書Ｄ１を用いた方が圧縮辞書Ｄ０を用いるよりも圧縮データに含まれる圧縮符号の数は少ない。その一方で、スペース記号以外の区切り記号が存在する場合には、圧縮辞書Ｄ０を用いても圧縮辞書Ｄ１を用いても圧縮データに含まれる圧縮符号の数は同じである。そのため、記号列圧縮辞書Ｄ１２に登録された記号列およびスペース記号の組み合わせが圧縮対象のデータ内に存在すれば、圧縮辞書Ｄ０よりも圧縮辞書Ｄ１を用いた方が圧縮データに使用される圧縮符号の数が少なくなる。
　さらに、スペース記号は圧縮対象のデータ内の単語とほぼ同数含まれる。英語などの言語で記述された文書データにおいては、単語と単語との境目がスペース記号で表現されるためである。一方、スペース記号以外の区切り記号は、一文の中に１回か２回程度用いられる。文書データにおいて、スペース記号以外の区切り記号よりもスペース記号の方が用いられる頻度が高い。
　一方、圧縮辞書Ｄ０と比較して、制御記号圧縮辞書Ｄ１３内の登録される圧縮符号の数だけ、圧縮辞書Ｄ１内の圧縮符号の数が多い。しかしながら、制御記号圧縮辞書Ｄ１３内の圧縮符号の数は、文字の種類と比較して圧倒的に少ない。例えば、エクスクラメーション、カンマ、ピリオド、コロン、セミコロンおよびクエスチョンに関する圧縮符号の制御記号辞書Ｄ１３への登録が行なわれたとしても、取り扱われる圧縮符号の種類の数が６種類増大するだけである。
　圧縮符号の種類が６種類増えたとしても、圧縮辞書全体として、圧縮符号長はほぼ変わらない。たとえ、圧縮辞書内に含まれる圧縮符号の種類の数が倍になったとしても、各圧縮符号について圧縮符号長が１ビット増加する程度である。
　そのため、単語数と同程度の頻度で存在するスペース記号を単語と組み合わせて圧縮辞書に登録した方が、制御記号圧縮辞書Ｄ１３が加わることによる圧縮符号長の増大よりも影響が大きい。そのため、圧縮辞書Ｄ１を用いた圧縮により圧縮率の向上が見込まれる。
［伸張手順の例］
　図３は、伸張データへの変換例を示す。図３には、図２で圧縮辞書Ｄ１を用いて生成された圧縮データの例である圧縮符号「ｃ（ｉｎｖｅｎｔｉｏｎ）ｃ（［－△］．）」に対応する伸張データの生成過程（１）～（５）が例示されている。記憶領域Ａ３は圧縮データが格納される記憶領域である。記憶領域Ａ５は記憶領域Ａ３に格納された圧縮符号に対応する伸張コードが格納されるバッファ領域である。また、記憶領域Ａ４は、記憶領域Ａ５に格納される伸張コードに基づき生成される伸張データが格納される記憶領域である。
　図３の過程（１）は、記憶領域Ａ３に圧縮データが格納されている状態を示す。まず、圧縮符号ｃ（ｉｎｖｅｎｔｉｏｎ△）に対応する伸張コードの生成が行なわれる。図３の過程（２）は、過程（１）で生成された伸張コードが記憶領域Ａ４に書き込まれた状態である。次に、圧縮符号ｃ（［－△］．）に対応する伸張コードの生成が行なわれる。図３の過程（３）は、過程（２）で生成された伸張コード「［－△］」と「．」とが書き込まれた状態を示す。記憶領域Ａ５に格納されている制御記号［－△］に基づく制御が記憶領域Ａ４に対して行なわれる。図３の過程（４）は、制御記号［－△］に基づく制御が行なわれた状態を示す。過程（３）の状態で「ｉｎｖｅｎｔｉｏｎ」に続いて存在していたスペース記号△が、過程（４）の状態では削除されている。さらに、記憶領域Ａ５に格納されている「．」に基づいて記憶領域Ａ４への書込みが行なわれる。図３の過程（５）は、「ｉｎｖｅｎｔｉｏｎ」に続いて「．」が書き込まれた状態を示す。
　図３の過程（３）において、記憶領域Ａ４内のスペース記号△を削除せずに、記憶領域Ａ４への書込み位置をずらすだけでもよい。その場合には、制御記号に後続する記号（この場合には「．」）は、スペース記号が書き込まれていた位置に上書きされる。
　上述の過程で制御記号［－△］に応じた変換処理が行なわれる。制御記号［－△］を用いることにより、末尾のスペース記号が一致しない記号列に対しても圧縮辞書Ｄ１に登録された記号列に対応する圧縮符号を用いて圧縮データを生成することによる不整合が解消される。
　上述の圧縮処理によれば、圧縮符号の種類の増大を少量に抑えつつ、圧縮データに用いられる圧縮符号の数を低減させることができるので、圧縮率が向上する。さらに、上述の圧縮処理で圧縮された圧縮データを伸張する場合には、処理対象となる圧縮符号の数が少なくなるので、伸張速度の向上が見込まれる。
　スペース記号に対応する圧縮符号が圧縮データ内に頻出することを抑制するために、例えば、圧縮処理においてそもそもスペース記号に対応する圧縮符号が生成されずに、伸張処理において単語を生成するたびにスペース記号を自動生成することが考えられる。
　しかしながら、圧縮辞書に登録されていない単語については文字単位で圧縮符号の生成処理が行なわれる。圧縮データ内には単語を示す圧縮符号と文字などの記号を示す圧縮符号とが含まれるので、圧縮符号に対応する伸張コードが単語であるか記号であるの判定が、伸張コードを生成するたびに行なわれる。また、圧縮符号が単語に対応する圧縮符号であるか文字に対応する圧縮符号であるかを識別するための仕組みが必要となる。
　さらに、単語に続いてスペース記号以外の区切り記号が存在することもありうるので、伸張コードが単語と判定された後に、単語の次の伸張コードがスペース記号以外の区切り記号であるか否かの判定が行なわれることとなる。この判定が行なわれると、複数の伸張コードにまたがってスペース記号を配置するかの判定が行なわれるため、判定のアルゴリズムが煩雑になる。その結果、伸張速度が劣化するとともに、すでに存在する伸張プログラムのソースコードに対して大幅な変更が必要となる。
　本実施例の伸張処理においては、伸張コードが制御記号であるか否かの判定が行なわれるのみである。例えば、レジスタに書き込まれた制御記号と、伸張辞書から読み出された伸張コードが書き込まれるレジスタとの判定処理を行なうことで実現される。１つの伸張コードに対して多重に判定処理を行なうことや、複雑なアルゴリズムで伸張プログラムを作成することが回避される。また、複数の伸張コードにまたがって処理を行なうことが抑制されるので、使用するレジスタの数も抑制することができる。
［機能・処理手順の説明］
　図４は、機能ブロックの構成例を示す。コンピュータ１は、圧縮部１１、伸張部１２、生成部１３、生成部１４および記憶部１５を含む。記憶部１５は、例えば、圧縮対象のファイルＦ１、圧縮ファイルＦ２、伸張ファイルＦ３、圧縮辞書Ｄ２や伸張辞書Ｄ３などを記憶する。また、記憶部１５は、例えば圧縮辞書Ｄ２や伸張辞書Ｄ３の生成に用いられる単語リストＬ１を記憶する。単語リストＬ１は、圧縮符号を割り当てる対象の単語群のリストである。また、記憶部１５は、記憶領域Ａ１、Ａ２、Ａ３、Ａ４およびＡ５などの記憶領域を設け、圧縮部１１、伸張部１２、生成部１３および生成部１４の処理のワークエリアとして用いられる。圧縮部１１は、記憶部１５に記憶されたファイルＦ１の圧縮処理を実行し、圧縮ファイルＦ２を生成する。伸張部１２は、記憶部１５に記憶された圧縮ファイルＦ２の伸張処理を実行し、伸張ファイルＦ３を生成する。生成部１３は、圧縮部１１の圧縮処理で用いられる圧縮辞書Ｄ２を生成する。生成部１４は、伸張部１２の伸張処理で用いられる伸張辞書Ｄ３を生成する。
　圧縮部１１は、制御部１１１、検索部１１２、読出部１１３および書込部１１４を含む。制御部１１１は、検索部１１２、読出部１１３および書込部１１４を制御し、ファイルＦ１の圧縮処理を実行する。制御部１１１は、ファイルＦ１を記憶領域Ａ１にロードする。読出部１１３は、ファイルＦ１からデータを読み出す。検索部１１２は、読出部１１３が読み出したデータについて、圧縮辞書Ｄ２の検索を行なう。書込部１１４は、検索部１１２の検索結果に応じた圧縮符号を記憶領域Ａ２に書き込む。制御部１１１は、読出部１１３の読出し位置や、書込部１１４の書込み位置などの管理を行ない、例えば、読出部１１３や書込部１１４に、ファイルＦ１に含まれる記号または記号列に対して順次処理を実行させる。また、制御部１１１は、記憶領域Ａ２に格納された圧縮データに基づいて圧縮ファイルＦ２を生成し、記憶部１５に圧縮ファイルＦ２を格納する。
　伸張部１２は、制御部１２１、検索部１２２、読出部１２３および書込部１２４を含む。制御部１２１は、検索部１２２、読出部１２３および書込部１２４を制御し、圧縮ファイルＦ２の伸張処理を実行する。制御部１２１は、圧縮ファイルＦ２を記憶領域Ａ３にロードする。読出部１２３は、圧縮ファイルＦ２から圧縮符号を読み出す。検索部１２２は、読出部１２３が読み出した圧縮符号について、伸張辞書Ｄ３の検索を行なう。書込部１２４は、検索部１２２の検索結果に応じた伸張コードを記憶領域Ａ４に書き込む。制御部１２１は、検索部１２２の検索結果により得られた伸張コードが制御記号を示す場合には、書込部１２４による書込みが行なわれる書込み位置をスペース記号１つ分（例えば１バイト）戻す調整を行なう。制御部１２１は、読出部１２３の読出し位置や、書込部１２４の書込み位置などの管理を行ない、例えば、読出部１２３や書込部１２４に、圧縮ファイルＦ２に含まれる圧縮符号に対して順次処理を実行させる。また、制御部１２１は、記憶領域Ａ４に格納された伸張データに基づいて伸張ファイルＦ３を生成し、記憶部１５に伸張ファイルＦ３を格納する。
　生成部１３は、制御部１３１、統計部１３２、割当部１３３およびソート部１３４を含む。生成部１３は、圧縮部１１からの指示に応じて、圧縮辞書Ｄ２を生成する。制御部１３１は、統計部１３２、割当部１３３およびソート部１３４を制御し、ファイルＦ１の圧縮に用いられる圧縮辞書Ｄ２を生成する。統計部１３２は、ファイルＦ１内に含まれる文字や単語の出現回数をカウントするなどにより、各文字や単語の統計情報を生成する。ソート部１３４は、統計部１３２が生成した統計情報に基づいて、統計情報を生成された各文字や単語をソートする。割当部１３３は、統計部１３２が生成した統計情報に基づいて、各文字や単語に対応する圧縮符号を生成し、生成した圧縮符号を各文字や単語に割り当てる。ソート部１３４は、さらに、圧縮符号を割り当てられた文字や単語を、文字や単語に対応する文字コードの順序（例えば文字コードの値が小さい順）でソートする。制御部１３１は、統計部１３２、割当部１３３およびソート部１３４による処理結果に基づいて圧縮辞書Ｄ２を生成し、記憶部１５に圧縮辞書Ｄ２を格納する。また、制御部１３１は、統計部１３２が生成した統計情報を記憶部１５に格納する。
　生成部１４は、制御部１４１、割当部１４２、複製部１４３およびソート部１４４を含む。生成部１４は、伸張部１２からの指示に応じて、伸張辞書Ｄ３を生成する。制御部１４１は、割当部１４２、複製部１４３およびソート部１４４を制御し、圧縮ファイルＦ２の伸張に用いられる伸張辞書Ｄ３を生成する。割当部１４２は、記憶部１５に格納された統計情報を用いて、各文字や単語に対応する圧縮符号を生成する。ソート部１４４は、圧縮符号が割り当てられた文字情報を、圧縮符号の値に応じてソートする。複製部１４３は、ソートされた各圧縮符号の符号長に応じて、圧縮符号に対応する文字や単語を示す文字コードを複製する。制御部１４１は、複製部１４３により複製された文字コードを、割当部１４２により生成された圧縮符号に対応したオフセット位置に配置することにより、伸張辞書Ｄ３を生成する。制御部１４１は、さらに記憶部１５に伸張辞書Ｄ３を格納する。
　圧縮部１１および生成部１３によりファイルＦ１の圧縮処理が行なわれる。圧縮処理の処理手順は、図５、図６、図７、図９および図１０に示される。また、伸張部１２および生成部１４により圧縮ファイルＦ２の伸張処理が行なわれる。伸張処理の処理手順は、図１２、図１３および図１４に示される。
　図５は、圧縮機能の処理手順例を示す。圧縮機能が呼び出されると、制御部１１１は、圧縮処理の前処理を実行する（Ｓ１０１）。圧縮機能の呼出しは、圧縮対象のファイルＦ１の指定を含む。Ｓ１０１の前処理においては、制御部１１１は、記憶領域Ａ１および記憶領域Ａ２を確保し、単語リストＬ１を記憶部１５からロードし、統計テーブルＴ１および圧縮辞書Ｄ２の格納領域を確保する。
　Ｓ１０１の処理が終了すると、制御部１１１は、記憶領域Ａ１にファイルＦ１をロードする（Ｓ１０２）。ファイルＦ１のサイズが所定のサイズよりも大きい場合には、制御部１１１は、ファイルＦ１をブロック分割し、分割して得られたブロックごとに以下の圧縮処理を行なう。続いて、制御部１１１は、生成部１３に圧縮辞書Ｄ２の生成指示を行なう（Ｓ１０３）。
　図６は、圧縮辞書生成の処理手順例を示す。制御部１１１から圧縮辞書の生成指示を受けると、制御部１３１は、統計部１３２にファイルＦ１の統計処理を実行させる（Ｓ２０１）。
　図７は、統計処理の処理手順例を示す。制御部１３１により統計処理の指示を受けると、統計部１３２は、記憶領域Ａ１にロードされたファイルＦ１について統計処理を開始する。統計処理の開始時において、読出し位置は記憶領域Ａ１にロードされたファイルＦ１の先頭を示す。統計部１３２は、記憶領域Ａ１の読出し位置から文字コードを取得する（Ｓ３０１）。Ｓ３０１の処理において、読出し位置はＳ３０１で取得された文字コード分進められる。
　次に、統計部１３２は、Ｓ３０１で取得した文字コードが区切り記号であるか否かを判定する（Ｓ３０２）。Ｓ３０２の判定は、区切り記号として処理する文字コードを予め設定しておき、Ｓ３０１で取得した文字コードが予め設定した文字コードのいずれかに該当するか否かに応じって判断される。区切り記号は、例えば、スペース記号（ＡＳＣＩＩコード系で０ｘ２０）、エクスクラメーション（ＡＳＣＩＩコード系で０ｘ２１）、カンマ（ＡＳＣＩＩコード系で０ｘ２Ｃ）、ピリオド（ＡＳＣＩＩコード系で０ｘ２Ｅ）、コロン（ＡＳＣＩＩコード系で０ｘ３Ａ）、セミコロン（ＡＳＣＩＩコード系で０ｘ３Ｂ）およびクエスチョン（ＡＳＣＩＩコード系で０ｘ３Ｆ）などである。もしくは、Ｓ３０２の判定は、Ｓ３０１で取得した文字コードが、予め定めた数値範囲（例えば、０ｘ２０～０ｘ３Ｆ）であるか否かに応じて判断されてもよい。
　Ｓ３０１で取得した文字コードが区切り記号でない場合（Ｓ３０２：ＮＯ）には、統計部１３２は、Ｓ３０１で取得した文字コードをバッファに格納する（Ｓ３０３）。Ｓ３０３の処理が終了するＳ３０９の手順に移行する。
　Ｓ３０１で取得した文字コードが区切り記号である場合（Ｓ３０２：ＹＥＳ）には、統計部１３２は、Ｓ３０１で取得した文字コードがスペース記号であるか否かを判定する（Ｓ３０４）。一例として、Ｓ３０４の判定がＳ３０２の判定よりも先に行なわれてもよい。その場合には、統計部１３２は、Ｓ３０４の条件を満たさない場合にＳ３０２の判定を行ない、Ｓ３０２の判定条件を満たせばＳ３０５の手順に移行し、Ｓ３０２の判定条件を満たさなければ、Ｓ３０３の手順に移行する。
　Ｓ３０１で取得した文字コードがスペース記号でない場合（Ｓ３０４：ＮＯ）には、統計部１３２は、単語のカウント処理を行なう（Ｓ３０５）。すなわち、統計部１３２は、バッファに格納されている文字コード（または文字コード列）とＳ３０１で直近に取得した文字コードとをつなげた文字列について、統計テーブルＴ１に格納された出現回数をインクリメントする。Ｓ３０５の処理において、統計テーブルＴ１内に対応する文字列が存在しない場合には、バッファ内の文字コードおよびＳ３０１で直近に取得した文字コードのそれぞれについて、統計テーブルＴ１内の出現回数をインクリメントする。
　図８は、統計テーブルＴ１の例を示す。統計テーブルＴ１には、文字や数字などの各記号、単語リストＬ１に含まれる各単語、および制御記号と各区切り記号との組み合わせのそれぞれについて、出現回数が格納される。
　統計テーブルＴ１を用いた統計処理の他の一例として、統計部１３２が、Ｓ３０２の判定条件を満たすことで区切られる文字列を単語として統計テーブルＴ１に登録してもよい。この他の一例においては、統計テーブルＴ１内に対応する文字列が存在しない場合に、統計部１３２は、文字列を単語として統計テーブルＴ１に新規登録する。これにより単語リストＬ１内に含まれ、ファイルＦ１内に含まれない単語に対して圧縮符号を割り当てることが抑制される。また、単語リストＬ１に含まれず、ファイルＦ１内に含まれる単語に対しても圧縮符号が割り当てられる。また、単語リストＬ１に含まれ、ファイルＦ１内に含まれない単語についても、統計テーブルＴ１に登録されることで記憶領域を占有してしまうことが抑制される。
　Ｓ３０５の処理を終えると、統計部１３２は、制御記号および区切り記号の組み合わせのカウントを行なう（Ｓ３０６）。Ｓ３０６においては、スペース記号を取り消す旨の制御記号と、Ｓ３０１で取得した区切り記号との組み合わせについての出現回数がインクリメントされる。Ｓ３０６の処理が終了すると、統計部１３２は、Ｓ３０９の手順に移行する。
　Ｓ３０１で取得した文字コードがスペース記号である場合（Ｓ３０４：ＹＥＳ）には、Ｓ３０５と同様に単語のカウントを行なう（Ｓ３０７）。また、Ｓ３０５と同様、統計部１３２は、統計テーブルＴ１に対応する単語が存在しない場合には、バッファに格納された文字コードも含めて文字コードごとにカウントを行なう。Ｓ３０７の処理が終了すると、統計部１３２は、バッファをクリアする（Ｓ３０８）。
　Ｓ３０３、Ｓ３０６およびＳ３０８のいずれかが行なわれると、統計部１３２は、読出し位置が、記憶領域Ａ１にロードしたファイルＦ１の終端であるか否かを判定する（Ｓ３０９）。Ｓ３０９の判定において終端でなければ（Ｓ３０９：ＮＯ）、統計部１３２は、Ｓ３０１の手順に移行する。またＳ３０９の判定において終端であれば（Ｓ３０９：ＹＥＳ）、統計部１３２は統計処理を終了する。
　統計部１３２による統計処理が終了すると、制御部１３１は、図６の手順に戻り、ソート部１３４にソート処理を実行させる（Ｓ２０２）。ソート部１３４は、統計テーブルＴ１に登録された文字情報（文字などの記号、単語などの記号列、制御記号と区切り記号との組み合わせなど）を、統計部１３２により生成された統計情報（各文字情報についての出現回数）に基づいて並べ替える。例えば、統計部１３２は出現回数が多い順か少ない順のいずれか一方で、統計テーブルＴ１に登録された文字情報を並べ替える。
　Ｓ２０２の処理が終了すると、制御部１３１は、割当部１３３に圧縮符号の割り当てを実行させる（Ｓ２０３）。割当部１３３は、Ｓ２０２で頻度順に並べ替えられた文字情報群に対して、ハフマン符号化や算術符号化など、高頻度の文字情報ほど短い圧縮符号を割り当てるアルゴリズムに基づいて圧縮符号を割り当てる。各文字情報に圧縮符号が割り当てられると、制御部１３１は、ソート部１３４に、文字情報と、文字情報に割り当てられた圧縮符号との組を、文字情報に基づいてソート処理させる（Ｓ２０４）。ソート部１３４は、例えば、文字情報の文字コードが小さい順に並べ替える。例えば、ソート部１３４は、文字情報の１文字目の文字コードの値が小さい順に並べ、１文字目の文字コードが同じ文字情報同士は、２文字目の文字コードの値が小さい順に並べる。Ｓ２０４の処理により並べ替えられた状態が、図１１に示す圧縮辞書Ｄ２である。
　Ｓ２０４の処理が終了すると、制御部１３１は、インデックスの生成処理を行なう（Ｓ２０５）。制御部１３１は、文字情報と、その文字情報がＳ２０４でソートされた文字情報群内で存在する位置（オフセット）を示す情報とを対応付けてインデックスを生成する。図１１に示す圧縮辞書Ｄ２に対して、例えば、文字「ｉ」にオフセット「０ｘ１２６」などが対応付けられる。圧縮符号の生成においてこのインデックスが利用されると、「ｉ」から始まる単語に対応する圧縮符号の検索が「０ｘ１２６」から開始される。Ｓ２０５の処理が終了すると、生成部１３は、圧縮辞書Ｄ２の生成処理を終了する。
　図１１は、圧縮辞書のデータ構造例を示す。図１１に示される圧縮辞書Ｄ２には、文字情報と圧縮符号とが対応付けられて格納される。文字情報と圧縮符号との組の格納位置は、圧縮辞書Ｄ２の格納位置を始点とするオフセットで示される。例えば、文字情報「ｉｎｖｅｎｔ△」の情報は、オフセット０ｘ０１４０に格納される。Ｓ２０５で生成されるインデックスは、このオフセットを利用して検索範囲の絞り込みを実現する。また、前述の通り、「ｃ（）」は、括弧内の文字情報に対応する圧縮符号であることを示す。
　圧縮辞書Ｄ２は、生成部１３により生成されたが、他の一例として、圧縮辞書Ｄ２が予め記憶部１５に記憶されていることとしてもよい。この場合には、圧縮辞書Ｄ２は、複数のファイルにおいて共通で用いられる。例えば、予め記憶部１５に記憶される圧縮辞書Ｄ２では、例えば、過去に圧縮されたファイルやデータベース内に存在する複数のファイルにおける文字情報の統計情報に基づいて圧縮符号が割り当てられる。
　生成部１３が圧縮辞書Ｄ２の生成処理を終了すると、制御部１１１は図５の手順に戻り、圧縮データ生成処理を実行する（Ｓ１０４）。
　図９は、圧縮データ生成処理の処理手順例を示す。圧縮データ生成処理の開始時点において、読出し位置は記憶領域Ａ１にロードされたファイルＦ１の始点にセットされ、書込み位置は記憶領域Ａ２の所定の位置にセットされ、バッファはクリアされる。読出部１１３は、読出し位置から文字コードを取得する（Ｓ４０１）。制御部１１１は、Ｓ４０１の文字コード取得後、読出し位置を更新する。さらに、制御部１１１は、読出部１１３がＳ４０１で取得した文字コードをバッファに格納する（Ｓ４０２）。制御部１１１は、Ｓ４０１で取得した文字コードがスペース記号であるか否かを判定する（Ｓ４０３）。
　Ｓ４０１で取得した文字コードがスペース記号でない場合（Ｓ４０３：ＮＯ）には、Ｓ４０１の手順に戻り、読出部１１３は、読出し位置から文字コードを取得する。すなわち、Ｓ４０１およびＳ４０２の手順が、スペース記号が読み出されるまで繰り返される。
　Ｓ４０１で取得した文字コードがスペース記号である場合（Ｓ４０３：ＹＥＳ）には、検索部１１２は、圧縮辞書Ｄ２をバッファ内に格納された文字コード（または文字コード列）で検索する（Ｓ４０４）。制御部１１１は、バッファ内に格納された文字コード（または文字コード列）と一致する一致文字情報が圧縮辞書Ｄ２内に存在するか否かを判定する（Ｓ４０５）。圧縮辞書Ｄ２内に一致文字情報が存在しない場合（Ｓ４０５：ＮＯ）の処理は、図１０に基づいて後述される。一致文字情報が存在する場合（Ｓ４０５：ＹＥＳ）には、書込部１１４は、記憶領域Ａ２の書込み位置に、圧縮辞書Ｄ２内で一致文字情報に対応付けられた圧縮符号を書き込む（Ｓ４０６）。続いて、制御部１１１は、書込み位置を更新し、バッファに格納された文字コード（または文字コード列）を削除（クリア）する（Ｓ４０７）。さらに、制御部１１１は、読出し位置が記憶領域Ａ１にロードされたファイルＦ１の終端であるか否かを判定する（Ｓ４０８）。
　読出し位置がファイルＦ１の終端でない場合（Ｓ４０８：ＮＯ）には、Ｓ４０１の手順に戻り、出部１１３は、読出し位置から文字コードを取得する。読出し位置がファイルＦ１の終端である場合（Ｓ４０８：ＹＥＳ）には、制御部１１１は、圧縮データ生成処理を終了する。
　図１０は、圧縮データ生成処理の処理手順例を示す。Ｓ４０５の処理で、圧縮辞書Ｄ２内に一致文字情報が存在しない場合（Ｓ４０５：ＮＯ）には、制御部１１１は、スペース記号で区切られた文字コード（または文字コード列）の末尾の文字コードが区切り記号であるか否かを判定する（Ｓ４０９）。すなわち、バッファに格納された文字コード列において、スペース記号の直前の文字コードが区切り記号を示すか否かが判定される。区切り記号であるか否かについて、図７のＳ３０２と同様の判定条件が用いられる。
　Ｓ４０９の判定で、末尾が区切り記号である場合（Ｓ４０９：ＹＥＳ）には、制御部１１１は、バッファ内の末尾の区切り記号までの文字コード列のうち、末尾の区切り符号をスペース記号に置換した文字コード列を生成する（Ｓ４１０）。検索部１１２は、Ｓ４１０で生成した文字コード列について、圧縮辞書Ｄ２を検索する（Ｓ４１１）。制御部１１１は、Ｓ４１１の検索結果に基づいて、圧縮辞書Ｄ２に、Ｓ４１０で生成した文字コード列と一致する一致文字情報が存在するか否かを判定する（Ｓ４１２）。
　一致文字情報が存在する場合（Ｓ４１２：ＹＥＳ）には、書込部１１４は、圧縮辞書Ｄ２内で一致文字情報と対応付けられた圧縮符号を記憶領域Ａ２の書込み位置に書込む（Ｓ４１３）。制御部１１１は、書込部１１４の書込みに応じて、書込み位置を更新する。さらに、書込部１１４は、圧縮辞書Ｄ２において、制御記号と区切り記号の組み合わせに対応付けられた圧縮符号（制御符号）およびスペース記号と対応づけられた圧縮符号を、記憶領域Ａ２の書込み位置に書き込む（Ｓ４１４）。制御部１１１は、書込部１１４の書込みに応じて、書込み位置を更新する。
　一致文字情報が存在しない場合（Ｓ４１２：ＮＯ）または末尾の文字コードが区切り記号ではない場合（Ｓ４０９：ＮＯ）には、制御部１１１は、バッファ内の各文字コードに対して処理を行なう（Ｓ４１５～Ｓ４１８）。制御部１１１は、各文字コードについて、検索部１１２に圧縮辞書Ｄ２を検索させ（Ｓ４１６）、検索の結果得られた圧縮符号を書込部１１４に書込み位置に書き込ませる（Ｓ４１７）。Ｓ４１６およびＳ４１７の処理が、バッファに格納された各文字コードに対して行なわれると、手順がＳ４０７に戻り、制御部１１１は、バッファに格納された文字コード列をクリアする。
　上述の圧縮データ生成処理が終了すると、図５に示すＳ１０５に手順が戻る。制御部１１１は、記憶領域Ａ２内に格納された圧縮データを用いて圧縮ファイルＦ２を生成し、記憶部１５に格納する（Ｓ１０５）。圧縮ファイルＦ２は、例えば、ヘッダ、記憶領域Ａ２内の圧縮データおよびトレーラ情報で構成される。ヘッダには、例えば、圧縮アルゴリズムを識別する識別情報や、ヘッダ、圧縮データおよびトレーラ情報それぞれのデータサイズなどの情報が含まれる。また、トレーラ情報には、例えば、統計テーブルＴ１または圧縮辞書Ｄ２に対応する伸張辞書Ｄ３が含まれる。伸張辞書Ｄ３は、図１５に基づいて後述される。
　Ｓ１０５の処理が終了すると、制御部１１１は、圧縮機能の呼出し先に圧縮処理が終了した旨の通知を行なう（Ｓ１０６）。Ｓ１０６の通知には、例えば、圧縮ファイルＦ２の格納先を示す情報が含まれる。Ｓ１０６の処理が終了すると、圧縮部１１による圧縮処理が終了する。
　図１２は、伸張機能の処理手順例を示す。伸張機能が呼び出されると、制御部１２１は、伸張処理の前処理を実行する（Ｓ５０１）。伸張機能の呼出しは、伸張対象の圧縮ファイルＦ２の指定を含む。Ｓ５０１の前処理においては、制御部１１１は、記憶領域Ａ３および記憶領域Ａ４を確保し、統計テーブルＴ１を圧縮ファイルＦ２からロードし、さらに、伸張辞書Ｄ３の格納領域を確保する。
　Ｓ５０１の処理が終了すると、制御部１２１は、圧縮ファイルＦ２を記憶領域Ａ３にロードする（Ｓ５０２）。次に、制御部１１１は生成部１４に伸張辞書を生成させる（Ｓ５０３）。
　図１３は、伸張辞書生成の処理手順例を示す。制御部１４１は、記憶領域Ａ３にロードされた圧縮ファイルＦ２のトレーラ情報から統計テーブルＴ１を取得する（Ｓ６０１）。統計テーブルＴ１が取得されると、割当部１４２は、統計テーブルＴ１内の各文字情報に対して圧縮符号を割り当てる（Ｓ６０２）。Ｓ６０２の処理においては、Ｓ２０３と同様のアルゴリズムにより圧縮符号が割り当てられる。ソート部１４４は、圧縮符号が割り当てられた文字情報を、圧縮符号の値に応じてソートする（Ｓ６０３）。さらに、制御部１４１は、圧縮符号が割り当てられた各文字情報に対し、割り当てられた圧縮符号の符号長を関連付ける（Ｓ６０４）。
　次に、複製部１４３は、文字情報に関連付けられた符号長に応じた数に、文字情報および符号長の情報を複製する（Ｓ６０５）。さらに、制御部１４１は、複製された情報を記憶部１５に確保された伸張辞書Ｄ３の格納領域内の位置であって、圧縮符号に基づいたオフセット位置に格納する（Ｓ６０６）。Ｓ６０６の結果、伸張辞書Ｄ３が生成され、手順は図１２のＳ５０４に移行する。
　図１５は、伸張辞書のデータ構造例を示す。伸張辞書Ｄ３は、伸張コード（文字情報）と符号長とを示す情報が、対応する圧縮符号に基づくオフセット位置に格納されるデータ構造を有している。図１５の伸張辞書Ｄ３は、圧縮符号の最大の符号長が１２ビットである場合を例示するものである。
　伸張辞書Ｄ３は、可変長の符号化が行なわれた圧縮データから固定長のデータを読み出して、読み出した固定長のデータに対応する伸張コードを取り出す処理に用いられる。固定長のデータを読み出すことで、1ビットずつ符号の境目を判定するよりも伸張速度の高速化が図られる。１２ビットよりも短い圧縮符号については余分に圧縮データからデータを読み出してしまうので、符号長に基づいて圧縮データからの読出し位置の調整が行なわれる。伸張辞書Ｄ３はこのような伸張処理に用いられる伸張辞書であるため、伸張コードおよび符号長が同じ情報が重複して登録される。
　例えば、伸張辞書Ｄ３における制御記号［－△］．に対応する圧縮符号ｃ（［－△］．）は、「０００１０１１」という７ビットのデータであるのに対し、圧縮データから１２ビットのデータでまとめて読み出される。読み出した１２ビットのうち前半の７ビットが「０００１０１１」であれば、後半の５ビットがどのようなデータであっても制御記号［－△］．という伸張コードが取得可能とする必要がある。そのため、後半の５ビットが取り得る値の全通りについて伸張コードおよび符号長を格納しておくことで、１２ビットの固定長データのうちの後半５ビットがどのようなデータであっても、７ビットの可変長符号に対応する伸張コードなどの情報が取得される。制御記号［－△］．の情報は、後半５ビットの全通り（「０００００」～「１１１１１」）の数（３２）に複製されて、圧縮符号が「０００１０１１」に応じたオフセット位置（０００１０１１０００００（０ｘ１６０））に格納される。
　記号列ａｂｏｕｔ△も、制御記号［－△］．と同様に、圧縮符号の符号長に応じた数に複製され、圧縮符号に応じたオフセット位置に格納される。伸張辞書Ｄ３において、ｃ（ａｂｏｕｔ△）は「０１１０１０１００１」という１０ビットのデータである。このため、記号列ａｂｏｕｔ△に対応する伸張コードおよび符号長の情報は、２の２乗（１２－１０＝２であるため）通りに複製され、「０１１０１０１００１００（０ｘ６Ａ４）」というオフセット位置に格納される。
　図１４は、伸張データ生成処理の処理手順例を示す。伸張辞書Ｄ３が生成されると、制御部１２１は、圧縮ファイルＦ２に含まれる圧縮データに対応する伸張データを生成する処理を開始する。記憶領域Ａ３からの読出し位置は圧縮ファイルＦ２の圧縮データの始点にセットされ、記憶領域Ａ４への書込み位置は記憶領域Ａ４内の所定の位置にセットされ、記憶領域Ａ５（バッファ）はクリアされている。
　読出部１２３は記憶領域Ａ３の読出し位置から圧縮データを読み出す（Ｓ７０１）。圧縮データの読出しは、前述の通り固定長で行なわれる。検索部１２２は、読み出した固定長データに基づいて伸張辞書Ｄ３を参照する（Ｓ７０２）。Ｓ７０２の参照により得られた伸張コードは、記憶領域Ａ５（バッファ）に格納される。続いて、記憶領域Ａ５内の伸張コードが、制御記号および区切り記号の組み合わせであるか否か判定する（Ｓ７０３）。Ｓ７０３の処理は、例えば、伸張コードの先頭の文字コードが制御記号であるか否かに応じて判断されてもよい。
　記憶領域Ａ５内の伸張コードが制御記号および区切り記号の組み合わせでない場合（Ｓ７０３：ＮＯ）には、書込み部１２４は、Ｓ７０２で得られた伸張コードを記憶領域Ａ４の書込み位置に書き込む（Ｓ７０４）。
　記憶領域Ａ５内の伸張コードが制御記号および区切り記号の組み合わせでない場合（Ｓ７０３：ＹＥＳ）には、制御部１２１は、書込み位置の調整を行なう（Ｓ７０５）。Ｓ７０５において、制御部１２１は、記憶領域Ａ４の書込み位置を文字コード１つ分戻す。Ｓ７０５に続いて、書込み部は、記憶領域Ａ５に格納された区切り記号を記憶領域Ａ４の書込み位置に書き込む（Ｓ７０６）。
　Ｓ７０４またはＳ７０６の処理が行なわれると、制御部１２１は、記憶領域Ａ３からの読出し位置を更新する（Ｓ７０７）。記憶領域Ａ３からの読出し位置は、Ｓ７０２の参照により得られた符号長に基づいて更新される。読出し位置は、符号長の情報示されるビット数だけ進められる。さらに、制御部１２１は、記憶領域Ａ４への書込み位置を更新する（Ｓ７０８）。記憶領域Ａ４への書込み位置は、Ｓ７０２で読みだした伸張コードの長さ（伸張コード長）に基づいて更新される。Ｓ７０７およびＳ７０８の処理順序を入れ替えても構わない。　
　続いて、制御部１２１は、記憶領域Ａ３からの読出し位置が、圧縮ファイルＦ２の圧縮データの終端であるか否かを判断する（Ｓ７０９）。記憶領域Ａ３からの読出し位置が圧縮データの終端でない場合（Ｓ７０９：ＮＯ）には手順がＳ７０１に戻り、再度読出部１２３が圧縮データの読出しを行なう。記憶領域Ａ３からの読出し位置が圧縮データの終端である場合（Ｓ７０９：ＹＥＳ）には、制御部１２１は伸張データ生成処理を終了し、手順がＳ５０５に移行する。
　他の一例として、伸張辞書Ｄ３は、伸張コードおよび符号長に加えて、さらに伸張コード長を示す情報を含んでもよい。その場合は、例えば、制御部１２１は、Ｓ７０８の処理において、それぞれの伸張コードに対応付けられた伸張コード長に基づいて書込み位置を更新する。
　さらに、他の一例として、伸張辞書Ｄ３は、伸張辞書の一例であり、同じ情報が重複して登録されていない伸張辞書が用いられてもよい。例えば、一般的なハフマン符号化の伸張辞書が用いられてもよい。その場合であっても、伸張辞書から伸張コードが取得された場合には、制御部１２１は、Ｓ７０３の判定を行ない、その判定結果に応じてＳ７０４か、Ｓ７０５およびＳ７０６かのいずれかの処理を行なう。
　伸張データ生成処理が終了すると、制御部１２１は、記憶領域Ａ４に格納された伸張データに基づいて伸張ファイルＦ３を生成し、生成した伸張ファイルＦ３を記憶部１５に格納する（Ｓ５０５）。さらに、制御部１２１は、伸張機能の呼出し先に伸張処理が終了した旨の通知を行なう（Ｓ５０６）。Ｓ５０６の通知には、例えば、伸張ファイルＦ３の格納先を示す情報が含まれる。Ｓ５０６の処理が終了すると、伸張部１２による伸張処理が終了する。
［構成の説明］
　以下に、上述の圧縮処理や伸張処理を実施する構成について説明する。
　図１６は、コンピュータ１のハードウェア構成例を示す。コンピュータ１は、例えば、プロセッサ３０１、ＲＡＭ（Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｍｅｍｏｒｙ）３０２、ＲＯＭ（Ｒｅａｄ　Ｏｎｌｙ　Ｍｅｍｏｒｙ）３０３、ドライブ装置３０４、記憶媒体３０５、入力インターフェース（Ｉ／Ｆ）３０６、入力デバイス３０７、出力インターフェース（Ｉ／Ｆ）３０８、出力デバイス３０９、通信インターフェース（Ｉ／Ｆ）３１０、ＳＡＮ（Ｓｔｏｒａｇｅ　Ａｒｅａ　Ｎｅｔｗｏｒｋ）インターフェース（Ｉ／Ｆ）３１１およびバス３１２などを含む。それぞれのハードウェアはバス３１２を介して接続されている。
　ＲＡＭ３０２は読み書き可能なメモリ装置であって、例えば、ＳＲＡＭ（Ｓｔａｔｉｃ　ＲＡＭ）やＤＲＡＭ（Ｄｙｎａｍｉｃ　ＲＡＭ）などの半導体メモリ、またはＲＡＭ以外にもフラッシュメモリなどが用いられてもよい。ＲＯＭ３０３は、ＰＲＯＭ（Ｐｒｏｇｒａｍｍａｂｌｅ　ＲＯＭ）などでもよい。ドライブ装置３０４は、記憶媒体３０５に記録された情報の読み出しか書き込みかの少なくともいずれか一方を行なう装置である。記憶媒体３０５は、ドライブ装置３０４によって書き込まれた情報を記憶する。記憶媒体３０５は、例えば、ハードディスク、ＳＳＤ（Ｓｏｌｉｄ　Ｓｔａｔｅ　Ｄｒｉｖｅ）などのフラッシュメモリ、ＣＤ（Ｃｏｍｐａｃｔ　Ｄｉｓｃ）、ＤＶＤ（Ｄｉｇｉｔａｌ　Ｖｅｒｓａｔｉｌｅ　Ｄｉｓｃ）、ブルーレイディスクなどの記憶媒体である。また、例えば、コンピュータ１は、複数種類の記憶媒体それぞれについて、ドライブ装置３０４及び記憶媒体３０５を設ける。
　入力インターフェース３０６は、入力デバイス３０７と接続されており、入力デバイス３０７から受信した入力信号をプロセッサ３０１に伝達する回路である。出力インターフェース３０８は、出力デバイス３０９と接続されており、出力デバイス３０９に、プロセッサ３０１の指示に応じた出力を実行させる回路である。通信インターフェース３１０はネットワーク３を介した通信の制御を行なう回路である。通信インターフェース３１０は、例えばネットワークインターフェースカード（ＮＩＣ）などである。ＳＡＮインターフェース３１１は、ストレージエリアネットワーク４によりコンピュータ１と接続された記憶装置との通信の制御を行なう回路である。ＳＡＮインターフェース３１１は、例えばホストバスアダプタ（ＨＢＡ）などである。
　入力デバイス３０７は、操作に応じて入力信号を送信する装置である。入力信号は、例えば、キーボードやコンピュータ１の本体に取り付けられたボタンなどのキー装置や、マウスやタッチパネルなどのポインティングデバイスである。出力デバイス３０９は、コンピュータ１の制御に応じて情報を出力する装置である。出力デバイス３０９は、例えば、ディスプレイなどの画像出力装置（表示デバイス）や、スピーカーなどの音声出力装置などである。また、例えば、タッチスクリーンなどの入出力装置が、入力デバイス３０７及び出力デバイス３０９として用いられる。また、入力デバイス３０７及び出力デバイス３０９は、コンピュータ１と一体になっていてもよいし、コンピュータ１に含まれず、例えば、コンピュータ１に外部から有線または無線で接続する装置であってもよい。
　例えば、プロセッサ３０１は、ＲＯＭ３０３や記憶媒体３０５に記憶されたプログラムをＲＡＭ３０２に読み出し、読み出されたプログラムの手順に従って圧縮部１１、伸張部１２、生成部１３および生成部１４の少なくとも１つの処理を行なう。その際にＲＡＭ３０２はプロセッサ３０１のワークエリアとして用いられる。記憶部１５の機能は、ＲＯＭ３０３および記憶媒体３０５がプログラムファイル（後述のアプリケーションプログラム２４、ミドルウェア２３およびＯＳ２２など）やデータファイル（ファイルＦ１、圧縮ファイルＦ２および伸張ファイルＦ３など）を記憶し、ＲＡＭ３０２がプロセッサ３０１のワークエリアとして用いられることによって実現される。プロセッサ３０１が読み出すプログラムについては、図１７を用いて説明する。
　図１７は、コンピュータ１で動作するプログラム構成例を示す。アプリケーションプログラム２４またはミドルウェア２３は、本実施形態の圧縮機能または伸張機能の処理手順が定められたプログラムである。もしくは、アプリケーションプログラム２４またはミドルウェア２３は、本実施形態の圧縮辞書生成または伸張辞書生成の処理手順が定められたプログラムである。
　圧縮機能の処理手順が定められた圧縮プログラムと、伸張機能の処理手順が定められた伸張プログラムとが一体のプログラムでもよいし、別体のプログラムでもよい。さらに、圧縮辞書生成の手順が定められた圧縮辞書生成プログラムは、圧縮プログラムに含まれてもよいし、圧縮プログラムにより呼び出される別体のプログラムでもよい。また、伸張辞書生成の手順が定められた伸張辞書生成プログラムは、伸張プログラムに含まれてもよいし、伸張プログラムにより読み出される別体のプログラムでもよい。もしくはＯＳ（オペレーティング・システム）２２の一機能として、本実施形態の圧縮機能および伸張機能の少なくとも一方が提供されてもよい。
　例えば、上述の圧縮機能および伸張機能の少なくとも一方、圧縮プログラム、伸張プログラム、圧縮辞書生成プログラムならびに伸張辞書生成プログラムの少なくとも１つは、記憶媒体に記憶される。例えば、その記憶媒体がドライブ装置３０４により読み取られ、インストールされることにより記憶媒体に記憶されたプログラムが実行可能な状態になる。インストールされたプログラムに定められた処理手順の各々は、ＯＳ２３に基づいてハードウェア群２１（３０１～３１２）が制御されることにより実行される。
　図４に示すコンピュータ１に含まれる各機能ブロックの機能は、プロセッサ３０１が、圧縮プログラムまたは伸張プログラムを実行することにより提供される。図５、図６、図７、図９および図１０に示される処理手順がプロセッサ３０１に実行されることにより圧縮部１１および生成部１３内に含まれる各機能ブロックの機能が提供される。また、図１２、図１３および図１４に示される処理手順がプロセッサ３０１に実行されることにより伸張部１２および生成部１４内に含まれる各機能ブロックの機能が提供される。
　例えば、圧縮部１１内の機能ブロックは、以下のようにハードウェア群２１を用いて実行される。制御部１１１の機能は、プロセッサ３０１が、ＲＡＭ３０２内へのアクセス（記憶領域の確保、ファイルのロードなど）を行ない、また、レジスタ内で処理ステータス（読出し位置や書込み位置など）を管理し、レジスタ内に保持された情報との合致判定を行なうことにより提供される。読出部１１３の機能は、プロセッサ３０１がレジスタ内の処理ステータスに応じてＲＡＭ３０２にアクセスすることにより提供される。検索部１１２の機能は、プロセッサ３０１がＲＡＭ３０２にアクセスし、アクセス結果に基づく照合判定を行なうことにより提供される。書込部１１４の機能は、プロセッサ３０１がレジスタ内の処理ステータスに応じてＲＡＭ３０２にアクセスすることにより提供される。
　例えば、伸張部１２内の機能ブロックは、以下のようにハードウェア群２１を用いて実行される。制御部１２１の機能は、プロセッサ３０１が、ＲＡＭ３０２内へのアクセス（記憶領域の確保、ファイルのロードなど）を行ない、レジスタ内で処理ステータス（読出し位置や書込み位置など）を管理し、レジスタ内に保持された情報との合致判定を行なうことにより提供される。また、読出部１２３の機能は、プロセッサ３０１がレジスタ内の処理ステータスに応じてＲＡＭ３０２にアクセスすることにより提供される。検索部１２２の機能は、プロセッサ３０１がＲＡＭ３０２にアクセスし、アクセス結果に基づく照合判定を行なうことにより提供される。書込部１２４の機能は、プロセッサ３０１がレジスタ内の処理ステータスに応じてＲＡＭ３０２にアクセスすることにより提供される。
　例えば、生成部１３内の機能ブロックは、以下のようにハードウェア群２１を用いて実行される。制御部１３１の機能は、プロセッサ３０１がＲＡＭ３０２の領域管理およびＲＡＭ３０２へのアクセスを行ない、さらに、プロセッサ３０１がルーチンの処理結果に応じたルーチンの呼出しを行なうことにより提供される。統計部１３２の機能は、プロセッサ３０１によるＲＡＭ３０２へのアクセス処理およびアクセス処理の結果に応じた演算処理により提供される。ソート部１３４の機能は、プロセッサ３０１によるＲＡＭ３０２へのアクセスとアクセス結果に応じた演算処理により提供される。割当部１３３の機能は、プロセッサ３０１がＲＡＭ３０２へのアクセスに基づく演算処理を行なうことにより提供される。
　例えば、生成部１４内の機能ブロックは、以下のようにハードウェア群２１を用いて実行される。制御部１４１の機能は、プロセッサ３０１がＲＡＭ３０２の領域管理およびＲＡＭ３０２へのアクセスを行ない、さらに、プロセッサ３０１がルーチンの処理結果に応じたルーチンの呼出しを行なうことにより提供される。複製部１４３の機能は、プロセッサ３０１によるＲＡＭ３０２へのアクセス処理により提供される。ソート部１４４の機能は、プロセッサ３０１によるＲＡＭ３０２へのアクセスとアクセス結果に応じた演算処理により提供される。割当部１４２の機能は、プロセッサ３０１がＲＡＭ３０２へのアクセスに基づく演算処理を行なうことにより提供される。
　本実施形態によれば、記号列とスペース記号とに対し、１つの圧縮符号を割り当てるため、圧縮符号数が抑制される。そのため、圧縮符号の書込みに要するメモリアクセス回数が抑制される。また、圧縮率が向上するため、圧縮ファイルを格納する際のＩ／Ｏの回数も抑制される。
　図１８は、コンピュータ１を用いたシステム構成例を示す。図１８に例示する情報処理システムは、基地局２、ネットワーク３、コンピュータ１ａおよびコンピュータ１ｂを含む。コンピュータ１ａは、無線または有線の少なくとも一方により、コンピュータ１ｂと接続されたネットワーク３に接続している。図４に示す圧縮部１１、伸張部１２、生成部１３および生成部１４が、コンピュータ１ａのみに含まれてもよいし、コンピュータ１ａおよびコンピュータ１ｂの双方に含まれてもよい。コンピュータ１ａが圧縮部１１および生成部１３を含み、コンピュータ１ｂが伸張部１２および生成部１４を含んでもよいし、それとは逆に、コンピュータ１ｂが圧縮部１１および生成部１３を含み、コンピュータ１ａが伸張部１２および生成部１４を含んでもよい。
　例えば、コンピュータ１ａで生成された圧縮ファイルＦ２がネットワーク３を介した通信によりコンピュータ１ｂに送信され、コンピュータ１ｂにより圧縮ファイルＦ２が伸張されて伸張ファイルＦ３が生成される。圧縮ファイルＦ２は無線で基地局２に送信され、基地局２からコンピュータ１ｂに送信されてもよい。
　本実施形態の圧縮機能や伸張機能によれば圧縮率が向上するので、通信される圧縮データの量が削減される。それにより通信処理に対する図１８に例示されるシステムのハードウェアリソースの使用が抑制される。
　図１９は、コンピュータ１を用いたシステム構成例を示す。図１９に例示する情報処理システムは、コンピュータ１、ネットワーク３、クライアント装置６、ストレージエリアネットワーク（ＳＡＮ）４およびストレージ装置５を含む。例えば、コンピュータ１は、クライアント装置６からの要求に応じた情報処理を行なう。情報処理対象のデータは、例えばストレージ装置５に圧縮されて記憶されている。コンピュータ１は、クライアント装置６から要求を受けた場合に、圧縮されてストレージ装置５に記憶された情報処理対象のデータを取得して伸張する。コンピュータ１は、伸張したデータに対してクライアント装置６から要求された情報処理を実行し、さらに、情報処理後のデータを圧縮し、ストレージ装置５に格納する。情報処理は、例えば、ストレージ装置５に記憶されたデータの更新処理や、ストレージ装置５に記憶されたデータの分析・解析処理などである。
　図１９に例示されるシステムにおいては、圧縮処理や伸張処理の度に圧縮辞書や伸張辞書を生成しなくても、一度作成した圧縮辞書や伸張辞書を保持しておき、その圧縮辞書や伸張辞書に基づいて圧縮処理または伸張辞書が実行されてもよい。その場合、図５のＳ１０３の処理や図１２のＳ５０３の処理は、単に保持されている圧縮辞書や伸張辞書をロードするのみでもよい。
　図１９に例示するシステムでは、情報処理の要求を受けるたびにデータの伸張が行なわれる。伸張処理に時間がかかると要求に対する応答までの時間も増大してしまう。本実施形態の圧縮機能により圧縮率が向上すると、圧縮データをストレージ装置５から読み出すＩ／Ｏ回数が削減される。また、圧縮符号数が少ないので伸張処理にかかるメモリアクセスの回数が抑制される。また、圧縮ファイルＦ２のロードに確保される記憶領域も少なく抑えられる。
［変形例の説明］
　以下、上述の実施形態における変形例の一部を説明する。
　圧縮処理の対象は、ファイル以外にも、システムから出力される監視メッセージなどでもよい。例えば、バッファに順次格納される監視メッセージを上述の圧縮処理により圧縮し、ログファイルとして格納するなどの処理が行なわれる。また、例えば、データベース内のページ単位に圧縮が行なわれてもよいし、複数のページをまとめた単位で圧縮が行なわれてもよい。また、圧縮辞書は複数の監視メッセージに対して共通の圧縮辞書が用いられてもよいし、複数のページに対して共通の圧縮辞書が用いられてもよい。
　文書データにおいて、スペース記号が多く用いられるが、その他の区切り記号も用いられる。圧縮辞書Ｄ２を用いた場合、区切り記号が付された記号列、区切り記号およびスペース記号を、記号列とスペース記号の組み合わせに対応する圧縮符号と、制御記号および区切り記号に対応する圧縮符号と、スペース記号に対応する圧縮符号の３つの圧縮符号が用いられる。しかし、スペース記号以外の区切り記号が用いられる際には、その区切り記号に後続してスペース記号が用いられることが多い。制御記号、区切り記号（スペース記号以外）およびスペース記号の組み合わせに対して圧縮符号を割り当てた圧縮辞書Ｄ４が圧縮辞書Ｄ２の代わりに用いられてもよい。
　図２０は、圧縮辞書のデータ構造例を示す。圧縮辞書Ｄ４には、制御記号と区切り記号（スペース記号以外）との組み合わせが登録されている。一方、図２０に示す圧縮辞書Ｄ４には、制御記号、区切り記号（スペース記号以外）およびスペース記号の組み合わせが登録されている。図７のＳ３０６の制御記号カウント処理において、スペース記号以外の区切り記号にスペース記号が後続するかを確認し、スペース記号が後続する場合には制御記号、区切り記号（スペース記号以外）およびスペース記号の組み合わせが登録されれば、図２０の圧縮辞書Ｄ４が生成される。
　図２１は、伸張辞書のデータ構造例を示す。図２１においても、制御記号、区切り記号（スペース記号以外）およびスペース記号の組み合わせが登録されている。図２０で説明した手順に則って統計テーブルＴ１が生成されると、その統計テーブルに従って伸張辞書Ｄ５が生成される。伸張辞書Ｄ５は伸張辞書Ｄ３の代わりに用いられる。
　文書データにおいては、文書データを構成する要素である単語などの言語単位の境目がスペース記号で示される。一方、ｃｓｖ（ｃｏｍｍａ－ｓｅｐａｒａｔｅｄ　ｖａｌｕｅｓ）形式のデータにおいては、データ列に含まれるカンマにより、ｃｓｖ形式のデータを構成する要素であるフィールドの区切りが示される。上述の圧縮アルゴリズムがｃｓｖ形式のファイルに用いられた場合にも、カンマに対応する圧縮符号がデータ間に繰り返し用いられるため、圧縮率が向上しにくい。
　図２２は、ｃｓｖ形式のデータ構造の例を示す。図２２に例示されるｃｓｖ形式のデータＥ１は、各行に６つのフィールドを含むデータであり、それぞれのフィールドのタイトルがヘッダ行（出願番号,出願日,発明者,国名,ルート,発明の名称）に示される。各行の区切りは改行コードにより示される。また、データＥ１内の発明者フィールドのデータは、発明者の姓および名が示され、姓と名との間がスペース記号で区切られている。
　図２３は、圧縮辞書のデータ構造例を示す。図２３に示される圧縮辞書Ｄ６には、記号列およびカンマの組み合わせが登録される。例えば、「ＩＮＤＥＸ，」や「ＩＮＦＯＲＭＡＴＩＯＮ，」などのように単語にカンマが付された文字情報が登録される。文字情報の末尾にカンマが含まれる文字情報を登録する圧縮辞書Ｄ６を用いる一方で、データＥ１内に単語の後にカンマ以外の区切り記号が存在するため、直前のカンマ記号を削除する制御記号［－，］が用いられる。例えば、圧縮辞書Ｄ６には、制御記号［－，］とスペース記号△との組み合わせが登録される。また、例えば、圧縮辞書Ｄ６には、制御記号［－，］と改行コード（改行コードは［改行］と図示される）との組み合わせが登録される。圧縮辞書Ｄ６には、登録された文字情報のそれぞれに対応する圧縮符号が、文字情報と対応付けられて格納される。
　図２４は、伸張辞書のデータ構造例を示す。図２４に示される伸張辞書Ｄ７に、圧縮辞書Ｄ６に登録された各文字情報が、対応する圧縮符号に応じたオフセット位置に、対応する圧縮符号の符号長に応じた数に複製されて格納されている。圧縮符号の符号長を示す情報も各文字情報に対応付けて伸張辞書Ｄ７に格納されている。
　ｃｓｖ形式のデータにおいては、カンマでデータの各要素が区切られるが、行の境目においては改行コードが用いられる。そのため、例えば、制御記号［－，］と改行コードとの組み合わせは、出現回数が多くなり、圧縮符号の符号長が短くなる傾向にある。
　また、フィールド内に複数の単語が含まれる場合に、スペース記号が含まれる場合がある。例えば、図２２に示すデータＥ１の発明者フィールドのデータは「ＫＡＴＡＯＫＡ△ＭＡＳＡＨＩＲＯ，」であるが、このデータに対応する圧縮符号は、ｃ（ＫＡＴＡＯＫＡ，）ｃ（［－，］△）ｃ（ＭＡＳＡＨＩＲＯ，）となる。
　ｃｓｖ形式のデータを扱う場合には、図７のＳ３０４の判定において、区切り記号がカンマであるか否かが判定される。さらに、図９のＳ４０３の判定において、Ｓ４０１で読みだした文字コードがカンマであるか否かが判定される。また、図１０のＳ４１０の処理では、末尾の区切り記号をカンマに置換した文字情報が生成される。
　一方、伸張処理においては、制御記号がカンマ以外の区切り記号の箇所に存在するように圧縮データが生成されているので、図１４の処理手順で処理可能である。
　また、上述の実施形態において、直前のスペース記号の削除を示す制御記号［－△］や直前のカンマの削除を示す制御記号［－，］と説明したが、単に読出し位置を文字コード分（１ｂｙｔｅ）戻すことを示す制御記号が用いられてもよい。その場合、記号列圧縮辞書Ｄ１２と同様の記号列に対応する圧縮辞書が、複数種類の区切り記号に対して設けられてもよい。例えば、単語およびスペース記号の組み合わせに対応する記号列圧縮辞書と、カ単語およびカンマの組み合わせに対応する記号列圧縮辞書との双方が用いられる。あ
　また、上述の実施形態において、単語などの記号列と、その直前に存在するスペース記号などの区切り記号の組み合わせを圧縮辞書に登録することとしてもよい。その場合には、例えば、後続するスペース記号を削除する旨の制御記号が用いられる。
　上述の変形例のみでなく、本発明の本旨を逸脱しない範囲の設計変更は適宜行われうる。
　１　　　　コンピュータ
　１ａ　　　コンピュータ
　１ｂ　　　コンピュータ
　２　　　　基地局
　３　　　　ネットワーク
　４　　　　ストレージエリアネットワーク
　５　　　　ストレージ装置
　６　　　　クライアント装置
　１１　　　圧縮部
　１２　　　伸張部
　１３　　　生成部
　１４　　　生成部
　１５　　　記憶部
 

Claims (17)

  1. 　データを構成する要素のうちの１つである第１の要素と、前記データにおいて前記要素間の区切りを示す第１の区切り記号との組み合わせに対応する１つの圧縮符号を、前記第１の要素と対応付けて記憶する記憶部と、
    　前記データから読み出された前記第１の要素と対応付けて記憶された前記圧縮符号を、前記記憶部から取得する取得部と、
    　取得した前記圧縮符号を、前記データの圧縮データを格納する格納領域に書き込む書込部と、
    　を含むことを特徴とする圧縮装置。
  2. 　前記記憶部は、さらに、前記第１の区切り記号を取り消す指示を示す制御記号と、前記データにおいて前記要素間の区切りを示す区切り記号であって前記第１の区切り記号と種類が異なる第２の区切り記号との組み合わせに対応する制御符号を、前記第２の区切り記号と対応付けて記憶し、
    　前記取得部は、前記データから前記第１の要素に後続する前記第２の区切り記号を読み出した場合に、前記圧縮符号に続いて、さらに前記制御符号を前記記憶部から取得し、
    　前記書込部は、さらに、取得した前記制御符号を、前記格納領域の前記圧縮符号に後続する位置に書き込む、
    　ことを特徴とする請求項１に記載の圧縮装置。
  3. 　前記制御符号に対応する組み合わせに、前記制御記号および前記第２の区切り符号に加えて前記第１の区切り符号が含まれる
    　ことを特徴とする請求項２に記載の圧縮装置。
  4. 　前記データは、テキストファイルであり、
    　前記要素は、単語単位のデータである、
    　ことを特徴とする請求項１～３のいずれか１項に記載の圧縮装置。
  5. 　前記データは、テーブル構造に対応するテキストファイルであり、
    　前記要素は、前記テーブル構造における１つのフィールドを構成する、
    　ことを特徴とする請求項１～３のいずれか１項に記載の圧縮装置。
  6. 　コンピュータに、
    　データを構成する要素のうちの１つである第１の要素と、前記データにおいて前記要素間の区切りを示す第１の区切り記号との組み合わせに対応する１つの圧縮符号を、前記第１の要素と対応付けて記憶する記憶装置から、前記データから読み出された前記第１の要素と対応付けて記憶された前記圧縮符号を取得し、
    　取得した前記圧縮符号を、前記データの圧縮データを格納する格納領域に書き込む、
    　ことを特徴とする圧縮方法。
  7. 　コンピュータに、
    　データを構成する要素のうちの１つである第１の要素と、前記データにおいて前記要素間の区切りを示す第１の区切り記号との組み合わせに対応する１つの圧縮符号を、前記第１の要素と対応付けて記憶する記憶装置から、前記データから読み出された前記第１の要素と対応付けて記憶された前記圧縮符号を取得し、
    　取得した前記圧縮符号を、前記データの圧縮データを格納する格納領域に書き込む、
    　処理を特徴とする圧縮プログラム。
  8. 　データを構成する要素のうちの１つである第１の要素と、前記データにおいて前記要素間の区切りを示す第１の区切り記号との組み合わせを、１つの圧縮符号と対応付けて記憶する記憶部と、
    　前記データを圧縮して得られる圧縮データから読み出された前記圧縮符号に対応する前記組み合わせを、前記記憶部から取得する取得部と、
    　取得した前記組み合わせに含まれる前記第１の要素及び前記第１の区切り記号の双方を、前記圧縮データを伸張して得られる伸張データの格納領域に書き込む書込部と、
    　を含むことを特徴とする伸張装置。
  9. 　前記記憶部は、さらに、前記区切り記号を取り消す指示を示す制御記号と、前記データにおいて前記要素間の区切りを示す区切り記号であって前記第１の区切り記号と種類が異なる第２の区切り記号との組み合わせを、前記圧縮符号と異なる他の圧縮符号と対応付けて記憶し、
    　前記取得部は、前記圧縮データから前記圧縮符号に後続する前記他の圧縮符号を読み出した場合に、前記第１の要素および前記第１の区切り記号に続いて、さらに前記制御記号および前記第２の区切り記号を前記記憶部から取得し、
    　前記書込部は、さらに、前記制御記号および前記第２の区切り記号を取得すると、取得した前記第２の区切り記号を、前記格納領域内の前記第１の区切り記号の格納位置に書き込む、
    　ことを特徴とする請求項８に記載の伸張装置。
  10. 　前記他の圧縮符号に対応づけられる組み合わせに、前記制御記号および前記第２の区切り記号に加えて、前記第１の区切り符号が含まれる、
    　ことを特徴とする請求項９に記載の伸張装置。
  11. 　前記データは、テキストファイルであり、
    　前記要素は、単語単位のデータである、
    　ことを特徴とする請求項８～１０のいずれか１項に記載の伸張装置。
  12. 　前記データは、テーブル構造に対応するテキストファイルであり、
    　前記要素は、前記テーブル構造における１つのフィールドを構成する、
    　ことを特徴とする請求項８～１０のいずれか１項に記載の伸張装置。
  13. 　コンピュータに、
    　データを構成する要素のうちの１つである第１の要素と、前記データにおいて前記要素間の区切りを示す第１の区切り記号との組み合わせを、１つの圧縮符号と対応付けて記憶する記憶装置から、前記データを圧縮して得られる圧縮データから読み出された前記圧縮符号に対応する前記組み合わせを取得し、
    　取得した前記組み合わせに含まれる前記第１の要素及び前記第１の区切り記号の双方を、前記圧縮データを伸張して得られる伸張データの格納領域に書き込む、
    　ことを実行させることを特徴とする伸張方法。
  14. 　コンピュータに、
    　データを構成する要素のうちの１つである第１の要素と、前記データにおいて前記要素間の区切りを示す第１の区切り記号との組み合わせを、１つの圧縮符号と対応付けて記憶する記憶装置から、前記データを圧縮して得られる圧縮データから読み出された前記圧縮符号に対応する前記組み合わせを取得し、
    　取得した前記組み合わせに含まれる前記第１の要素及び前記第１の区切り記号の双方を、前記圧縮データを伸張して得られる伸張データの格納領域に書き込む、
    　処理を実行させることを特徴とする伸張プログラム。
  15. 　記憶装置と、
    　　データを構成する要素のうちの１つである第１の要素と前記データにおいて前記要素間の区切りを示す区切り記号の組み合わせと、１つの圧縮符号とが対応付けられた変換辞書を記憶する記憶部と、
    　　前記記憶装置から、データを圧縮して得られる圧縮データを受ける受信部と、
    　　前記圧縮データから読み出された前記圧縮符号に対応する前記組み合わせを、前記変換辞書から取得する第１の取得部と、
    　　取得した前記組み合わせに含まれる前記第１の要素及び前記区切り記号の双方を、前記圧縮データを伸張して得られる伸張データの第１の格納領域に書き込む第１の書込部と、
    　　前記第１の格納領域に書き込まれた前記伸長データに対して情報処理を行なう処理部と、
    　　前記情報処理が行なわれた前記伸長データから読み出された前記第１の要素に対応付けて記憶された前記圧縮符号を、前記変換辞書から取得する第２の取得部と、
    　　取得した前記圧縮符号を、前記データの圧縮データを格納する第２の格納領域に書き込む第１の書込部と、
    　　前記第２の格納領域に書き込まれた圧縮データを、前記記憶部に送信する送信部と、を含む情報処理装置と、
    　を含むことを特徴とする情報処理システム。
  16. 　データにおいて要素間の区切りを示す区切り記号と、前記区切り記号によって区切られる１つのデータ要素との組み合わせに対応する１つの圧縮符号を前記データ要素に対応づけた圧縮処理用情報を、前記データ要素の種類ごとに含む構造を有する圧縮辞書データであって、　コンピュータによる圧縮処理において、前記１つのデータ要素に基づいて前記１つの圧縮符号が参照される前記圧縮辞書データ、
    　を記憶したコンピュータ読み取り可能な記憶媒体。
  17. 　データにおいて要素間の区切りを示す区切り記号と、前記区切り記号によって区切られる１つのデータ要素との組み合わせを、前記組み合わせに対応する１つの圧縮符号と対応づけた伸長処理用情報を、前記データ要素の種類ごとに含む構造を有する伸長辞書データであって、
    　コンピュータによる伸張処理において、前記１つの圧縮符号に基づいて前記組み合わせが参照される前記伸張辞書データ、
    　を記憶したコンピュータ読み取り可能な記憶媒体。
PCT/JP2013/001976 2013-03-22 2013-03-22 圧縮装置、圧縮方法、伸張装置、伸張方法および情報処理システム WO2014147671A1 (ja)

Priority Applications (7)

Application Number Priority Date Filing Date Title
PCT/JP2013/001976 WO2014147671A1 (ja) 2013-03-22 2013-03-22 圧縮装置、圧縮方法、伸張装置、伸張方法および情報処理システム
EP13879073.8A EP2978135A4 (en) 2013-03-22 2013-03-22 COMPRESSION DEVICE, COMPRESSION METHOD, DECOMPRESSION DEVICE, DECOMPRESSION PROCESS AND INFORMATION PROCESSING SYSTEM
CN201380074817.7A CN105191144B (zh) 2013-03-22 2013-03-22 压缩装置、压缩方法、解压装置、解压方法以及信息处理系统
KR1020157025611A KR101750646B1 (ko) 2013-03-22 2013-03-22 압축 장치, 압축 방법, 신장 장치, 신장 방법 및 정보 처리 시스템
AU2013382910A AU2013382910B2 (en) 2013-03-22 2013-03-22 Compression device, compression method, decompression device, decompression method, and information processing system
JP2015506367A JP6527462B2 (ja) 2013-03-22 2013-03-22 圧縮装置、圧縮方法、記録媒体および伸張装置
US14/857,553 US9509333B2 (en) 2013-03-22 2015-09-17 Compression device, compression method, decompression device, decompression method, information processing system, and recording medium

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/JP2013/001976 WO2014147671A1 (ja) 2013-03-22 2013-03-22 圧縮装置、圧縮方法、伸張装置、伸張方法および情報処理システム

Related Child Applications (1)

Application Number Title Priority Date Filing Date
US14/857,553 Continuation US9509333B2 (en) 2013-03-22 2015-09-17 Compression device, compression method, decompression device, decompression method, information processing system, and recording medium

Publications (1)

Publication Number Publication Date
WO2014147671A1 true WO2014147671A1 (ja) 2014-09-25

Family

ID=51579413

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2013/001976 WO2014147671A1 (ja) 2013-03-22 2013-03-22 圧縮装置、圧縮方法、伸張装置、伸張方法および情報処理システム

Country Status (7)

Country Link
US (1) US9509333B2 (ja)
EP (1) EP2978135A4 (ja)
JP (1) JP6527462B2 (ja)
KR (1) KR101750646B1 (ja)
CN (1) CN105191144B (ja)
AU (1) AU2013382910B2 (ja)
WO (1) WO2014147671A1 (ja)

Families Citing this family (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9779312B2 (en) * 2015-01-30 2017-10-03 Honda Motor Co., Ltd. Environment recognition system
TWI625715B (zh) * 2016-05-31 2018-06-01 瑞鼎科技股份有限公司 顯示驅動裝置及其運作方法
US10432217B2 (en) * 2016-06-28 2019-10-01 International Business Machines Corporation Page filtering via compression dictionary filtering
CN109582653B (zh) * 2018-11-14 2020-12-08 网易（杭州）网络有限公司 文件的压缩、解压缩方法及设备
US10476518B1 (en) * 2018-12-06 2019-11-12 Nyquist Semiconductor Limited Hardware friendly data compression
US12118041B2 (en) * 2019-10-13 2024-10-15 Thoughtspot, Inc. Query execution on compressed in-memory data
WO2021108788A1 (en) * 2019-11-30 2021-06-03 Bytedance Inc. Palette coding mode
CN113138968A (zh) * 2020-01-20 2021-07-20 普天信息技术有限公司 日志压缩方法及日志解压缩方法
CN114492322A (zh) * 2020-10-23 2022-05-13 晶晨半导体(上海)股份有限公司 文本压缩方法、模块、芯片、电子设备和存储介质
US20230004533A1 (en) * 2021-07-01 2023-01-05 Microsoft Technology Licensing, Llc Hybrid intermediate stream format
CN115587076B (zh) * 2022-12-12 2023-05-16 北京象帝先计算技术有限公司 数据解压系统、图形处理系统、组件、设备及解压方法

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH04167821A (ja) * 1990-10-31 1992-06-15 Fujitsu Ltd データ符号化及び復号化方法
JPH05324427A (ja) * 1992-05-27 1993-12-07 Hitachi Ltd 文書情報圧縮装置
JPH09212395A (ja) * 1996-01-30 1997-08-15 Sharp Corp テキスト圧縮用辞書作成装置およびテキスト圧縮装置
JPH11177438A (ja) * 1997-12-12 1999-07-02 Toyota Central Res & Dev Lab Inc 情報変換装置
JP2010093414A (ja) 2008-10-06 2010-04-22 Fujitsu Ltd 情報処理プログラム、情報処理装置、および情報処理方法

Family Cites Families (16)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1985001814A1 (en) * 1983-10-19 1985-04-25 Text Sciences Corporation Method and apparatus for data compression
US5590317A (en) 1992-05-27 1996-12-31 Hitachi, Ltd. Document information compression and retrieval system and document information registration and retrieval method
US5325091A (en) * 1992-08-13 1994-06-28 Xerox Corporation Text-compression technique using frequency-ordered array of word-number mappers
US5710919A (en) * 1995-09-29 1998-01-20 Electronic Data Systems Corporation Record compression
US5999949A (en) * 1997-03-14 1999-12-07 Crandall; Gary E. Text file compression system utilizing word terminators
JP3337633B2 (ja) 1997-12-03 2002-10-21 富士通株式会社 データ圧縮方法及びデータ復元方法並びにデータ圧縮プログラム又はデータ復元プログラムを記録したコンピュータ読み取り可能な記録媒体
JP3511901B2 (ja) 1998-07-01 2004-03-29 株式会社日立製作所 情報処理装置および情報処理システム
JP4774145B2 (ja) * 2000-11-24 2011-09-14 富士通株式会社 構造化文書圧縮装置および構造化文書復元装置並びに構造化文書処理システム
JP2004518327A (ja) * 2001-01-11 2004-06-17 コーニンクレッカ　フィリップス　エレクトロニクス　エヌ　ヴィ 逆進的にストリングを参照する為の識別子を用いたデータ圧縮方法
US20030123841A1 (en) * 2001-12-27 2003-07-03 Sylvie Jeannin Commercial detection in audio-visual content based on scene change distances on separator boundaries
US7624021B2 (en) * 2004-07-02 2009-11-24 Apple Inc. Universal container for audio data
US8554745B2 (en) * 2009-04-27 2013-10-08 Netapp, Inc. Nearstore compression of data in a storage system
CN101807926B (zh) * 2010-01-21 2013-01-23 上海电力学院 低功耗soc测试数据压缩编码方法
CN101944362B (zh) * 2010-09-14 2012-05-30 北京大学 一种基于整形小波变换的音频无损压缩编码、解码方法
CN102480335B (zh) * 2010-11-30 2015-08-05 金蝶软件（中国）有限公司 一种业务数据的发送方法及系统
US8560508B2 (en) * 2011-07-22 2013-10-15 International Business Machines Corporation Real-time compression of tabular data

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH04167821A (ja) * 1990-10-31 1992-06-15 Fujitsu Ltd データ符号化及び復号化方法
JPH05324427A (ja) * 1992-05-27 1993-12-07 Hitachi Ltd 文書情報圧縮装置
JPH09212395A (ja) * 1996-01-30 1997-08-15 Sharp Corp テキスト圧縮用辞書作成装置およびテキスト圧縮装置
JPH11177438A (ja) * 1997-12-12 1999-07-02 Toyota Central Res & Dev Lab Inc 情報変換装置
JP2010093414A (ja) 2008-10-06 2010-04-22 Fujitsu Ltd 情報処理プログラム、情報処理装置、および情報処理方法

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See also references of EP2978135A4 *

Also Published As

Publication number Publication date
CN105191144A (zh) 2015-12-23
EP2978135A1 (en) 2016-01-27
KR101750646B1 (ko) 2017-06-23
CN105191144B (zh) 2019-01-01
JPWO2014147671A1 (ja) 2017-02-16
US9509333B2 (en) 2016-11-29
EP2978135A4 (en) 2016-06-01
KR20150119402A (ko) 2015-10-23
AU2013382910B2 (en) 2017-01-05
US20160006454A1 (en) 2016-01-07
JP6527462B2 (ja) 2019-06-05
AU2013382910A1 (en) 2015-10-08

Similar Documents

Publication Publication Date Title
WO2014147671A1 (ja) 圧縮装置、圧縮方法、伸張装置、伸張方法および情報処理システム
AU2016200550B2 (en) Encoding program, decompression program, compression method, decompression method, compression device and decompression device
CN107506153B (zh) 一种数据压缩方法、数据解压方法及相关系统
WO2014147672A1 (ja) 圧縮装置、圧縮方法、辞書生成装置、辞書生成方法、伸長装置、伸長方法、伸長プログラムおよび情報処理システム
US10671306B2 (en) Chunk-based data deduplication
US20170302292A1 (en) Computer-readable recording medium, encoding device, and encoding method
US10521414B2 (en) Computer-readable recording medium, encoding method, encoding device, retrieval method, and retrieval device
CN108475508B (zh) 音频数据和保存在块处理存储系统中的数据的简化
JP6032292B2 (ja) 圧縮プログラム、圧縮装置、伸張プログラムおよび伸張装置
US9479195B2 (en) Non-transitory computer-readable recording medium, compression method, decompression method, compression device, and decompression device
US9424293B2 (en) Row, table, and index compression
US9219497B2 (en) Compression device, compression method, and recording medium
US8463759B2 (en) Method and system for compressing data
US9496895B2 (en) Compression method and decompression method
JP2010287167A (ja) アーカイブストレージ装置、ストレージシステム、データ格納方法、およびデータ格納プログラム
US20240070126A1 (en) Storage control apparatus and method
US20160210304A1 (en) Computer-readable recording medium, information processing apparatus, and conversion process method
CN109271463A (zh) 一种恢复MySQL数据库的innodb压缩数据的方法

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 201380074817.7

Country of ref document: CN

121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 13879073

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 20157025611

Country of ref document: KR

Kind code of ref document: A

WWE Wipo information: entry into national phase

Ref document number: 2013879073

Country of ref document: EP

ENP Entry into the national phase

Ref document number: 2015506367

Country of ref document: JP

Kind code of ref document: A

NENP Non-entry into the national phase

Ref country code: DE

ENP Entry into the national phase

Ref document number: 2013382910

Country of ref document: AU

Date of ref document: 20130322

Kind code of ref document: A