JP5928201B2 - RESTORE PROGRAM, COMPRESSION PROGRAM, RESTORE DEVICE, COMPRESSION DEVICE, RESTORE METHOD, AND COMPRESSION METHOD - Google Patents

Description

  The present invention relates to a restoration program, a compression program, a restoration device, a compression device, a restoration method, and a compression method.

  Conventionally, there is a compression technique for reducing the size of a data string by compressing the data string. As the compression technique, for example, there is a lossless compression (lossless compression) technique capable of restoring a compressed data string to a compression source data string. The lossless compression technique includes, for example, a compression technique that uses a compression algorithm “LZ77” and a compression technique that uses a compression algorithm “LZSS”.

  In the compression of the data string by the compression technique described above, when the same data appears in the data string, the processor converts the data that appears later (hereinafter, subsequent data) to the data that appears first (hereinafter, the preceding data). ) Is compressed into data indicating the start position and data length. On the other hand, in the restoration to the data string by the compression technique described above, the processor sequentially acquires the preceding data at the position indicated by the compressed data in the compressed data in units of 1 byte, thereby converting the compressed data into the preceding data. Restore to subsequent data that is the same data.

  There is also a technique for searching for preceding data and subsequent data that are the same data from a compressed data string. As another compression technique, there is a Golomb-Rice coding technique for executing entropy coding used for lossless compression of voice and images.

JP 2006-092725 A JP 2009-105838 A

Nobuko Iya, Shigeru Yoshida, “C MAGAZINE”, Softbank Creative, 2004, October, pages 106-110

  However, the above-described conventional compressed data indicates the position and data length of the preceding data, and does not indicate whether or not the preceding data can be acquired in register width units. For this reason, the processor sequentially acquires the preceding data in units of 1 byte. Therefore, the processor cannot effectively use the register width, and there is a problem that the use efficiency of the register is reduced in the decompression process of the compressed data.

  On the other hand, in order for the processor to acquire the preceding data in register width units and to use the register width, it is necessary to cause the processor to calculate the number of data that can be processed in register width units among the preceding data. Further, it is necessary to cause the processor to execute a process of writing or reading the calculated number in the storage device. Therefore, there is a problem that the processing amount and processing time required for data restoration increase.

  An object of the present invention is to increase the speed of data restoration by efficiently utilizing the register width of a processor.

  According to one aspect of the present invention, a processor having a predetermined length register calculates a reference position of uncompressed data as a reference destination, a quotient obtained by dividing the length of uncompressed data that is greater than or equal to a predetermined length by a predetermined length, and a remainder. Compressed data is detected from a storage unit that stores a compressed data string including compressed data and non-compressed data, and predetermined reference data starting from a reference position included in the detected compressed data Obtaining a first data string having a length obtained by multiplying the quotient by a predetermined length unit, and obtaining a second data string having a surplus length obtained by removing the first data string from the reference destination data; A restoration program, a restoration device, and a restoration method for writing a first data string acquired in a predetermined length unit to a predetermined storage area and writing the acquired second data string to a predetermined storage area are proposed

  According to another aspect of the present invention, a processor having a register of a predetermined length causes a write destination position in a predetermined storage area and a plurality of positions divided by a predetermined length unit from the beginning of the predetermined storage area. Among them, the section length between the end of the writing destination and the position within the predetermined length from the writing destination position is specified, and the reference position of the uncompressed data serving as the reference destination, the predetermined From a storage unit for storing a compressed data string including a compressed data having a quotient and a remainder obtained by dividing a length obtained by subtracting a section length from a length of uncompressed data that is equal to or longer than a predetermined length, and the uncompressed data The compressed data is detected, and the first data string that becomes the section length and the length obtained by multiplying the predetermined length by the quotient in order from the top of the reference destination data starting from the reference position included in the detected compressed data. Second data string in a predetermined length unit and extra length A third data string, and a first data string, a second data string, and a third data string written in the order of acquisition from the write destination position in a predetermined storage area And a restoration method is proposed.

  According to another aspect of the present invention, the processor detects preceding data and subsequent data that is the same data as the preceding data from the storage unit that stores the data string, and the detected preceding data is detected. A compression program that generates a compressed data having a quotient and a remainder obtained by dividing the position of the preceding data that is equal to or greater than the predetermined length by the predetermined length, and that stores the data string in which the subsequent data is replaced with the generated compressed data, compression An apparatus and a compression method are proposed.

  According to one aspect of the present invention, the processor detects preceding data and subsequent data that is the same data as the preceding data from the storage unit that stores the data string, and then performs subsequent processing in the data string. Among the positions of the data and a plurality of positions delimited in units of a predetermined length from the beginning of the data string, a position that is on the end side of the position of the subsequent data and is within a predetermined length range from the position of the subsequent data , And generates compressed data having a quotient obtained by dividing a length obtained by subtracting the section length from the length of the preceding data that is equal to or greater than the predetermined length, and a remainder, and a remainder. A compression program, a compression device, and a compression method for storing a data string obtained by replacing subsequent data with generated compressed data are proposed.

  According to one aspect of the present invention, it is possible to increase the speed of data restoration by efficiently using the register width of a processor.

FIG. 1 is an explanatory diagram showing the contents of the compressed data string decompression process. FIG. 2 is a block diagram of a hardware configuration example of the information processing apparatus 100 according to the embodiment. FIG. 3 is a block diagram of an example of a functional configuration related to data string compression of the information processing apparatus 100 according to the first embodiment. FIG. 4 is an explanatory diagram showing an example of the compression source data string. FIG. 5 is an explanatory diagram showing an example of a method for searching for reference destination data. FIG. 6 is an explanatory diagram of a compression rule according to the first embodiment. FIG. 7 is an explanatory diagram (part 1) illustrating an example of uncompressed data that has not been compressed and an example of compressed data that has been compressed according to the compression rule illustrated in FIG. 6. FIG. 8 is an explanatory diagram (part 2) illustrating an example of uncompressed data that has not been compressed and an example of compressed data that has been compressed according to the compression rule illustrated in FIG. 6. FIG. 9 is an explanatory diagram (part 1) of the flow of data string compression by the information processing apparatus 100 according to the first embodiment. FIG. 10 is an explanatory diagram (part 2) of the flow of data string compression by the information processing apparatus 100 according to the first embodiment. FIG. 11 is an explanatory diagram (part 3) of the flow of data string compression by the information processing apparatus 100 according to the first embodiment. FIG. 12 is an explanatory diagram (part 4) of the flow of data string compression by the information processing apparatus 100 according to the first embodiment. FIG. 13 is an explanatory diagram (part 5) of the flow of data string compression by the information processing apparatus 100 according to the first embodiment. FIG. 14 is an explanatory diagram (part 6) of the flow of data string compression by the information processing apparatus 100 according to the first embodiment. FIG. 15 is an explanatory diagram showing a storage example of the discrimination bit string and the compressed data string shown in FIGS. FIG. 16 is a flowchart showing a detailed processing procedure of the data string compression processing for realizing the compression of the data string shown in FIGS. FIG. 17 is a block diagram of an example of a functional configuration related to the decompression of the compression source data string dsB of the information processing apparatus 100 according to the first embodiment. FIG. 18 is an explanatory diagram (part 1) of a flow of decompression of the compression source data string dsB by the information processing apparatus 100 according to the first embodiment. FIG. 19 is an explanatory diagram (part 2) of the flow of decompression of the compression source data string dsB by the information processing apparatus 100 according to the first embodiment. FIG. 20 is an explanatory diagram (part 3) of the decompression flow of the compression source data string dsB by the information processing apparatus 100 according to the first embodiment. FIG. 21 is an explanatory diagram (part 4) of the decompression flow of the compression source data string dsB by the information processing apparatus 100 according to the first embodiment. FIG. 22 is an explanatory diagram (part 5) of the flow of decompression of the compression source data string dsB by the information processing apparatus 100 according to the first embodiment. FIG. 23 is an explanatory diagram (part 6) of the flow of decompression of the compression source data string dsB by the information processing apparatus 100 according to the first embodiment. FIG. 24 is a flowchart showing a detailed processing procedure of the compression source data sequence decompression processing for realizing the decompression of the compression source data sequence dsB shown in FIGS. FIG. 25 is a block diagram of an example of a functional configuration related to data string compression of the information processing apparatus 100 according to the second embodiment. FIG. 26 is an explanatory diagram of a compression rule according to the second embodiment. FIG. 27 is an explanatory diagram (part 1) illustrating an example of uncompressed data that has not been compressed, and an example of compressed data that has been compressed according to the compression rule illustrated in FIG. FIG. 28 is an explanatory diagram (part 2) illustrating an example of uncompressed data that has not been compressed, and an example of compressed data that has been compressed according to the compression rule illustrated in FIG. FIG. 29 is an explanatory diagram (part 1) of the flow of data string compression by the information processing apparatus 100 according to the second embodiment. FIG. 30 is an explanatory diagram (part 2) of the flow of data string compression by the information processing apparatus 100 according to the second embodiment. FIG. 31 is an explanatory diagram (part 3) of the flow of data string compression by the information processing apparatus 100 according to the second embodiment. FIG. 32 is an explanatory diagram (part 4) of the flow of data string compression by the information processing apparatus 100 according to the second embodiment. FIG. 33 is an explanatory diagram (part 5) of the flow of data string compression by the information processing apparatus 100 according to the second embodiment. FIG. 34 is an explanatory diagram (part 6) of the flow of data string compression by the information processing apparatus 100 according to the second embodiment. FIG. 35 is a flowchart showing a detailed processing procedure of the data string compression processing for realizing the compression of the data strings shown in FIGS. FIG. 36 is a block diagram of a functional configuration example related to the decompression of the compression source data string dsB of the information processing apparatus 100 according to the second embodiment. FIG. 37 is an explanatory diagram (part 1) of a flow of decompression of the compression source data string dsB by the information processing apparatus 100 according to the second embodiment. FIG. 38 is an explanatory diagram (part 2) of the decompression flow of the compression source data string dsB by the information processing apparatus 100 according to the second embodiment. FIG. 39 is an explanatory diagram (part 3) of the flow of decompression of the compression source data string dsB by the information processing apparatus 100 according to the second embodiment. FIG. 40 is an explanatory diagram (part 4) of the flow of decompression of the compression source data string dsB by the information processing apparatus 100 according to the second embodiment. FIG. 41 is an explanatory diagram (part 5) of the flow of decompression of the compression source data string dsB by the information processing apparatus 100 according to the second embodiment. FIG. 42 is an explanatory diagram (part 6) of a flow of decompression of the compression source data string dsB by the information processing apparatus 100 according to the second embodiment. FIG. 43 is a flowchart showing a detailed processing procedure of the compression source data sequence decompression processing for realizing the decompression of the compression source data sequence dsB shown in FIGS.

  Exemplary embodiments of a restoration program, a compression program, a restoration device, a compression device, a restoration method, and a compression method according to the present invention will be described below in detail with reference to the accompanying drawings. Hereinafter, an information processing apparatus having the function of a compression apparatus and the function of a decompression apparatus will be described as an example.

(Contents of compressed data string restoration processing)
FIG. 1 is an explanatory diagram showing the contents of the compressed data string decompression process.

  The information processing apparatus is a computer that holds a restoration program. In FIG. 1, the information processing apparatus 100 restores a compression source data string from a compressed data string using a restoration program.

  The processor of the information processing apparatus 100 includes a data register (hereinafter simply referred to as “register”). Here, as an example, the register width of the register is “8 bytes”. The register is a storage device that can be accessed at high speed from the processor of the information processing device 100 as compared to other storage devices such as a ROM (Read Only Memory), a RAM (Random Access Memory), and a magnetic disk drive (Hard Disk Drive). is there. Here, one byte is a so-called octet and is 8 bits.

  Here, since the processor of the information processing apparatus 100 includes a register having a register width of “8 bytes”, data in units of 8 bytes can be processed collectively. Therefore, when the processor of the information processing apparatus 100 processes data of 8 bytes, the processing is completed in a shorter time when the processing is performed in units of 8 bytes rather than sequentially in units of 1 byte. be able to.

  Hereinafter, the compressed data string is referred to as “compressed data string”. A compression source data string restored from the compression data string cdsA is referred to as a “compression source data string”. The compressed data string cdsA is compressed because the data used for restoration exists in the compression source data string and can be compressed, and the data used for restoration does not exist in the compression source data string. Uncompressed data that could not be recorded.

  Also, the discrimination bit string bsA is given to the compressed data string cdsA. The determination bit string bsA is information used to specify the position where the compressed data starts in the compressed data string cdsA. Hereinafter, the position where the compressed data starts is referred to as “compressed data position”.

  In the example of FIG. 1, the compressed data string cdsA to be restored is “internationalization 30, 2, 4. Each alphabet which is uncompressed data in the compressed data string cdsA is 1-byte data. “30, 2, 4” which is the compressed data in the compressed data string cdsA is 3-byte data.

  The discrimination bit string bsA is “00000000000000000000... 1”. Each discrimination bit in the discrimination bit string bsA is 1-bit data. Each determination bit in the determination bit string bsA indicates whether or not the data at the position corresponding to the determination bit is compressed data. For example, when the determination bit is “0”, it indicates that the data corresponding to the determination bit in the compressed data string cdsA is uncompressed data. For example, when the determination bit is “1”, it indicates that the data corresponding to the determination bit in the compressed data string cdsA is compressed data.

  In FIG. 1, the information processing apparatus 100 refers to the determination bits sequentially from the beginning of the determination bit string bsA, and specifies that each alphabet of “internationalization...” Starting from the head in the compressed data string cdsA is uncompressed data. . Then, it is assumed that the information processing apparatus 100 stores the uncompressed data as it is in the decompression buffer.

  (1) Next, when the information processing apparatus 100 refers to the determination bit bA of the determination bit string bsA, since the referred determination bit bA is “1”, the data “30, 2” at the position corresponding to the determination bit bA , 4 "is specified as the compressed data cdA.

  (2) Next, the information processing apparatus 100 refers to the specified compressed data cdA “30, 2, 4” and restores the compression source data from the compressed data cdA that is at the head of the specified compressed data cdA. Therefore, “30” indicating the position where the data to be referred to starts is extracted.

  Hereinafter, the compression source data is referred to as “compression source data”. Data referred to for decompressing the compression source data is referred to as “reference destination data”. The position where the reference destination data starts is referred to as “reference destination data position”. Here, the extracted “30” indicates that the position of the reference destination data is “30 bytes before” the position of the compressed data cdA.

  (3) Then, the information processing apparatus 100 refers to the specified compressed data cdA (“30, 2, 4”) and divides the reference destination data in units of “8 bytes” that are the register width. “2” indicating the number of possible data is extracted. In addition, the information processing apparatus 100 sets the fraction data length that is the data length of the remaining data that cannot be collectively processed in “8-byte” units among the reference destination data, and is the data length to be processed in 1-byte units. “4” shown is extracted.

  (4) Next, the information processing apparatus 100 specifies the position of the reference destination data that is “30” bytes from the position of the compressed data cdA, and starts acquiring the reference destination data. Specifically, the information processing apparatus 100 acquires, for example, data of “8 bytes” as many as the extracted number in order from the position of the specified reference destination data.

  (5) Here, first, the information processing apparatus 100 collectively obtains “internet” in the 8-th byte unit from the specified reference destination data and stores it in the restoration buffer. (6) Next, the information processing apparatus 100 collectively acquires the “2” -th 8-byte unit data “ionaliza” that follows the acquired “1” -th data and stores it in the restoration buffer. Store.

  (7) Then, the information processing apparatus 100 sequentially acquires the data “tion” for “4” bytes, which is the fraction data length, following the acquired “2” -th data, in units of 1 byte. And store it in the restoration buffer.

  Thereby, the information processing apparatus 100 can store the data string in which the compressed data “30, 2, 4” in the compressed data string cdsA is replaced with the compression source data “internationalization” in the restoration buffer. Then, the information processing apparatus 100 can output the data sequence “internationalization... Internationalization...” Stored in the restoration buffer as the compression source data sequence dsA.

  Further, in this way, the information processing apparatus 100 can refer to the compressed data cdA, divide the reference destination data into 8-byte data, collect the data, and store the data in the restoration buffer. As a result, the information processing apparatus 100 can efficiently utilize the register width, and can speed up data restoration.

  Here, the position of the reference destination data indicated by the compressed data is indicated by how many bytes before the position of the compressed data is the position of the reference destination data, but is not limited thereto. For example, the position of the reference destination data indicated by the compressed data may be indicated by how many bytes from the position of the compressed data string cdsA are the position of the reference destination data.

  Here, the compressed data indicates data indicating the position of the reference destination data, data indicating the number of pieces of data that can be divided and processed in units of 8 bytes, and fractional data length to be processed in units of 1 byte. It was included in the order of data, but is not limited to this. For example, the compressed data includes data indicating the number of pieces of data that can be divided and processed in units of 8 bytes of the reference destination data, data indicating the fraction data length to be processed in units of bytes, and data indicating the position of the reference destination data , May be included in this order.

  Here, the discrimination bit string bsA is stored as data different from the compressed data string cdsA, but is not limited thereto. For example, each determination bit in the determination bit string bsA may be provided immediately before the compressed data or the non-compressed data in the compressed data string cdsA corresponding to the determination bit. An example of storing the discrimination bit string bsA and the compressed data string cdsA will be described later with reference to FIG.

  Here, the information processing apparatus 100 has only the function of restoring the compression source data string dsA from the compression data string cdsA, but is not limited thereto. For example, the information processing apparatus 100 may further have a function of compressing the data string and generating the compressed data string cdsA in addition to the function of restoring the compression source data string dsA from the compressed data string cdsA.

