[go: up one dir, main page]

WO2004062110A1 - データ圧縮方法、プログラム及び装置 - Google Patents

データ圧縮方法、プログラム及び装置 Download PDF

Info

Publication number
WO2004062110A1
WO2004062110A1 PCT/JP2002/013600 JP0213600W WO2004062110A1 WO 2004062110 A1 WO2004062110 A1 WO 2004062110A1 JP 0213600 W JP0213600 W JP 0213600W WO 2004062110 A1 WO2004062110 A1 WO 2004062110A1
Authority
WO
WIPO (PCT)
Prior art keywords
candidate
character string
value
encoding
address
Prior art date
Legal status (The legal status 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 status listed.)
Ceased
Application number
PCT/JP2002/013600
Other languages
English (en)
French (fr)
Inventor
Noriko Itani
Takahiro Nomiyama
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fujitsu Ltd
Original Assignee
Fujitsu Ltd
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 Fujitsu Ltd filed Critical Fujitsu Ltd
Priority to PCT/JP2002/013600 priority Critical patent/WO2004062110A1/ja
Priority to JP2004564417A priority patent/JP3889762B2/ja
Priority to EP02792004.0A priority patent/EP1578020B1/en
Publication of WO2004062110A1 publication Critical patent/WO2004062110A1/ja
Anticipated expiration legal-status Critical
Priority to US11/166,146 priority patent/US7536399B2/en
Ceased legal-status Critical Current

Links

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
    • H03M7/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method
    • H03M7/3086—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method employing a sliding window, e.g. LZ77
    • 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
    • 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
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
    • Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10S707/00—Data processing: database and file management or data structures
    • Y10S707/99941—Database schema or data structure
    • Y10S707/99942—Manipulating data structure, e.g. compression, compaction, compilation

