Data compression method, data compression device, data decompression method, and data decompression device

Patent metadata

Field	Value
Publication number	US-11606103-B2
Application number	US-202117443369-A
Country	US
Kind code	B2
Filing date	Jul 26, 2021
Priority date	Sep 15, 2020
Publication date	Mar 14, 2023
Grant date	Mar 14, 2023

Abstract

A data compression method includes inputting a data sequence that includes first data strings and second data strings alternating with each other, each of the first data strings containing one or more first data all of which have a same predetermined value, each of the second data strings containing one or more second data different from the predetermined value, determining first numbers and second numbers from a beginning of the input data sequence sequentially, each of the first numbers being a number of the first data in a respective one of the first data strings, and each of the second numbers being a number of the second data in a respective one of the second data strings, and arranging the first numbers, the second numbers, and the second data strings in a cyclic manner to generate compressed data.

First claim

What is claimed is:

1. A data compression method comprising:
inputting a data sequence that includes first data strings and second data strings alternating with each other, each of the first data strings containing one or more first data all of which have a same predetermined value, and each of the second data strings containing one or more second data which are different from the predetermined value;
determining first numbers and second numbers from a beginning of the input data sequence sequentially, each of the first numbers being a number of the first data in a respective one of the first data strings, and each of the second numbers being a number of the second data in a respective one of the second data strings; and
arranging the first numbers, the second numbers, and the second data strings in a cyclic manner to generate compressed data such that each cycle includes one of the first numbers, one of the second numbers, and one of the second data strings containing one or more second data that are equal in number to the one of the second numbers.

2. The data compression method as claimed in claim 1 , further comprising:
calculating a first maximum number, the first maximum number being a maximum value of the first numbers;
arranging a header before a body in which the compressed data is arranged, the header including the calculated first maximum number; and
representing the first numbers arranged in the body by using a minimum number of bits that can represent the first maximum number.

3. The data compression method as claimed in claim 2 , further comprising:
calculating a second maximum number, the second maximum number being a maximum value of the second numbers;
arranging the calculated second maximum number in the header; and
representing the second numbers arranged in the body by using a minimum number of bits that can represent the second maximum number.

4. The data compression method as claimed in claim 2 , further comprising:
arranging presence information in the header, the presence information indicating whether each of the first numbers is present as a number of the first data in a corresponding one of the first data strings included in the data sequence;
assigning serial numbers to the first numbers that are present; and
arranging the serial numbers in the body instead of the first numbers.

5. The data compression method as claimed in claim 1 , further comprising:
searching for a combination of a first division number and a number of bits for each of first code values assigned to the plurality of first groups, so that a size of the compressed data becomes minimum, the first division number being a number of a plurality of first groups, in a case where the first numbers that appear are divided into the plurality of first groups in order from a smallest value, a corresponding value of the first code values is assigned to each of the first numbers that appear to arrange the first code values instead of the first numbers to generate the compressed data, the number of bits of the corresponding value of the first code values is different for each of the plurality of first groups, and the number of bits of the corresponding value of the first code values decreases as a first group to which the corresponding value is assigned among the plurality of first groups includes a smaller value of the first numbers;
arranging a header before a body in which the compressed data is arranged, the header including the searched first division number and first bit number information, and the first bit number information indicating the number of bits for each of the first code values assigned to the plurality of first groups; and
arranging the first code values in the body instead of the first numbers.

6. The data compression method as claimed in claim 5 , further comprising:
searching for a combination of a second division number of a plurality of second groups and a number of bits for each of second code values assigned to the plurality of second groups, so that the size of the compressed data becomes minimum, in a case where the second numbers that appear are divided into the plurality of second groups in order from a smallest value, a corresponding value of the second code values is assigned to each of the second numbers that appear to arrange the second code values instead of the second numbers to generate the compressed data, the number of bits of the corresponding value of the second code values is different for each of the plurality of second groups, and the number of bits of the corresponding value of the second code values decreases as a second group to which the corresponding value of the second code values is assigned among the plurality of second groups includes a smaller value of the second numbers;
arranging the header before the body in which the compressed data is arranged, the header including the searched second division number and second bit number information, and the second bit number information indicating the number of bits for each of the second code values assigned to the plurality of second groups; and
arranging the second code values in the body instead of the second numbers.

7. The data compression method as claimed in claim 2 , further comprising:
arranging start information in the header, the start information indicating whether leading data of the data sequence is the first data or the second data;
arranging one of the first numbers, one of the second numbers, and one of the second data strings, or one of the second numbers, one of the second data strings, and one of the first numbers sequentially in accordance with the start information to generate the compressed data.

8. The data compression method as claimed in claim 7 , further comprising:
arranging end information in the header, the end information indicating whether last data of the data sequence is the first data or the second data;
arranging one of the first numbers or one of the second numbers and one of the second data strings in the last data of the compressed data in accordance with the end information; and
adding padding to the last data of the compressed data, in a case where the last data of the compressed data is not byte data.

9. The data compression method as claimed in claim 1 , wherein the data sequence is differential data obtained by comparing data to be updated and updated data.

10. A data compression device comprising:
a processor; and
a memory storing program instructions that cause the processor to:
input a data sequence that includes first data strings and second data strings alternating with each other, each of the first data strings containing one or more first data all of which have a same predetermined value, and each of the second data strings containing one or more second data which are different from the predetermined value;
determine first numbers and second numbers from a beginning of the input data sequence sequentially, each of the first numbers being a number of the first data in a respective one of the first data strings, and each of the second numbers being a number of the second data in a respective one of the second data strings; and
arrange the first numbers, the second numbers, and the second data strings in a cyclic manner to generate compressed data such that each cycle includes one of the first numbers, one of the second numbers, and one of the second data strings containing one or more second data that are equal in number to the one of the second numbers.

11. A non-transitory computer-readable recording medium having stored therein a data compression program for causing a computer to perform a process comprising:
inputting a data sequence that

Assignees

• Fuji Electric Co Ltd

Inventors

• Takatsukasa Kenji

Classifications

• H03M7/40 Primary

  Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code · CPC title

• H03M7/48 Primary

  alternating with other codes during the code conversion process, e.g. run-length coding being performed only as long as sufficientlylong runs of digits of the same kind are present · CPC title