(Hardware configuration example of information processing apparatus 100)
FIG. 2 is a block diagram of a hardware configuration example of the information processing apparatus 100 according to the embodiment. In FIG. 2, an information processing apparatus 100 includes a processor 201, a ROM 202, a RAM 203, a magnetic disk drive 204, a magnetic disk 205, an optical disk drive 206, an optical disk 207, a display 208, and an I / F (Interface). 209, a keyboard 210, a mouse 211, a scanner 212, and a printer 213. Each component is connected by a bus 220.

  Here, the processor 201 controls the entire information processing apparatus 100. Further, the processor 201 has a register for storing data to be processed. The processor 201 can execute the access to the register at a higher speed than the access to the ROM 202, the RAM 203, the magnetic disk 205, and the optical disk 207. The ROM 202 stores programs such as a boot program, a compression program, and a restoration program. The RAM 203 is used as a work area for the processor 201. The magnetic disk drive 204 controls reading / writing of data with respect to the magnetic disk 205 according to the control of the processor 201. The magnetic disk 205 stores data written under the control of the magnetic disk drive 204.

  The optical disc drive 206 controls reading / writing of data with respect to the optical disc 207 according to the control of the processor 201. The optical disk 207 stores data written under the control of the optical disk drive 206, or causes the computer to read data stored on the optical disk 207.

  The display 208 displays data such as a document, an image, and function information as well as a cursor, an icon, or a tool box. As this display 208, for example, a liquid crystal display, a plasma display, or the like can be adopted.

  An interface (hereinafter abbreviated as “I / F”) 209 is connected to a network 214 such as a LAN (Local Area Network), a WAN (Wide Area Network), and the Internet through a communication line. Connected to other devices. The I / F 209 controls an internal interface with the network 214 and controls data input / output from an external device. For example, a modem or a LAN adapter may be employed as the I / F 209.

  The keyboard 210 includes keys for inputting characters, numbers, various instructions, and the like, and inputs data. Moreover, a touch panel type input pad or a numeric keypad may be used. The mouse 211 performs cursor movement, range selection, window movement, size change, and the like. A trackball or a joystick may be used as long as they have the same function as a pointing device.

  The scanner 212 optically reads an image and takes in image data into the information processing apparatus 100. The scanner 212 may have an OCR (Optical Character Reader) function. The printer 213 prints image data and document data. As the printer 213, for example, a laser printer or an ink jet printer can be adopted. Note that at least one of the optical disk drive 206, the optical disk 207, the display 208, the keyboard 210, the mouse 211, the scanner 212, and the printer 213 may be omitted.

Example 1
Next, Example 1 will be described. In the first embodiment, the compressed data includes the number of pieces of data to be acquired by dividing the reference data by the processor 201 that restores the compression source data in units of 8 bytes and the fraction data to be acquired in units of 1 byte. This is data indicating the length. The compressed data also indicates the position of reference destination data.

<Data Compression by Information Processing Apparatus 100 According to Embodiment 1>
In the following, first, data string compression performed by the information processing apparatus 100 according to the first embodiment is illustrated in FIGS. Further, decompression of the compression source data string by the information processing apparatus 100 according to the first embodiment is illustrated in FIGS. 17 to 24 described later.

(Functional configuration example regarding compression of data string of information processing apparatus 100 according to first embodiment)
First, a functional configuration example related to compression of a data string of the information processing apparatus 100 according to the first embodiment will be described with reference to FIG. FIG. 3 is a block diagram of an example of a functional configuration related to data string compression of the information processing apparatus 100 according to the first embodiment. The information processing apparatus 100 includes a storage unit 301, a detection unit 302, a generation unit 303, and a storage unit 304.

  Here, the information processing apparatus 100 includes a register having a predetermined length. The predetermined length is a register width that is a power of 2, and is, for example, the above-described 8 bytes. One byte is a set of a plurality of bits, for example, so-called octets, which are 8 bits. The register is, for example, the data register described above. The data register is also called an accumulator.

  For example, when the compressed data is restored by the own apparatus, the information processing apparatus 100 compresses the data according to the register width of the processor 201 of the own apparatus. Further, when the compressed data is restored by another apparatus, the information processing apparatus 100 may compress the data in accordance with the register width of the processor of the other apparatus.

  The storage unit 301 stores a data string. Here, the data string is a data string to be compressed. Specifically, the storage unit 301 stores, for example, a compression source data string input by an operation of an input device such as the keyboard 210 and the mouse 211 by a user of the information processing apparatus 100.

  Specifically, the storage unit 301 realizes its function by a storage device such as the ROM 202, the RAM 203, the magnetic disk 205, and the optical disk 207 shown in FIG. Thereby, the detection unit 302 can refer to the compression source data string to be compressed. Here, an example of the compression source data string stored in the storage unit 301 will be described with reference to FIG.

  FIG. 4 is an explanatory diagram showing an example of the compression source data string. In the example of FIG. 4, the compression source data string dsB is “compression decompression compression.”. Each character such as an alphabet included in the compression source data string dsB is 1-byte data.

  Specifically, each character is, for example, “ISO (International Organization for Standardization) / IEC (International Electrotechnical Commission) 8859” or “ASCII (American Standard Code Information)”.

  In the example of FIG. 4, it is assumed that the address width of the storage area of the storage unit 301 is “8 bytes” and the storage area of the storage unit 301 is aligned with “8 bytes”. The compression source data string dsB is stored from the beginning of the storage area, and is divided into “8 bytes”.

  Here, when accessing the data string, the information processing apparatus 100 has a property of accessing each data in the section that is aligned and divided. Therefore, for example, when 8-byte data is stored in an aligned and divided section, the information processing apparatus 100 can acquire 8-byte data by one access. On the other hand, when the 8-byte data is stored across the aligned and separated positions, the information processing apparatus 100 acquires the data by two accesses. Specifically, the information processing apparatus 100 accesses a section storing the head portion of 8-byte data, and then accesses a section storing the tail portion of 8-byte data. 8-byte data is acquired.

  Returning to FIG. 3, the detection unit 302 detects preceding data and subsequent data that is the same data as the preceding data from the storage unit 301 that stores the data string. The subsequent data is, for example, the compression source data described above. The preceding data is, for example, reference destination data used for decompressing the compression source data.

  Specifically, for example, the detection unit 302 specifies the compression source data “compression” in the 24th to 34th bytes of the compression source data string dsB from the compression source data string dsB. Next, the detection unit 302 searches for reference destination data that is the same data as the compression source data from the compression source data string dsB.

  Then, the detection unit 302 identifies reference destination data “compression” in the first to eleventh bytes of the compression source data string dsB that is the same data as the compression source data. The identified data is stored in a storage area such as the RAM 203, the magnetic disk 205, and the optical disk 207, for example.

  Specifically, the detection unit 302 realizes its function by causing the processor 201 to execute a program stored in a storage device such as the ROM 202, the RAM 203, the magnetic disk 205, and the optical disk 207 illustrated in FIG. . Accordingly, the detection unit 302 can send the compression source data to be compressed and the reference destination data used for compression of the compression source data to the generation unit 303. Here, the specification of the compression source data and the reference destination data by the detection unit 302 will be described with reference to FIG.

  FIG. 5 is an explanatory diagram showing an example of a method for searching for reference destination data. In the example of FIG. 5, (11) the detection unit 302 extracts a combination of data for 3 bytes and a position where the data for 3 bytes starts from the compression source data string dsB. Specifically, the detection unit 302 extracts, for example, a combination of 3 bytes of data “com” and the “1” byte of the compression source data string dsB that is the position where “com” starts.

  Next, the detection unit 302 rearranges the extracted combinations so that 3 bytes of data are in alphabetical order. Specifically, for example, the detection unit 302 rearranges the extracted combinations using a radix sort (Radix sort). Radix sorting is one of the sorting algorithms. Since the radix sort is a conventional technique, the description is omitted here.

  (12) Then, the detection unit 302 identifies the preceding data and the succeeding data that are the same data in the rearranged combination, and identifies how many bytes before the succeeding data starts the preceding data. To do. Next, the detection unit 302 generates a search table 500 by associating the position of the subsequent data with the relative position of the preceding data with respect to the subsequent data.

  Specifically, for example, the detection unit 302 detects that the position of “com” is at the “1” byte, the “15” byte, and the “24” byte. Next, since “com” is in the “1” byte and the “15” byte, the detection unit 302 confirms that the position of the preceding data is “14 (15-1)” bytes before the position of the subsequent data. Is identified. Then, the detection unit 302 associates the position “15” byte of the subsequent data with the position of the preceding data “14 (15-1)” before the position of the subsequent data, and associates the search table with the search table. 500 is generated.

  (13) Next, the detection unit 302 specifies that the preceding data having the same data as the subsequent data “compress” in the 24th to 31st bytes of the compression source data string dsB is “9” bytes before. To do. In addition, the detection unit 302 identifies that the second preceding data that is the same data as the identified first preceding data is “23 (9 + 14)” bytes before. Further, the detection unit 302 specifies that the preceding data having the same data as the subsequent data “session” in the 30th to 34th bytes of the compression source data string dsB is “23” bytes before.

  As a result, the detection unit 302 specifies that the subsequent data “compress” and the subsequent data “session” both have preceding data that becomes the same data before “23” bytes. Then, the detection unit 302 employs data “compression” obtained by combining each subsequent data as the compression source data, and the reference destination data “compression” that is the same data as the compression source data is “23” bytes before the compression source data. Identifies that

  Here, the detection unit 302 employs data obtained by combining each subsequent data as the compression source data, but is not limited thereto. For example, the detection unit 302 may employ each subsequent data as separate compression source data.

  More specifically, for example, the detection unit 302 employs the subsequent data “compress” as the first compression source data, and the reference destination data “compress” that becomes the same data as the compression source data is obtained from the compression source data. It may be specified that it is 9 "bytes before. Further, the detection unit 302 employs the subsequent data “ion” that remains uncompressed as the second compression source data, and the reference destination data “ion” that becomes the same data as the compression source data becomes “ It may be specified that it is 23 ”bytes ago.

  Therefore, the data adopted as the compression source data by the detection unit 302 is not limited to data indicating a word. For example, the data adopted as the compression source data by the detection unit 302 may be data indicating a sentence including a plurality of words. Further, the data adopted as the compression source data by the detection unit 302 may be data indicating a part of a word.

  Here, the detection unit 302 uses the radix sort when rearranging the extracted combinations, but is not limited thereto. For example, the detection unit 302 may use merge sort. Further, the detection unit 302 uses the search method shown in FIG. 5, but is not limited thereto. For example, the detection unit 302 may use a search method using a hash table or a search method using a tree structure. A search method using a hash table and a search method using a tree structure are conventional techniques, and thus the description thereof is omitted here.

  Returning to FIG. 3, the generation unit 303 generates compressed data having the quotient and remainder obtained by dividing the position of the detected preceding data, the length of the preceding data that is equal to or longer than the predetermined length by the predetermined length. Here, in general, a remainder obtained by dividing a length obtained by subtracting a section length from the length of the preceding data by a predetermined length is less than the predetermined length, but is not limited thereto. For example, the remainder may be a predetermined length or more.

  More specifically, for example, when “20 bytes” is divided by “8 bytes”, “2” may be employed as the quotient and “4 bytes” may be employed as the remainder. Further, for example, when “20 bytes” is divided by “8 bytes”, “1” may be adopted as a quotient and “12 bytes” may be adopted as a remainder.

  Specifically, the generation unit 303 generates data indicating the relative position of the reference destination data specified by the detection unit 302, for example. Next, the generation unit 303 calculates a quotient and a remainder obtained by dividing the data length of the reference destination data by 8 bytes. Then, the generation unit 303 adopts the quotient calculated as described above as the number of data that can be divided and processed in units of 8 bytes in the reference destination data, and generates data indicating the adopted quotient.

  Next, after processing the reference data in units of 8 bytes, the generation unit 303 adopts the remainder calculated as described above as the fraction data length to be processed in units of 1 byte, and indicates the adopted remainder Generate data. And the production | generation part 303 produces | generates the compressed data which connected the produced | generated data. Next, the generation unit 303 generates a determination bit indicating that the compression source data has been compressed. In addition, when the compression source data cannot be compressed, the generation unit 303 may generate a determination bit indicating that the compression source data has not been compressed.

  In addition, the register width of another processor that executes restoration may be a multiple of the register width of the information processing apparatus 100. In this case, the generation unit 303 may generate compressed data having a quotient and a remainder obtained by dividing the position of the detected preceding data, the length of the preceding data that is greater than or equal to the predetermined length by a multiple of the predetermined length. As a result, even when the register width of the other processor that executes restoration is different from the register width of the processor 201 of the information processing apparatus 100, data compression is possible. The generated data is stored in a storage area such as the RAM 203, the magnetic disk 205, and the optical disk 207, for example.

  Specifically, the generation unit 303 realizes its function by causing the processor 201 to execute a program stored in a storage device such as the ROM 202, the RAM 203, the magnetic disk 205, and the optical disk 207 illustrated in FIG. . Thereby, the generation unit 303 can send the compressed data to be replaced with the compression source data to the storage unit 304.

  Here, the content of the compressed data generated by the generation unit 303 according to the first embodiment will be described with reference to FIGS. Specifically, the compression rule according to the first embodiment will be described with reference to FIG. 6, and an example of compressed data compressed with the compression rule illustrated in FIG. 6 will be described with reference to FIGS. 7 and 8.

  FIG. 6 is an explanatory diagram of a compression rule according to the first embodiment. As shown in FIG. 6, in the compression rule according to the first embodiment, the compressed data includes “13 bits” fixed length data 601 indicating the position of the reference destination data and “3 bits + 8” indicating the data length of the reference destination data. Variable length data having a data length that is a multiple of bits. The data length that is a multiple of 3 bits + 8 bits is, for example, 3 bits, 11 bits, or 19 bits.

  Fixed length data 601 indicating the position of the reference destination data indicates the data length from the position of the compressed data to the position of the reference destination data. Since the fixed length data 601 is “13 bits”, the data length from the position of the compressed data to the position of the reference destination data is indicated in the range of “0 bytes to 8191 bytes”.

  The variable length data indicating the data length of the reference destination data is “3-bit” data 602 when the data length of the reference destination data is less than “10” bytes. Since the variable length data 601 has a data length of “3 bits”, the data length of the reference destination data is indicated in the range of “3 bytes to 9 bytes”. Here, for example, when the variable length data 602 is “000”, the variable length data 602 indicates the decimal number “3” instead of the decimal number “0” corresponding to the binary number “000”.

  In the compression rule of the first embodiment, the data length of the compressed data is 2 bytes or more. Therefore, when the data length of the compression source data is “1 byte or 2 bytes”, the information processing apparatus 100 does not reduce the data size even if the compression is performed. Also good. Accordingly, since it is not necessary to indicate “0 bytes to 2 bytes” as the data length of the reference destination data, the variable length data 602 converts each binary number into a decimal number into “000 to 110”. Instead of “0-7”, “3-9” is associated.

  The variable length data indicating the data length of the reference destination data is “3 bits” data 602 and “5 bits” data when the data length of the reference destination data is “10” bytes or more and less than “256 bytes”. This is data obtained by concatenating 603 and “3-bit” data 604.

  Among the variable length data 602 to 604, the data 602 is “111”, indicating that the data length of the reference destination data is “10 bytes” or more, and the subsequent “8-bit” data 603, 604 is the reference destination. Indicates that the data indicates the data length.

  Of the variable length data 602 to 604, the data 603 indicates the number of pieces of data that can be obtained by dividing the reference destination data in units of “8 bytes”. Since the data 603 has a data length of “5 bits”, the number is indicated in a range of “1 to 31”. In other words, the data 603 indicates one of data lengths that are multiples of 8 within the range of “8 bytes to 248 bytes”. In the compression rule of the first embodiment, since it is not necessary to indicate “0” as the number of data that can be obtained by being divided in units of “8 bytes”, the data 603 includes two pieces of data “00000 to 11110”. Instead of “0-30” converted from decimal numbers to decimal numbers, “1-31” are associated.

  Data 604 indicates a fraction data length obtained by subtracting “8 bytes” corresponding to the number indicated by the data 603 from the data length of the reference destination data. Here, since the data length of the data 604 is “3 bits”, the fraction data length is indicated in the range of “0 bytes to 7 bytes”.

  Further, the data length of the reference destination data may be “256 bytes” or more. In this case, the variable length data indicating the data length of the reference destination data is obtained by concatenating “3 bits” data 602, “5 bits” data 603, “3 bits” data 604, and “8 bits” data 605. Data. Since the data 602 and 604 are the same as the case where the data length of the reference destination data is “10 bytes” or more and less than “256 bytes”, the description is omitted here.

  Of the variable length data 602 to 605, the data 603 is “11111”, which indicates that the number of pieces of data that can be obtained by dividing the reference destination data in units of “8 bytes” is “31” or more. The data 603 indicates that the subsequent “8-bit” data 605 is data indicating the number of pieces of data that can be obtained by dividing the reference destination data in units of “8 bytes”.

  Among the variable length data 602 to 605, the data 605 is indirect by indicating how many pieces of data that can be obtained by dividing the reference destination data in units of “8 bytes” more than “31”. Shows the number of data. Since the data 605 has a data length of “8 bits”, the data 605 indicates how many more than the number “31” is in a range of “1 to 255”.

  As a result, the data 605 indicates the number of pieces of data that can be acquired in units of “8 bytes” among the reference destination data in the range of “32 to 286 (31 + 1 to 31 + 255)”. In other words, the data 605 indicates one of data lengths that are multiples of 8 within the range of “256 bytes to 2040 bytes”.

  Thereafter, the variable length data indicating the data length of the reference destination data is updated each time the number of data that can be obtained by dividing in units of “8 bytes” described above cannot be indicated by the data length being used to indicate the number. Is added with 8-bit data for indicating the number. Then, using the added 8-bit data, the number of pieces of data that can be obtained by being divided in units of “8 bytes” is indicated.

  7 and 8 are explanatory diagrams illustrating an example of uncompressed data that has not been compressed, and an example of compressed data that has been compressed according to the compression rule illustrated in FIG. 6.

  FIG. 7A shows an example of uncompressed data that has not been compressed. FIG. 7B shows an example of compressed data when compression source data having a data length of 9 bytes or less is compressed. FIG. 7C shows an example (part 1) of compressed data when compression source data having a data length longer than 9 bytes is compressed. FIG. 8D shows an example (part 2) of compressed data when compression source data having a data length longer than 9 bytes is compressed.

  As shown in FIG. 7A, the data included in the compression source data string dsC may be data dC that cannot be compressed. In this case, the generation unit 303 sends the non-compressible data dC as it is to the storage unit 304 as uncompressed data ndC. Further, the generation unit 303 generates a determination bit bC “0” indicating that compression is not performed.

  As illustrated in FIG. 7B, the compression source data string dsD includes compression source data tdD and reference destination data rdD that are the same data, and the compression source data tdD may be “9 bytes” or less. In this case, the generation unit 303 generates “00000000000010 (10)” indicating “13 bits” and the relative position “10” of the reference destination data rdD.

  Next, the generation unit 303 generates “001 (4)” indicating the data length “4 bytes” of the reference destination data rdD with “3 bits”. Then, the generation unit 303 generates compressed data cdD “00000000000010 (10) 001 (4)” obtained by concatenating the generated data. Further, the generation unit 303 generates a determination bit bD “1” indicating that compression has been performed.

  As shown in FIG. 7C, the compression source data string dsE includes compression source data tdE and reference destination data rdE that become the same data, and the compression source data tdE may be larger than “9 bytes”. Here, it is assumed that the second byte from the position of the compression source data tdE is a position that is aligned and separated from the head of the compression source data string dsE.

  In this case, the generation unit 303 generates “0000000010100 (20)” that indicates “13 bits” and indicates the relative position “20” of the reference destination data rdE. Next, the generation unit 303 generates “111 (10)” indicating that “3 bits” and the data length of the reference destination data rdE is greater than “9 bytes”.

  Then, the generation unit 303 calculates the number “1” of data that can be divided and processed in units of 8 bytes by dividing the data length “11 bytes” of the reference destination data rdE “compression” by “8 bytes”. . Next, the generation unit 303 generates data “00000 (1)” indicating the number of data “1” that can be divided and processed in units of 8 bytes.

  Then, the generation unit 303 calculates the fraction data length “3 bytes” by subtracting “8 bytes” for the calculated number from the data length of the reference destination data rdE “compression”. Next, the generation unit 303 generates data “011 (3)” indicating the fraction data length “3” to be processed in units of 1 byte. Then, the generation unit 303 generates compressed data cdE “0000000010100 (20) 111 (10) 00000 (1) 011 (3)” obtained by concatenating the generated data. In addition, the generation unit 303 generates a determination bit bE “1” indicating compression.

  As illustrated in FIG. 8D, the compression source data string dsF includes compression source data tdF and reference destination data rdF that are the same data, and the compression source data tdF may be larger than “9 bytes”. Here, it is assumed that the second byte from the position of the compression source data tdF is aligned and separated from the head of the compression source data string dsF.

  In this case, the generation unit 303 generates “0010001100000 (1120)” indicating the relative position “1120” of the reference destination data rdF with “13 bits”. Next, the generation unit 303 generates “111 (10)” indicating that “3 bits” and the data length of the reference destination data rdF is greater than “9 bytes”.

  Then, the generation unit 303 divides the data length “303 bytes” of the reference destination data rdF by “8 bytes” to calculate the number of data “37” that can be divided and processed in units of 8 bytes. Next, the generation unit 303 generates data “11111 (32)” indicating that the number is 5 bits and larger than “31” in order to indicate the number of data “37” that can be processed in units of 8 bytes. To do. Then, the generation unit 303 generates data “00000101 (31 + 6 = 37)” indicating the number “37” by indicating “6” which is a shortage from “31” to “37” in 8 bits.

  Next, the generation unit 303 calculates a fraction data length “7” by subtracting “8 bytes” for the calculated number from the data length of the reference destination data rdF “compression”. Next, the generation unit 303 generates data “111 (7)” indicating the fraction data length “7” to be processed in units of 1 byte. Then, the generation unit 303 generates compressed data cdF “0010001100000 (1120) 111 (10) 11111 (32) 111 (7) 00000101 (37)” obtained by concatenating the generated data. In addition, the generation unit 303 generates a determination bit bF “1” indicating that compression has been performed.

  Returning to FIG. 3, the storage unit 304 stores the data string obtained by replacing the subsequent data with the generated compressed data. Specifically, for example, the storage unit 304 generates a compressed data string in which the compression source data in the compression source data string dsB is replaced with the compressed data. Next, the storage unit 304 stores the discrimination bit string and the compressed data string. An example of storing the discrimination bit string and the compressed data string will be described later with reference to FIG.

  Specifically, the storage unit 304 realizes its function by causing the processor 201 to execute a program stored in a storage device such as the ROM 202, the RAM 203, the magnetic disk 205, and the optical disk 207 illustrated in FIG. . As a result, the storage unit 304 can reduce the memory size of the data string. As a result, the information processing apparatus 100 can reduce the size of the storage area to be used when storing the data string, as compared with the case where the data string is stored without being compressed. Further, when transmitting the data string to another computer, the information processing apparatus 100 can reduce the transmission time by compressing the data string and transmitting the data string.

