Data compression method for efficiently compressing data based on data periodicity

Claim 2

A data compression method for compressing an input data stream and outputting the encoded stream, comprising the steps of: storing encoded input data in a moving window having a predetermined size; comparing a partial sequence starting from a given position (entry) in the moving window with a data sequence to be encoded by a plurality of comparators; finding an entry having a maximum matching length by a matching finder in comparison by the plurality of comparators; and encoding a pair of offsets up to the entry and a matching length (offsets and matching length) by a matching code generator when matching is found by the matching finder, wherein the number of comparators is smaller than the size of the moving window, and some of offsets near offset 0 (0 indicates including no offset), offsets near offset L, offsets near offset 2L, offsets near offsets 3L, . . . are used as entries.

Claim 3

A data compression method according to claim 1 , characterized in that L which defines an offset is an externally supplied parameter.

Claim 4

A data compression method according to claim 1 , wherein when the input data is image data, L which defines an offset is a line length of the input image data.

Claim 5

A data compression method according to claim 1 , wherein L which defines an offset is an externally supplied parameter, and offsets M, 2M, . . . (M is an externally supplied parameter; M<L), offsets L±M, L±2M, . . . , and offsets 2L±M, 2L±2M, . . . are respectively employed as offsets near offset 0, offsets near offset L, and offsets near offset 2L.

Claim 6

A data compression method according to claim 1 , wherein when the input data is image data of pixels each having n bytes (n: an integer not less than 2), L which defines an offset is an externally supplied parameter, and offsets M, 2M, . . . (M=n; M<L), offsets L+M, L±2M, . . . , and offsets 2L±M, 2L±2M, are respectively employed as offsets near offset 0, offsets near offset L, and offsets near offset 2L.

Claim 7

A data compression method according to claim 1 , wherein when the input data is a dot image or centralized dither image having an interval of n bytes between dots in a main scanning direction or between peaks in a centralized dither, L which defines an offset is a line length of the input image data, and offsets M, 2M, . . . (M=n; M<L), offsets L±M, L±2M, . . . , and offsets 2L±M, 2L±2M, . . . are respectively employed as offsets near offset 0, offsets near offset L, and offsets near offset 2L.

Claim 8

A data compression method according to claim 1 , wherein when the input data is image data of pixels each having m bits (m is a natural number which cannot be divided by 8), L which defines an offset is an externally supplied parameter, and offsets M, 2M, . . . (M=a least common multiple of m and 8; M<L), offsets L±M, L±2M, . . . , and offsets 2L±M, 2L±2M, . . . are respectively employed as offsets near offset 0, offsets near offset L, and offsets near offset 2L.

Claim 9

A data compression method according to claim 1 , wherein when the input data is a dot image or centralized dither image having an interval of m bits (m is a natural number which cannot be divided by 8) between dots in a main scanning direction or between peaks in a centralized dither, L which defines an offset is a line length of the input image data, and offsets M, 2M, . . . (M=a least common multiple of m and 8; M<L), offsets L±M, L±2M, . . . , and offsets 2L±M, 2L±2M, . . . are respectively employed as offsets near offset 0, offsets near offset L, and offsets near offset 2L.

Claim 10

A data compression method for compressing an input data stream and outputting the encoded stream, wherein comprising the steps of: rearranging by a pre-processing unit a byte order of the input data stream: 0, 1, 2, 3, . . . , L, L+1, L+2, . . . , 2L, 2L+1, 2L+2, . . . into 0, L, 2L, . . . , nL, 1, L+1, 2L+1, . . . , nL+1, 2, L+2, 2L+2, . . . , nL+2, . . . (n=1, 2, . . . ); and compressing the input data stream rearranged by the pre-processing unit, by a compression apparatus main body and outputting the encoded stream, wherein the step of outputting the encoded stream by the compression apparatus main body comprises the steps of: storing encoded input data to a moving window having a predetermined size; comparing a partial sequence starting from a given position (entry) in the moving window with a data sequence to be encoded by a plurality of comparators; finding an entry having a maximum matching length by a matching finder in comparison by the plurality of comparators; and encoding a pair of offsets up to the entry and a matching length (offsets and matching length) by a matching code generator when matching is found by the matching finder, wherein the number of comparators is smaller than the size of the moving window, and some of offsets near offset 0 (0 indicates including no offset), offsets near offset L (L is an externally supplied parameter), offsets near offset 2L, offsets near offsets 3L, . . . are used as entries.

Claim 11