Definitions

  • the present invention relates to a data compression method, a program and a device for generating compressed data from a compressed data sequence, and more particularly to a data compression method and a program for compressing the data sequence using a dictionary generated from the compressed data sequence. And a device.
  • the present invention can be applied not only to the compression of character codes but also to the compression of various data.
  • the data sequence is divided into word units, and Is called a character, and a data string of an arbitrary number of keys is called a character string.
  • LZ77 coding is the mainstream in actual use, because a sufficient compression ratio can be obtained with simple processing.
  • LZ77 encoding as shown in Fig. 1, a fixed-size slide buffer 100 is provided, a character string that matches the input character string in the buffer 1000 is searched for the longest, and its position and length are searched. Is used to encode the input character string. Since the buffer 100 slides as the encoding progresses, this encoding method is also called a slide dictionary method. In FIG. 1, when the input string “abcdaaa Q...” On the right of the buffer 200 is encoded, the longest matching string in the buffer 200 is “ab cd”.
  • the slide buffer that is actually used is long, and it takes an enormous amount of time to search the character strings in the buffer in order to find the longest matching character string.
  • the appearance position of the character string prefix (about 2 to 4 characters) is registered in the table as needed and stored in the table Is matched only with the string at the position indicated.
  • Tables used for such a search include a lookup table (Look Up Tab 1 e, LUT) and a hash table (Hash Table).
  • FIG. 2 shows a character string search using the LUT.
  • the LUT 202 stores the appearance position (address or pointer) of the character string in the buffer 200 using the prefix of the character string in the buffer 200 as an address. Then, at the time of retrieval, the area of the LUT 202 is accessed using the prefix of the input character string as an address, and the position of the corresponding character string is obtained.
  • a plurality of character strings having the same prefix exist in the buffer 100
  • a plurality of occurrence positions are held in the form of a linked list 204 as shown in FIG. Therefore, the position of all corresponding character strings in the buffer 200 can be obtained by accessing the LUT 202 only once.
  • a prefix of two characters is used, and the area of the LUT 202 corresponding to the prefix “ab” of the input character string holds two appearance positions using the linked list 104. I have.
  • the LUT can perform a very high-speed search because the prefix to be searched corresponds to the area of the table one-to-one and the necessary information can be obtained only by one table lookup.
  • the number of areas required for the table increases as a power of the number of characters that can appear, so the required area becomes enormous. For example, Assuming that the number of characters that can appear is 8 bits, 256, then a prefix of n characters requires 256 n powers.
  • the prefix to be searched is lengthened, only a part of the prepared area that is actually used (registered) is limited, and the table becomes sparse. Therefore, if the search prefix is lengthened, 'the efficiency of memory usage will decrease.
  • Figure 4 shows a string search using a hash table.
  • the hash code generation unit 206 generates a hash code 208 from the prefix “abc” of the input character string, and accesses the hash table 210 using the hash code as an address.
  • the hash buble 210 stores the position in the buffer 200 corresponding to the hash code 208, and by comparing the character string "abcde" at that position with the input character string, Are checked for a prefix match. If they match, it is determined that a character string that matches the input character string exists in the buffer 200.
  • a hash table as in the case of the LUT, multiple occurrence positions are held in the form of a linked list for multiple character strings with the same prefix in the buffer. In each case, the linked list is used to find the longest matching string.
  • Japanese Patent Application No. 2000-98834 Japanese Patent Application No. 2000-98834
  • an input buffer is provided and a search table for the input buffer is created at one time, instead of sequentially registering it in the search table while proceeding with encoding as in the past.
  • the search uses a ranking list in which character strings starting from each address in the input buffer are rearranged according to the contents of the character strings.
  • it is possible to implement with the least amount of memory by generating a list of the most recent matches from the ranking list, and detecting a portion where the same number continues from the list of the most recent matches to find a match.
  • FIG. 5 is a specific example of the input buffer, the rank list, and the closest match position list used in the method proposed by the present inventors. This method is processed in the following procedure.
  • the ranking list 214 is created by sorting three character strings starting from each address of the input buffer 212 in numerical order.
  • the latest matching position list 216 stores the relative position of the most recently appearing address. For example, since the character string “com” from address 15 most recently appears at address 1 and relative position 14, the relative position 14 is stored in the address 15 of the closest match position list 216.
  • the address itself is stored in the closest match position list. In this case, address 1 is stored in address 15 of the closest match position list 216.
  • a matching character string is detected and encoded from a portion where the same numeral in the recent matching position list 216 continues.
  • the number 14 is continuous with addresses 15 to 20
  • the number 9 is continuous with addresses 24 to 29, and the number 23 is continuous with addresses 30 to 31.
  • the data compression method shown in Fig. 5 detects a matching character string by detecting a place where the same number continues in the recent matching position list.
  • the longest match cannot be detected in a case where a short character string that forms a long character string repeatedly appears during a long character string repetition. That is, in the input buffer 2 12 shown in FIG. 6A, between the long character string “abcdef” from addresses 1 and 16, the short character string “from addresses 7, 10 and 13” abc '' and ⁇ cde '' are repeated, but the closest match list 2 16 in Figure 6 (B) generated from the data in the input buffer 2 There is a problem that the repetition of the column "abcdef" cannot be detected. Disclosure of the invention
  • the present invention uses a recent matching position list to narrow down candidates for matching character strings that have appeared in the past, and detects and encodes matching character strings by comparing character strings in the input buffer that have become candidates.
  • Basic a recent matching position list to narrow down candidates for matching character strings that have appeared in the past, and detects and encodes matching character strings by comparing character strings in the input buffer that have become candidates.
  • the present invention provides a data compression method for generating compressed data from a compressed data stream. This data compression method
  • a list generation step for generating and holding a closest match position list storing a relative position where each character string of a predetermined length most recently appears starting from each address in the input buffer by the closest match position list generation unit;
  • a candidate obtaining step of obtaining a repetition candidate at a position where the character string at the encoding position has appeared in the past by using the recent matching position list by the candidate obtaining unit;
  • a match detection unit that compares a character string starting from the position of the obtained repetition candidate with a character string starting from the encoding position, and detects a matched character string from the position of the repetition candidate;
  • the candidate obtaining step uses the encoding position as an address and sets the stored value obtained from the most recent matching position list as the first candidate of the repeated position of the character string
  • the match detecting step uses the character string starting from the position of the first candidate as the starting point. Is compared with the character string starting from the encoding position, and the matched character string is obtained and encoded.
  • the process of detecting and encoding repetition of the matching character string by narrowing down candidates in the recent matching position list can be realized at high speed.
  • By detecting matches by comparing strings in the input buffer longer strings can be matched.
  • the first form of the candidate obtaining step in the data compression method of the present invention further comprises: a first step in which the first candidate is used as an evaluation value;
  • the stored value obtained from the closest matching position list is compared with the evaluation value using each position following the encoded position as an address, and if the obtained stored value is a value earlier than the evaluated value, the distance from the encoded position With one or more successors following the first candidate in ascending order of
  • the match detection step is characterized in that a character string starting from the first candidate and the subsequent candidate is compared with a character string starting from the encoding position, and the character string having the longest matching length is obtained and encoded. .
  • the second form of the candidate obtaining step in the data compression method of the present invention further comprises:
  • the stored value obtained from the closest matching position list is compared with the evaluation value using each position following the encoded position as an address. If the obtained stored value is a value earlier than the evaluated value, the distance from the encoded position is determined. With one or more successors following the first candidate in ascending order of
  • the match detecting step is characterized in that a character string starting from the first candidate and the subsequent candidate is compared with a character string starting from the encoding position, and a character string having the longest matching length is detected and encoded. .
  • the candidate obtaining step when obtaining the subsequent candidate, uses the value of the obtained subsequent candidate as an address and the value obtained from the most recent matching position list as an evaluation value for obtaining the next succeeding candidate. Is also good.
  • the third form of the candidate acquiring step in the data compression method of the present invention further comprises, as one or more succeeding candidates following the first candidate, a stored value acquired from the closest matching position list using the preceding candidate as an address. Is a subsequent candidate, and in the match detection step, the character string starting from the first candidate and the subsequent candidate is compared with the character string starting from the encoding position, and the character string having the longest matching length is obtained and encoded. It is characterized by the following.
  • the fourth form of the candidate obtaining step in the data compression method of the present invention further comprises a storage value obtained from the most recent matching position list with the first candidate as an evaluation value and each position following the encoding position as an address. If the obtained stored value is a value that is earlier than the evaluation value, one or more succeeding candidates following the first candidate in ascending order of the distance from the encoding position are determined.
  • a first step in which a character string starting from the succeeding candidate is compared with a character string starting from the encoding position, and a character string having the longest match length with the character string at the encoding position is set as a revised first candidate;
  • the stored value obtained from the closest matching position list as the preceding candidate is used as the second revised candidate.
  • the match detection step compares the character string starting from the first candidate for revision and the subsequent candidate for revision with the character string starting from the encoding position, and detects the character string having the longest matching length to perform the encoding. Characterize.
  • the code generation step in the data compression method of the present invention is characterized in that a character string from an encoding position is encoded with a relative position and a matching length of a detected matching character string.
  • the present invention provides a program for generating compressed data from a compressed data sequence. This program is
  • a list generation step for generating and holding a nearest match position list storing a relative position where each character string of a predetermined length starting from each address in the input buffer most recently appears;
  • the present invention provides a data compression device for generating a compressed data from a compressed data sequence. This device
  • An input buffer for inputting and holding a compressed data sequence in the input buffer
  • a closest match position list generation unit that generates and holds a closest match position list storing a relative position where each character string of a predetermined length starting from each address in the input buffer most recently appears;
  • a match detection unit that compares a character string starting from the position of the obtained repetition candidate with a character string starting from the encoding position, and detects a matched character string from the position of the repetition candidate.
  • FIG 1 is an illustration of the conventional LZ77 data compression process
  • FIG. 2 is an explanatory diagram of processing using LUT in LZ77;
  • FIG. 3 is an explanatory diagram of a process using a linked list in LZ77;
  • FIG. 4 is an explanatory diagram of processing using a hash table in LZ77;
  • FIG. 5 is an explanatory diagram of a matched character string search using a recently matched position list proposed by the present inventors
  • Figure 6 is an explanatory diagram of an example where the same number is not consecutive in the closest match list even if the character string is repeated in the input buffer;
  • FIG. 7 is a block diagram of the functional configuration of the present invention.
  • FIG. 8 is an explanatory diagram of a hardware environment of a computer to which the embodiment of the present invention is applied;
  • FIG. 9 is an explanatory diagram of a data compression process according to the first embodiment of the present invention.
  • FIG. 10 is a flowchart of a data compression process according to the first embodiment of FIG. 9;
  • FIG. 11 is a flowchart of a data compression process following FIG. 10;
  • FIG. 12 is an explanatory diagram of a data compression process according to the second embodiment of the present invention.
  • FIG. 13 is a flowchart of a data compression process according to the second embodiment of FIG. 12;
  • FIG. 14 is a flowchart of a data compression process following FIG. 13;
  • FIG. 15 is an explanatory diagram of a data compression process according to the third embodiment of the present invention.
  • FIG. 16 is a flowchart of the data compression process according to the third embodiment of FIG. 15;
  • FIG. 17 is a flowchart of the data compression process following FIG. 16;
  • FIG. 18 is an explanatory diagram of the overnight compression processing according to the fourth embodiment of the present invention
  • FIG. 19 is a flowchart of a data compression process according to the fourth embodiment of FIG. 18
  • FIG. 20 is a flowchart of a data compression process following FIG. 19;
  • FIG. 7 is a block diagram of a functional configuration of the data compression device according to the present invention.
  • the data compression apparatus of the present invention includes an input file 10, an input unit 11, an input buffer 12, a closest match position list generation unit 14, a repeated candidate acquisition unit 16, and a match detection unit 1.
  • the input file 10 stores compressed data to be compressed.
  • the compressed data of the input cuff file is cut out by the input unit 1 I for the buffer size of the input buffer 12, input to the input buffer 12, and held.
  • the closest match position list generation unit 14 converts each character string of a predetermined length starting from each address in the input buffer in the compressed data string held in the input buffer 12, for example, three character strings, Generate and maintain a list 24 of the most recent matching positions storing the relative positions that appeared most recently.
  • the match detection unit 18 obtains a repetition candidate at a position where the character string at the encoding position appeared in the past using the recent match position list 24. That is, the match detection unit 18 uses the recent match position list 24 to narrow down candidates for matched character strings that have appeared in the past.
  • the code generator 20 compares the character string starting from the position of the repetition candidate acquired by the match detector 18 with the character string starting from the encoding position, and detects the character string having the longest matching length.
  • the code generation unit 20 encodes the matched character string detected by the match detection unit 18. In this encoding, encoding is performed using the (relative position, matching length) of the detected matching character string.
  • the code generated by the code generation unit 20 is stored in the output file 22 as compressed data, and file transfer and file storage are performed as needed.
  • the present invention employs the following first and second methods. There are four ways to be clarified in the second, third and fourth embodiments.
  • the data compression apparatus of the present invention in FIG. 7 is realized by, for example, computer hardware resources as shown in FIG. In the computer shown in Fig.
  • the RAM 101 is connected to the bus 101 of the CPU 100, and the hard disk controller (soft) 10 4.
  • Floppy disk driver (software) 110, CD-ROM driver (software) 114, mouse controller 118, keyboard controller 122, display controller 126, and communication board 130 are connected.
  • the hard disk controller 104 is connected to the hard disk drive 106 and loads an application program for executing the data compression processing of the present invention. When the computer starts up, the hard disk controller 104 calls a required program from the hard disk drive 106. , Expanded on the RAMI 02 and executed by the CPU 100.
  • a floppy disk drive 110 is connected to the floppy disk driver 110, which can read from and write to a floppy disk (R).
  • a CD drive (hardware) 116 is connected to the CD-ROM driver 114 so that data and programs stored on the CD can be read.
  • the 18 transmits the input operation of the mouse 120 to the CPU 100.
  • the keypad controller 122 transmits an input operation of the keyboard 124 to the CPU 100.
  • the display controller 126 performs display on the display unit 128.
  • the communication board 130 uses a communication line 132 to perform communication with another combination or a server via a network such as the Internet.
  • FIG. 9 is an explanatory diagram of the first embodiment of the data compression method according to the present invention.
  • the repetition candidate acquiring unit 16 in FIG. 7 performs the following processing.
  • the position acquired from the most recent matching position list 24 is set as the first candidate for the repeated position of the character string.
  • Each position following the encoding position that is, each position with +1, +2, +3,... + N at the encoding position is used as an address, and the stored value obtained from the most recent matching position list 24 and evaluated.
  • the values are compared, and if the acquired stored value is a value earlier than the evaluation value, specifically, if the acquired stored value is larger than the evaluation value, the first candidate is selected in ascending order of the distance from the encoding position.
  • One or more subsequent candidates that is, a second candidate, a third candidate, and so on.
  • the match detection unit 18 in FIG. The character string starting from the dress and the character string starting from the encoding position are compared, and the character string having the longest matching length is obtained and encoded by the code generation unit 20.
  • the processing of the first embodiment is performed by comparing the character string stored in the input buffer 12 in FIG. 9A with the closest matching position in FIG. 9B generated from the character string in the input buffer 12 in FIG.
  • the specific description with reference to Listing 24 is as follows.
  • each character string of a predetermined length for example, three characters, appears most recently starting from each address in the input buffer 12.
  • Relative position A list 24 of the closest matches within ⁇ is generated. The generation of the closest match position list 24 is performed, for example, for the character string “abc” from address 1 of the input buffer 12, since there is no character string that appeared most recently. “1” holds the value “0” indicating that no matching character string exists.
  • the addresses 2 to 6 of the input buffer 12 0 is stored in the addresses 2 to 6 of the recently matched position list 24, since there is no character string that appears most recently.
  • 0 is stored if there is no recently appearing character string in each address of the recently matched position list 24, and if there is a character string, a value indicating the relative position is stored. If the closest match position list 24 has been generated in this way, the repeated candidate acquisition unit 16 in FIG. 7 narrows down the candidates for the repeated character string using the generated closest match position list 24.
  • the address 19 of the input buffer 12 is the encoding position 26 in FIG.
  • the closest match position list 24 is referred to by the address 19 of the encoding position 26 of the input buffer 12 and the stored value of the address 19 is set as the first candidate of the repeated position of the character string.
  • the position of the first candidate is 19 from the address 19 and its stored value 6, and the position of the address 13 is indicated by an arrow 36 as indicated by the arrow 19, which is the address 1 in the input buffer 12. This means that the repeated character string from 3 is the first candidate 28.
  • referring to the closest matching position list 24 using +1, + 2, and + N as the addresses for the encoding position 26, 1 is set as the stored value of each address. Get 0, 5, and 18.
  • the stored value obtained from the address at each position following the encoding position 26 is compared with the evaluation value 6 given by the storage value at the first candidate position, and the value larger than the evaluation value is compared with the subsequent candidate.
  • the order of the following candidates is the first candidate, the second candidate,...
  • the stored value of each position following the encoding position 26 is three, that is, the stored value 10 of the address 20, the stored value 5 of the address 21, and the stored value 18 of the address 22. Among them, the stored value 10 and the stored value 18 are larger than the evaluation value 6.
  • the stored value 10 of the address 20 having the smaller distance from the encoding position 26 is set as the second candidate of the repetition position.
  • the character string from address 1 of input buffer 12 corresponding to position 1 is the third candidate 32.
  • the character string of the first candidate 28 from address 13 of each candidate and the second character from address 9 (2) Match the character string from the third position (3) and the character string from the third candidate (3) of the address (1), and compare and match with the character string from the encoding position (3). Is obtained and encoded.
  • the first candidate is used as the evaluation value when obtaining the third candidate, but the longer one of the first candidate and the second candidate that matches may be used. However, in FIG. 9, since the match length of the second candidate is 0, the first candidate is inevitably used as an evaluation value for obtaining the third candidate.
  • FIG. 10 and FIG. 11 are flowcharts of the data compression processing according to the first embodiment of the present invention, and have the following processing procedure.
  • Step S 3 Check whether the obtained value of the relative position R i is a value other than 0 indicating a character match, and if so, proceed to step S 4; otherwise, proceed to step S 13.
  • Step S 4 The value of the relative position R i is set as the first candidate and the evaluation value.
  • Step S 6 It is checked whether or not the acquired value of the relative position R is a value other than 0 indicating a character match. If so, the process proceeds to step S 7; otherwise, the process proceeds to step S 9.
  • Step S7 Check whether the value of the obtained relative position R is larger than the evaluation value.
  • step S8 if it is bigger, otherwise go to step S9.
  • Step S8 Set the relative position R as the next candidate and return to step S5.
  • Step S9 This is the case where the value of the obtained relative position is 0, which indicates that the character is not a character match.
  • the character string starting from each candidate position is compared with the character string starting from the encoding target position, and the matching is performed. Find the length s.
  • Step S11 If the encoding position address t becomes larger than the buffer size, the process proceeds to step S12, otherwise returns to step S2.
  • Step S12 The end of the data to be compressed is checked. If it is completed, the process ends. Otherwise, the process returns to step S1.
  • FIG. 12 is an explanatory diagram of the data compression processing according to the second embodiment of the present invention.
  • the repetition candidate acquiring unit 16 in FIG. 7 performs the following processing. (1)
  • the stored value 6 obtained from the closest matching position list 24 using the encoding position 26 as an address is set as the first candidate of the repeated position of the character string.
  • FIG. 13 and FIG. 14 are flowcharts of the data compression processing according to the second embodiment of the present invention, and the processing procedure is as follows.
  • Step S2 The relative position R1 is acquired from the address t of the list of the most recent matching position.
  • Step S3 Check whether the obtained value of the relative position R1 is a value other than 0 indicating character matching, and if so, proceed to step S4; otherwise, proceed to step S13.
  • Step S4 The value of the relative position R1 is set as the first candidate, and the relative value of the address of the first candidate is set.
  • the position 2 is set as the evaluation value (the position relative to the encoding position t is R 1 + R 2).
  • Step S 6 It is checked whether or not the acquired value of the relative position R is a value other than 0 indicating a character match. If so, the process proceeds to step S 7; otherwise, the process proceeds to step S 9.
  • Step S7 Check whether the acquired value of the relative position R is larger than the evaluation value. If it is larger, proceed to Step S8. Otherwise, proceed to Step S9.
  • Step S 8 Set the relative position R to the next candidate.
  • Step S 9 This is the case where the acquired relative position value is 0, which indicates that there is no character match.
  • the matching between the character string starting from the candidate position and the character string starting from the encoding target position is compared, and the matching length s is detected.
  • Step S11 When the encoding position address t becomes larger than the buffer size, the process proceeds to Step S12, otherwise, the process returns to Step S2.
  • Step S12 The end of the data to be compressed is checked. If it is completed, the process ends. Otherwise, the process returns to step S1.
  • the first candidate is also used as the evaluation value when obtaining the third and subsequent candidates, but the longer the match between the first candidate and the second candidate, the better. May be used. However, there is no third candidate in this case.
  • FIG. 15 is an explanatory diagram of the data compression processing according to the third embodiment of the present invention.
  • the repetition candidate acquisition unit 16 in FIG. 7 performs the following processing.
  • the match detection unit 18 in FIG. The character string starting from each address 13, 7, 1 of the second candidate 46 and the third candidate 48 matches the character string starting from the address 19 of the encoding position 26. The character string is obtained and encoded by the code generation unit 20.
  • FIGS. 16 and 17 are flowcharts of the data compression processing according to the third embodiment of the present invention, and have the following processing procedure.
  • Step S2 Obtain the relative position Ri from the address t of the closest matching position list c
  • Step S3 Check whether the obtained value of the relative position R is a value other than 0 indicating character matching, and if so, Go to step S4, otherwise go to step S12.
  • Step S4 Set the value of the relative position R1 as the first candidate.
  • Step S5 Obtain relative position R2 from encoding position address (t-R1) Yes ⁇
  • Step S6 Check whether the obtained value of the relative position R is a value other than 0 indicating a character match, and if so, proceed to step S7; otherwise, proceed to step S8.
  • Step S8 This is the case where the value of the obtained relative position is 0, which indicates that there is no character match.
  • the character string starting from each candidate position is compared with the character string starting with the encoding target position as the starting point. Find the match length s.
  • Step S10 If the encoding position address t becomes larger than the buffer size, the process proceeds to step S11, otherwise returns to step S2.
  • Step S11 The end of the data to be compressed is checked. If it is completed, the process ends. If not, the process returns to step S1.
  • FIG. 18 is an explanatory diagram of the data compression processing according to the fourth embodiment of the present invention.
  • the fourth embodiment after the longest matching character string is obtained according to the first embodiment of FIG. 9, the obtained character string candidate is re-designated as a first candidate, a so-called revised first candidate, as shown in FIG.
  • a feature of the fifth embodiment is that the processing of the third embodiment is applied. That is, although the first embodiment of FIG. 9 is a process that can find the most recent matching portion, since it is not possible to further extend the past, the candidates can be extended to the past matching portion.
  • the processing by the repetition candidate acquisition unit 16 of FIG. 7 is the first processing of the first embodiment of FIG. 9 and the processing of the third embodiment of FIG. 15. It is divided into a certain second process.
  • 4 to 17 are not candidates because they are smaller than the evaluation value of 4.
  • FIG. 19 and FIG. 20 are flowcharts of the data compression processing according to the fourth embodiment of the present invention, and have the following processing procedure.
  • Step S2 The relative position R1 is acquired from the address t of the list of the most recent matching position.
  • Step S3 Check whether the obtained value of the relative position R1 is a value other than 0 indicating character matching, and if so, proceed to step S4; otherwise, proceed to step S18.
  • Step S4 The value of the relative position R1 is set as a first candidate and an evaluation value.
  • Step S6 Is the value of the obtained relative position R1 a non-zero value indicating character matching?
  • Step S7 Check whether the value of the obtained relative position R1 is larger than the evaluation value.
  • step S8 if it is bigger, otherwise go to step S9.
  • Step S8 Set the relative position R1 as the next candidate and return to step S5.
  • Step S9 This is the case where the value of the obtained relative position is 0, which indicates that the character is not a character match.
  • the character string starting from each candidate position is compared with the character string starting from the encoding target position, and the values match. Find the length s.
  • Step S 0 The longest match candidate is selected and set as the first candidate for revision.
  • Step S 1 Assuming that the relative position of the first candidate for revision is R 1, the relative position R 2 of the address (t—R 1) of the closest matching position list is obtained.
  • Step S2 Check whether the acquired value of the relative position R is a value other than 0 indicating character matching, and if so, proceed to step S13, otherwise proceed to step S14.
  • Step S3 The relative position R2 is set as the next revision candidate R1, and the process returns to step S11.
  • Step S4 This is a case where the value of the relative position acquired in step S12 indicates that the character does not match, and the character string starting from each candidate position matches the character string starting from the encoding target position. And the match length s is detected.
  • Step S16 If the encoding position address t becomes larger than the buffer size, proceed to step S17, otherwise return to step S2.
  • Step S17 The end of the data to be compressed is checked. If the end is found, the process ends. If not, the process returns to step S1.
  • each character string having a predetermined length starting from each address in the input buffer is used as a candidate for a matching character string in the closest matching position list storing the most recent relative value.
  • the longest character string can be detected and coded by detecting the match of the character string with the coding position. Even if the character string of the compressed data is unknown, the longest matching character string can be detected and encoded at high speed.
  • the data compression function can be implemented with a small amount of memory.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)