(Data stream compression flow)
Next, the flow of data string compression by the information processing apparatus 100 according to the first embodiment will be described with reference to FIGS. 9 to 14.

  9 to 14 are explanatory diagrams illustrating a flow of data string compression by the information processing apparatus 100 according to the first embodiment. In FIG. 9, the information processing apparatus 100 first inputs the compression source data string dsB by the operation of the input device such as the keyboard 210 and the mouse 211 by the user of the information processing apparatus 100. Next, the information processing apparatus 100 stores the input compression source data string dsB in the input buffer.

  Then, the information processing apparatus 100 sets the compression pointer 900 at the head of the compression source data string dsB stored in the input buffer. Next, the information processing apparatus 100 sets a determination buffer 910 that stores a determination bit string and a compression buffer 920 that stores a compressed data string. Then, the information processing apparatus 100 starts compressing the compression source data string dsB.

  In FIG. 9, (21) the information processing apparatus 100 acquires “3 bytes” of data “com” starting from the position indicated by the compression pointer 900. Next, the information processing apparatus 100 searches for preceding data that becomes the same data as the acquired data “com” from the head side from the position indicated by the compression pointer 900.

  Here, specifically, for example, the information processing apparatus 100 refers to the search table 500 illustrated in FIG. 5 and acquires the position information “0” of the preceding data corresponding to the position indicated by the compression pointer 900. Next, since the position information is “0”, the information processing apparatus 100 determines that there is no preceding data that becomes the same data as the data “com” starting from the position indicated by the compression pointer 900 and the data “com” cannot be compressed. To do.

  (22) The information processing apparatus 100 stores the data “c” at the position indicated by the compression pointer 900 as it is in the compression buffer 920 as data that could not be compressed. (23) Further, the information processing apparatus 100 stores the determination bit “0” indicating that the data “c” at the position indicated by the compression pointer 900 could not be compressed in the determination buffer 910.

  Next, the information processing apparatus 100 shifts the compression pointer 900 by “1 byte” toward the end, and proceeds to the processing of FIG.

  10, (24) the information processing apparatus 100 acquires “3 bytes” of data “omp” starting from the position indicated by the compression pointer 900 as in FIG. 9. Next, the information processing apparatus 100 searches for preceding data that becomes the same data as the acquired data “omp” from the head side from the position indicated by the compression pointer 900. The information processing apparatus 100 determines that the data “omp” cannot be compressed because there is no preceding data that becomes the same data as the data “omp” starting from the position indicated by the compression pointer 900.

  (25) Next, the information processing apparatus 100 stores the data “o” at the position indicated by the compression pointer 900 as is in the compression buffer 920 as data that could not be compressed. (26) Further, the information processing apparatus 100 stores the determination bit “0” indicating that the data “o” at the position indicated by the compression pointer 900 could not be compressed in the determination buffer 910.

  Next, the information processing apparatus 100 shifts the compression pointer 900 by “1 byte” toward the end, and proceeds to the processing of FIG.

  In FIG. 11, (27) the information processing apparatus 100 acquires “3 bytes” of data “mpr” starting from the position indicated by the compression pointer 900 in the same manner as in FIG. Next, the information processing apparatus 100 searches for preceding data that is the same data as the acquired data “mpr” from the beginning of the position indicated by the compression pointer 900. The information processing apparatus 100 determines that the data “mpr” cannot be compressed because there is no preceding data that becomes the same data as the data “mpr” starting from the position indicated by the compression pointer 900.

  (28) Next, the information processing apparatus 100 stores the data “m” at the position indicated by the compression pointer 900 as it is in the compression buffer 920 as data that could not be compressed. (29) Further, the information processing apparatus 100 stores the determination bit “0” indicating that the data “m” at the position indicated by the compression pointer 900 could not be compressed in the determination buffer 910.

  Thereafter, the information processing apparatus 100 stores the data at the positions “4th byte” to “14th byte” of the compression source data in the compression buffer 920 without being compressed in the same manner as in FIGS. 9 to 11. Suppose that Next, the information processing apparatus 100 shifts the compression pointer 900 by “1 byte” toward the end, and proceeds to the processing of FIG.

  In FIG. 12, (30) the information processing apparatus 100 acquires “3 bytes” of data “com” starting from the position indicated by the compression pointer 900. Next, the information processing apparatus 100 searches for preceding data that becomes the same data as the acquired data “com” from the head side from the position indicated by the compression pointer 900.

  Here, specifically, for example, the information processing apparatus 100 refers to the search table 500 illustrated in FIG. 5 and acquires the position information “14” of the preceding data corresponding to the position indicated by the compression pointer 900. Next, since the position information is “14”, the information processing apparatus 100 determines that the preceding data having the same data as the data “com” starting from the position indicated by the compression pointer 900 is “14 bytes before”. Therefore, the information processing apparatus 100 determines that “com” can be compressed.

  Here, the information processing apparatus 100 determines whether or not the data at the end of “com” can be compressed together with “com”. Specifically, for example, the information processing apparatus 100 acquires the position information “14” of the preceding data corresponding to the position “1 byte” at the end of the position indicated by the compression pointer 900.

  Here, the acquired position information “14” of the preceding data is the same as the position information “14” of the preceding data corresponding to the position indicated by the compression pointer 900. Therefore, the information processing apparatus 100 determines that the data “com” at the position indicated by the compression pointer 900 can be compressed and “omp” at the end of “one byte” from the position indicated by the compression pointer 900 can be compressed. To do.

  In other words, the information processing apparatus 100 determines that “4 bytes” of data “comp” starting from the position indicated by the compression pointer 900 can be compressed using the preceding data “comp” at “14 bytes before”. To do.

  Similarly, the information processing apparatus 100 can compress the “compress” of “8 bytes” starting from the position indicated by the compression pointer 900 by using the preceding data “compress” at “14 bytes before”. Is determined.

  Next, the information processing apparatus 100 generates “13-bit” data “0000000001110 (14)” indicating the relative position of the reference destination data. Further, the information processing apparatus 100 generates “3-bit” data “101 (8)” indicating the data length of the reference destination data. Next, the information processing apparatus 100 generates compressed data “0000000001110 (14) 101 (8)” obtained by concatenating the generated data. Hereinafter, the compressed data “0000000001110 (14) 101 (8)” is represented as compressed data “14,8”.

  (31) The information processing apparatus 100 stores the compressed data “14, 8” in the compression buffer 920 instead of the data “compress” starting from the position indicated by the compression pointer 900. (32) Further, the information processing apparatus 100 stores the determination bit “1” indicating that the data “compress” starting from the position indicated by the compression pointer 900 is compressed in the determination buffer 910.

  Next, the information processing apparatus 100 shifts the compression pointer 900 to “8 bytes”, which is the data length of the compressed data, toward the end side, and performs the same processing as in FIGS. Assume that the data “(blank)” at the position of the “23rd byte” is stored in the compression buffer 920 without being compressed. Then, the information processing apparatus 100 shifts the compression pointer 900 to “1 byte” toward the end, and proceeds to the processing of FIG.

  In FIG. 13, (33) the information processing apparatus 100 acquires “3 bytes” of data “com” starting from the position indicated by the compression pointer 900. Next, the information processing apparatus 100 searches for preceding data that becomes the same data as the acquired data “com” from the head side from the position indicated by the compression pointer 900.

  Here, as in FIG. 12, the information processing apparatus 100 uses the data “compression” of “11 bytes” starting from the position indicated by the compression pointer 900 and the preceding data “compression” at “23 bytes before”. And determine that compression is possible.

  Next, the information processing apparatus 100 generates “13-bit” data “0000000010111 (23)” indicating the relative position of the reference destination data. Then, the information processing apparatus 100 generates “3 bit” data “111 (10)” indicating that the data length of the reference destination data is longer than 9 bytes.

  Next, since the data length of the reference destination data is “11 bytes”, the information processing apparatus 100 generates data “00000 (1)” indicating the number of data “1” that can be divided and processed in units of 8 bytes. To do. The information processing apparatus 100 generates data “011 (3)” indicating the fraction data length “3 bytes” to be processed in units of 1 byte after processing the reference destination data in units of 8 bytes. Next, the information processing apparatus 100 generates compressed data “0000000010111 (23) 111 (10) 00000 (1) 011 (3)” obtained by concatenating the generated data. Hereinafter, the compressed data “0000000010111 (23) 111 (10) 00000 (1) 011 (3)” is expressed as compressed data “23, 1, 3”.

  (34) The information processing apparatus 100 stores the compressed data “23, 1, 3” in the compression buffer 920 instead of the data “compression” starting from the position indicated by the compression pointer 900. (35) Further, the information processing apparatus 100 stores the determination bit “1” indicating that the data “compression” starting from the position indicated by the compression pointer 900 is compressed in the determination buffer 910.

  Next, the information processing apparatus 100 shifts the compression pointer 900 toward the end side by “11 bytes” which is the data length of the compressed data, and performs the same processing as in FIGS. It is assumed that the data “.” At the position “34th byte” is stored in the compression buffer 920 without being compressed.

  FIG. 14 shows a compressed data string compressed by the processing described with reference to FIGS. As shown in FIG. 14, the discrimination bit string bsG stored in the discrimination buffer 910 is “18 bits”. The compressed data string cdsG stored in the compression buffer 920 is “21 bytes”.

  Therefore, the information processing apparatus 100 has converted the compression source data string dsB of “35 bytes” into the discrimination bit string bsG of “18 bits” and the compressed data string cdsG of “21 bytes”. In other words, the information processing apparatus 100 can reduce the data length of the data string by a data length of “(35 bytes) − (21 bytes + 18 bits) = (11 bytes + 6 bits)”.

  Thus, the information processing apparatus 100 can reduce the size of the data string. As a result, the information processing apparatus 100 can reduce the size of the storage area to be used when storing the data string, as compared with the case where it is stored without compression. Further, when transmitting the data string to another computer, the information processing apparatus 100 can reduce the transmission time by compressing the data string and transmitting the data string.

(Example of saving discrimination bit string and compressed data string)
Next, a storage example in the case where the determination bit string bsG and the compressed data string cdsG illustrated in FIG. 14 are stored in the storage device will be described with reference to FIG. Here, the storage device is, for example, the ROM 202, the RAM 203, the magnetic disk 205, the optical disk 207, etc. shown in FIG.

  FIG. 15 is an explanatory diagram illustrating a storage example of the discrimination bit string bsG and the compressed data string cdsG illustrated in FIGS. 7 to 14. FIG. 15A shows a storage example 1 of the discrimination bit string bsG and the compressed data string cdsG. FIG. 15B shows a storage example 2 of the discrimination bit string bsG and the compressed data string cdsG. FIG. 15C shows a storage example 3 of the discrimination bit string bsG and the compressed data string cdsG.

  As shown in FIG. 15A, for example, the information processing apparatus 100 stores the determination bit string bsG together in the address width section at the head of the storage device and stores the compressed data string cdsG in the subsequent address width section. Can be saved together. Further, for example, the information processing apparatus 100 may store padding at the end of the stored discrimination bit string bsG to adjust the data string in address width units, or store padding at the end of the stored compressed data string cdsG. Then, it may be adjusted to a data string in address width units.

  Specifically, for example, the determination bit string bsG and the compressed data string cdsG are stored in the storage device in the order of “determination bit string bsG → padding → compressed data string cdsG → padding”. The information processing apparatus 100 can write and read the discrimination bit string bsG collectively by storing it as shown in FIG.

  As shown in FIG. 15B, the information processing apparatus 100, for example, assigns each discrimination bit to the top of uncompressed data or compressed data corresponding to each discrimination bit in order from the top of the storage device. Can be saved. Further, for example, the information processing apparatus 100 may store padding at the end of the stored data string and adjust the stored data string to data in byte units.

  Specifically, for example, the determination bit string bsG and the compressed data are stored in the storage device in the order of “determination bit → uncompressed data → determination bit → uncompressed data →... → determination bit → compressed data →. The column cdsG is saved. The information processing apparatus 100 stores the determination bit string bsG and the compressed data string cdsG in the order used for restoration by storing as shown in FIG. Random access can be suppressed.

  As illustrated in FIG. 15C, the information processing apparatus 100 stores, for example, “1 byte” of the determination bit group sequentially from the top of the storage device, and corresponds to each determination bit of the stored determination bit group. The uncompressed data or the compressed data to be stored can be stored after the discrimination bit group. Further, when the discrimination bit group is less than “1 byte”, the information processing apparatus 100 may store padding at the end of the discrimination bit group and adjust the discrimination bit group to “1 byte”.

  Specifically, for example, in the storage device, “1 byte determination bit → 8 bytes of uncompressed data or compressed data →... → 2 bits determination bit and 6 bits padding → 2 bytes The determination bit string bsG and the compressed data string cdsG are stored in the order of “uncompressed data and compressed data →. By saving the information processing apparatus 100 as shown in FIG. 15C, the address where the discrimination bit, the compressed data, and the non-compressed data are stored can be changed to an address delimited in units of bytes. For this reason, the information processing apparatus 100 does not need to perform bit shift when accessing each data, and can reduce the time required for accessing each data.