A data compression method for compressing an input data stream and outputting the encoded stream, wherein comprising the steps of: rearranging by a pre-processing unit a byte order of the input data stream: 0, 1, 2, 3, . . . , L, L+1, L+2, . . . , 2L, 2L+1, 2L+2, . . . into 0, L, 2L, . . . , nL, 1, L+1, 2L+1, . . . , nL+1, 2, L+2, 2L+2, . . . , nL+2, . . . (n=1, 2, . . . ); and compressing the input data stream rearranged by the pre-processing unit, by a compression apparatus main body and outputting the encoded stream, wherein the step of outputting the encoded stream by the compression apparatus main body comprises the steps of: storing encoded input data to a moving window having a predetermined size; comparing a partial sequence starting from a given position (entry) in the moving window with a data sequence to be encoded by a plurality of comparators; finding an entry having a maximum matching length by a matching finder in comparison by the plurality of comparators; and encoding a pair of offsets up to the entry and a matching length (offsets and matching length) by a matching code generator when matching is found by the matching finder, wherein the number of comparators is smaller than the size of the moving window, and some of offsets near offset 0 (0 indicates including no offset), offsets near offset L (L is an externally supplied parameter), offsets near offset 2L, offsets near offsets 3L, . . . are used as entries.

Claim 12

A data compression method according to claim 9 , wherein when the input data is image data, L which defines an offset is a line length of the input image data.

Claim 13

A data compression method according to claim 9 , wherein when the input data is image data, L which defines an offset is a line length of the input image data, and when a transfer source of the input data is a memory, a readout order (order to supply addresses) is set to a head of a 0th line, a head of a first line, . . . , a head of an nth line, the next of the 0th line, the next of the first line, . . . , the next of the nth line, and processing is done by a pre-processing unit corresponding to a readout unit.

Claim 14

A data compression method for compressing an input data stream and outputting the encoded stream, wherein comprising the steps of: rearranging by a pre-processing unit a byte order of the input data stream: 0, 1, 2, 3, . . . L, L+1, L+2, . . . 2L, 2L+1, 2L+2, . . . into 0, L, 2L, . . . nL, 1, L+1, 2L+1, . . . , nL+1, 2, L+2, 2L+2, . . . , nL+2, . . . (n=1, 2, . . . ); and compressing the input data stream rearranged by the pre-processing unit, by a compression apparatus main body and outputting the encoded stream, wherein the step of outputting the encoded stream by the compression apparatus main body comprises the steps of: storing encoded input data to a moving window having a predetermined size; comparing a partial sequence starting from a given position (entry) in the moving window with a data sequence to be encoded by a plurality of comparators; finding an entry having a maximum matching length by a matching finder in comparison by the plurality of comparators; and encoding a pair of offsets up to the entry and a matching length (offsets and matching length) by a matching code generator when matching is found by the matching finder, wherein the number of comparators is smaller than the size of the moving window, and some of offsets near offset 0 (0 indicates including no offset), offsets near offset nL, offsets near offset 2nL, offsets near offsets 3nL, . . . are used as entries.

Claim 15

A data compression method for compressing an input data stream and outputting the encoded stream, wherein comprising the steps of: rearranging by a pre-processing unit a byte order of the input data stream: 0, 1, 2, 3, . . . L, L+1, L+2, . . . 2L, 2L+1, 2L+2, . . . into 0, L, 2L, . . . nL, 1, L+1, 2L+1, . . . , nL+1, 2, L+2, 2L+2, . . . , nL+2, . . . (n=1, 2, . . . ); and compressing the input data stream rearranged by the pre-processing unit, by a compression apparatus main body and outputting the encoded stream, wherein the step of outputting the encoded stream by the compression apparatus main body comprises the steps of: storing encoded input data to a moving window having a predetermined size; comparing a partial sequence starting from a given position (entry) in the moving window with a data sequence to be encoded by a plurality of comparators; finding an entry having a maximum matching length by a matching finder in comparison by the plurality of comparators; and encoding a pair of offsets up to the entry and a matching length (offsets and matching length) by a matching code generator when matching is found by the matching finder, wherein the number of comparators is smaller than the size of the moving window, and some of offsets near offset 0 (0 indicates including no offset), offsets near offset nL, offsets near offset 2nL, offsets near offsets 3nL, . . . are used as entries.

Claim 16

A data compression method according to claim 12 , wherein when the input data is image data, L which defines an offset is a line length of the input image data.

Claim 17