Abstract

最近一致位置リストを過去に出現した一致文字列の候補の絞り込みに用い、候補となった入力バッファ中の文字列を比較することで一致文字列を検出して符号化する。入力部は、入力バッファに被圧縮データ列を入力して保持する。最近一致位置リスト生成部は、入力バッファ中の各アドレスを起点とする所定長の各文字列が最も最近出現した相対位置を格納した最近一致位置リストを生成して保持する。繰返し候補取得部は、最近一致位置リストを用いて符号化位置の文字列が過去に出現した位置の繰返し候補を取得する。一致検出部は、取得した繰返し候補の位置を起点にする文字列と符号化位置を起点にする文字列を比較し、候補位置からの最長一致した文字列を検出する。符号生成部は、検出した一致文字列の一致長と相対位置により符号化する。

Description

明 細 書 データ圧縮方法、 プログラム及び装置 技術分野
本発明は、 被圧縮データ列から圧縮データを生成するデータ圧縮方法、 プログ ラム及び装置に関し、 特に、 被圧縮データ列から生成される辞書を用いて、 その データ列を圧縮するデータ圧縮方法、 プログラム及び装置に関する。 背景技術
近年、 文字コード、 画像データ等の様々な種類のデータがコンピュータで扱わ れるようになるのに伴い、 取り扱われるデ一夕量も増大している。 そのような大 量のデータを扱う場合、 デ一夕中の冗長な部分を省いて圧縮することにより、 必 要な記憶容量を減らしたり、 遠隔地へ高速に伝送したりすることができる。 ここで本発明は、 文字コードの圧縮に限らず、.様々なデータの圧縮に適用でき るが、 以下の説明では情報理論に基づき、 デ一夕列をワード単位に分割し、 1ヮ 一ドのデ一夕を文字と呼び、 任意のヮ一ド数のデータ列を文字列と呼ぶことにす る。
従来のデ一夕圧縮技術には、 デー夕系列の類似性を利用した辞書型符号化と、 データ列の出現頻度を利用した確率統計型符号化とがある。 このうち、 前者の辞 書型符号化の代表的な方法として、 L Z 7 7符号化と L Z 7 8符号化が知られて いる （植松友彦箸、 「文書データ圧縮アルゴリズム入門」 、 C Q出版、 p p . 1 3 1 - 2 0 8 , 1 9 9 5年） 。
L Z 7 7符号化と L Z 7 8符号化では、 L Z 7 7符号化の方が、 簡単な処理で 充分な圧縮率が得られることから、 実際の使用では主流となっている。 L Z 7 7 符号化では、 図 1に示すように、 一定サイズのスライドバッファ 1 0 0を設け、 このバッファ 1 0 0内で入力文字列と最長一致する文字列を検索し、 その位置と 長さを用いて入力文字列を符号化する。 符号化が進むにつれてバッファ 1 0 0を スライドさせていくことから、 この符号化方法は、 スライド辞書法とも呼ばれる 図 1では、 バッファ 200の右隣の入力文字列 " a b c d a a a Q. . . " が符 号化されるとき、 バッファ 200内で一致する文字列のうち最長のものは "ab c d" である。 そこで、 この最長一致文字列の先頭位置と入力文字列の先頭位置 の相対アドレス "5 (バイト） " を一致位置とし、 最長一致文字列の長さ "4 (バイト） " を一致長として、 （一致位置， 一致長） = (5, 4) のような符号 を生成する。 これにより、 入力文字列の先頭の "a b e d" が （5， 4) に置き 換えられる。 同様にして、 次の文字列 "a a a" は、 符号 （1 3， 3) に置き換 えられる。 し力 ^し、 実際に用いられるスライドバッファはもつと長く、 最長一致 する文字列を発見するためにバッファ内の文字列を順に検索していくと、 膨大な 時間を要する。 このため、 実際には、 バッファ内のすべての文字列と照合するの ではなく、 文字列の接頭部 （2〜4文字程度） の出現位置を随時テ一ブルに登録 し、 テ一ブルに保持されている位置の文字列のみと照合している。 このような検 索に使用されるテーブルとしては、 ルックアップテーブル （L o ok Up T a b 1 e, LUT) とハッシュテーブル（Ha s h Ta b l e)とがある。
図 2は、 LUTを用いた文字列検索を示している。 LUT 202は、 バッファ 200内の文字列の接頭部をァドレスとして、 その文字列のバッファ 200内に おける出現位置 （アドレスまたはポインタ） を格納している。 そして、 検索時に は、 入力文字列の接頭部をアドレスとして、 LUT202の領域にアクセスし、 対応する文字列の位置を取得する。 同じ接頭部の文字列がバッファ 1 00内に複 数存在する場合は、 図 3のように、 リンクドリスト 204の形式で複数の出現位 置が保持される。 したがって、 LUT 202に 1回アクセスするだけで、 バッフ ァ 200内のすべての対応する文字列の位置を取得することができる。 ここでは、 2文字分の接頭部が用いられており、 入力文字列の接頭部 "a b" に対応する L UT 202の領域は、 リンクドリスト 104を利用して 2つの出現位置を保持し ている。
このように、 LUTは、 検索する接頭部をテーブルの領域に 1対 1に対応させ、 1回のテーブル引きのみで必要な情報を取得できるため、 非常に高速な検索を行 うことができる。 しかし、 長い文字列を検索する場合、 テーブルに必要な領域の 数は出現可能な文字の数の巾乗で増えるため、 必要な領域が膨大になる。 例えば、 出現可能な文字の数を 8ビット、 2 5 6個とすると、 n文字の接頭部に対して 2 5 6の n乗個の領域が必要となる。 ところが、 検索する接頭部を長くすると、 用 意された領域のうち実際に使用される （登録される） 部分は一部分のみに止まり、 テ一ブル内はまばらな状態になる。 したがって、 検索する接頭部を長くすると、 'メモリの使用効率が悪化する。 そこで、 ハッシュテーブルでは、 検索文字列をァ' ドレスとして用いる際に、 一定の数値以下に縮退させて、 複数の文字列が 1つの 領域を共有するようにしている。 このため、 テーブル引きの後で、 得られた文字 列が実際に検索している文字列かどうかをチェックする必要があるが、 L U Tに 比べて、 同等のテーブル領域でより長い文字列を検索することができる。
図 4は、 ハッシュテーブルを用いた文字列検索を示している。 ハッシュコード 生成部 2 0 6は、 入力文字列の接頭部 " a b c " からハッシュコード 2 0 8を生 成し、 それをアドレスとしてハッシュテーブル 2 1 0にアクセスする。 ハッシュ ブーブル 2 1 0には、 ハッシュコード 2 0 8に対応するバッファ 2 0 0内の位置 が格納されており、 その位置にある文字列 " a b c d e " と入力文字列を照合す ることで、 両者の接頭部が一致するかどうかがチェックされる。 そして、 それら がー致すれば、 入力文字列と一致する文字列がバッファ 2 0 0内に存在すると判 断される。 ハッシュテーブルの場合も、 L UTの場合と同様に、 バッファ内の同 じ接頭部を持つ複数の文字列に対しては、 リンクドリストの形式で複数の出現位 置が保持される。 いずれの場合も、 リンクドリストは、 最長一致文字列を検索す るために用いられる。
しかしながら、 このような従来のデータ圧縮技術には、 次のような問題がある。 まず L U Tを用いて長い文字列を検索する場合、 膨大な領域を持つテーブルを用 意しても、 その一部分のみしか使用されないので、 テ一ブル内はまばらな状態に なる。 ハッシュテーブルでは、 L U Tと比べるとテーブルサイズが小さくなるが、 入力データが少なければ、 同じようにテーブル内がまばらな状態になる。 したが つて、 メモリが必ずしも有効に利用されないという問題がある。 また、 最長一致 文字列を検索する際、 リンクドリストに保持された複数の出現位置を一つ一つ迪 らなければならず、 同じ接頭部を持つ文字列が多くなると、 検索処理に時間がか かるという問題もある。 この問題を解決するため本願発明者等にあっては、 入力データ量に比例した少 ないメモリ量で検索できるデータ圧縮方法を提案している （日本国特許出願：特 願 2000 - 98834) 。 この方法は、 従来のように符号化を進めながら順次、 検索テーブルに登録して行くのではなく、 入力バッファを設け、 入力バッファ用 の検索テーブルを一度で作り上げる方法である。 検索には、 入力バッファ中の各 アドレスを起点とした文字列を、 文字列の内容に従って並びかえた順位リストを 利用する。 中でも、 順位リストから最近一致位置リストを生成し、 最近一致位置 リストから同じ数字が続く箇所を検出して一致を見つける方法が最も少ないメモ リ量で実装することが出来る。
図 5は、 本願発明者が提案している方法で使用される入力バッファ、 順位リス ト及び最近一致位置リストの具体例である。 この方法は次の手順で処理される。
(データ入力とリスト生成）
図 5 (A) 入力バッファ 212にバッファサイズのデ一夕を入力し、 符号化対 象位置アドレス tを t = 1に初期化し、 図 5 (B) の順位リスト 2 14と図 5 (C) の最近一致位置リスト 216を作成する。 ここで、 順位リスト 214は、 入力バッファ 212の各アドレスを始点とする 3文字列を数値順にソートして作 成する。 また最近一致位置リスト 216は、 最も最近に出現したアドレスの相対 位置を格納する。 例えばアドレス 15からの文字列 「c om」 が最も最近に出現 したのはアドレス 1、 相対位置 14であることから、 最近一致位置リスト 216 のァドレス 1 5に相対位置 14を格納する。 なお、 特願 2000 - 98834号 ではアドレスそのものを最近一致位置リストに格納して.おり、 この場合、 最近一 致位置リスト 216のアドレス 15にはァドレス 1を格納する。
(一致文字列の検出と符号化）
最近一致位置リスト 216の中の同じ数字が連続する部分をから一致文字列を 検出して符号化する。 図 5 (D) の最近一致位置リスト 216について見ると、 アドレス 15〜 20に数字 14が連続し、 アドレス 24〜 29に数字 9が連続し、 アドレス 30〜31に数字 23が連続している。 まずアドレス 15〜20に連続 する数字 14は、 アドレス 15— 14=1からの文字列と一致し、 一致長は 6 + 2 = 8で一致位置が 14となり、 （一致長， 位置） = (8, 14) が符号として 生成される。 またアドレス 2 4〜2 9 , 3 0〜3 2に連続する数字 9， 2 3は、 アドレス 2 4— 2 3 = 1からの文字列と一致し、 一致長は 9 + 2 = 1 1で一致位 置が 2 3となり、 （一致長， 位置） = ( 1 1 , 2 3 ) が符号として生成される。 しかしながら、 図 5に示したデータ圧縮方法は、 最近一致位置リストから同じ 数字が連続する箇所を検出することによって一致文字列を検出しているが、 図 6 (A) の入力バッファ 1 1 2のように、 長い文字列の繰返しの間に、 長い文字列 を形成している短い文字列の繰返し 出現するようなデ一夕では、 最長一致を検 出することができない。 即ち、 図 6 (A) の入力バッファ 2 1 2にあっては、 ァ ドレス 1， 1 6からの長い文字列 「a b c d e f」 の間に、 アドレス 7 , 1 0 , 1 3からの短い文字列 「a b c」 、 「c d e」 が繰り返されているが、 入力バッ ファ 2 1 2のデータから生成された図 6 ( B ) の最近一致位置リスト 2 1 6には 同じ数字が連続した個所がなく、 文字列 「a b c d e f」 の繰返しが検出できな いという問題がある。 発明の開示
本発明は、 最近一致位置リストに同じ数字の連続がなくとも一致文字列の繰返 しを検出して符号化できるデータ圧縮方法、 プログラム及び装置を提供すること を目的とする。
本発明は、 最近一致位置リストを過去に出現した一致文字列の候補の絞り込み に用い、 候補となった入力バッファ中の文字列を比較することで一致文字列を検 出して符号化することを基本とする。
(方法）
本発明は、 被圧縮デ一夕列から圧縮データを生成するデータ圧縮方法を提供す る。 このデータ圧縮方法は、
入力部により、 入力バッファに被圧縮データ列を入力して保持する入カステツ プと、
最近一致位置リスト生成部により、 入力バッファ中の各ァドレスを起点とする 所定長の各文字列が最も最近出現した相対位置を格納した最近一致位置リストを 生成して保持するリス卜生成ステツプと、 候補取得部により、 最近一致位置リストを用いて符号化位置の文字列が過去に 出現した位置の繰返し候補を取得する候補取得ステツプと、
一致検出部により、 取得した繰返し候補の位置を起点にする文字列と符号化位 置を起点にする文字列を比較し、 繰返し候補の位置からの一致した文字列を検出 する一致検出ステップと、
符号生成部により、 検出した一致文字列を符号化する符号生成ステツプと、 を備えたことを特徴とする。
ここで候補取得ステツプは、 符号化位置をァドレスとして最近一致位置リスト から取得した格納値を文字列の繰返し位置の第 1候補とし、 一致検出ステップは、 第 1候補の位置を起点にする文字列と符号化位置を起点にする文字列を比較し、 一致した文字列を取得して符号化させる。
このような本発明のデータ圧縮方法によれば、 最近一致位置リストに同じ数字 の連続がなくとも、 最近一致位置リストで候補を絞り込むことで、 一致文字列の 繰返しを検出して符号化する処理を高速で実現できる。 また入力バッファ中の文 字列の比較で一致検出することで、 より長い文字列の一致検出ができる。 更に、 検索テ一ブルとして使用するのは、 入力バッファと最近一致位置リストのみであ るため、 少ないメモリ量で実装できる。
本発明のデータ圧縮方法における候補取得ステップの第 1形態は、 更に、 第 1候補を評価値とする第 1ステツプと、
符号化位置に後続する各位置をァドレスとして最近一致位置リストから取得し た格納値と評価値を比較し、 取得した格納値が評価値より過去の値である場合に、 符号化位置からの距離が小さい順に第 1候補に続く 1又は複数の後続候補とする を備え、
一致検出ステツプは、 第 1候補及び後続候補を起点にする文字列と符号化位置 を起点にする文字列を比較し、 一致長の最も長い文字列を取得して符号化させる ことを特徴とする。
ここで、 候補取得ステップは、 後続候補を取得した際に、 取得した後続候補の 値を次に後続する候補を取得するための評価値としても良い。 また本発明のデータ圧縮方法における候補取得ステップの第 2形態は、 更に、 第 1候補をァドレスとして最近一致位置リストから取得した値を評価値とする 第 1ステップと、
符号化位置に後続する各位置をァドレスとして最近一致位置リストから取得し た格納値と評価値を比較し、 取得した格納値が評価値より過去の値である場合に， 符号化位置からの距離が小さい順に第 1候補に続く 1又は複数の後続候補とする を備え、
一致検出ステップは、 第 1候補及び後続候補を起点にする文字列と符号化位置 を起点にする文字列を比較し、 一致長の最も長い文字列を検出して符号化させる ことを特徴とする。
この場合にも、 候補取得ステップは、 後続候補を取得した際に、 取得した後続 候補の値をァドレスとして最近一致位置リストから取得した値を次に後続する候 補を取得するための評価値としても良い。
また本発明のデ一夕圧縮方法における候補取得ステップの第 3形態は、 更に、 第 1候補に続く 1又は複数の後続候補として、 先行する候補をアドレスとして最 近一致位置リストから取得した格納値を後続候補とし、 一致検出ステップは、 第 1候補及び後続候補を起点にする文字列と符号化位置を起点にする文字列を比較 し、 一致長の最も長い文字列を取得して符号化させることを特徴とする。
更に本発明のデ一夕圧縮方法における候補取得ステップの第 4形態は、 更に、 第 1候補を評価値とし、 符号化位置に後続する各位置をァドレスとして最近一 致位置リストから取得した格納値と評価値を比較し、 取得した格納値が評価値よ り過去の値である場合に、 符号化位置からの距離が小さい順に第 1候補に続く 1 又は複数の後続候補とし、 第 1候補及び後続候補を起点にする文字列と符号化位 置を起点にする文字列を比較し、 符号化位置の文字列との一致長の最も長い文字 列を改定第 1候補とする第 1ステップと、
改定第 1候補に続く 1又は複数の改定後続候補として、 先行する候補をァドレ スとして前記最近一致位置リストから取得した格納値を改定後続候補とする第 2 を備え、
一致検出ステップは、 改定第 1候補及び改定後続候補を起点にする文字列と符 号化位置を起点にする文字列を比較し、 一致長の最も長い文字列を検出して号化 させることを特徴する。
本発明のデータ圧縮方法における符号生成ステップは、 符号化位置からの文字 列を、 検出された一致文字列の相対位置と一致長で符号化することを特徴とする。
(プログラム）
本発明は、 被圧縮デ一夕列から圧縮デー夕を生成するプログラムを提供する。 このプログラムは、 コンピュータに、
入力バッファに被圧縮データ列を入力して保持する入力ステップと、
入力バッファ中の各アドレスを起点とする所定長の各文字列が最も最近出現し た相対位置を格納した最近一致位置リストを生成して保持するリスト生成ステツ プと、
最近一致位置リストを用いて符号化位置の文字列が過去に出現した位置の繰返 し候補を取得する候補取得ステツプと、
取得した繰返し候補の位置を起点にする文字列と符号化位置を起点にする文字 列を比較し、 繰返し候補の位置からの一致した文字列を取得する一致検出ステツ プと、
検出した一致文字列を符号化する符号生成ステツプと、 '
を実行させることを特徴とする。 なお、 このプログラムの詳細はデータ圧縮方法 と基本的に同じになる。 本発明は、 被圧縮データ列から圧縮デ一夕を生成するデータ圧縮装置を提供す る。 この装置は、
入力バッファに被圧縮データ列を入力して保持する入力バッファと、
入力バッファ中の各アドレスを起点とする所定長の各文字列が最も最近出現し た相対位置を格納した最近一致位置リストを生成して保持する最近一致位置リス 卜生成部と、
最近一致位置リストを用いて符号化位置の文字列が過去に出現した位置の繰返 し候補を取得する候補取得部と、
取得した繰返し候補の位置を起点にする文字列と符号化位置を起点にする文字 列を比較し、 繰返し候補の位置からの一致した文字列を検出する一致検出部と、 検出した一致文字列を符号化する符号生成部と、
を備えたことを特徴とする。 なお、 このデ一夕圧縮装置の詳細はデータ圧縮方法 と基本的に同じになる。 図面の簡単な説明
図 1は従来の L Z 7 7 よるデータ圧縮処理の説明図；
図 2は L Z 7 7における L U Tを用いた処理の説明図；
図 3は L Z 7 7におけるリンクドリストを用いた処理の説明図；
図 4は L Z 7 7におけるハッシュテーブルを用いた処理の説明図；
図 5は本願発明者等が提案している最近一致位置リストを用いた一致文字列検索 の説明図；
図 6は入カバッファで文字列の繰返しがあつても最近一致位置リストで同じ数字 が連続しない例の説明図；
図 7は本発明の機能構成のブロック図；
図 8は本発明の実施形態が適用されるコンピュータのハードウェア環境の説明 図；
図 9は本発明の第 1実施形態によるデータ圧縮処理の説明図；
図 1 0は図 9の第 1実施形態によるデータ圧縮処理のフローチャート； 図 1 1は図 1 0に続くデータ圧縮処理のフローチャート；
図 1 2は本発明の第 2実施形態によるデータ圧縮処理の説明図；
図 1 3は図 1 2の第 2実施形態によるデータ圧縮処理のフローチャート ； 図 1 4は図 1 3に続くデータ圧縮処理のフローチャート；
図 1 5は本発明の第 3実施形態によるデータ圧縮処理の説明図；
図 1 6は図 1 5の第 3実施形態によるデータ圧縮処理のフロ一チャート ； 図 1 7は図 1 6に続くデータ圧縮処理のフローチャート；
図 1 8は本発明の第 4実施形態によるデ一夕圧縮処理の説明図； 図 1 9は図 1 8の第 4実施形態によるデータ圧縮処理のフローチャート； 図 2 0は図 1 9に続くデータ圧縮処理のフローチャート； 発明を実施するための最良の形態
図 7は、 本発明によるデータ圧縮装置の機能構成のブロック図である。 図 7に おいて、 本発明のデータ圧縮装置は、 入力ファイル 1 0、 入力部 1 1、 入力バッ ファ 1 2、 最近一致位置リスト生成部 1 4、 繰返し候補取得部 1 6、 一致検出部 1 8、 符号生成部 2 0及び出力ファイル 2 2で構成される。 入力ファイル 1 0に はデー夕圧縮を行う被圧縮デー夕が格納されている。 この入カフアイルの被圧縮 データは、 入力部 1 Iにより入力バッファ 1 2のバッファサイズ分切り出され、 入力バッファ 1 2に入力されて保持される。 最近一致位置リスト生成部 1 4は、 入力バッファ 1 2に保持された被圧縮データ列における入力バッファ中の各アド レスを起点とする所定長の各文字列、 例えば 3文字の各文字列が、 最も最近に出 現した相対位置を格納した最近一致位置リスト 2 4を生成して保持する。 一致検 出部 1 8は、 最近一致位置リスト 2 4を用いて符号化位置の文字列が過去に出現 した位置の繰返し候補を取得する。 即ち一致検出部 1 8は、 最近一致位置リスト 2 4を過去に出現した一致文字列の候補の絞り込みに使用している。 符号生成部 2 0は、 一致検出部 1 8により取得した繰返し候補の位置を起点とする文字列と 符号化位置を起点とする文字列を比較し、 一致長の最も長い文字列を検出する。 更に符号生成部 2 0は、 一致検出部 1 8で檢出した一致文字列を符号化する。 こ の符号化は、 検出した一致文字列の （相対位置， 一致長） で符号化を行う。 符号 生成部 2 0で生成された符号は出力ファイル 2 2に圧縮データとして格納され、 必要に応じてフアイル転送やフアイル格納が行われることになる。 このような本 発明のデータ圧縮装置において、 繰返し候補取得部 1 6による最近一致位置リス ト 2 4を用いた繰返し文字列の候補の絞り込み方法として、 本発明にあっては、 後の第 1， 第 2 , 第 3及び第 4実施形態で明らかにする 4つの方法がある。 図 7における本発明のデ一夕圧縮装置は， 例えば図 8のようなコンピュータの ハードウェア資源により実現される。 図 8のコンピュータにおいて、 C P U 1 0 0のバス 1 0 1には R AM I 0 2、 ハードディスドコント口一ラ （ソフト） 1 0 4、 フロッピィディスクドライバ （ソフト） 1 10、 CD— ROMドライバ （ソ フト） 1 14、 マウスコントローラ 1 18、 キ一ボードコント口一ラ 122、 デ イスプレイコントローラ 126、 通信用ボード 130が接続される。 ハードディ スクコントローラ 104はハードディスクドライブ 106を接続し、 本発明のデ —タ圧縮処理を実行するアプリケーションプログラムを口一ディングしており、 コンピュータの起動時にハ一ドディスクドライブ 106から必要なプログラムを 呼び出して、 RAMI 02上に展開し、 CPU 100により実行する。 フロッピ ィディスクドライバ 1 10にはフロッピィディスクドライブ ひ、一ド） 1 12が 接続され、 フロッピィディスク （R) に対する読み書きができる。 CD— ROM ドライバ 1 14に対しては、 CDドライブ （ハード） 1 16が接続され、 CDに 記憶されたデータやプログラムを読み込むことができる。 マウスコントローラ 1
18はマウス 120の入力操作を CPU 100に伝える。 キーポ一ドコント口一 ラ 122はキーボード 124の入力操作を CPU 100に伝える。 ディスプレイ コントローラ 126は表示部 128に対して表示を行う。 通信用ボード 130は 通信回線 1 32を使用し、 インターネット等のネットワークを介して他のコンビ ユー夕やサーバとの間で通信を行う。
図 9は、 本発明によるデータ圧縮方法の第 1実施形態の説明図である。 この第 1実施形態において、 図 7の繰返し候補取得部 16は、 次の処理を行う。
(1) 符号化位置をアドレスとして、 最近一致位置リスト 24から取得した位 置を文字列の繰返し位置の第 1候補とする。
(2) 第 1候補を評価値とする。
(3) 符号化位置に後続する各位置、 即ち符号化位置に + 1， +2, + 3, … + Nとした各位置をァドレスとして、 最近一致位置リスト 24から取得し た格納値と評価値を比較し、 取得した格納値が評価値より過去の値である 場合、 具体的には取得した格納値が評価値より大きい場合に、 符号化位置 からの距離が小さい順に、 第 1候補に続く 1または複数の後続候補、 即ち 第 2候補、 第 3候補…とする。
このような繰返し候補取得部 16により第 1候補及び第 2候補以降の後続する 候補が取得されたならば、 図 7の一致検出部 18は、 第 1候補及び後続候補のァ ドレスを起点とする文字列と符号化位置を起点とする文字列を比較し、 一致長の 最も長い文字列を取得して符号生成部 2 0により符号化させる。 この第 1実施形 態の処理を、 図 9 (A) の入力バッファ 1 2に格納された文字列と、 この入力パ ッファ 1 2の文字列から生成された図 9 (B ) の最近一致位置リスト 2 4を参照 して具体的に説明すると次のようになる。
図 9 (A) の入力バッファ 1 2に保持された被圧縮データとしての文字列に対 し、 入力バッファ 1 2中の各アドレスを起点として所定長例えば 3文字の各文字 列が最も最近に出現した相対位置を！^内した最近一致位置リスト 2 4が生成され る。 この最近一致位置リスト 2 4の生成は、 例えば入力バッファ 1 2のアドレス 1からの文字列 「a b c」 については、 最も最近に出現した文字列がないことか ら、 最近一致位置リスト 2 4のアドレス 1には一致文字列が存在しないことを示 す値 「0」 を保持する。 入力バッファ 1 2のアドレス 2〜 6についても、 それぞ れ最も最近に出現した文字列がないことから、 最近一致位置リスト 2 4のァドレ ス 2〜6に 0を保持する。 続いて入力バッファ 1 2のアドレス 7からの文字列 「a b c」 については、 最も最近に出現した文字列としてアドレス 1からの文字 列 「a b c」 があることから、 7— 1 = 6となる相対位置を示す値を最近一致位 置リスト 2 4のアドレス 7に保持する。 以下同様にして、 入力バッファ 1 2に基 づき、 最近一致位置リスト 2 4の各ァドレスに最近出現した文字列がない場合は 0を、 文字列がある場合は相対位置を示す値を格納する。 このようにして最近一 致位置リスト 2 4が生成できたならば、 生成した最近一致位置リスト 2 4を用い て、 図 7の繰返し候補取得部 1 6が繰返し文字列の候補の絞り込みを行う。 いま、 図 9において、 入力バッファ 1 2のアドレス 1 9が符号化位置 2 6であったとし て説明すると次のようになる。 まず入力バッファ 1 2の符号化位置 2 6のァドレ ス 1 9により最近一致位置リスト 2 4を参照し、 アドレス 1 9の格納値を文字列 の繰返し位置の第 1候補とする。 この第 1候補の位置は、 アドレス 1 9とその格 納値 6から 1 9一 6 = 1 3となり、 矢印 3 6のようにアドレス 1 3の位置を示し、 これは入力バッファ 1 2におけるアドレス 1 3からの繰返し文字列を第 1候補 2 8とすることを意味する。 続いて、 符号化位置 2 6に対し + 1 , + 2 , + Nを アドレスとして最近一致位置リスト 2 4を参照し、 各アドレスの格納値として 1 0， 5 , 1 8を取得する。 このように符号化位置 2 6に後続する各位置のァドレ' スから取得した格納値について、 第 1候補位置の格納値で与えられる評価値 6と 比較し、 評価値より大きいものを後続する候補とする。 この後続する候補の順位 は、 符号化位置 2 6からの距離の小さい順に第 1候補、 第 2候補、 …とする。 こ の符号化位置 2 6に続く各位置の格納値は、 アドレス 2 0の格納値 1 0、 ァドレ ス 2 1の格納値 5及びァドレス 2 2の格納値 1 8の 3つである。 このうち評価値 6より大きいのは格納値 1 0と格納値 1 8である。 そのうち符号化位置 2 6から の距離が小さい方のアドレス 2 0の格納値 1 0を繰返し位置の第 2候補とする。 この第 2候補の位置は矢印 3 8に示すように 1 9一 1 0 = 9からアドレス 9の位 置であり、 入力バッファ 1 2におけるアドレス 9からの文字列が繰返し文字列の 第 2候補 3 0となる。 更に、 最近一致位置リスト 2 4のアドレス 2 2の格納値 1 8による繰返し位置が第 3候補となり、 この第 3候補の位置は矢印 4 2に示すよ うに 1 9— 1 8 = 1となるァドレス 1の位置であり、 これに対応した入力バッフ ァ 1 2のアドレス 1からの文字列が第 3候補 3 2となる。 このようにして文字列 繰返し位置の第 1候補、 第 2候補及び第 3候補が取得されたならば、 各候補のァ ドレス 1 3からの第 1候補 2 8の文字列、 アドレス 9からの第 2候補 3 0の文字 列、 及びァドレス 1の第 3候補 3 2からの文字列のそれぞれにっき、 符号化位置 2 6からの文字列との一致比較 3 4を行い、 一致長の最も長い文字列を取得して 符号化する。 この場合、 第 3候補 3 2からの文字列が最も長く符号化位置 2 6か らの文字列に一致し、 一致文字列は 「a b c d e f」 となり、 したがって （相対 位置， 一致長） = ' ( 1 8 , 6 ) で符号化を行う。 なお図 9の実施形態にあっては、 第 3候補を求める際の評価値に第 1候補を用いたが、 第 1候補と第 2候補のうち、 より長く一致したほうを用いてもよい。 ただし、 図 9にあっては、 第 2候補の一 致長は 0であることから、 必然的に第 1候補が第 3候補を取得するための評価値 に使用されている。
図 1 0及び図 1 1は、 本発明の第 1実施形態のデ一タ圧縮処理のフローチヤ一 トであり、 次の処理手順となる。
ステップ S 1 ： 入力バッファにバッファサイズのデータを入力し、 符号化対象 位置ァドレス tを t == 1に初期化し、 順位リストと最近一致位置 リストを作成する。
2 最近一致位置リストのァドレス tから相対位置 R iを取得する。 ステップ S 3 取得した相対位置 R iの値が文字一致を示す 0以外の値か否か チェックし、 そうであればステップ S 4に進み、 そうでなければ ステップ S 1 3に進む。
ステップ S 4 相対位置 R iの値を第 1候補および評価値に設定する。
ステップ S 5 符号化位置ァドレス tからアドレス t = t + 1の相対位置相対 位置 Rを取得する。
ステップ S 6 取得した相対位置 Rの値が文字一致を示す 0以外の値か否か チェックし、 そうであればステップ S 7に進み、 そうでなけ ればステップ S 9に進む。
ステップ S 7 ： 取得した相対位置 Rの値が評価値より大きいかどうかチ
エックし、 大きければステップ S 8に進み、 そうでなければステ ップ S 9に進む。
ステップ S 8 ： 相対位置 Rを次の候補に設定してステップ S 5に戻る。
ステップ S 9 ： 取得した相対位置の値が文字一致でないことを示す 0の場合で あり、 各候補位置を起点とする文字列と符号化対象位置を起点と する文字列の一致を比較し、 一致長 sを検出する。
ステップ S 1 0 ： 最長一致の候補文字列の相対位置 Rと一致長 sを符号化した 後に、 t = t + sに設定する。
ステップ S 1 1 ： 符号化位置アドレス tがバッファサイズより大きくなつたら ステップ S 1 2に進み、 そうでなければステップ S 2に戻る。 ステップ S 1 2 ： 圧縮するデータの終了をチェックし、 終了であれば処理を終 わり、 そうでなければステップ S 1に戻る。
ステップ S 1 3 : ステップ S 3で文字一致を示す値でなかった場合であり、 ァ ドレス tの文字をそのまま符号として出力し、 t = t + lとして ステップ S 1 1に進む。
図 1 2は、 本発明の第 2実施形態によるデータ圧縮処理の説明図である。 この 第 2実施形態にあっては、 図 7の繰返し候補取得部 1 6は次の処理を行う。 ( 1 ) 符号化位置 26をアドレスとして最近一致位置リスト 24から取得した 格納値 6を文字列の繰返し位置の第 1候補とする。
(2) 第 1候補 6は、 符号化位置 26からの相対位置なので、 アドレス 19一 6 = 13として、 最近一致位置リスト 24のアドレス 13から取得した値 6を符号化位置 26からの相対位置に換算した値、 即ち 6 + 6 = 12を評 価値とする。
(3) 符号化位置 26に後続する + 1, +2， + Νの各位置をアドレス 19， 20, 21， 22として、 最近一致位置リスト 24から取得した格納値 1 0， 5, 18と評価値 12を比較し、 取得した格納値が評価値より大きい 場合、 符号化位置 26からの距離が小さい順に、 第 1候補に続く 1または 複数の後続候補、 この例ではアドレス 22の格納値 18を第 2候補とする。 このようにして繰返し候補取得部 16により第 1候補及び第 2候補が取得され たならば、 図 7の一致検出部 18が第 1候補のアドレス 19— 6 = 13となる入 力バッファ 12のアドレス 13からの第 1候補 28の文字列、 第 2候補のァドレ ス 19一 18 = 1となる入力バッファ 12のアドレス 1からの第 2候補 44の文 字列を、 符号化位置 26からの文字列と一致比較 34を行い、 最長一致した文字 列、 この場合にはアドレス 1からの第 2候補 44との一致比較による文字 「ab c d e f」 を検出し、 符号生成部 20が （相対位置， 一致長） = (18， 6) で 符号化を行う。
図 13及び図 14は、 本発明の第 2実施形態のデ一夕圧縮処理のフローチヤ一 トであり、 次の処理手順となる。
ステップ S 1 ： 入力バッファにバッファサイズのデ一夕を入力し、 符号化対象 位置ァドレス tを t = 1に初期化し、 順位リストと最近一致位置 リストを作成する。
ステップ S 2 ： 最近一致位置リストのアドレス tから相対位置 R 1を取得する。 ステップ S 3 ： 取得した相対位置 R 1の値が文字一致を示す 0以外の値か否か チェックし、 そうであればステップ S 4に進み、 そうでなければ ステップ S 13に進む。
ステップ S 4 ： 相対位置 R 1の値を第 1候補とし、 第 1候補のアドレスの相対 位置 2を評価値に設定 （符号化位置 tからの相対位置は R 1 + R 2 ) する。
ステップ S 5 符号化位置ァドレス tからアドレス t = t + 1の相対位置相対 位置 Rを取得する。
ステップ S 6 取得した相対位置 Rの値が文字一致を示す 0以外の値か否か チェックし、 そうであればステップ S 7に進み、 そうでなけ ればステップ S 9に進む。
ステップ S 7 取得した相対位置 Rの値が評価値より大きいかどうかチエツク し、 大きければステップ S 8に進み、 そうでなければステ ップ S 9に進む。
ステップ S 8 相対位置 Rを次の候補に ·設¾Η定^ ΐ , フ 、" 。 ς 5に戻る， ステップ S 9 取得した相対位置の値が文字一致でないことを示す 0の場合で あり、 各候補位置を起点とする文字列と符号化対象位置を起点と する文字列の一致を比較し、 一致長 sを検出する。
0 ： 最長一致の候補文字列の相対位置 Rと一致長 sを符号化した 後に、 t = t + sに設定する。
ステップ S 1 1 ： 符号化位置アドレス tがバッファサイズより大きくなつたら ステップ S 1 2に進み、 そうでなければ ° ステップ S 2に戻る。 ステップ S 1 2 ：. 圧縮するデータの終了をチェックし、 終了であれば処理を終 わり、 そうでなければステップ S 1に戻る。
ステップ S 1 3 ： ステップ S 3で文字一致を示す値でなかった場合であり、 ァ ドレス tの文字をそのまま符号として出力し、 t = t + lとして ステップ S 1 1に進む。
なお図 1 2の第 2実施形態にあっては、 第 3候補以降の候補を求める際の評価 値にも第 1候補を用いるが、 第 1候補と第 2候補のうち、 より長く一致したほう を用いてもよい。 ただし、 このケースでは第 3候補は存在していない。
図 1 5は、 本発明の第 3実施形態によるデータ圧縮処理の説明図である。 この 第 3実施形態にあっては、 図 7の繰返し候補取得部 1 6が次の処理を行う。
( 1 ) 入力バッファ 1 2の符号化位置 2 6をアドレス 1 9として、 最近一致位 置リスト 24から取得した格納値 6を文字列の繰返し位置の第 1候補とす る。
(2) 第 1候補に続く後続候補として、 先行する候補をアドレスとして最近一 致位置リスト 24から取得した格納値を後続候補とする。 即ち、 第 1候補 をアドレス 19— 6 = 13として、 最近一致位置リスト 24のアドレス 1
3から取得した格納値 6を第 2候補とする。 また、 第 2候補のアドレス 1 3— 6 = 7として、 最近一致位置リスト 24のアドレス 7から取得した格 納値 6を第 3候補とする。 更に、 第 3候補をアドレス 7— 6 =1とした最 近一致位置リスト 24のアドレス 1から取得した格納値を第 3候補とする。 このようにして繰返し文字列の位置の候補、 即ち第 1候補、 第 2候補、 第 3候 補が取得されたならば、 図 7の一致検出部 18が入力バッファ 12における第 1 候補 28、 第 2候補 46、 第 3候補 48の各アドレス 13, 7, 1を起点とする 文字列と符号化位置 26のアドレス 19を起点とする文字列と一致比較 34を行 レ 、 一致長の最も長い候補の文字列を取得して符号生成部 20により符号化させ る。 この例では、 第 3候補 48からの文字列が符号化位置 26からの文字列に最 も長く一致する文字列 「ab c d e f」 であることから、 第 3候補 48の相対位 置 19一 1=18と一致長 6を求め、 （相対位置， 一致長） = (18, 6) で符 号化を行う。
図 16及び図 17は、 本発明の第 3実施形態によるデータ圧縮処理のフローチ ャ一トであり、 次の処理手順となる。
ステップ S 1 ： 入力バッファにバッファサイズのデータを入力し、 符号化対象 位置ァドレス tを t = 1に初期化し、 順位リストと最近一致位置 リストを作成する。
ステップ S 2 ： 最近一致位置リストのアドレス tから相対位置 R iを取得する c ステップ S 3 ： 取得した相対位置 Rの値が文字一致を示す 0以外の値か否か チェックし、 そうであれぱステップ S 4に進み、 そうでなければ ステップ S 12に進む。
ステップ S 4 ： 相対位置 R 1の値を第 1候補に設定する。
ステップ S 5 ： 符号化位置アドレス （t一 R1) からの相対位置 R2を取得 する <
ステップ S 6 ： 取得した相対位置 Rの値が文字一致を示す 0以外の値か否か チェックし、 そうであればステップ S 7に進み、 そうでなけ ればステップ S 8に進む。
ステップ S 7 : 相対位置 R 2を次の候補 R 1に設定する （符号化位置からの 位置は R 1 + R 2のため、 R 1 = R 1 + R 2 ) 。
ステップ S 8 ： 取得した相対位置の値が文字一致でないことを示す 0の場合で あり、 各候補位置を起点とする文字列と符号化対象位置を起点と ' する文字列の一致を比較し、 一致長 sを検出する。
ステップ S 9 ： 最長一致の候補文字列の相対位置 Rと一致長 sを符号化した後 に、 t = t + sに設定する。
ステップ S 1 0 ： 符号化位置ァドレス tがバッファサイズより大きくなつたら ステップ S 1 1に進み、 そうでなければステップ S 2に戻る。 ステップ S 1 1 ： 圧縮するデータの終了をチェックし、 終了であれば処理を終 わり、 そうでなければステップ S 1に戻る。
ステップ S 1 2 ： ステップ S 3で文字一致を示す値でなかった場合であり、 ァ ドレス tの文字をそのまま符号として出力し、 t = t + 1として ステップ S 1 0に進む。
図 1 8は、 本発明の第 4実施形態によるデータ圧縮処理の説明図である。 この 第 4実施形態にあっては、 図 9の第 1実施形態によって最長一致の文字列を取得 した後、 この取得した文字列の候補を改めて第 1候補いわゆる改定第 1候補とし て、 図 1 5の第 3実施形態の処理を適用するようにしたことを特徴とする。 即ち、 図 9の第 1実施形態は最近の一致部分を見つけることのできる処理であるが、 そ れ以上、 過去に延ばすことができないことから、 これに過去の一致部分に候補を 延ばすことのできる図 1 5の第 3実施形態の処理を組み合わせたものである。 図 1 8の第 4実施形態について、 図 7の繰返し候補取得部 1 6による処理は、 図 9の第 1実施形態の処理である第 1処理と、 図 1 5の第 3実施形態の処理であ る第 2処理とに分かれる。
(第 1処理） (1) 符号化位置 50をアドレス 1 1として、 最近一致位置リスト 24から取 得した格納値 4を文字列繰返し位置の第 1候補とする。
(2) 第 1候補の格納値を評価値 4とする。
(3) 符号化位置 50に後続する + 1， +2, …十 Nの各位置をアドレス 12 〜17として、 最近一致位置リスト 24から取得した格納値 7， 7, 3，
3， 3, 3を評価値 4と比較し、 評価値 4より大きい場合に符号化位置 5 0からの距離の小さい順に、 第 1候補に続く後続候補とする。 この場合、 アドレス 12， 13の格納値が 7となって、 評価値 4より大きいことから、 第 2候補となる。 ここでアドレス 12， 13の格納値は共に 7であること から、 第 2候補のアドレスは 1 1一 7=4となる。 それ以外のアドレス 1
4〜17については、 評価値 4より小さいことから候補外である。
このようにして第 1候補及び第 2候補が取得されたならば、 図 7の一致検出部 18によりアドレス 7の第 1候補 52及びアドレス 4の第 2候補 54を起点とし た文字列と、 符号化位置 50のアドレス 1 1を起点とした文字列の一致比較 60 を行い、 一致長の最も長い文字列、 この場合にはアドレス 4からの第 2候補 54 の文字列 「ab c ab c」 を、 次の第 2処理のための改定第 1候補 56とする。 (第 2処理）
第 2処理は、 改定第 1候補 56のアドレス 4一 3 =1として、 最近一致位置リ スト 24から取得した格納値を改定第 2候補 58とする。 そして図 7の符号生成 部 20により、 改定第 1候補 56のアドレス 4及び改定第 2候補のアドレス 1を 起点とする文字列と、 符号化位置 50のアドレス 1 1を起点とする文字列を比較 する一致比較 60を行い、 最も長く一致する候補の文字列を検出する。 この塲合 には第 2改定候補 58の文字列が、 文字列 「ab c ab c ab c」 となって最も 長く一致し、 改定第 2候補の相対位置 1 1— 1 = 10で一致長が 9であることか ら、 （相対位置， 一致長） = (10， 9) で符号化を行う。
図 19及び図 20は、 本発明の第 4実施形態のデータ圧縮処理のフローチヤ一 トであり、 次の処理手順となる。
ステップ S 1 ： 入力バッファにバッファサイズのデータを入力し、 符号化対象 位置ァドレス tを t = 1に初期化し、 順位リストと最近一致位置 リストを作成する。
ステップ S 2 ： 最近一致位置リストのアドレス tから相対位置 R 1を取得する。 ステップ S 3 ： 取得した相対位置 R 1の値が文字一致を示す 0以外の値か否か チェックし、 そうであればステップ S 4に進み、 そうでなければ ステップ S 1 8に進む。
ステップ S 4 ： 相対位置 R 1の値を第 1候補及び評価値に設定する。
ステップ S 5 ： 符号化位置ァドレス tからアドレス t = t + 1の相対位置相対 位置 Rを取得する。
ステップ S 6 ： 取得した相対位置 R 1の値が文字一致を示す 0以外の値か
否かチェックし、 そうであればステップ S 7に進み、 そうでなけ ればステップ S 9に進む。
ステップ S 7 ： 取得した相対位置 R 1の値が評価値より大きいかどうかチ
エックし、 大きければステップ S 8に進み、 そうでなければステ ップ S 9に進む。
ステップ S 8 ： 相対位置 R 1を次の候補に設定してステップ S 5に戻る。
ステップ S 9 ： 取得した相対位置の値が文字一致でないことを示す 0の場合で あり、 各候補位置を起点とする文字列と符号化対象位置を起点と する文字列の一致を比較し、 一致長 sを検出する。
ステップ S 0 ： 最長一致の候補を選択し、 改定第 1候補とする。
ステップ S 1 ： 改定第 1候補の相対位置を R 1とすると、 最近一致位置リス トのアドレス （t— R 1 ) の相対位置 R 2を取得する。
ステップ S 2 ： 取得した相対位置 Rの値が文字一致を示す 0以外の値か否か チェックし、 そうであればステップ S 1 3に進み、 そうで なければステップ S 1 4に進む。
ステップ S 3 ： 相対位置 R 2を次の改定候補 R 1に設定してステップ S 1 1 に戻る。
ステップ S 4 ： ステップ S 1 2で取得した相対位置の値が文字一致でないこ とを示す場合であり、 各候補位置を起点とする文字列と符号化対 象位置を起点とする文字列の一致を比較し、 一致長 sを検出する。 ステップ S 1 5 ： 最長一致の候補文字列の相対位置 Rと一致長 sを符号化した 後に、 t = t + sに設定する。
ステップ S 1 6 ： 符号化位置ァドレス tがバッフアサイズょり大きくなつたら ステップ S 1 7に進み、 そうでなければステップ S 2に戻る。 ステップ S 1 7 : 圧縮するデータの終了をチェックし、 終了であれば処理を終 わり、 そうでなければステップ S 1に戻る。
ステップ S 1 8 ： ステップ S 3で文字一致を示す値でなかった場合であり、 ァ ドレス tの文字をそのまま符号として出力し、 t = t + lとして ステップ S 1 6に進む。
なお、 本発明は上記の実施形態に限定されず、 その目的と利点を損なうことの ない適宜の変形を含む。 更に本発明は、 上記の実施形態に示した数値による限定 は受けない。 産業上の利用の可能性
以上説明してきたように本発明によれば、 入力バッファ中の各アドレスを起点 とする所定長の各文字列が、 最も最近出現した相対値を格納した最近一致位置リ ストで一致文字列の候補を絞り込み、 絞り込んだ候補について符号化位置との文 字列の一致検出で最も長い文字列を検出して符号化することができ、 最近一致位 置リストに同じ数字が連続せずに一致位置が不明となる被圧縮データの文字列で あっても、 最長一致文字列を検出して高速に符号化することができる。
また、 最長一致文字列の検出による符号化に使用する検索テーブルとして使用 するのは入カバッファと最近一致位置リストのみで済むため、 少ないメモリ量で データ圧縮機能を実装することができる。

Claims

請求の範囲
1 . 被圧縮データ列から圧縮データを生成するデータ圧縮方法に於いて、 入力部により、 入力バッファに被圧縮データ列を入力して保持する入カステツ プと、
最近一致位置リスト生成部により、 前記入力バッファ中の各ァドレスを起点と する所定長の各文字列が最も最近出現した位置を格納した最近一致位置リストを 生成して保持するリスト生成ステップと、
• 繰返し候補取得部により、 前記最近一致位置リストを用いて符号化位置の文字 列が過去に出現した位置の繰返し候補を取得する候補取得ステップと、
一致検出部により、 取得した繰返し候補の位置を起点にする文字列と符号化位 置を起点にする文字列を比較し、 前記繰返し候補の位置からの一致した文字列を 検出する一致検出ステップと、
符号生成部により、 検出した一致文字列を符号化する符号生成ステップと、 を備えたことを特徴とするデータ圧縮方法。
2 . 請求の範囲 1のデータ圧縮方法に於いて、
前記候補取得ステップは、 符号化位置をァドレスとして前記最近一致位置リス トから取得した格納値を文字列の繰返し位置の第 1候補とし、
前記一致検出ステップは、 前記第 1候補の位置を起点にする文字列と符号化位 置を起点にする文字列を比較し、 一致した文字列を取得して符号化させることを 特徴とするデータ圧縮方法。
3 . 請求の範囲 2のデータ圧縮方法に於いて、
前記候補取得ステップは、 更に、
前記第 1候補を評価値とする第 1ステップと、
前記符号化位置に後続する各位置をァドレスとして前記最近一致位置リストか ら取得した格納値と前記評価値を比較し、 取得した格納値が評価値より過去の値 である場合に、 符号化位置からの距離が小さい順に前記第 1候補に続く 1又は複 数の後続候補を取得する第 2ステップと、
を備え、
前記一致検出ステップは、 前記第 1候補及び後続候補を起点にする文字列と符 号化位置を起点にする文字列を比較し、 一致長の最も長い文字列を検出して符号 化させることを特徴とするデータ圧縮方法。
4. 請求の範囲 3のデ一夕圧縮方法に於いて、 前記候補取得ステップは、 後続候 補を取得した際に、 取得した後続候補の値を次に後続する候補を取得するための 評価値とすることを特徴とするデ一夕圧縮方法。
5 . 請求の範囲 2のデータ圧縮方法に於いて、 - 前記候補取得ステップは、 更に、
前記第 1候補をァドレスとして前記最近一致位置リストから取得した値を評価 値とする第 1ステップと、
前記符号化位置に後続する各位置をァドレスとして'前記最近一致位置リストか ら取得した格納値と前記評価値を比較し、 取得した格納値が評価値より過去の値 である場合に、 符号化位置からの距離が小さい順に第 1候補に続く 1又は複数の 後続候補を取得する第 2ステップと、
を備え、
前記一致検出ステップは、 前記第 1候補及び後続候補を起点にする文字列と符 号化位置を起点にする文字列を比較し、 一致長の最も長い文字列を検出して符号 化させることを特徴とするデータ圧縮方法。
6 . 請求の範囲 5のデ一夕圧縮方法に於いて、 前記候補取得ステップは、 後続候 補を取得した際に、 取得した後続候補の値を次に後続する候補を取得するための 評価値とすることを特徴とするデータ圧縮方法。
7 . 請求の範囲 2のデータ圧縮方法に於いて、
前記候補取得ステップは、 更に、 第 1候補に続く 1又は複数の後続候補として、 先行する候補をァドレスとして前記最近一致位置リストから取得した格納値を後 続候補とし、
前記一致検出ステツプは、 前記第 1候補及び後続候補を起点にする文字列と符 号化位置を起点にする文字列を比較し、 一致長の最も長い文字列を取得して符号 化させることを特徴とするデ一夕圧縮方法。
8 . 請求の範囲 2のデータ圧縮方法に於いて、
前記候補取得ステップは、 更に、
前記第 1候補を評価値とし、 前記符号化位置に後続する各位置をァドレスとし て前記最近 致位置リストから取得した格納値と前記評価値を比較し、 取得した 格納値が評価値より過去の値である場合に、 符号化位置からの距離が小さい順に 前記第 1候補に続く 1又は複数の後続候補とし、 前記第 1候補及び後続候補を起 点にする文字列と符号化位置を起点にする文字列を比較し、 符号化位置の文字列 との一致長の最も長い文字列を改定第 1候補として取得する第 1ステツプと、 前記改定第 1候補に続く 1又は複数の後続候補として、 先行する候補をァドレ スとして前記最近一致位置リストから取得した格納値を改定後続候補とする第 2 を備え、
前記一致検出ステップは、 前記改定第 1候補及び改定後続候補を起点にする文 字列と符号化位置を起点にする文字列を比較し、 一致長の最も長い文字列を検出 して符号化させることを特徴とするデ一夕圧縮方法。
9 . 請求の範囲 1のデータ圧縮方法に於いて、 前記符号生成ステップは、 符号化 位置からの文字列を、 検出された一致文字列の相対位置と一致長で符号化するこ とを特徴とするデータ圧縮方法。
1 0 . コンピュータに、
入力バッファに被圧縮データ列を入力して保持する入力ステップと、 前記入力バッファ中の各ァドレスを起点とする所定長の各文字列が最も最近出 現した位置を格納した最近一致位置リストを生成して保持するリスト生成ステツ プと、
前記最近一致位置リストを用いて符号化位置の文字列が過去に出現した位置の 繰返し候補を取得する候補取得ステツプと、
取得した繰返し候補の位置を起点にする文字列と符号化位置を起点にする文字 列を比較し、 前記繰返し候補の位置からの一致した文字列を検出する一致検出ス 検出した一致文字列を符号化する符号生成
を実行させることを特徴とするプログラム。
1 1 . 請求の範囲 1 0のプログラムに於いて、
前記候補取得ステップは、 符号化位置をァドレスとして前記最近一致位置リス トから取得した格納値を文字列の繰返し位置の第 1候補とし、
前記一致検出ステップは、 前記第 1候補の位置を起点にする文字列と符号化位 置を起点にする文字列を比較し、 一致した文字列を検出して符号化させることを 特徴とするプログラム。
1 2 . 請求の範囲 1 1のプログラムに於いて、
前記候補取得ステップは、 更に、
前記第 1候補を評価値とする第 1ステップと、 .
前記符号化位置に後続する各位置をァドレスとして前記最近一致位置リストか ら取得した格納値と前記評価値を比較し、 取得した格納値が評価値より過去の値 である場合に、 符号化位置からの距離が小さい順に前記第 1候補に続く 1又は複 数の後続候補として取得する第 2ステップと、
を備え、
前記一致検出ステツプは、 前記第 1候補及び後続候補を起点にする文字列と符 号化位置を起点にする文字列を比較し、 一致長の最も長い文字列を検出して符号 化させることを特徴とするプログラム。
1 3 . 請求の範囲 1 2のプログラムに於いて、 前記候補取得ステップは、 後続候 補を取得した際に、 取得した後続候補の値を次に後続する候補を取得するための 評価値とすることを特徴とするプログラム。
1 4. 請求の範囲 1 1のプログラムに於いて、
前記候補取得ステップは、 更に、
前記第 1候補をァドレスとして前記最近一致位置リストから取得した値を評価 値とする第 1ステップと、
前記符号化位置に後続する各位置をァドレスとして前記最近一致位置リストか ら取得した格納値と前記評価値を比較し、 取得した格納値が評価値より過去の値 である場合に、 符号化位置からの距離が小さい順に第 1候補に続く 1又は複数の 後続候補を取得する第 2ステップと、
を備え、
前記一致検出ステップは、 前記第 1候補及び後続候補を起点にする文字列と符 号化位置を起点にする文字列を比較し、 一致長の最も長い文字列を検出して符号 化させることを特徴とするプログラム。
1 5 . 請求の範囲 1 4のプログラムに於いて、 前記候補取得ステップは、 後続候 補を取得した際に、 取得した後続候補の値を次に後続する候補を取得するための 評価値とすることを特徴とするプログラム。
1 6 . 請求の範囲 1 1のプログラムに於いて、
前記候補取得ステップは、 更に、 第 1候補に続く 1又は複数の後続候補として、 先行する候補をァドレスとして前記最近一致位置リストから取得した格納値を後 続候補とし、
前記一致検出ステップは、 前記第 1候補及び後続候補を起点にする文字列と符 号化位置を起点にする文字列を比較し、 一致長の最も長い文字列を検出して符号 化させることを特徴とするプログラム。
1 7 . 請求の範囲 1 1のプログラムに於いて、
前記候補取得ステップは、 更に、
前記第 1候補を評価値とし、 前記符号化位置に後続する各位置をァドレスとし て前記最近一致位置リストから取得した格納値と前記評価値を比較し、 取得した 格納値が評価値より過去の値である場合に、 符号化位置からの距離が小さい順に 前記第 1候補に続く 1又は複数の後続候補とし、 前記第 1候補及び後続候補を起. 点にする文字列と符号化位置を起点にする文字列を比較し、 符号化位置の文字列 との一致長の最も長い文字列を改定第 1候補とする第 1ステップと、
前記改定第 1候補に続く 1又は複数の改定後続候補として、 .先行する候補をァ ドレスとして前記最近一致位置リストから取得した格納値を改定後続候補とする 第 2ステップと、 - を備え、
前記一致検出ステップは、 前記改定第 1候補及び改定後続候補を起点にする文 字列と符号化位置を起点にする文字列を比較し、 一致長の最も長い文字列を取得 して符号化させることを特徴とするプログラム。
1 8 . 請求の範囲 1 0のプログラムに於いて、 前記符号生成ステップは、 符号化 位置からの文字列を、 検出された一致文字列の相対位置と一致長で符号化するこ とを特徴とするプログラム。
1 9 . 被圧縮データ列から圧縮データを生成するデータ圧縮装置に於いて、 入力バッファに被圧縮データ列を入力して保持する入力バッファと、
前記入力バッファ中の各アドレスを起点とする所定長の各文字列が最も最近出 現した位置を格納した最近一致位置リストを生成して保持する最近一致位置リス ト生成部と、
前記最近一致位置リストを用いて符号化位置の文字列が過去に出現した位置の 繰返し候補を取得する候補取得部と、
取得した繰返し候補の位置を起点にする文字列と符号化位置を起点にする文字 列を比較し、 前記候補位置からの一致した文字列を検出する一致検出部と、 検出した一致文字列を符号化する符号生成部と、 を備えたことを特徴とするデータ圧縮装置。
PCT/JP2002/013600 2002-12-26 2002-12-26 データ圧縮方法、プログラム及び装置 Ceased WO2004062110A1 (ja)

Priority Applications (4)

Application Number Priority Date Filing Date Title
PCT/JP2002/013600 WO2004062110A1 (ja) 2002-12-26 2002-12-26 データ圧縮方法、プログラム及び装置
JP2004564417A JP3889762B2 (ja) 2002-12-26 2002-12-26 データ圧縮方法、プログラム及び装置
EP02792004.0A EP1578020B1 (en) 2002-12-26 2002-12-26 Data compressing method, program and apparatus
US11/166,146 US7536399B2 (en) 2002-12-26 2005-06-27 Data compression method, program, and apparatus to allow coding by detecting a repetition of a matching character string

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/JP2002/013600 WO2004062110A1 (ja) 2002-12-26 2002-12-26 データ圧縮方法、プログラム及び装置

Related Child Applications (1)

Application Number Title Priority Date Filing Date
US11/166,146 Continuation US7536399B2 (en) 2002-12-26 2005-06-27 Data compression method, program, and apparatus to allow coding by detecting a repetition of a matching character string

Publications (1)

Publication Number Publication Date
WO2004062110A1 true WO2004062110A1 (ja) 2004-07-22

Family

ID=32697298

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2002/013600 Ceased WO2004062110A1 (ja) 2002-12-26 2002-12-26 データ圧縮方法、プログラム及び装置

Country Status (4)

Country Link
US (1) US7536399B2 (ja)
EP (1) EP1578020B1 (ja)
JP (1) JP3889762B2 (ja)
WO (1) WO2004062110A1 (ja)

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2012533921A (ja) * 2009-07-17 2012-12-27 イーストソフト コーポレーション データの圧縮方法
JP2013197850A (ja) * 2012-03-19 2013-09-30 Fujitsu Ltd 符号化方法、符号化装置及びコンピュータプログラム
JP2014017629A (ja) * 2012-07-06 2014-01-30 Fujitsu Ltd 復元プログラム、圧縮プログラム、復元装置、圧縮装置、復元方法、および圧縮方法
JP2014204356A (ja) * 2013-04-08 2014-10-27 日本電信電話株式会社 文字列圧縮方法及び装置
JP2015186077A (ja) * 2014-03-25 2015-10-22 インターナショナル・ビジネス・マシーンズ・コーポレーションＩｎｔｅｒｎａｔｉｏｎａｌ Ｂｕｓｉｎｅｓｓ Ｍａｃｈｉｎｅｓ Ｃｏｒｐｏｒａｔｉｏｎ データ圧縮を高速化する方法、並びに、データ圧縮を高速化するためのコンピュータ、及びそのコンピュータ・プログラム

Families Citing this family (34)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7653643B2 (en) * 2005-03-24 2010-01-26 Microsoft Corporation Method and apparatus for compressing a data set
JP2006295853A (ja) * 2005-04-14 2006-10-26 Sony Corp 符号化装置、復号装置、および、符号化方法ならびに復号方法
US8489562B1 (en) 2007-11-30 2013-07-16 Silver Peak Systems, Inc. Deferred data storage
US8811431B2 (en) 2008-11-20 2014-08-19 Silver Peak Systems, Inc. Systems and methods for compressing packet data
US8929402B1 (en) * 2005-09-29 2015-01-06 Silver Peak Systems, Inc. Systems and methods for compressing packet data by predicting subsequent data
US8885632B2 (en) 2006-08-02 2014-11-11 Silver Peak Systems, Inc. Communications scheduler
US8755381B2 (en) 2006-08-02 2014-06-17 Silver Peak Systems, Inc. Data matching using flow based packet data storage
US8046532B2 (en) * 2007-08-27 2011-10-25 Comtech Ef Data Corp. Content-addressable memories and state machines for performing three-byte matches and secondary matches, and for providing error protection
US8307115B1 (en) 2007-11-30 2012-11-06 Silver Peak Systems, Inc. Network memory mirroring
US9717021B2 (en) 2008-07-03 2017-07-25 Silver Peak Systems, Inc. Virtual network overlay
US8743683B1 (en) 2008-07-03 2014-06-03 Silver Peak Systems, Inc. Quality of service using multiple flows
US10805840B2 (en) 2008-07-03 2020-10-13 Silver Peak Systems, Inc. Data transmission via a virtual wide area network overlay
US10164861B2 (en) 2015-12-28 2018-12-25 Silver Peak Systems, Inc. Dynamic monitoring and visualization for network health characteristics
US20110181448A1 (en) * 2008-10-15 2011-07-28 Veeresh Rudrapa Koratagere Lossless compression
US9130991B2 (en) 2011-10-14 2015-09-08 Silver Peak Systems, Inc. Processing data packets in performance enhancing proxy (PEP) environment
US9626224B2 (en) 2011-11-03 2017-04-18 Silver Peak Systems, Inc. Optimizing available computing resources within a virtual environment
CN110830803B (zh) * 2013-10-12 2022-04-19 深圳艺慧影视传媒有限公司 结合块匹配和串匹配的图像压缩方法
US9264068B2 (en) * 2014-05-09 2016-02-16 Micron Technology, Inc. Deflate compression algorithm
US9948496B1 (en) 2014-07-30 2018-04-17 Silver Peak Systems, Inc. Determining a transit appliance for data traffic to a software service
US9875344B1 (en) 2014-09-05 2018-01-23 Silver Peak Systems, Inc. Dynamic monitoring and authorization of an optimization device
CN106294528B (zh) * 2015-06-29 2020-03-03 深圳市腾讯计算机系统有限公司 一种实现信息发送的方法及装置
US9537504B1 (en) * 2015-09-25 2017-01-03 Intel Corporation Heterogeneous compression architecture for optimized compression ratio
US10432484B2 (en) 2016-06-13 2019-10-01 Silver Peak Systems, Inc. Aggregating select network traffic statistics
US9967056B1 (en) 2016-08-19 2018-05-08 Silver Peak Systems, Inc. Forward packet recovery with constrained overhead
US10892978B2 (en) 2017-02-06 2021-01-12 Silver Peak Systems, Inc. Multi-level learning for classifying traffic flows from first packet data
US10257082B2 (en) 2017-02-06 2019-04-09 Silver Peak Systems, Inc. Multi-level learning for classifying traffic flows
US11044202B2 (en) 2017-02-06 2021-06-22 Silver Peak Systems, Inc. Multi-level learning for predicting and classifying traffic flows from first packet data
US10771394B2 (en) 2017-02-06 2020-09-08 Silver Peak Systems, Inc. Multi-level learning for classifying traffic flows on a first packet from DNS data
US11212210B2 (en) 2017-09-21 2021-12-28 Silver Peak Systems, Inc. Selective route exporting using source type
US10224957B1 (en) * 2017-11-27 2019-03-05 Intel Corporation Hash-based data matching enhanced with backward matching for data compression
US10637721B2 (en) 2018-03-12 2020-04-28 Silver Peak Systems, Inc. Detecting path break conditions while minimizing network overhead
JP2021149416A (ja) 2020-03-18 2021-09-27 キオクシア株式会社 メモリシステム
CN113705175B (zh) * 2021-08-18 2024-02-23 厦门海迈科技股份有限公司 一种电子表格行列精简的方法、服务器及存储介质
CN117216023B (zh) * 2023-11-07 2024-01-26 陕西长瑞安驰信息技术集团有限公司 一种大规模网络数据存储方法及系统

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0946235A (ja) * 1994-10-04 1997-02-14 Nec Corp データ圧縮装置
JPH09153818A (ja) * 1995-09-29 1997-06-10 Kyocera Corp データ圧縮・伸長装置
JP2000082967A (ja) * 1998-07-09 2000-03-21 Fujitsu Ltd デ―タ圧縮方法及びデ―タ圧縮装置

Family Cites Families (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5126739A (en) * 1989-01-13 1992-06-30 Stac Electronics Data compression apparatus and method
US5532693A (en) * 1994-06-13 1996-07-02 Advanced Hardware Architectures Adaptive data compression system with systolic string matching logic
US5883588A (en) * 1994-10-04 1999-03-16 Nec Corporation Data compression system and data compression device for improving data compression rate and coding speed
JP3540109B2 (ja) * 1996-12-24 2004-07-07 富士通株式会社 データ圧縮方法及び装置

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0946235A (ja) * 1994-10-04 1997-02-14 Nec Corp データ圧縮装置
JPH09153818A (ja) * 1995-09-29 1997-06-10 Kyocera Corp データ圧縮・伸長装置
JP2000082967A (ja) * 1998-07-09 2000-03-21 Fujitsu Ltd デ―タ圧縮方法及びデ―タ圧縮装置

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2012533921A (ja) * 2009-07-17 2012-12-27 イーストソフト コーポレーション データの圧縮方法
JP2013197850A (ja) * 2012-03-19 2013-09-30 Fujitsu Ltd 符号化方法、符号化装置及びコンピュータプログラム
JP2014017629A (ja) * 2012-07-06 2014-01-30 Fujitsu Ltd 復元プログラム、圧縮プログラム、復元装置、圧縮装置、復元方法、および圧縮方法
JP2014204356A (ja) * 2013-04-08 2014-10-27 日本電信電話株式会社 文字列圧縮方法及び装置
JP2015186077A (ja) * 2014-03-25 2015-10-22 インターナショナル・ビジネス・マシーンズ・コーポレーションＩｎｔｅｒｎａｔｉｏｎａｌ Ｂｕｓｉｎｅｓｓ Ｍａｃｈｉｎｅｓ Ｃｏｒｐｏｒａｔｉｏｎ データ圧縮を高速化する方法、並びに、データ圧縮を高速化するためのコンピュータ、及びそのコンピュータ・プログラム

Also Published As

Publication number Publication date
EP1578020B1 (en) 2014-08-27
US20050283355A1 (en) 2005-12-22
EP1578020A4 (en) 2005-11-16
US7536399B2 (en) 2009-05-19
JP3889762B2 (ja) 2007-03-07
JPWO2004062110A1 (ja) 2006-05-18
EP1578020A1 (en) 2005-09-21

Similar Documents

Publication Publication Date Title
WO2004062110A1 (ja) データ圧縮方法、プログラム及び装置
EP0584992B1 (en) Text compression technique using frequency ordered array of word number mappers
JP3234104B2 (ja) 圧縮データをサーチする方法及びシステム
JP4261779B2 (ja) データ圧縮装置および方法
US20160321282A1 (en) Extracting method, information processing method, computer product, extracting apparatus, and information processing apparatus
US9916314B2 (en) File extraction method, computer product, file extracting apparatus, and file extracting system
JP4114600B2 (ja) 可変長文字列検索装置及び可変長文字列検索方法並びにプログラム
JP4077409B2 (ja) 高速最長一致探索方法及び装置
JP6447161B2 (ja) 意味構造検索プログラム、意味構造検索装置、及び意味構造検索方法
JP2000201080A (ja) 付加コ―ドを用いたデ―タ圧縮／復元装置および方法
Gupta et al. A novel approach for compressing DNA sequences using semi-statistical compressor
JP2993540B2 (ja) 昇順整数列データの圧縮および復号システム
JPH05241775A (ja) データ圧縮方式
JP3038233B2 (ja) データ圧縮及び復元装置
JP2005004560A (ja) インバーテッドファイル作成方法
WO1991013395A1 (fr) Procede de compression et de reconstitution de donnees et dispositif prevu a cet effet
JP3053656B2 (ja) データ圧縮における辞書登録方式
Anisimov et al. Practical Word-based Text Compression Using the Reverse Multi-Delimiter Codes.
JP2952067B2 (ja) データ圧縮方式
JPH05152971A (ja) データ圧縮・復元方法
JP3058931B2 (ja) データ圧縮・復元における辞書登録方式
JP3708318B2 (ja) データ圧縮／復元装置およびデータ圧縮／復元方法
JPH1155125A (ja) 文字データの圧縮・復元方法
JP3236747B2 (ja) データ伸長方式
Bookstein et al. An overhead reduction technique for mega-state compression schemes

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): JP US

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR IE IT LU MC NL PT SE SI SK TR

121 Ep: the epo has been informed by wipo that ep was designated in this application
WWE Wipo information: entry into national phase

Ref document number: 2004564417

Country of ref document: JP

WWE Wipo information: entry into national phase

Ref document number: 2002792004

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 11166146

Country of ref document: US

WWP Wipo information: published in national office

Ref document number: 2002792004

Country of ref document: EP