(Data string compression processing)
Next, a detailed processing procedure of the data string compression processing for realizing the compression of the data strings shown in FIGS. 7 to 14 will be described with reference to FIG.

  FIG. 16 is a flowchart showing a detailed processing procedure of the data string compression processing for realizing the compression of the data string shown in FIGS. As shown in FIG. 16, the information processing apparatus 100 first detects preceding data that becomes the same data as subsequent data at the position indicated by the compression pointer 900 from the compression source data in the input buffer (step S1601). .

  Next, the information processing apparatus 100 determines whether preceding data has been detected (step S1602). If the preceding data is not detected (step S1602: No), the information processing apparatus 100 generates a determination bit “0” indicating that compression is not performed, and stores the determination bit “0” in the determination buffer 910 (step S1603).

  Next, the information processing apparatus 100 stores the data for the first byte of the subsequent data as it is in the compression buffer 920 (step S1604). Then, the information processing apparatus 100 shifts the compression pointer 900 toward the end of “one byte” (step S1605).

  Next, the information processing apparatus 100 determines whether or not the compression has ended (step S1606). Here, when the compression is completed (step S1606: Yes), the information processing apparatus 100 ends the data string compression process.

  On the other hand, if the compression has not ended (step S1606: No), the information processing apparatus 100 returns to step S1601. The information processing apparatus 100 processes data that cannot be compressed by the processing through steps S1601 to S1606.

  On the other hand, when preceding data is detected in step S1602 (step S1602: Yes), the information processing apparatus 100 generates a determination bit “1” indicating compression and stores it in the determination buffer 910 (step S1607). ).

  Next, the information processing apparatus 100 determines whether or not the data length of the preceding data is longer than 9 bytes (step S1608). If the data length of the preceding data is 9 bytes or less (step S1608: No), the information processing apparatus 100 generates data indicating the position of the preceding data and data indicating the data length of the preceding data. And stored in the compression buffer 920 (step S1609).

  Next, the information processing apparatus 100 shifts the compression pointer 900 toward the end of “the data length of the preceding data” (step S1610). Then, the information processing apparatus 100 proceeds to step S1606. By the processing through steps S1601, S1602, S1607 to S1610, and S1606, the information processing apparatus 100 compresses compressible data having a data length of 9 bytes or less.

  On the other hand, when the data length of the preceding data is longer than 9 bytes in step S1608 (step S1608: Yes), the information processing apparatus 100 determines that the data indicating the position of the preceding data and the data length of the preceding data are longer than 9 bytes. And data indicating Next, the information processing apparatus 100 stores the generated data in the compression buffer 920 (step S1611).

  Then, the information processing apparatus 100 calculates a quotient and a remainder obtained by dividing the data length of the preceding data by the register width, generates data indicating the calculated quotient, and data indicating the calculated remainder, and generates a compressed buffer. It stores in 920 (step S1612).

  Next, the information processing apparatus 100 proceeds to step S1610. The information processing apparatus 100 compresses compressible data having a data length longer than 9 bytes by the processing through steps S1601, S1602, S1607, S1608, S1611, S1612, S1610, and S1606.

  As a result, the information processing apparatus 100 can specify the number of data that can be processed by dividing the reference destination data in register width units and the fractional bytes that should be processed in 1-byte units in decompression of the compression source data. Compressed data can be generated.

(Restoration of the compression source data string dsB by the information processing apparatus 100 according to the first embodiment)
Next, decompression of the compression source data string dsB by the information processing apparatus 100 according to the first embodiment is illustrated in FIGS.

(Functional configuration example relating to decompression of the compression source data string dsB of the information processing apparatus 100 according to the first embodiment)
First, a functional configuration example relating to the decompression of the compression source data string dsB of the information processing apparatus 100 according to the first embodiment will be described with reference to FIG. FIG. 17 is a block diagram of an example of a functional configuration related to the decompression of the compression source data string dsB of the information processing apparatus 100 according to the first embodiment. The information processing apparatus 100 includes a storage unit 1701, a detection unit 1702, an acquisition unit 1703, and a storage unit 1704.

  The storage unit 1701 is a compressed data including a reference position of uncompressed data to be referred to, compressed data having a quotient and a remainder obtained by dividing the length of the uncompressed data that is greater than or equal to a predetermined length by a predetermined length, and the uncompressed data Remember the column. The uncompressed data serving as a reference destination is, for example, the reference destination data described above. The predetermined length is a register width that is a power of 2, and is, for example, the above-described 8 bytes.

  The compressed data includes, for example, data “0000000001110 (14)” indicating the relative position “14” of the reference destination data. The compressed data includes, for example, data “111 (10)” indicating that the reference destination data is 10 bytes or more. The compressed data includes, for example, data “00000 (1)” indicating the number of data “1” that can be divided and processed in units of 8 bytes, and data indicating the fraction data length “3” to be processed in units of 1 byte. “011 (3)”.

  Specifically, the storage unit 1701 stores, for example, a compressed data string including compressed data and non-compressed data, and a discrimination bit string. Specifically, the storage unit 1701 realizes its function by a storage device such as the ROM 202, the RAM 203, the magnetic disk 205, and the optical disk 207 shown in FIG. Accordingly, the detection unit 1702 can acquire the compressed data string and the discrimination bit string stored in the storage unit 1701.

  The detection unit 1702 detects compressed data from the storage unit 1701. Specifically, for example, the detection unit 1702 acquires a determination bit from the determination bit string, and determines whether the data corresponding to the acquired determination bit is uncompressed data or compressed data.

  Next, when it is determined that the data is compressed data, the detection unit 1702 detects “1 byte” of data “0000000001110 (14) 111 (10)” corresponding to the determination bit. Here, the detection unit 1702 has “111 (10)” indicating that the data length of the reference destination data is longer than “9 bytes” because the end “3 bits” of the detected data is “1 byte”. "00000 (1) 011 (3)" is further detected.

  In this manner, the detection unit 1702 detects the compressed data “0000000001110 (14) 111 (10) 00000 (1) 011 (3)”. Specifically, the detection unit 1702 realizes its function by causing the processor 201 to execute a program stored in a storage device such as the ROM 202, the RAM 203, the magnetic disk 205, and the optical disk 207 illustrated in FIG. . Accordingly, the acquisition unit 1703 can acquire reference destination data using the compressed data detected by the detection unit 1702.

  The acquisition unit 1703 acquires, in a predetermined length unit, a first data string having a length obtained by multiplying a predetermined length by a quotient among reference destination data starting from a reference position included in the detected compressed data. In addition, the acquisition unit 1703 acquires a second data string having a surplus length obtained by removing the first data string from the reference destination data.

  Specifically, the acquisition unit 1703 specifies, for example, from “0000000001110 (14)” in the compressed data that the position of the reference destination data is “14 bytes” ahead of the position of the compressed data. .

  Next, the acquisition unit 1703 obtains “8 bytes” of data, which is obtained by multiplying “8 bytes” by the quotient indicated by “00000 (1)” in the compressed data among the reference destination data starting from the specified position. Collected in units of 8 bytes. Further, the acquisition unit 1703 acquires the extra “3 bytes” of data indicated by “011 (3)” in the compressed data for each “1 byte”.

  In addition, the register width of another processor that has performed compression may be a multiple of the register width of the processor 201 of the information processing apparatus 100. In this case, the acquisition unit 1703 has a predetermined length that is a length obtained by multiplying the first data string and a multiple of a predetermined length by a quotient in order from the top of the reference destination data starting from the reference position included in the detected compressed data. The second data string in the long unit and the third data string may be acquired.

  Specifically, the acquisition unit 1703 realizes its function by causing the processor 201 to execute a program stored in a storage device such as the ROM 202, the RAM 203, the magnetic disk 205, and the optical disk 207 illustrated in FIG. . Thereby, the acquisition unit 1703 can send the reference destination data to be replaced with the compressed data to the storage unit 1704.

  The storage unit 1704 writes the first data string acquired in units of a predetermined length in a predetermined storage area, and writes the acquired second data string in a predetermined storage area. Specifically, the storage unit 1704 stores, for example, “compress” acquired in “8-byte units” in the reference buffer data “compression” in the restoration buffer, and the acquired “ion” of “3 bytes”. Is stored in the restore buffer.

  Specifically, the storage unit 1704 realizes its function by causing the processor 201 to execute a program stored in a storage device such as the ROM 202, the RAM 203, the magnetic disk 205, and the optical disk 207 illustrated in FIG. . Accordingly, the storage unit 1704 can replace the compressed data with the duplicate data of the reference destination data, and can restore the compression source data.

  The storage unit 1704 stores the data determined as non-compressed data by the detection unit 1702 as it is in the restoration buffer. As a result, the storage unit 1704 can store uncompressed data that may become reference data in the decompression buffer.

(Flow of decompression of compression source data string dsB)
Next, the flow of decompression of the compression source data string dsB by the information processing apparatus 100 according to the first embodiment will be described with reference to FIGS.

  18 to 23 are explanatory diagrams illustrating a flow of decompression of the compression source data string dsB by the information processing apparatus 100 according to the first embodiment. In FIG. 18, first, the information processing apparatus 100 sets a discrimination pointer 1810 at the head of the discrimination bit string. Next, the information processing apparatus 100 sets a restoration pointer 1820 at the head of the compressed data string. Then, the information processing apparatus 100 sets the decompression buffer 1800 that stores the decompressed compression source data string dsB.

  18, (41) the information processing apparatus 100 detects the determination bit at the position indicated by the determination pointer 1810. (42) Next, the information processing apparatus 100 determines that the data at the position indicated by the restoration pointer 1820 is uncompressed data because the detected discrimination bit is “0”, and the position indicated by the restoration pointer 1820 The data “c” is acquired.

  (43) The information processing apparatus 100 stores the acquired uncompressed data “c” in the restoration buffer 1800 as it is. Next, the information processing apparatus 100 shifts the determination pointer 1810 toward the end of “1 bit”, shifts the restoration pointer 1820 toward the end of “1 byte”, and proceeds to the processing of FIG.

  19, (44) the information processing apparatus 100 detects the discrimination bit at the position indicated by the discrimination pointer 1810, as in FIG. (45) Next, the information processing apparatus 100 determines that the data at the position indicated by the restoration pointer 1820 is non-compressed data because the detected discrimination bit is “0”, and the position indicated by the restoration pointer 1820 The data “o” in is acquired.

  (46) The information processing apparatus 100 stores the acquired uncompressed data “o” in the restoration buffer 1800 as it is. Next, the information processing apparatus 100 shifts the determination pointer 1810 toward the end of “1 bit”, shifts the restoration pointer 1820 toward the end of “1 byte”, and proceeds to the processing of FIG.

  20, (47) the information processing apparatus 100 detects the discrimination bit at the position indicated by the discrimination pointer 1810 in the same manner as in FIG. (48) Next, the information processing apparatus 100 determines that the data at the position indicated by the restoration pointer 1820 is uncompressed data because the detected discrimination bit is “0”, and the position indicated by the restoration pointer 1820 The data “m” in is acquired.

  (49) The information processing apparatus 100 stores the acquired uncompressed data “m” in the restoration buffer 1800 as it is. Thereafter, the information processing apparatus 100 stores the data at the positions of the “first byte” to the “14th byte” of the compressed data in the restoration buffer 1800 as they are, as in FIGS. To do. Next, the information processing apparatus 100 shifts the determination pointer 1810 toward the end of “1 bit”, shifts the restoration pointer 1820 toward the end of “1 byte”, and proceeds to the processing of FIG.

  In FIG. 21, (50) the information processing apparatus 100 detects the discrimination bit at the position indicated by the discrimination pointer 1810. (51) Next, since the detected determination bit is “1”, the information processing apparatus 100 determines that the data at the position indicated by the restoration pointer 1820 is compressed data, and places the data at the position indicated by the restoration pointer 1820. A certain data “14, 8” is acquired.

  (52) The information processing apparatus 100 refers to the acquired compressed data “14, 8” and determines that the reference destination data is “14 bytes before” the compressed data. Next, the information processing apparatus 100 refers to the acquired compressed data “14, 8”, acquires “8 bytes” of reference destination data in units of 1 byte, and stores it in the restoration buffer 1800.

  Next, it is assumed that the information processing apparatus 100 shifts the discrimination pointer 1810 toward the end of “1 byte” and shifts the decompression pointer 1820 toward the end of “2 bytes” that is the data length of the compressed data. Then, it is assumed that the information processing apparatus 100 stores the uncompressed data “(blank)” at the position indicated by the restoration pointer 1820 in the restoration buffer 1800 in the same manner as in FIGS. Next, the information processing apparatus 100 shifts the determination pointer 1810 toward the end of “1 bit”, shifts the restoration pointer 1820 toward the end of “1 byte”, and proceeds to the processing of FIG.

  22, (53) the information processing apparatus 100 detects the discrimination bit at the position indicated by the discrimination pointer 1810. (54) Next, since the detected determination bit is “1”, the information processing apparatus 100 determines that the data at the position indicated by the restoration pointer 1820 is compressed data, and places the data at the position indicated by the restoration pointer 1820. Some data “23, 1, 3” is acquired.

  (55) The information processing apparatus 100 refers to the acquired compressed data “23, 1, 3” and determines that the reference destination data is “23 bytes before” the compressed data. Next, the information processing apparatus 100 refers to the acquired compressed data “23, 1, 3”, and the number of data that can be processed by dividing the reference destination data into “8-byte units” is “one time”. Identifies it. Then, the information processing apparatus 100 acquires the first “8 bytes” of data “compress” from the top of the reference destination data, and stores it in the restoration buffer 1800.

  Next, the information processing apparatus 100 refers to the acquired compressed data “23, 1, 3” and determines that the fraction data length to be processed in “1-byte units” for the reference destination data is “3 bytes”. Identify. The information processing apparatus 100 acquires the data “compress” from the reference destination data, acquires the remaining data “ion” in units of 1 byte, and stores it in the restoration buffer 1800.

  Next, it is assumed that the information processing apparatus 100 shifts the determination pointer 1810 toward the end of “1 byte” and shifts the decompression pointer 1820 toward the end of “3 bytes” that is the data length of the compressed data. Then, it is assumed that the information processing apparatus 100 stores the uncompressed data “.” At the position indicated by the restoration pointer 1820 in the restoration buffer 1800 in the same manner as in FIGS.

  FIG. 23 shows the compression source data string dsB restored by the processing described with reference to FIGS. As illustrated in FIG. 23, the information processing apparatus 100 can restore the compression source data string dsB to the restoration buffer 1800 without loss.

  In this way, in the decompression of the compression source data string dsB, the information processing apparatus 100 obtains the reference destination data that can be acquired in units of 8 bytes, acquires the data in units of 8 bytes, and stores it in the recovery buffer 1800. As a result, the information processing apparatus 100 can effectively use the register width to shorten the time taken to restore the compression source data string dsB.

(Compression source data string restoration processing)
Next, with reference to FIG. 24, a detailed processing procedure of the compression source data sequence decompression processing for realizing the decompression of the compression source data sequence dsB illustrated in FIGS. 18 to 23 will be described.

  FIG. 24 is a flowchart showing a detailed processing procedure of the compression source data sequence decompression processing for realizing the decompression of the compression source data sequence dsB shown in FIGS. As shown in FIG. 24, the information processing apparatus 100 first obtains a discrimination bit at the position indicated by the discrimination pointer 1810 (step S2401).

  Next, the information processing apparatus 100 refers to the obtained determination bit and determines whether or not the data at the position indicated by the restoration pointer 1820 is compressed data (step S2402). If the data is uncompressed data (step S2402: NO), the information processing apparatus 100 acquires 1-byte data at the position indicated by the restoration pointer 1820 and stores it in the restoration buffer 1800 (step S2403).

  Next, the information processing apparatus 100 shifts the determination pointer 1810 toward the end of “1 byte” and shifts the restoration pointer 1820 toward the end of “1 byte” (step S2404). Then, the information processing apparatus 100 determines whether the restoration is finished (step S2405). Here, when the restoration ends (step S2405: Yes), the information processing apparatus 100 ends the compression source data string restoration process.

  On the other hand, when the restoration is not completed (step S2405: No), the information processing apparatus 100 returns to step S2401. The information processing apparatus 100 processes the uncompressed data by the processing through the above steps S2401 to S2405.

  On the other hand, if it is compressed data in step S2402 (step S2402: Yes), the information processing apparatus 100 refers to the compressed data and acquires the position of the reference destination data and the data length of the reference destination data ( Step S2406).

  Next, the information processing apparatus 100 determines whether or not the data length of the acquired reference destination data is longer than 9 bytes (step S2407). Here, when the data length of the reference destination data is 9 bytes or less (step S2407: No), the information processing apparatus 100 determines the data corresponding to the data length of the reference destination data from the position of the reference destination data in units of 1 byte. It is acquired and stored in the restoration buffer 1800 (step S2408).

  Next, the information processing apparatus 100 shifts the determination pointer 1810 toward the end of “1 byte” and shifts the decompression pointer 1820 toward the end of “the data length of the compressed data” (step S2409). Then, the information processing apparatus 100 proceeds to step S2405.

  The information processing apparatus 100 restores the compression source data having a data length of 9 bytes or less by the processing through the above steps S2401, S2402, S2406 to S2409, and S2405.

  On the other hand, when the data length of the reference destination data is longer than 9 bytes (step S2407: Yes), the information processing apparatus 100 refers to the acquired compressed data and divides the reference destination data in “8-byte units”. Specify the number of data that can be processed. Next, the information processing apparatus 100 acquires “8 bytes” of the specified number of pieces of reference destination data from the top, and stores them in the restoration buffer 1800 (step S2410).

  Next, the information processing apparatus 100 refers to the acquired compressed data and specifies the fraction data length to be processed for the reference destination data in “1-byte units”. Then, the information processing apparatus 100 acquires “8 bytes” of data corresponding to the number from the reference destination data, acquires the remaining data in units of 1 byte from the top, and stores it in the restoration buffer 1800 (step S2411).

  Next, the information processing apparatus 100 shifts the determination pointer 1810 toward the end of “1 byte” and shifts the decompression pointer 1820 toward the end of “the data length of the compressed data” (step S2412). Then, the information processing apparatus 100 proceeds to step S2405.

  The information processing apparatus 100 restores the compression source data having a data length longer than 9 bytes by the processing through the above steps S2401, S2402, S2406, S2407, S2410 to S2412, and S2405.

  As described above, the information processing apparatus 100 refers to the compressed data and acquires the reference destination data corresponding to the compressed data by dividing the register data in units of register widths, and cannot acquire the reference data in units of register widths. The obtained data is divided and acquired in units of 1 byte. In this way, the information processing apparatus 100 processes the uncompressed reference destination data corresponding to the register width together by the processor 201, thereby processing the data corresponding to the register width in a shorter time than sequentially processing the data corresponding to the register width one byte at a time. Can be terminated. Thereby, the information processing apparatus 100 can process the reference destination data by efficiently using the register width, and can speed up the data restoration.

  In addition, the register width of another processor that has performed compression may be a multiple of the register width of the processor 201 of the information processing apparatus 100. In this case, the ratio of the register widths of other processors that have performed compression on the register width of the processor 201 of the information processing apparatus 100 to the number of pieces of data that can be acquired by dividing the register width unit indicated by the compressed data. The number multiplied by may be calculated. Then, the information processing apparatus 100 acquires data divided by the register width unit for the calculated number of reference destination data, and divides the data that could not be acquired by dividing by the register width unit by 1 byte unit. Get. As a result, data restoration is possible even when the register width of the other processor that has performed compression is different from the register width of the processor 201 of the information processing apparatus 100.

  In addition, the information processing apparatus 100 detects reference destination data that is the same data as the compression source data, and divides the compression source data by the register width unit of the position of the reference destination data and the reference destination data. Compressed into compressed data indicating the number and fraction data length. Thus, the processor 201 that restores the compressed data can restore the data with reference to the compressed data. Specifically, for example, the processor 201 acquires data divided in register width units among the reference destination data, and divides the remaining data that cannot be acquired by dividing in register width units in 1-byte units. Data can be restored. In addition, the information processing apparatus 100 expresses the data length of the reference destination data in multiples of 8, thereby improving the compression efficiency for the reference destination data of 248 bytes or more compared to the case where the data length of the reference destination data is expressed as it is. Can be improved.

  In addition, the register width of another processor that executes restoration may be a multiple of the register width of the information processing apparatus 100. In this case, the information processing apparatus 100 compresses compressed data indicating the position of the reference destination data, the number of pieces of data that can be obtained by dividing the reference destination data in multiples of the register width, and the fractional data length. Compress to As a result, data compression is possible even when the register width of the other processor that executes restoration is different from the register width of the processor 201 of the information processing apparatus 100.