A data compression method according to claim 12 , wherein when the input data is image data, L which defines an offset is a line length of the input image data, and when a transfer source of the input data is a memory, a readout order (order to supply addresses) is set to a head of a 0 th line, a head of a first line, . . . , a head of an nth line, the next of the 0 th line, the next of the first line, . . . , the next of the nth line, . . . and processing is done by a pre-processing unit corresponding to a readout unit.

Claim 18

A data compression method for compressing an input data stream and outputting the encoded stream, comprising the steps of: storing encoded input data in a moving window having a predetermined size; comparing a partial sequence starting from a given position (entry) in the moving window with a data sequence to be encoded by a plurality of comparators; finding an entry having a maximum matching length by a matching finder in comparison by the plurality of comparators; encoding a pair of offsets up to the entry and a matching length (offsets and matching length) by a matching code generator when matching is found by the matching finder, wherein the number of comparators is smaller than the size of the moving window, and at least one of offsets near offset 0 (0 indicates including no offset) and near offset L are used as entries; rearranging by a pre-processing unit a byte order of an input data stream: 0, 1, 2, 3, . . . , L, . . . (L is a rearrangement cycle, L=p×q, p and q are integers not less than 2) into 0, p, 2p, . . . , (q−1)p 1, p+1, 2p+1, . . . , (q−1)p+1 2, p+2, 2p+2, . . . , (q−1)p+2 . . . . . . p−1, p+[1] p −1, 2p+p−1, . . . , (q−1)p+p−1; and compressing the input data stream rearranged by the pre-processing unit and outputting the encoded stream by a compression apparatus main body.

Claim 19

A data compression method for compressing an input data stream and outputting the encoded stream, comprising the steps of: storing encoded input data in a moving window having a predetermined size; comparing a partial sequence starting from a given position (entry) in the moving window with a data sequence to be encoded by a plurality of comparators; finding an entry having a maximum matching length by a matching finder in comparison by the plurality of comparators; encoding a pair of offsets up to the entry and a matching length (offsets and matching length) by a matching code generator when matching is found by the matching finder, wherein the number of comparators is smaller than the size of the moving window, and at least one of offsets near offset 0 (0 indicates including no offset) and near offset L are used as entries; rearranging by a pre-processing unit a byte order of an input data stream: 0, 1, 2, 3, . . . , L, . . . (L is a rearrangement cycle, L=p×q, p and q are integers not less than 2) into 0, p, 2p, . . . , (q−1)p 1, p+1, 2p+1, . . . , (q−1)p+1 2, p+2, 2p+2, . . . , (q−1)p+2 . . . . . . p−1, p+[1] p −1, 2p+p−1, . . . , (q−1)p+p−1; and compressing the input data stream rearranged by the pre-processing unit and outputting the encoded stream by a compression apparatus main body.

Claim 20

A data compression method for compressing an input data stream and outputting the encoded stream, comprising the steps of: storing encoded input data in a moving window having a predetermined size; comparing a partial sequence starting from a given position (entry) in the moving window with a data sequence to be encoded by a plurality of comparators; finding an entry having a maximum matching length by a matching finder in comparison by the plurality of comparators; encoding a pair of offsets up to the entry and a matching length (offsets and matching length) by a matching code generator when matching is found by the matching finder, wherein the number of comparators is smaller than the size of the moving window, and at least one of offsets near offset 0 (0 indicates including no offset) and near offset L are used as entries; rearranging by a pre-processing unit a byte order of an input data stream: 0, 1, 2, 3, . . . , L, into 0, 2, 4, . . . , L−2, 1, 3, 5, . . . , L−1, . . . (L is an even number) or 0, 2, 4, . . . , L−1, 1, 3, 5, . . . , L−2, . . . (L is an odd number); and compressing the input data stream rearranged by the pre-processing unit and outputting the encoded stream by a compression type compression apparatus.

Claim 21

A data compression method for compressing an input data stream and outputting the encoded stream, comprising the steps of: storing encoded input data in a moving window having a predetermined size; comparing a partial sequence starting from a given position (entry) in the moving window with a data sequence to be encoded by a plurality of comparators; finding an entry having a maximum matching length by a matching finder in comparison by the plurality of comparators; encoding a pair of offsets up to the entry and a matching length (offsets and matching length) by a matching code generator when matching is found by the matching finder, wherein the number of comparators is smaller than the size of the moving window, and at least one of offsets near offset 0 (0 indicates including no offset) and near offset L are used as entries; rearranging by a pre-processing unit a byte order of an input data stream: 0, 1, 2, 3, . . . , L, into 0, 2, 4, . . . , L−2, 1, 3, 5, . . . , L−1, . . . (L is an even number) or 0, 2, 4, . . . , L−1, 1, 3, 5, . . . , L−2, . . . (L is an odd number); and compressing the input data stream rearranged by the pre-processing unit and outputting the encoded stream by a compression type compression apparatus.

