Data compression device, memory system and method

A method for compression of data to be written into a nonvolatile memory, the method comprising:

• performing a first process of sequentially storing input data in a history buffer, to refer to the history buffer as a dictionary in which past input data is stored to search for a first piece of past input data matching a first piece of new input data in parallel for N (N is a natural number equal to or greater than 2) sequences of search units each having a length of N times one data length, each head of the first piece of new input data being shifted by the one data length, and outputting match information including a relative position from the first piece of new input data indicating a position of the first piece of past input data matching the first piece of new input data on the history buffer and a match length from the head;
• when at least one match information is output from the performing the first process and the at least one match information includes the match information of which the match length is N times the one data length, performing a second process of selecting the match information of which the match length is N times the one data length from the at least one match information, comparing a second piece of past input data subsequent to the first piece of past input data indicated by the match information with a second piece of new input data subsequent to the first piece of new input data of a sequence for which the match information has been output, and outputting the match information including a relative position from the second piece of new input data subsequent to the first piece of new input data indicating a position of the second piece of past input data subsequent to the first piece of past input data on the history buffer and a match length from the head;
• performing a third process of generating compressed data by replacing a part of the input data with match information using the match information output from the performing the first process and the match information output from the performing the second process;
• and
• when a plurality of match information are consecutive in the compressed data generated by the performing the third process and the plurality of match information each have the relative position of an identical value, performing a forth process of replacing the plurality of match information in the compressed data with single match information including a relative position of the identical value and a match length obtained by summing the match length of each of the plurality of match information.