Example 2
Next, Example 2 will be described. In the first embodiment, the information processing apparatus 100 stores an area in a decoding buffer that stores data of a register width acquired from reference destination data regardless of whether it is an aligned section. On the other hand, in the second embodiment, the information processing apparatus 100 causes the area in the decoding buffer that stores the register width data acquired from the reference destination data to be a section that is aligned and divided.

  Therefore, in the second embodiment, the compressed data is acquired by dividing the reference data from the reference destination data in units of 8 bytes out of the remaining data excluding the head data acquired by the processor 201 that restores the compression source data. This is data indicating the number of data to be processed. Here, of the reference destination data, the head side data is data used to fill the empty area from the write destination position in the restoration buffer to the end position of the section that is aligned and divided. .

  As a result, the information processing apparatus 100 obtains 1 byte unit from the beginning of the reference destination data and stores it in the restoration buffer until the writing destination position in the restoration buffer reaches the beginning position of the aligned section. Go. Then, when the write destination position in the restoration buffer becomes the head position of the aligned section, the information processing apparatus 100 acquires data in register width units and aligns the data length corresponding to the register width. In addition, it can be stored without excess or deficiency.

  In other words, the information processing apparatus 100 does not store data across the aligned positions when storing data in register width units. Therefore, the information processing apparatus 100 can reduce the number of accesses to the restoration buffer when storing data in register width units, and can increase the speed of data restoration.

<Compression of Data Sequence by Information Processing Device 100 According to Second Embodiment>
In the following, first, data string compression performed by the information processing apparatus 100 according to the second embodiment will be described with reference to FIGS. The decompression of the compression source data string dsB by the information processing apparatus 100 according to the second embodiment is illustrated in FIGS. 36 to 43 described later.

(Functional configuration example regarding compression of data string of information processing apparatus 100 according to second embodiment)
First, an example of a functional configuration related to compression of a data string of the information processing apparatus 100 according to the second embodiment will be described with reference to FIG. FIG. 25 is a block diagram of an example of a functional configuration related to data string compression of the information processing apparatus 100 according to the second embodiment. The information processing apparatus 100 includes a storage unit 2502, a detection unit 2503, a specification unit 2501, a generation unit 2504, and a storage unit 2505.

  Here, the information processing apparatus 100 includes a register having a predetermined length. Since the register is the same as that described with reference to FIG. For example, when the compressed data is restored by the own apparatus, the information processing apparatus 100 compresses the data according to the register width of the processor 201 of the own apparatus. Further, when the compressed data is restored by another apparatus, the information processing apparatus 100 may compress the data in accordance with the register width of the processor of the other apparatus.

  The specifying unit 2501 is located on the end side of the subsequent data position from the position of the subsequent data in the position of the subsequent data in the data string and a plurality of positions divided by a predetermined length unit from the head of the data string, and from the position of the subsequent data The section length between the position within the predetermined length and the section length is specified.

  Specifically, for example, the specifying unit 2501 includes, for example, the position of the compression source data “24th byte” and the end of the section including the position of the compression source data among the sections divided every 8 bytes from the top of the data string. The position “25th byte” is specified. Next, the specifying unit 2501 specifies the data length “1 byte” of the partial section between the specified “24th byte” and “25th byte”.

  Specifically, the specifying unit 2501 realizes its function by causing the processor 201 to execute a program stored in a storage device such as the ROM 202, the RAM 203, the magnetic disk 205, and the optical disk 207 illustrated in FIG. . Thus, the generation unit 2504 can generate compressed data with reference to the data length of the partial section.

  The storage unit 2502 stores a data string. The data string stored by the storage unit 2502 is the same as the data string described using FIG. 3 and FIG. The detection unit 2503 detects preceding data and subsequent data that is the same data as the preceding data from the storage unit 2502 that stores the data string. Specifically, the detection unit 2503 realizes its function by causing the processor 201 to execute a program stored in a storage device such as the ROM 202, the RAM 203, the magnetic disk 205, and the optical disk 207 illustrated in FIG. . The detection process performed by the detection unit 2503 is the same as the process described with reference to FIGS. 3 and 5 and will not be described.

  The generation unit 2504 generates compressed data having a quotient and a remainder obtained by dividing a position obtained by subtracting a section length from a position of the detected preceding data and a length of the preceding data that is equal to or longer than the predetermined length. Here, in general, a remainder obtained by dividing a length obtained by subtracting a section length from the length of the preceding data by a predetermined length is less than the predetermined length, but is not limited thereto. For example, the remainder may be a predetermined length or more.

  More specifically, for example, when “20 bytes” is divided by “8 bytes”, “2” may be employed as the quotient and “4 bytes” may be employed as the remainder. Further, for example, when “20 bytes” is divided by “8 bytes”, “1” may be adopted as a quotient and “12 bytes” may be adopted as a remainder.

  Specifically, the generation unit 2504 generates data indicating the relative position of the reference destination data identified by the detection unit 2503, for example. Next, the generation unit 2504 subtracts the data length of the specified partial section from the data length of the reference destination data, and calculates a quotient and a remainder obtained by dividing the subtracted data length by 8 bytes. Then, the information processing apparatus 100 employs the quotient calculated as described above as the number of data that can be divided and processed in units of 8 bytes out of the subtracted data length data, and data indicating the quotient employed. Generate.

  Next, the generation unit 2504 adopts the remainder calculated as described above as the fraction data length to be processed in units of 1 byte after processing the data for the subtracted data length in units of 8 bytes. Data indicating the remainder is generated. Then, the generation unit 2504 generates compressed data obtained by concatenating the generated data. Next, the generation unit 2504 generates a determination bit indicating that the compression source data has been compressed. In addition, when the compression source data cannot be compressed, the generation unit 2504 may generate a determination bit indicating that the compression source data has not been compressed.

  In addition, the register width of another processor that executes restoration may be a multiple of the register width of the processor 201 of the information processing apparatus 100. In this case, the generation unit 2504 generates compressed data having a quotient and a remainder obtained by dividing the position of the detected preceding data, the length of the preceding data that is greater than or equal to the predetermined length, by subtracting the length of the section by a multiple of the predetermined length It may be generated. As a result, even when the register width of the other processor that executes restoration is different from the register width of the processor 201 of the information processing apparatus 100, data compression is possible. The generated data is stored in a storage area such as the RAM 203, the magnetic disk 205, and the optical disk 207, for example.

  Specifically, the generation unit 2504 realizes its function by causing the processor 201 to execute a program stored in a storage device such as the ROM 202, the RAM 203, the magnetic disk 205, and the optical disk 207 illustrated in FIG. . Accordingly, the generation unit 2504 can send the compressed data to be replaced with the compression source data to the storage unit 2505.

  Here, the content of the compressed data generated by the generation unit 2504 according to the second embodiment will be described with reference to FIGS. Specifically, a compression rule according to the second embodiment will be described with reference to FIG. 26, and an example of compressed data compressed with the compression rule illustrated in FIG. 26 will be described with reference to FIGS.

  FIG. 26 is an explanatory diagram of a compression rule according to the second embodiment. As shown in FIG. 26, in the compression rule according to the second embodiment, the compressed data includes “13 bits” fixed length data 2601 indicating the position of the reference destination data and “3 bits + 8” indicating the data length of the reference destination data. Variable length data having a data length that is a multiple of bits. The data length that is a multiple of 3 bits + 8 bits is, for example, 3 bits, 11 bits, or 19 bits.

  The fixed length data 2601 indicating the position of the reference destination data indicates the data length from the position of the compressed data to the position of the reference destination data. Since the fixed length data 2601 is “13 bits”, the data length from the position of the compressed data to the position of the reference destination data is indicated in the range of “0 bytes to 8191 bytes”.

  The variable length data indicating the data length of the reference destination data is “3 bits” data 2602 when the data length of the reference destination data is less than “10” bytes. Since the variable length data 2602 has a data length of “3 bits”, the data length of the reference destination data is indicated in the range of “3 bytes to 9 bytes”. Here, for example, when the variable length data 2602 is “000”, the variable length data 2602 indicates a decimal number “3” instead of a decimal number “0” corresponding to the binary number “000”.

  In the compression rule of the second embodiment, the data length of the compressed data is 2 bytes or more. Therefore, when the data length of the compression source data is “1 byte or 2 bytes”, the information processing apparatus 100 does not reduce the data size even if the compression is performed. Also good. Therefore, since it is not necessary to indicate “0 bytes to 2 bytes” as the data length of the reference destination data, the variable length data 2602 converts each binary number into a decimal number into “000 to 110”. Instead of “0-7”, “3-9” is associated.

  The variable length data indicating the data length of the reference destination data is “3 bits” data 2602 and “5 bits” data when the data length of the reference destination data is “10” bytes or more and less than “248 bytes”. This is data obtained by concatenating 2603 and “3-bit” data 2604.

  Among the variable length data 2602 to 2604, the data 2602 becomes “111”, indicating that the data length of the reference destination data is “10 bytes” or more, and the subsequent “8-bit” data 2603 and 2604 are the reference destination. Indicates that the data indicates the data length.

  Of the variable length data 2602 to 2604, the data 2603 is “8” among the data corresponding to the data length obtained by subtracting the section length from the data length of the reference destination data to the aligned and delimited position from the position of the compression source data. Indicates the number of data that can be acquired by dividing by "byte". Here, since the data 2603 has a data length of “5 bits”, the number is indicated in a range of “0 to 30”. In other words, the data 2603 indicates one of data lengths that are multiples of 8 within the range of “0 bytes to 240 bytes”.

  The data 2604 is fractional data obtained by subtracting the section length from the position of the compression source data to the aligned and delimited position from the data length of the reference destination data, and subtracting “8 bytes” for the number indicated by the data 2603. Indicates length. Here, since the data length of the data 2604 is “3 bits”, the fraction data length is indicated in a range of “0 bytes to 7 bytes”.

  Further, the data length of the reference destination data may be “248 bytes” or more. In this case, the variable-length data indicating the data length of the reference destination data is concatenation of “3-bit” data 2602, “5-bit” data 2603, “3-bit” data 2604, and “8-bit” data 2605. Data. Since the data 2602 and 2604 are the same as the case where the data length of the reference destination data is “10” bytes or more and less than “248 bytes”, description thereof is omitted here.

  Of the variable length data 2602 to 2605, the data 2603 is “11111”, indicating that the number of pieces of data that can be obtained by being divided in units of “8 bytes” is “30” or more. Further, the data 2603 indicates that the subsequent “8-bit” data 2605 is data indicating the number of pieces of data that can be obtained by dividing the reference destination data in units of “8 bytes”.

  Among the variable-length data 2602-2605, the data 2605 is indirectly the number of data by indicating how many more than “30” the number of data that can be divided and acquired in units of “8 bytes” described above. Indicates. Since the data 2605 has a data length of “8 bits”, the data 2605 indicates how many more than the number “30” is in a range of “1 to 255”.

  As a result, the data 2605 indicates the number of data that can be divided and acquired in units of “8 bytes” as described above in the range of “31 to 285 (30 + 1 to 30 + 255)”. In other words, the data 2605 indicates one of data lengths that are multiples of 8 within the range of “248 bytes to 2032 bytes”.

  Thereafter, the variable length data indicating the data length of the reference destination data is newly added each time the number of data that can be obtained by being divided in units of “8 bytes” cannot be indicated by the data being used to indicate the number. 8-bit data for indicating the number is added. Then, using the added 8-bit data, the number of pieces of data that can be obtained by being divided in units of “8 bytes” is indicated.

  27 and 28 are explanatory diagrams illustrating an example of uncompressed data that has not been compressed and an example of compressed data that has been compressed according to the compression rule illustrated in FIG. 26.

  FIG. 27A shows an example of uncompressed data that has not been compressed. FIG. 27B shows an example of compressed data when compression source data having a data length of 9 bytes or less is compressed. FIG. 27C shows an example (part 1) of compressed data when compression source data having a data length longer than 9 bytes is compressed. FIG. 28D shows an example (part 2) of compressed data when compression source data having a data length longer than 9 bytes is compressed.

  As shown in FIG. 27A, the data included in the compression source data string dsH may be data dH that cannot be compressed. In this case, the generation unit 2504 sends the uncompressible data dH as it is to the storage unit 2505 as uncompressed data ndH. In addition, the generation unit 2504 generates a determination bit bH “0” indicating that compression is not performed.

  As shown in FIG. 27B, the compression source data string dsI includes compression source data tdI and reference destination data rdI that are the same data, and the compression source data tdI may be “9 bytes” or less. In this case, the generation unit 2504 generates “00000000000010 (10)” indicating “13 bits” and the relative position “10” of the reference destination data rdI.

  Next, the generation unit 2504 generates “001 (4)” indicating “4 bytes” of the reference destination data rdI with “3 bits”. Then, the generation unit 2504 generates compressed data cdI “00000000000010 (10) 001 (4)” obtained by concatenating the generated data. In addition, the generation unit 2504 generates a determination bit bI “1” indicating compression.

  As shown in FIG. 27C, the compression source data string dsJ includes compression source data tdJ and reference destination data rdJ that are the same data, and the compression source data tdJ may be larger than “9 bytes”. Here, it is assumed that the second byte from the position of the compression source data tdJ is a position that is aligned and separated from the head of the compression source data string dsJ.

  In this case, the generation unit 2504 generates “0000000010100 (20)” that indicates “13 bits” and indicates the relative position “20” of the reference destination data rdJ. Next, the generation unit 2504 generates “111 (10)” indicating that “3 bits” and the data length of the reference destination data rdJ is greater than “9 bytes”.

  Then, the generation unit 2504 subtracts the section length “2 bytes” between the position of the compression source data tdJ and the aligned and separated position from the data length “11 bytes” of the reference destination data rdJ “compression”. Next, the generation unit 2504 calculates the number “1” that can be divided and processed in units of 8 bytes by dividing “9 bytes” of the subtraction result by “8 bytes”. Then, the generation unit 2504 generates data “00001 (1)” indicating the number of data “1” that can be divided and processed in units of 8 bytes.

  Next, the generation unit 2504 calculates a fraction data length “1 byte” by subtracting “8 bytes” corresponding to the calculated number from “9 bytes” of the subtraction result. Then, the generation unit 2504 generates data “001 (1)” indicating the fraction data length “1” to be processed in units of 1 byte. Next, the generation unit 2504 generates compressed data cdJ “0000000010100 (20) 111 (10) 00001 (1) 001 (1)” concatenated with the generated data. In addition, the generation unit 2504 generates a determination bit bJ “1” indicating compression.

  As shown in FIG. 28D, the compression source data string dsK includes compression source data tdK and reference destination data rdK that are the same data, and the compression source data tdK may be larger than “9 bytes”. Here, it is assumed that the second byte from the position of the compression source data tdK is a position that is aligned and separated from the head of the compression source data string dsK.

  In this case, the generation unit 2504 generates “0010001100000 (1120)” indicating the relative position “1120” of the reference destination data rdK with “13 bits”. Next, the generation unit 2504 generates “111 (10)” indicating “3 bits” and the data length of the reference destination data rdK being greater than “9 bytes”.

  Then, the generation unit 2504 subtracts the section length “2 bytes” between the position of the compression source data tdK and the aligned and separated position from the data length “303 bytes” of the reference destination data rdK. Next, the generation unit 2504 calculates the number “37” that can be divided and processed in units of 8 bytes by dividing “301 bytes” of the subtraction result by “8 bytes”. Then, the generation unit 2504 generates data “11111 (31)” indicating that the number is 5 bits and larger than “30” in order to indicate the number of data “37” that can be processed in units of 8 bytes. . Then, the generation unit 2504 generates data “00000110 (30 + 7 = 37)” indicating the number “37” by indicating “7” which is a shortage from “30” to “37” in 8 bits.

  Next, the generation unit 2504 calculates the fraction data length “5 bytes” by subtracting “8 bytes” corresponding to the calculated number from “301 bytes” of the subtraction result. Then, the generation unit 2504 generates data “101 (5)” indicating the fraction data length “5” to be processed in units of 1 byte. Then, the generation unit 2504 generates compressed data cdK “0010001100000 (1120) 111 (10) 11111 (31) 101 (5) 00000110 (37)” obtained by concatenating the generated data. In addition, the generation unit 2504 generates a determination bit bK “1” indicating compression.

  Returning to FIG. 25, the storage unit 2505 stores the data string obtained by replacing the subsequent data with the generated compressed data. The storage process by the storage unit 2505 is the same as the process described with reference to FIG.