Claim 22

A data compression method for compressing an input data stream and outputting the encoded stream, comprising the steps of: storing encoded input data to a moving window having a predetermined size; comparing a partial sequence starting from a given position (entry) in the moving window with a data sequence to be encoded by a plurality of comparators; finding an entry having a maximum matching length by a matching finder in comparison by the plurality of comparators; and encoding a pair of offsets up to the entry and a matching length (offsets and matching length) by a matching code generator when matching is found by the matching finder, wherein the number of comparators is smaller than the size of the moving window, and at least one of offsets near offset 0 (0 indicates including no offset) and near offset L are used as entries.

Claim 23

A data compression method for compressing an input data stream and outputting the encoded stream, comprising the steps of: storing encoded input data to a moving window having a predetermined size; comparing a partial sequence starting from a given position (entry) in the moving window with a data sequence to be encoded by a plurality of comparators; finding an entry having a maximum matching length by a matching finder in comparison by the plurality of comparators; and encoding a pair of offsets up to the entry and a matching length (offsets and matching length) by a matching code generator when matching is found by the matching finder, wherein the number of comparators is smaller than the size of the moving window, and at least one of offsets near offset 0 (0 indicates including no offset) and near offset L are used as entries.

Claim 24

A data compression method according to claim 17 , characterized in that L which defines an offset is an externally supplied parameter.

Claim 25

A data compression method according to claim 17 , wherein when the input data is image data, L which defines an offset is a line length of the input image data.

Claim 26

A data compression method according to claim 17 , wherein L which defines an offset is an externally supplied parameter, and offsets M, where M is an externally supplied parameter and M<L, and L±M are respectively employed as offsets near offset 0, and near offset L.

Claim 27

A data compression method according to claim 17 , wherein when the input data is image data of pixels each having n bytes, n being an integer not less than 2, L which defines an offset is an externally supplied parameter, and offsets M, where M=n and M<L, and L±M are respectively employed as offsets near offset 0 and near offset L.

Claim 28

A data compression method according to claim 17 , wherein when the input data is a dot image or centralized dither image having an interval of n bytes between dots in a main scanning direction or between peaks in a centralized dither, L which defines an offset is a line length of the input image data, and offsets M and L±M are respectively employed as offsets near offset 0 and near offset L.

Claim 29

A data compression method according to claim 17 , wherein when the input data is image data of pixels each having m bits, m being a natural number which cannot be divided by 8, L which defines an offset is an externally supplied parameter, and offsets M, where M=a least common multiple of m and 8 and M<L, and L±M are respectively employed as offsets near offset 0 and near offset L.

Claim 30

A data compression method according to claim 17 , wherein when the input data is a dot image or centralized dither image having an interval of m bits, where m is a natural number which cannot be divided by 8, between dots in a main scanning direction or between peaks in a centralized dither, L which defines an offset is a line length of the input image data, and offsets M, wherein M=a least common multiple of m and 8 and M<L, and L±M are respectively employed as offsets near offset 0 and near offset L.

Claim 31