(Data stream compression flow)
Next, the flow of data string compression by the information processing apparatus 100 according to the second embodiment will be described with reference to FIGS. 29 to 34.

  FIGS. 29 to 34 are explanatory diagrams illustrating a flow of data string compression by the information processing apparatus 100 according to the second embodiment. In FIG. 29, the information processing apparatus 100 first inputs the compression source data string dsB by the operation of the input device such as the keyboard 210 and the mouse 211 by the user of the information processing apparatus 100. Next, the information processing apparatus 100 stores the input compression source data string dsB in the input buffer.

  Then, the information processing apparatus 100 sets the compression pointer 900 at the head of the compression source data string dsB stored in the input buffer. Next, the information processing apparatus 100 sets a determination buffer 910 that stores a determination bit string and a compression buffer 920 that stores a compressed data string. Then, the information processing apparatus 100 starts compressing the compression source data string dsB.

  In FIG. 29, (61) the information processing apparatus 100 acquires “3 bytes” of data “com” starting from the position indicated by the compression pointer 900. Next, the information processing apparatus 100 searches for preceding data that becomes the same data as the acquired data “com” from the head side from the position indicated by the compression pointer 900.

  Here, specifically, for example, the information processing apparatus 100 refers to the search table 500 illustrated in FIG. 5 and acquires the position information “0” of the preceding data corresponding to the position indicated by the compression pointer 900. Next, since the position information is “0”, the information processing apparatus 100 determines that there is no preceding data that becomes the same data as the data “com” starting from the position indicated by the compression pointer 900 and the data “com” cannot be compressed. To do.

  (62) The information processing apparatus 100 stores the data “c” at the position indicated by the compression pointer 900 as it is in the compression buffer 920 as data that could not be compressed. (63) Further, the information processing apparatus 100 stores the determination bit “0” indicating that the data “c” at the position indicated by the compression pointer 900 could not be compressed in the determination buffer 910.

  Next, the information processing apparatus 100 shifts the compression pointer 900 toward the end by “1 byte”, and proceeds to the processing of FIG. 30.

  30, (64) the information processing apparatus 100 acquires “3 bytes” of data “omp” starting from the position indicated by the compression pointer 900 in the same manner as in FIG. Next, the information processing apparatus 100 searches for preceding data that becomes the same data as the acquired data “omp” from the head side from the position indicated by the compression pointer 900. The information processing apparatus 100 determines that the data “omp” cannot be compressed because there is no preceding data that becomes the same data as the data “omp” starting from the position indicated by the compression pointer 900.

  (65) Next, the information processing apparatus 100 stores the data “o” at the position indicated by the compression pointer 900 as it is in the compression buffer 920 as data that could not be compressed. (66) Further, the information processing apparatus 100 stores the determination bit “0” indicating that the data “o” at the position indicated by the compression pointer 900 could not be compressed in the determination buffer 910.

  Next, the information processing apparatus 100 shifts the compression pointer 900 by “1 byte” toward the end, and proceeds to the processing of FIG.

  In FIG. 31, (67) the information processing apparatus 100 acquires “3 bytes” of data “mpr” starting from the position indicated by the compression pointer 900 in the same manner as in FIG. Next, the information processing apparatus 100 searches for preceding data that is the same data as the acquired data “mpr” from the beginning of the position indicated by the compression pointer 900. The information processing apparatus 100 determines that the data “mpr” cannot be compressed because there is no preceding data that becomes the same data as the data “mpr” starting from the position indicated by the compression pointer 900.

  (68) Next, the information processing apparatus 100 stores the data “m” at the position indicated by the compression pointer 900 as it is in the compression buffer 920 as data that could not be compressed. (69) Further, the information processing apparatus 100 stores the determination bit “0” indicating that the data “m” at the position indicated by the compression pointer 900 could not be compressed in the determination buffer 910.

  Thereafter, the information processing apparatus 100 stores the data at the positions “4th byte” to “14th byte” of the compression source data in the compression buffer 920 without compression in the same manner as in FIGS. 29 to 31. Suppose that Next, the information processing apparatus 100 shifts the compression pointer 900 by “1 byte” toward the end, and proceeds to the processing of FIG.

  In FIG. 32, (70) the information processing apparatus 100 acquires “3 bytes” of data “com” starting from the position indicated by the compression pointer 900. Next, the information processing apparatus 100 searches for preceding data that becomes the same data as the acquired data “com” from the head side from the position indicated by the compression pointer 900.

  Here, specifically, for example, the information processing apparatus 100 refers to the search table 500 illustrated in FIG. 5 and acquires the position information “14” of the preceding data corresponding to the position indicated by the compression pointer 900. Next, since the position information is “14”, the information processing apparatus 100 determines that the preceding data having the same data as the data “com” starting from the position indicated by the compression pointer 900 is “14 bytes before”. Therefore, the information processing apparatus 100 determines that “com” can be compressed.

  Here, the information processing apparatus 100 determines whether or not the data at the end of “com” can be compressed together with “com”. Specifically, for example, the information processing apparatus 100 acquires the position information “14” of the preceding data corresponding to the position “1 byte” at the end of the position indicated by the compression pointer 900.

  Here, the acquired position information “14” of the preceding data is the same as the position information “14” of the preceding data corresponding to the position indicated by the compression pointer 900. Therefore, the information processing apparatus 100 determines that the data “com” at the position indicated by the compression pointer 900 can be compressed and “omp” at the end of “one byte” from the position indicated by the compression pointer 900 can be compressed. To do.

  In other words, the information processing apparatus 100 determines that “4 bytes” of data “comp” starting from the position indicated by the compression pointer 900 can be compressed using the preceding data “comp” at “14 bytes before”. To do.

  Similarly, the information processing apparatus 100 can compress the “compress” of “8 bytes” starting from the position indicated by the compression pointer 900 by using the preceding data “compress” at “14 bytes before”. Is determined.

  Next, the information processing apparatus 100 generates “13-bit” data “0000000001110 (14)” indicating the relative position of the reference destination data. Further, the information processing apparatus 100 generates “3-bit” data “101 (8)” indicating the data length of the reference destination data. Next, the information processing apparatus 100 generates compressed data “0000000001110 (14) 101 (8)” obtained by concatenating the generated data. Hereinafter, the compressed data “0000000001110 (14) 101 (8)” is represented as compressed data “14,8”.

  (71) The information processing apparatus 100 stores the compressed data “14, 8” in the compression buffer 920 instead of the data “compress” starting from the position indicated by the compression pointer 900. (72) Further, the information processing apparatus 100 stores the determination bit “1” indicating that the data “compress” starting from the position indicated by the compression pointer 900 is compressed in the determination buffer 910.

  Next, the information processing apparatus 100 shifts the compression pointer 900 to the end side by “8 bytes” which is the data length of the compressed data, and performs the same processing as “FIG. Assume that the data “(blank)” at the position of the “23rd byte” is stored in the compression buffer 920 without being compressed. Then, the information processing apparatus 100 shifts to the process of FIG. 33 assuming that the compression pointer 900 is shifted to “1 byte” by the end.

  In FIG. 33, (73) the information processing apparatus 100 acquires “3 bytes” of data “com” starting from the position indicated by the compression pointer 900. Next, the information processing apparatus 100 searches for preceding data that becomes the same data as the acquired data “com” from the head side from the position indicated by the compression pointer 900.

  Here, the information processing apparatus 100 uses the data “compression” of “11 bytes” starting from the position indicated by the compression pointer 900 and the preceding data “compression” at “23 bytes before” in the same manner as in FIG. And determine that compression is possible.

  Next, the information processing apparatus 100 generates “13-bit” data “0000000010111 (23)” indicating the relative position of the reference destination data. Then, the information processing apparatus 100 generates “3 bit” data “111 (10)” indicating that the data length of the reference destination data is longer than 9 bytes.

  Next, the information processing apparatus 100 calculates the section length “1 byte” from the position indicated by the compression pointer 900 to the aligned and delimited position that appears immediately after the compression pointer 900. Then, the information processing apparatus 100 calculates “10 bytes” by subtracting the section length “1 byte” from the data length “11 bytes” of the reference destination data.

  Next, since the subtraction result is “10 bytes”, the information processing apparatus 100 has data “00001” indicating the number of data “1” that can be divided and processed in units of 8 bytes among the data of “10 bytes”. 1) ".

  Then, the information processing apparatus 100 processes the 8-byte data corresponding to the number of the “10 bytes” data obtained by removing the data corresponding to the section length from the reference destination data, and then processes the fraction to be processed in 1-byte units. Data “010 (2)” indicating the data length “2 bytes” is generated. Next, the information processing apparatus 100 generates compressed data “0000000010111 (23) 111 (10) 00001 (1) 010 (2)” obtained by concatenating the generated data. Hereinafter, the compressed data “0000000010111 (23) 111 (10) 00001 (1) 010 (2)” is represented as compressed data “23,1,2”.

  (74) The information processing apparatus 100 stores the compressed data “23, 1, 2” in the compression buffer 920 instead of the data “compression” starting from the position indicated by the compression pointer 900. (75) Further, the information processing apparatus 100 stores the determination bit “1” indicating that the data “compression” starting from the position indicated by the compression pointer 900 is compressed in the determination buffer 910.

  Next, the information processing apparatus 100 shifts the compression pointer 900 toward the end by “11 bytes”, which is the data length of the compressed data, and performs the same processing as in FIGS. It is assumed that the data “.” At the position “34th byte” is stored in the compression buffer 920 without being compressed.

  FIG. 34 shows a compressed data string compressed by the processing described with reference to FIGS. As shown in FIG. 34, the information processing apparatus 100 converts the compression source data string dsB of “35 bytes” into a discrimination bit string bsL of “18 bits” and a compressed data string cdsL of “21 bytes”. Yes. Therefore, the information processing apparatus 100 has converted the compression source data string dsB of “35 bytes” into the discrimination bit string bsL of “18 bits” and the compressed data string cdsL of “21 bytes”. In other words, the information processing apparatus 100 can reduce the data length of the data string by a data length of “(35 bytes) − (21 bytes + 18 bits) = (11 bytes + 6 bits)”.

  Thus, the information processing apparatus 100 can reduce the size of the data string. As a result, the information processing apparatus 100 can reduce the size of the storage area to be used when storing the data string, as compared with the case where the data string is stored without being compressed. Further, when transmitting the data string to another computer, the information processing apparatus 100 can reduce the transmission time by compressing the data string and transmitting the data string.

(Example of saving compressed data string and discrimination bit string)
Next, an example of saving when the compressed data string cdsL and the discrimination bit string bsL shown in FIGS. 29 to 34 are saved in the storage device will be described. Here, the example of storing the compressed data string cdsL and the determination bit string bsL is the same as the example of storing the compressed data string cdsL and the determination bit string bsL shown in FIG.

(Data string compression processing)
Next, a detailed processing procedure of the data string compression processing for realizing the compression of the data strings shown in FIGS. 29 to 34 will be described with reference to FIG.

  FIG. 35 is a flowchart showing a detailed processing procedure of the data string compression processing for realizing the compression of the data strings shown in FIGS. As shown in FIG. 35, the information processing apparatus 100 first detects preceding data that becomes the same data as subsequent data at the position indicated by the compression pointer 900 from the compression source data in the input buffer (step S3501). .

  Next, the information processing apparatus 100 determines whether preceding data has been detected (step S3502). If the preceding data is not detected (step S3502: NO), the information processing apparatus 100 generates a determination bit “0” indicating that compression is not performed and stores the determination bit “0” in the determination buffer 910 (step S3503).

  Next, the information processing apparatus 100 stores the data for the first 1 byte of the subsequent data as it is in the compression buffer 920 (step S3504). Then, the information processing apparatus 100 shifts the compression pointer 900 toward the end of “one byte” (step S3505).

  Next, the information processing apparatus 100 determines whether the compression has been completed (step S3506). Here, when the compression ends (step S3506: Yes), the information processing apparatus 100 ends the data string compression processing.

  On the other hand, when the compression has not ended (step S3506: No), the information processing apparatus 100 returns to step S3501. The information processing apparatus 100 processes data that cannot be compressed by the processing through steps S3501 to S3506.

  On the other hand, when preceding data is detected in step S3502 (step S3502: Yes), the information processing apparatus 100 generates a determination bit “1” indicating compression and stores it in the determination buffer 910 (step S3507). ).

  Next, the information processing apparatus 100 determines whether or not the data length of the preceding data is longer than 9 bytes (step S3508). Here, when the data length of the preceding data is 9 bytes or less (step S3508: No), the information processing apparatus 100 generates data indicating the position of the preceding data and data indicating the data length of the preceding data. And stored in the compression buffer 920 (step S3509).

  Next, the information processing apparatus 100 shifts the compression pointer 900 toward the end of “the data length of the preceding data” (step S3510). Then, the information processing apparatus 100 proceeds to step S3506. By the processing through steps S3501, S3502, S3507 to S3510, and S3506, the information processing apparatus 100 compresses compressible data having a data length of 9 bytes or less.

  On the other hand, in step S3508, when the data length of the preceding data is longer than 9 bytes (step S3508: Yes), the information processing apparatus 100 determines that the data indicating the position of the preceding data and the data length of the preceding data are longer than 9 bytes. And data indicating Next, the information processing apparatus 100 stores the generated data in the compression buffer 920 (step S3511).

  Next, the information processing apparatus 100 has a portion between the position indicated by the compression pointer 900 and the end position of the section including the position indicated by the compression pointer 900 among the sections divided by the register width from the top of the input buffer. Specify the data length of the section. The information processing apparatus 100 calculates a quotient and a remainder when the data length of the specified partial section is subtracted from the data length of the preceding data and divided by the register width. Next, the information processing apparatus 100 generates data indicating the calculated quotient and data indicating the calculated remainder, and stores the generated data in the compression buffer 920 (step S3512).

  Then, the information processing apparatus 100 proceeds to step S3510. The information processing apparatus 100 compresses compressible data having a data length longer than 9 bytes by the processing through steps S3501, S3502, S3507, S3508, S3511, S3512, S3510, and S3506.

(Restoration of the compression source data string dsB from the compression data string by the information processing apparatus 100 according to the second embodiment)
Next, decompression of the compression source data string dsB by the information processing apparatus 100 according to the second embodiment is illustrated in FIGS. 36 to 42.

(Functional configuration example regarding decompression of the compression source data string dsB of the information processing apparatus 100 according to the second embodiment)
Next, with reference to FIG. 36, a functional configuration example relating to the decompression of the compression source data string dsB of the information processing apparatus 100 according to the second embodiment will be described. FIG. 36 is a block diagram of a functional configuration example related to the decompression of the compression source data string dsB of the information processing apparatus 100 according to the second embodiment. The information processing apparatus 100 includes a specifying unit 3601, a storage unit 3602, a detection unit 3603, an acquisition unit 3604, and a storage unit 3605.

  The specifying unit 3601 is located at the end side of the write destination among the position of the write destination in the predetermined storage area and a plurality of positions divided by a predetermined length unit from the beginning of the predetermined storage area, and The section length between the position of the insertion destination and the position within a predetermined length is specified.

  Specifically, the specifying unit 3601 specifically includes, for example, the position of the compression source data and the position of the end of the section including the position of the compression source data among the sections aligned and divided every 8 bytes from the top of the data string. And specify the data length of the partial section between them.

  Specifically, the specifying unit 3601 realizes its function by causing the processor 201 to execute a program stored in a storage device such as the ROM 202, the RAM 203, the magnetic disk 205, and the optical disk 207 illustrated in FIG. . Thereby, the acquisition unit 3604 can acquire the reference destination data with reference to the data length of the partial section.

  The storage unit 3602 is a reference position of uncompressed data to be referred to, compressed data having a quotient and a remainder obtained by dividing a length obtained by subtracting a section length from the length of the uncompressed data that is equal to or longer than a predetermined length, and A compressed data string including uncompressed data is stored. The uncompressed data serving as a reference destination is, for example, the reference destination data described above. The predetermined length is a register width that is a power of 2, and is, for example, the above-described 8 bytes.

  The compressed data includes, for example, data “0000000001110 (14)” indicating the relative position “14” of the reference destination data. The compressed data includes, for example, data “111 (10)” indicating that the reference destination data is 10 bytes or more. The compressed data is, for example, data “00001 (1)” indicating the number of data “1” that can be divided and processed in units of 8 bytes out of the data excluding the data for the section length specified from the reference destination data. Is included. The compressed data has data “011 (3)” indicating the fraction data length “3” to be processed in units of 1 byte.

  Specifically, the storage unit 3602 stores, for example, a compressed data string including compressed data and non-compressed data, and a discrimination bit string. Specifically, the storage unit 3602 realizes its function by a storage device such as the ROM 202, the RAM 203, the magnetic disk 205, and the optical disk 207 shown in FIG. Accordingly, the detection unit 3603 can acquire the compressed data string and the discrimination bit string stored in the storage unit 3602.

  The detection unit 3603 detects compressed data from the storage unit 3602. Specifically, the detection unit 3603 acquires, for example, a determination bit from the determination bit string, and determines whether the data corresponding to the acquired determination bit is non-compressed data or compressed data.

  Next, when it is determined that the data is compressed data, the detection unit 3603 detects data “0000000001110 (14) 111 (10)” of “1 byte”. The detecting unit 3603 has “111 (10)” indicating that the end “3 bits” of the detected data is longer than “9 bytes” of the reference destination data, and therefore the subsequent “1 byte” data. “00001 (1) 010 (2)” is further detected.

  In this way, the detection unit 3603 detects the compressed data “0000000001110 (14) 111 (10) 00001 (1) 010 (2)”. Specifically, the detection unit 3603 realizes its function by causing the processor 201 to execute a program stored in a storage device such as the ROM 202, the RAM 203, the magnetic disk 205, and the optical disk 207 illustrated in FIG. . Thereby, the acquisition unit 3604 can acquire the reference destination data using the compressed data detected by the detection unit 3603.

  The acquisition unit 3604, in order from the top of the reference destination data starting from the reference position included in the detected compressed data, the first data string that is the section length and the predetermined length that is the length obtained by multiplying the predetermined length by the quotient The second data string of the unit and the third data string having the extra length are acquired.

  Specifically, the acquisition unit 3604 specifies, for example, from “0000000001110 (14)” in the compressed data that the position of the reference destination data is “14 bytes” at the head of the compressed data position. .

  Next, the acquisition unit 3604 acquires data for the section length among the reference destination data starting from the specified position. Then, the acquisition unit 3604 acquires “8 bytes” of data obtained by multiplying “8 bytes” by the quotient indicated by “00001 (1)” in the compressed data, in units of “8 bytes”. In addition, the acquisition unit 3604 acquires the extra “2 bytes” of data indicated by “010 (2)” in the compressed data for each “1 byte”.

  In addition, the register width of another processor that has performed compression may be a multiple of the register width of the processor 201 of the information processing apparatus 100. In this case, the acquisition unit 3604 is a predetermined length that is a length obtained by multiplying the first data string and a multiple of a predetermined length by the quotient in order from the top of the reference destination data starting from the reference position included in the detected compressed data. The second data string in the long unit and the third data string may be acquired.

  Specifically, the acquiring unit 3604 realizes its function by causing the processor 201 to execute a program stored in a storage device such as the ROM 202, the RAM 203, the magnetic disk 205, and the optical disk 207 illustrated in FIG. . Accordingly, the acquisition unit 3604 can send the reference destination data to be replaced with the compressed data to the storage unit 3605.

  The storage unit 3605 writes the first data string, the second data string, and the third data string in the order of acquisition from the write destination position in the predetermined storage area. Specifically, for example, the storage unit 3605 stores the data “c” for the acquired section length in the restoration buffer 1800 in the reference destination data “compression”. Next, the storage unit 3605 stores “ompressi” acquired in “8-byte units” in the reference buffer data “compression” in the recovery buffer 1800, and stores “on” of “2 bytes” acquired. 1800 is stored.

  Specifically, the storage unit 3605 realizes its function by causing the processor 201 to execute a program stored in a storage device such as the ROM 202, the RAM 203, the magnetic disk 205, and the optical disk 207 illustrated in FIG. . Accordingly, the storage unit 3605 can replace the compressed data with the duplicate data of the reference destination data, and can restore the compression source data.

  In addition, the storage unit 3605 stores the data determined as non-compressed data by the detection unit 3603 in the restoration buffer 1800 as it is. Accordingly, the storage unit 3605 can store uncompressed data that may become reference destination data in the decompression buffer 1800.

(Flow of decompression of compression source data string dsB)
Next, the flow of decompression of the compression source data string dsB by the information processing apparatus 100 according to the second embodiment will be described with reference to FIGS.

  FIGS. 37 to 42 are explanatory diagrams illustrating a flow of decompression of the compression source data string dsB by the information processing apparatus 100 according to the second embodiment. In FIG. 37, first, the information processing apparatus 100 sets a discrimination pointer 1810 at the head of the discrimination bit string bsL. Next, the information processing apparatus 100 sets the restoration pointer 1820 at the head of the compressed data string cdsL. Then, the information processing apparatus 100 sets the decompression buffer 1800 that stores the decompressed compression source data string dsB.

  In FIG. 37, (81) the information processing apparatus 100 detects the discrimination bit at the position indicated by the discrimination pointer 1810. (82) Next, since the detected determination bit is “0”, the information processing apparatus 100 determines that the data at the position indicated by the restoration pointer 1820 is uncompressed data, and the position indicated by the restoration pointer 1820 The data “c” is acquired.

  (83) The information processing apparatus 100 stores the acquired uncompressed data “c” in the restoration buffer 1800 as it is. Next, the information processing apparatus 100 shifts the determination pointer 1810 toward the end of “1 bit”, shifts the restoration pointer 1820 toward the end of “1 byte”, and proceeds to the processing of FIG.

  38, (84) the information processing apparatus 100 detects the discrimination bit at the position indicated by the discrimination pointer 1810 in the same manner as in FIG. (85) Next, since the detected determination bit is “0”, the information processing apparatus 100 determines that the data at the position indicated by the restoration pointer 1820 is uncompressed data, and the position indicated by the restoration pointer 1820 The data “o” in is acquired.

  (86) The information processing apparatus 100 stores the acquired uncompressed data “o” in the restoration buffer 1800 as it is. Next, the information processing apparatus 100 shifts the determination pointer 1810 toward the end of “1 bit”, shifts the restoration pointer 1820 toward the end of “1 byte”, and proceeds to the processing of FIG.

  39, (87) the information processing apparatus 100 detects the discrimination bit at the position indicated by the discrimination pointer 1810 in the same manner as in FIG. (88) Next, since the detected discrimination bit is “0”, the information processing apparatus 100 determines that the data at the position indicated by the restoration pointer 1820 is uncompressed data, and the position indicated by the restoration pointer 1820 The data “m” in is acquired.

  (89) Then, the information processing apparatus 100 stores the acquired uncompressed data “m” in the restoration buffer 1800 as it is. Thereafter, the information processing apparatus 100 stores the data at the positions of the “first byte” to the “14th byte” of the compressed data in the restoration buffer 1800 as they are, as in FIGS. 37 to 39. To do. Next, the information processing apparatus 100 shifts the determination pointer 1810 toward the end of “1 bit”, shifts the restoration pointer 1820 toward the end of “1 byte”, and proceeds to the processing of FIG.

  40, (90) the information processing apparatus 100 detects the discrimination bit at the position indicated by the discrimination pointer 1810. (91) Next, since the detected determination bit is “1”, the information processing apparatus 100 determines that the data at the position indicated by the restoration pointer 1820 is compressed data, and places the data at the position indicated by the restoration pointer 1820. Some data “14, 8” is acquired.

  (92) Then, the information processing apparatus 100 refers to the acquired compressed data “14, 8” and determines that the reference destination data is “14 bytes before” the compressed data. Next, the information processing apparatus 100 refers to the acquired compressed data “14, 8”, acquires “8 bytes” of reference destination data in units of 1 byte, and stores it in the restoration buffer 1800.

  Next, it is assumed that the information processing apparatus 100 shifts the discrimination pointer 1810 toward the end of “1 byte” and shifts the decompression pointer 1820 toward the end of “2 bytes” that is the data length of the compressed data. Then, it is assumed that the information processing apparatus 100 stores the uncompressed data “(blank)” at the position indicated by the restoration pointer 1820 in the restoration buffer 1800 in the same manner as in FIGS. Next, the information processing apparatus 100 shifts the determination pointer 1810 toward the end of “1 bit”, shifts the restoration pointer 1820 toward the end of “1 byte”, and proceeds to the processing of FIG.

  In FIG. 41, (93) the information processing apparatus 100 detects the discrimination bit at the position indicated by the discrimination pointer 1810. (94) Next, since the detected determination bit is “1”, the information processing apparatus 100 determines that the data at the position indicated by the restoration pointer 1820 is compressed data, and places the data at the position indicated by the restoration pointer 1820. Some data “23, 1, 2” is acquired.

  (95) Then, the information processing apparatus 100 refers to the acquired compressed data “23, 1, 2” and determines that the reference destination data is “23 bytes before” the compressed data. Next, the information processing apparatus 100 sets the section length “1 byte” from the current storage destination position of the restoration buffer 1800 to the aligned and delimited position from the beginning of the restoration buffer 1800 that appears immediately after the storage destination position. calculate. Then, the information processing apparatus 100 acquires the data “c” having the calculated section length “1 byte” and stores it in the restoration buffer 1800.

  Next, the information processing apparatus 100 refers to the acquired compressed data “23, 1, 2”, acquires “data” “c” from the reference destination data, and among the remaining data “compression”, “8 byte unit” The number of data that can be divided and processed by “1” is specified as “1”. Then, the information processing apparatus 100 acquires the first “8 bytes” of data “ompressi” from the remaining data “ompression” and stores it in the restoration buffer 1800.

  Next, the information processing apparatus 100 refers to the acquired compressed data “23, 1, 2” and specifies that the fraction data length to be processed in “1-byte units” is “3 bytes”. Then, the information processing apparatus 100 acquires the data “on” obtained by acquiring the data “c” and the data “ompressi” from the reference destination data in units of 1 byte, and stores them in the restoration buffer 1800.

  Next, it is assumed that the information processing apparatus 100 shifts the determination pointer 1810 toward the end of “1 byte” and shifts the decompression pointer 1820 toward the end of “3 bytes” that is the data length of the compressed data. Then, it is assumed that the information processing apparatus 100 stores the uncompressed data “.” At the position indicated by the restoration pointer 1820 in the restoration buffer 1800 in the same manner as in FIGS.

  FIG. 42 shows the compression source data string dsB restored by the processing described with reference to FIGS. As illustrated in FIG. 42, the information processing apparatus 100 can restore the compression source data string dsB without loss. Further, in the decompression of the compression source data string dsB, the information processing apparatus 100 obtains reference destination data that can be acquired in units of 8 bytes, acquires the data in units of 8 bytes, and stores it in the recovery buffer 1800. As a result, the information processing apparatus 100 can effectively use the register width to shorten the time taken to restore the compression source data string dsB.

(Compression source data string restoration processing)
Next, with reference to FIG. 43, a detailed processing procedure of the compression source data sequence decompression processing for realizing the decompression of the compression source data sequence dsB shown in FIGS. 37 to 42 will be described.

  FIG. 43 is a flowchart showing a detailed processing procedure of the compression source data sequence decompression processing for realizing the decompression of the compression source data sequence dsB shown in FIGS. As shown in FIG. 43, the information processing apparatus 100 first acquires a determination bit at the position indicated by the determination pointer 1810 (step S4301).

  Next, the information processing apparatus 100 refers to the obtained determination bit and determines whether the data at the position indicated by the restoration pointer 1820 is compressed data (step S4302). If the data is uncompressed data (step S4302: NO), the information processing apparatus 100 acquires 1-byte data at the position indicated by the restoration pointer 1820 and stores it in the restoration buffer 1800 (step S4303).

  Next, the information processing apparatus 100 shifts the determination pointer 1810 toward the end of “1 byte” and shifts the restoration pointer 1820 toward the end of “1 byte” (step S4304). Then, the information processing apparatus 100 determines whether the restoration is finished (step S4305). Here, when the restoration is finished (step S4305: Yes), the information processing apparatus 100 finishes the compression source data string restoration process.

  On the other hand, when the restoration has not ended (step S4305: No), the information processing apparatus 100 returns to step S4301. The information processing apparatus 100 processes the uncompressed data by the processing through the above steps S4301 to S4305.

  On the other hand, if it is compressed data in step S4302 (step S4302: Yes), the information processing apparatus 100 refers to the compressed data and acquires the position of the reference destination data and the data length of the reference destination data ( Step S4306).

  Next, the information processing apparatus 100 determines whether or not the data length of the acquired reference destination data is longer than 9 bytes (step S4307). Here, when the data length of the reference destination data is 9 bytes or less (step S4307: No), the information processing apparatus 100 determines the data for the data length of the reference destination data from the position of the reference destination data in units of 1 byte. It is acquired and stored in the restoration buffer 1800 (step S4308).

  Next, the information processing apparatus 100 shifts the determination pointer 1810 toward the end of “one byte” and shifts the decompression pointer 1820 toward the end of “the data length of the compressed data” (step S4309). Then, the information processing apparatus 100 proceeds to step S4305.

  The information processing apparatus 100 restores the compression source data having a data length of 9 bytes or less by the processing via the above steps S4301, S4302, S4306 to S4309, and S4305.

  On the other hand, when the data length of the reference destination data is longer than 9 bytes (step S4307: Yes), the subsequent processing is executed. The information processing apparatus 100 uses the end position of the stored data in the restoration buffer 1800 and the end position of the section including the end position of the stored data in the section divided from the beginning of the restoration buffer 1800 for each register width. The data length of the partial section is specified. Then, the information processing apparatus 100 acquires the data corresponding to the data length of the specified partial section from the top of the reference destination data, and stores it in the restoration buffer 1800 (step S4310).

  Next, the information processing apparatus 100 refers to the acquired compressed data and specifies the number of data that can be processed by dividing the reference destination data by “8-byte units”. Then, the information processing apparatus 100 acquires the data corresponding to the data length of the partial section from the reference destination data, acquires the data of “8 bytes” for the specified number from the top, and restores the data. The data is stored in the buffer 1800 (step S4311).

  Next, the information processing apparatus 100 refers to the acquired compressed data and specifies the fraction data length to be processed for the reference destination data in “1-byte units”. Then, the information processing apparatus 100 acquires “8 bytes” of data corresponding to the number from the reference destination data, acquires the remaining data in units of 1 byte from the top, and stores it in the restoration buffer 1800 (step S4312).

  Next, the information processing apparatus 100 shifts the determination pointer 1810 toward the end of “1 byte” and shifts the decompression pointer 1820 toward the end of “the data length of the compressed data” (step S4313). Then, the information processing apparatus 100 proceeds to step S4305.

  The information processing apparatus 100 restores the compression source data having a data length longer than 9 bytes by the processing through steps S4301, S4302, S4306, S4307, S4310 to S4313, and S4305.

  As described above, the information processing apparatus 100 sequentially stores data for the section length between the write destination position of the restoration buffer and the aligned position that appears next to the write destination position in order from the top of the reference destination data. get. After that, the information processing apparatus 100 refers to the compressed data, and obtains the remaining data by dividing it into the number of data indicated by the compressed data in register width units, and cannot obtain the divided data in register units. The obtained data is divided and acquired in units of 1 byte. In this way, the information processing apparatus 100 processes the uncompressed reference destination data corresponding to the register width together by the processor 201, thereby processing the data corresponding to the register width in a shorter time than sequentially processing the data corresponding to the register width one byte at a time. Can be terminated.

  Thereby, the information processing apparatus 100 can process the reference destination data by efficiently using the register width, and can speed up the data restoration. Further, when storing the decompressed compression source data in the decompression buffer, the information processing apparatus 100 stores the data obtained by dividing by the register width unit within the aligned and segmented section in the decompression buffer. Can do. As a result, the information processing apparatus 100 can prevent an increase in the number of accesses for storing data and increase the speed of data restoration so that the stored data does not cross the aligned and partitioned positions. it can.

  In addition, the register width of another processor that has performed compression may be a multiple of the register width of the processor 201 of the information processing apparatus 100. In this case, the information processing apparatus 100 multiplies the number of pieces of data that can be obtained by dividing the register width indicated by the compressed data by the ratio of the register width of the other processor that has performed compression on the register width of the processor 201. It may be calculated. In addition, the information processing apparatus 100 specifies the section length between the write destination position of the restoration buffer and the aligned position that appears next to the write destination position. Then, the information processing apparatus 100 sequentially acquires data for the section length from the top of the reference destination data, then acquires data divided by the register width unit for the calculated number, and stores the data for the fraction data length. get. As a result, even if the register width of the other processor that has performed compression is different from the register width of the processor 201 of the information processing apparatus 100, data restoration is possible.

  Further, the information processing apparatus 100 identifies the section length between the write destination position of the restoration buffer and the aligned position that appears next to the write destination position in the processor that performs the restoration, and the section identified from the reference destination data Specify the data length excluding the long data. Then, the information processing apparatus 100 determines the compression source data, the position of the reference destination data, and the number of pieces of data and the fractional data length that can be acquired by dividing the data length by the register width unit. Compress to the compressed data shown.

  Thus, the processor 201 that restores the compressed data can restore the data with reference to the compressed data. Specifically, for example, the processor 201 acquires data for the specified section length in order from the top of the reference destination data. The information processing apparatus 100 then refers to the compressed data, acquires data divided in register width units, and acquires data that cannot be acquired by dividing in register width units in 1-byte units. Thus, data can be restored. In addition, the information processing apparatus 100 expresses the data length of the reference destination data in multiples of 8, thereby improving the compression efficiency for the reference destination data of 256 bytes or more compared to the case where the data length of the reference destination data is expressed as it is. Can be improved.

  In addition, the register width of another processor that executes restoration may be a multiple of the register width of the processor 201 of the information processing apparatus 100. In this case, the information processing apparatus 100 can acquire the compression source data by dividing the compression source data in units of multiples of the register width from the data of the reference destination data and the data length excluding the above, and the fractional number. Compressed into compressed data indicating the data length. As a result, even when the register width of the other processor that executes restoration is different from the register width of the processor 201 of the information processing apparatus 100, data compression is possible.

  The compression method or decompression method described in this embodiment can be realized by executing a program prepared in advance on a computer such as a personal computer or a workstation. The compression program or the restoration program is recorded on a computer-readable recording medium such as a hard disk, a flexible disk, a CD-ROM, an MO, or a DVD, and is executed by being read from the recording medium by the computer. Further, the compression program or the restoration program may be distributed via a network such as the Internet.

  The following additional notes are disclosed with respect to the embodiment described above.