A data compression method for compressing an input data stream and outputting the encoded stream, comprising the steps of: storing encoded input data in a moving window having a predetermined size; comparing a partial sequence starting from a given position (entry) in the moving window with a data sequence to be encoded by a plurality of comparators; finding an entry having a maximum matching length by a matching finder in comparison by the plurality of comparators; encoding a pair of offsets up to the entry and a matching length (offsets and matching length) by a matching code generator when matching is found by the matching finder, wherein the number of comparators is smaller than the size of the moving window, and at least one of offsets near offset 0 (0 indicates including no offset) and near offset L are used as entries; rearranging by a pre-processing unit an order of m-bit bytes (m=p×q; p is an integer not less than 1 and q is an integer not less than 2) of the input data stream: First Line: 0, 1, 2, . . . , Second Line: L, L+1, L+2, . . . , . . . . . . qth Line: (q−1)L, (q−1)L+1, (q−1)L+2, . . . , qL−1 into a new first byte made up of m bits: 0 : b(0), . . . , 0 : b(p−1), L : b(0), . . . , L : b(p−1), . . . . . . (q−1)L : b(0), . . . , (q−1)L : b(p−1) a new second byte made up of m bits: 0 : b(0), . . . , 0 : b(2p−1), L : b(0), . . . , L : b(2p−1), . . . . . . (q−1)L : b(0), . . . , (q−1)L : b(2p−1) . . . . . . a new qth byte made up of m bits: 0 : b((q−1)p), . . . , 0 : b(qp−1), L : b((q−1)p), . . . , L : b(q2p−1), . . . . . . (q−1)L : b((q−1)p), . . . , (q−1)L : b(q2p−1) a new (q+1)th byte made up of m bits: 1 : b(0), . . . , 1 : b(p−1), L+1 : b(0), . . . , L+1 : b(p−1), . . . . . . (q−1)L+1 : b(0), . . . , (q−1)L+1 : b(p−1) . . . . . . a new (q+2)th byte made up of m bits: 1 : b(p), . . . , 1 : b(2p−1), L+1 : b(p), . . . , L+1 : b(2p−1), . . . . . . (q−1)L+1 : b(p), . . . , (q−1)L+1 : b(2p−1) . . . . . . a new 2qth byte made up of m bits: 1 : b((q−1)p), . . . , 1 : b(qp−1), L+1 : b((q−1)p), . . . , L+1 : b(q2p−1), . . . . . . (q−1)L+1 : b((q−1)p), . . . , (q−1)L+1 : b(q2p−1) . . . . . . wherein the first, second, . . . , mth bits within a byte are respectively represented by b(0), b(1), . . . , b(m−1), and left and right sides of “0: b(0)” respectively represent the byte order of an input stream and a bit in the byte; and compressing the input data stream rearranged by the pre-processing unit and outputting the encoded stream by a compression type compression apparatus main body.

Claim 32

A data compression method for compressing an input data stream and outputting the encoded stream, comprising the steps of: storing encoded input data in a moving window having a predetermined size; comparing a partial sequence starting from a given position (entry) in the moving window with a data sequence to be encoded by a plurality of comparators; finding an entry having a maximum matching length by a matching finder in comparison by the plurality of comparators; encoding a pair of offsets up to the entry and a matching length (offsets and matching length) by a matching code generator when matching is found by the matching finder, wherein the number of comparators is smaller than the size of the moving window, and at least one of offsets near offset 0 (0 indicates including no offset) and near offset L are used as entries; rearranging by a pre-processing unit an order of m-bit bytes (m=p×q; p is an integer not less than 1 and q is an integer not less than 2) of the input data stream: First Line: 0, 1, 2, . . . , Second Line: L, L+1, L+2, . . . , . . . . . . qth Line: (q−1)L, (q−1)L+1, (q−1)L+2, . . . , qL−1 into a new first byte made up of m bits: 0 : b(0), . . . , 0 : b(p−1), L : b(0), . . . , L : b(p−1), . . . . . . (q−1)L : b(0), . . . , (q−1)L : b(p−1) a new second byte made up of m bits: 0 : b(0), . . . , 0 : b(2p−1), L : b(0), . . . , L : b(2p−1), . . . . . . (q−1)L : b(0), . . . , (q−1)L : b(2p−1) . . . . . . a new qth byte made up of m bits: 0 : b((q−1)p), . . . , 0 : b(qp−1), L : b((q−1)p), . . . , L : b(q2p−1), . . . . . . (q−1)L : b((q−1)p), . . . , (q−1)L : b(q2p−1) a new (q+1)th byte made up of m bits: 1 : b(0), . . . , 1 : b(p−1), L+1 : b(0), . . . , L+1 : b(p−1), . . . . . . (q−1)L+1 : b(0), . . . , (q−1)L+1 : b(p−1) . . . . . . a new (q+2)th byte made up of m bits: 1 : b(p), . . . , 1 : b(2p−1), L+1 : b(p), . . . , L+1 : b(2p−1), . . . . . . (q−1)L+1 : b(p), . . . , (q−1)L+1 : b(2p−1) . . . . . . a new 2qth byte made up of m bits: 1 : b((q−1)p), . . . , 1 : b(qp−1), L+1 : b((q−1)p), . . . , L+1 : b(q2p−1), . . . . . . (q−1)L+1 : b((q−1)p), . . . , (q−1)L+1 : b(q2p−1) . . . . . . wherein the first, second, . . . , mth bits within a byte are respectively represented by b(0), b(1), . . . , b(m−1), and left and right sides of “0: b(0)” respectively represent the byte order of an input stream and a bit in the byte; and compressing the input data stream rearranged by the pre-processing unit and outputting the encoded stream by a compression type compression apparatus main body.