(Appendix 1) To a processor having a register of a predetermined length,
A compressed data string including a reference position of uncompressed data to be a reference destination, compressed data having a quotient and a remainder obtained by dividing the length of the uncompressed data that is not less than the predetermined length by the predetermined length, and the uncompressed data Detecting the compressed data from the storage unit for storing
Among reference destination data starting from a reference position included in the detected compressed data, a first data string having a length obtained by multiplying the predetermined length by the quotient is obtained in the predetermined length unit, and the reference destination Obtaining a second data string having the extra length obtained by removing the first data string from data;
Writing the first data string acquired in units of the predetermined length to a predetermined storage area and writing the acquired second data string to the predetermined storage area;
A restoration program characterized by causing a process to be executed.

(Supplementary note 2)
Among the reference destination data starting from the reference position included in the detected compressed data, a first data string having a length obtained by multiplying a multiple of the predetermined length by the quotient is obtained in the predetermined length unit, and Obtaining a second data string having the extra length obtained by removing the first data string from reference destination data;
The restoration program according to supplementary note 1, characterized by:

(Supplementary Note 3) To a processor having a register of a predetermined length,
Of the write destination position in a predetermined storage area and a plurality of positions delimited by the predetermined length unit from the beginning of the predetermined storage area, the write destination position is on the end side and the write Specify the section length between the previous position and the position within the predetermined length range,
A reference position of uncompressed data as a reference destination, compressed data having a quotient obtained by dividing the length of the uncompressed data that is equal to or longer than the predetermined length by the predetermined length and a remainder, and the remainder; The compressed data is detected from a storage unit that stores a compressed data string including uncompressed data,
In order from the beginning of the reference destination data starting from the reference position included in the detected compressed data, the first data string that is the section length, and the predetermined length unit that is the length obtained by multiplying the predetermined length by the quotient A second data string and a third data string having the extra length,
Writing the first data string, the second data string, and the third data string in the order of acquisition from the write destination position in the predetermined storage area;
A restoration program characterized by causing a process to be executed.

(Supplementary note 4)
In order from the beginning of the reference destination data starting from the reference position included in the detected compressed data, the first data string that is the section length, and the predetermined length that is a multiple of the predetermined length multiplied by the quotient Obtaining a second data string in a long unit and a third data string serving as the extra length;
The restoration program according to supplementary note 3, characterized by:

(Supplementary note 5)
Detecting preceding data and subsequent data that is the same data as the preceding data from the storage unit that stores the data string,
Generating the compressed data having the position of the detected preceding data, the quotient obtained by dividing the length of the preceding data that is equal to or longer than the predetermined length by the predetermined length, and the remainder;
Storing the data string in which the subsequent data is replaced with the generated compressed data;
A compression program characterized by causing processing to be executed.

(Appendix 6) The process to generate is
Generating the compressed data having the detected position of the preceding data, the quotient obtained by dividing the length of the preceding data that is not less than the predetermined length by a multiple of the predetermined length, and a remainder;
The compression program according to appendix 5, characterized by:

(Supplementary note 7)
Detecting preceding data and subsequent data that is the same data as the preceding data from the storage unit that stores the data string,
Of the position of the subsequent data in the data string and a plurality of positions delimited in units of a predetermined length from the head of the data string, the position is on the end side of the position of the subsequent data, and from the position of the subsequent data Specify the section length of the position within the predetermined length range,
Generating a compressed data having a quotient and a remainder obtained by dividing a length obtained by subtracting the section length from the position of the preceding data detected, the length of the preceding data that is equal to or longer than the predetermined length, and the predetermined length;
Storing the data string in which the subsequent data is replaced with the generated compressed data;
A compression program characterized by causing processing to be executed.

(Supplementary note 8) The process to generate is
Generating compressed data having a quotient and a remainder obtained by dividing a position obtained by subtracting the section length from the length of the preceding data which is equal to or greater than the predetermined length, the position of the detected preceding data, and a multiple of the predetermined length;
The compression program according to appendix 7, characterized in that:

(Supplementary note 9) A restoration device executed by a processor having a register of a predetermined length,
A compressed data string including a reference position of uncompressed data to be a reference destination, compressed data having a quotient and a remainder obtained by dividing the length of the uncompressed data that is not less than the predetermined length by the predetermined length, and the uncompressed data A storage unit for storing
A detection unit for detecting the compressed data from the compressed data string;
A first data string having a length obtained by multiplying the predetermined length by the quotient among reference destination data strings starting from a reference position included in the compressed data detected by the detection unit is acquired in units of the predetermined length. And an acquisition unit that acquires the second data string having the extra length obtained by removing the first data string from the reference data string;
A storage unit that writes the first data string acquired by the acquisition unit in the predetermined length unit to a predetermined storage area and writes the second data string acquired by the acquisition unit to the predetermined storage area;
A restoration apparatus comprising:

(Supplementary Note 10) A restoration device executed by a processor having a register of a predetermined length,
Of the write destination position in a predetermined storage area and a plurality of positions delimited by the predetermined length unit from the beginning of the predetermined storage area, the write destination position is on the end side and the write A position that is within the range of the predetermined length from the previous position, and a specifying unit that specifies a section length;
A reference position of uncompressed data as a reference destination, compressed data having a quotient obtained by dividing the length of the uncompressed data that is equal to or longer than the predetermined length by the predetermined length and a remainder, and the remainder; A storage unit for storing a compressed data string including uncompressed data;
A detection unit for detecting the compressed data from the compressed data string;
In order from the beginning of the reference destination data starting from the reference position included in the compressed data detected by the detection unit, the first data string that is the section length and the length obtained by multiplying the predetermined length by the quotient An acquisition unit that acquires the second data string in the predetermined length unit and the third data string serving as the extra length;
A storage unit that writes the first data string, the second data string, and the third data string acquired by the acquisition unit in the order of acquisition from the write destination position in the predetermined storage area;
A restoration apparatus comprising:

(Supplementary note 11) A compression device executed by a processor,
A storage unit for storing the data string;
A detection unit that detects preceding data and subsequent data that is the same data as the preceding data from the data string;
A generation unit that generates compressed data having a quotient and a remainder obtained by dividing the position of the preceding data detected by the detection unit, the length of the preceding data that is equal to or longer than a predetermined length by the predetermined length;
A storage unit for storing the data string obtained by replacing the subsequent data with the compressed data generated by the generation unit;
A compression apparatus comprising:

(Supplementary note 12) A compression device executed by a processor,
A storage unit for storing the data string;
A detection unit that detects preceding data and subsequent data that is the same data as the preceding data from the data string;
Of the position of the subsequent data in the data string and a plurality of positions delimited in units of a predetermined length from the head of the data string, the position is on the end side of the position of the subsequent data, and from the position of the subsequent data A position that is within the range of the predetermined length, and a specifying unit that specifies a section length;
Generates compressed data having a quotient and a remainder obtained by dividing the position of the preceding data detected by the detection unit, the length of the preceding data that is equal to or greater than the predetermined length, by subtracting the section length by the predetermined length A generator to
A storage unit for storing the data string obtained by replacing the subsequent data with the compressed data generated by the generation unit;
A compression apparatus comprising:

(Supplementary note 13) A processor having a register of a predetermined length is
A compressed data string including a reference position of uncompressed data to be a reference destination, compressed data having a quotient and a remainder obtained by dividing the length of the uncompressed data that is not less than the predetermined length by the predetermined length, and the uncompressed data Detecting the compressed data from the storage unit for storing
Among reference destination data strings starting from a reference position included in the detected compressed data, a first data string having a length obtained by multiplying the predetermined length by the quotient is obtained in the predetermined length unit, and the reference Obtaining a second data string having the extra length obtained by removing the first data string from a previous data string;
Writing the first data string acquired in units of the predetermined length to a predetermined storage area and writing the acquired second data string to the predetermined storage area;
A restoration method characterized by executing processing.

(Supplementary Note 14) A processor having a register of a predetermined length is
Of the write destination position in a predetermined storage area and a plurality of positions delimited by the predetermined length unit from the beginning of the predetermined storage area, the write destination position is on the end side and the write Specify the section length between the previous position and the position within the predetermined length range,
A reference position of uncompressed data as a reference destination, compressed data having a quotient obtained by dividing the length of the uncompressed data that is equal to or longer than the predetermined length by the predetermined length and a remainder, and the remainder; The compressed data is detected from a storage unit that stores a compressed data string including uncompressed data,
In order from the beginning of the reference destination data starting from the reference position included in the detected compressed data, the first data string that is the section length, and the predetermined length unit that is the length obtained by multiplying the predetermined length by the quotient A second data string and a third data string having the extra length,
Writing the first data string, the second data string, and the third data string in the order of acquisition from the write destination position in the predetermined storage area;
A restoration method characterized by executing processing.

(Supplementary note 15)
Detecting preceding data and subsequent data that is the same data as the preceding data from the storage unit that stores the data string,
Generating the compressed data having the position of the detected preceding data, the quotient obtained by dividing the length of the preceding data that is equal to or longer than the predetermined length by the predetermined length, and the remainder;
Storing the data string in which the subsequent data is replaced with the generated compressed data;
A compression method characterized by executing processing.

(Supplementary Note 16) The processor
Detecting preceding data and subsequent data that is the same data as the preceding data from the storage unit that stores the data string,
Of the position of the subsequent data in the data string and a plurality of positions delimited in units of a predetermined length from the head of the data string, the position is on the end side of the position of the subsequent data, and from the position of the subsequent data Specify the section length of the position within the predetermined length range,
Generating a compressed data having a quotient and a remainder obtained by dividing a length obtained by subtracting the section length from the position of the preceding data detected, the length of the preceding data that is equal to or longer than the predetermined length, and the predetermined length;
Storing the data string in which the subsequent data is replaced with the generated compressed data;
A compression method characterized by executing processing.

DESCRIPTION OF SYMBOLS 100 Information processing apparatus 2501, 3601 Identification part 301,1701,502,3602 Storage part 302,1702,2503,3603 Detection part 303,2504 Generation part 304,2505 Storage part 1703,3604 Acquisition part 1704,3605 Storage part

Claims (12)

To a processor having a register of a predetermined length,
A compressed data string including a reference position of uncompressed data to be a reference destination, compressed data having a quotient and a remainder obtained by dividing the length of the uncompressed data that is not less than the predetermined length by the predetermined length, and the uncompressed data Detecting the compressed data from the storage unit for storing
Among reference destination data starting from a reference position included in the detected compressed data, a first data string having a length obtained by multiplying the predetermined length by the quotient is obtained in the predetermined length unit, and the reference destination Obtaining a second data string having the extra length obtained by removing the first data string from data;
Writing the first data string acquired in units of the predetermined length to a predetermined storage area and writing the acquired second data string to the predetermined storage area;
A restoration program characterized by causing a process to be executed. To a processor having a register of a predetermined length,
Of the write destination position in a predetermined storage area and a plurality of positions delimited by the predetermined length unit from the beginning of the predetermined storage area, the write destination position is on the end side and the write Specify the section length between the previous position and the position within the predetermined length range,
A reference position of uncompressed data as a reference destination, compressed data having a quotient obtained by dividing the length of the uncompressed data that is equal to or longer than the predetermined length by the predetermined length and a remainder, and the remainder; The compressed data is detected from a storage unit that stores a compressed data string including uncompressed data,
In order from the beginning of the reference destination data starting from the reference position included in the detected compressed data, the first data string that is the section length, and the predetermined length unit that is the length obtained by multiplying the predetermined length by the quotient A second data string and a third data string having the extra length,
Writing the first data string, the second data string, and the third data string in the order of acquisition from the write destination position in the predetermined storage area;
A restoration program characterized by causing a process to be executed. To the processor,
Detecting preceding data and subsequent data that is the same data as the preceding data from the storage unit that stores the data string,
Generating compressed data having a quotient and a remainder obtained by dividing the length of the preceding data by a predetermined length that is equal to or longer than a predetermined length that is a length of a register included in the position of the detected preceding data and a processor that performs restoration ;
Storing the data string in which the subsequent data is replaced with the generated compressed data;
A compression program characterized by causing processing to be executed. To the processor,
Detecting preceding data and subsequent data that is the same data as the preceding data from the storage unit that stores the data string,
Of the position of the subsequent data in the data string and a plurality of positions delimited in units of a predetermined length from the head of the data string, the position is on the end side of the position of the subsequent data, and from the position of the subsequent data Specify the section length of the position within the predetermined length range,
Generating a compressed data having a quotient and a remainder obtained by dividing a length obtained by subtracting the section length from the position of the preceding data detected, the length of the preceding data that is equal to or longer than the predetermined length, and the predetermined length;
Storing the data string in which the subsequent data is replaced with the generated compressed data;
A compression program characterized by causing processing to be executed. A restoration device executed by a processor having a register of a predetermined length,
A compressed data string including a reference position of uncompressed data to be a reference destination, compressed data having a quotient and a remainder obtained by dividing the length of the uncompressed data that is not less than the predetermined length by the predetermined length, and the uncompressed data A storage unit for storing
A detection unit for detecting the compressed data from the compressed data string;
A first data string having a length obtained by multiplying the predetermined length by the quotient among reference destination data strings starting from a reference position included in the compressed data detected by the detection unit is acquired in units of the predetermined length. And an acquisition unit that acquires the second data string having the extra length obtained by removing the first data string from the reference data string;
A storage unit that writes the first data string acquired by the acquisition unit in the predetermined length unit to a predetermined storage area and writes the second data string acquired by the acquisition unit to the predetermined storage area;
A restoration apparatus comprising: A restoration device executed by a processor having a register of a predetermined length,
Of the write destination position in a predetermined storage area and a plurality of positions delimited by the predetermined length unit from the beginning of the predetermined storage area, the write destination position is on the end side and the write A position that is within the range of the predetermined length from the previous position, and a specifying unit that specifies a section length;
A reference position of uncompressed data as a reference destination, compressed data having a quotient obtained by dividing the length of the uncompressed data that is equal to or longer than the predetermined length by the predetermined length and a remainder, and the remainder; A storage unit for storing a compressed data string including uncompressed data;
A detection unit for detecting the compressed data from the compressed data string;
In order from the beginning of the reference destination data starting from the reference position included in the compressed data detected by the detection unit, the first data string that is the section length and the length obtained by multiplying the predetermined length by the quotient An acquisition unit that acquires the second data string in the predetermined length unit and the third data string serving as the extra length;
A storage unit that writes the first data string, the second data string, and the third data string acquired by the acquisition unit in the order of acquisition from the write destination position in the predetermined storage area;
A restoration apparatus comprising: A compression device executed by a processor,
A storage unit for storing the data string;
A detection unit that detects preceding data and subsequent data that is the same data as the preceding data from the data string;
Compressed data having a quotient and remainder obtained by dividing the position of the preceding data detected by the detection unit, the length of the preceding data that is equal to or greater than the length of the register included in the processor that performs restoration, by the predetermined length A generating unit for generating
A storage unit for storing the data string obtained by replacing the subsequent data with the compressed data generated by the generation unit;
A compression apparatus comprising: A compression device executed by a processor,
A storage unit for storing the data string;
A detection unit that detects preceding data and subsequent data that is the same data as the preceding data from the data string;
Of the position of the subsequent data in the data string and a plurality of positions delimited in units of a predetermined length from the head of the data string, the position is on the end side of the position of the subsequent data, and from the position of the subsequent data A position that is within the range of the predetermined length, and a specifying unit that specifies a section length;
Generates compressed data having a quotient and a remainder obtained by dividing the position of the preceding data detected by the detection unit, the length of the preceding data that is equal to or greater than the predetermined length, by subtracting the section length by the predetermined length A generator to
A storage unit for storing the data string obtained by replacing the subsequent data with the compressed data generated by the generation unit;
A compression apparatus comprising: A processor having a register of a predetermined length
A compressed data string including a reference position of uncompressed data to be a reference destination, compressed data having a quotient and a remainder obtained by dividing the length of the uncompressed data that is not less than the predetermined length by the predetermined length, and the uncompressed data Detecting the compressed data from the storage unit for storing
Among reference destination data strings starting from a reference position included in the detected compressed data, a first data string having a length obtained by multiplying the predetermined length by the quotient is obtained in the predetermined length unit, and the reference Obtaining a second data string having the extra length obtained by removing the first data string from a previous data string;
Writing the first data string acquired in units of the predetermined length to a predetermined storage area and writing the acquired second data string to the predetermined storage area;
A restoration method characterized by executing processing. A processor having a register of a predetermined length
Of the write destination position in a predetermined storage area and a plurality of positions delimited by the predetermined length unit from the beginning of the predetermined storage area, the write destination position is on the end side and the write Specify the section length between the previous position and the position within the predetermined length range,
A reference position of uncompressed data as a reference destination, compressed data having a quotient obtained by dividing the length of the uncompressed data that is equal to or longer than the predetermined length by the predetermined length and a remainder, and the remainder; The compressed data is detected from a storage unit that stores a compressed data string including uncompressed data,
In order from the beginning of the reference destination data starting from the reference position included in the detected compressed data, the first data string that is the section length, and the predetermined length unit that is the length obtained by multiplying the predetermined length by the quotient A second data string and a third data string having the extra length,
Writing the first data string, the second data string, and the third data string in the order of acquisition from the write destination position in the predetermined storage area;
A restoration method characterized by executing processing. Processor
Detecting preceding data and subsequent data that is the same data as the preceding data from the storage unit that stores the data string,
Generating compressed data having a quotient and a remainder obtained by dividing the length of the preceding data by a predetermined length that is equal to or longer than a predetermined length that is a length of a register included in the position of the detected preceding data and a processor that performs restoration ;
Storing the data string in which the subsequent data is replaced with the generated compressed data;
A compression method characterized by executing processing. Processor
Detecting preceding data and subsequent data that is the same data as the preceding data from the storage unit that stores the data string,
Of the position of the subsequent data in the data string and a plurality of positions delimited in units of a predetermined length from the head of the data string, the position is on the end side of the position of the subsequent data, and from the position of the subsequent data Specify the section length of the position within the predetermined length range,
Generating a compressed data having a quotient and a remainder obtained by dividing a length obtained by subtracting the section length from the position of the preceding data detected, the length of the preceding data that is equal to or longer than the predetermined length, and the predetermined length;
Storing the data string in which the subsequent data is replaced with the generated compressed data;
A compression method characterized by executing processing.

Images