# US 2026/0064273 A1 · Method, compression encoder, and compression/decompression system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2026/0064273 A1
- Document ID: US20260064273A1
- Status: Published application
- Kind: A1
- Application number: 19/069,591
- Filed: 2025-03-04
- Published: 2026-03-05
- Earliest claimed: 2024-08-28
- Assignees: Kioxia Corporation
- Applicants: Kioxia Corporation
- Inventors: Youhei FUKAZAWA; Kohei OIKAWA; Keiri NAKANISHI; Masato SUMIYOSHI
- Web page: https://patentgrep.com/patent/US20260064273A1

## CPC

- G06F 3/0608: {Saving storage space on storage systems}
- G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling}
- G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

According to one embodiment, a method includes identifying an input string of less than the predetermined length as a mismatch character string, determining whether the mismatch character string matches the character strings in a buffer, storing, as to the matched mismatch character string, a first data set including flag information indicating a match and index information indicating the entry of the buffer in which the mismatch character string determined to be a match is stored, in a nonvolatile memory, and storing the unmatched mismatch character string in the buffer, and storing, as to the unmatched mismatch character string, a second data set including flag information indicating the mismatch and the mismatch character strings, in the nonvolatile memory.

## Claims

### Claim 1

A method of controlling a nonvolatile memory, the method comprising:
outputting information as compressed data, the information indicating a result of comparison between an input string of a predetermined length or longer and a string which has appeared previously;
storing data based on the output compressed data in the nonvolatile memory;
identifying an input string of less than the predetermined length as a mismatch character string;
determining whether or not the identified mismatch character string matches one of the mismatch character strings in the buffer where the mismatch character strings that have appeared previously are stored;
storing, as to the identified mismatch character string matching any of the mismatch character strings in the buffer, data based on a first data set including flag information indicating a match and index information indicating the entry of the buffer in which the mismatch character string determined to be a match is stored, in the nonvolatile memory; and
storing the identified mismatch character string which does not match any of the mismatch character strings in the buffer in the buffer, and storing, as to the identified mismatch character string, data based on a second data set including flag information indicating the mismatch and the identified mismatch character strings, in the nonvolatile memory.

### Claim 2 (depends on 1)

The method of claim 1, wherein
an index is assigned in ascending order from a first entry to last in the buffer, and
the method further comprising updating the buffer so that a mismatch character string in the buffer which is determined to match the identified mismatch character string is moved to the first entry, and index corresponding to the mismatch character string stored in each entry from the first entry to the entry one before the entry in which the mismatch character string which is determined to match is stored is moved down by one.

### Claim 3 (depends on 2)

The method of claim 2,
wherein the storing of the identified mismatch character string which does not match any of the mismatch character strings in the buffer to the buffer further comprises
storing the identified mismatch character string in the first entry by moving down an index corresponding to the mismatch character string stored in each entry of the buffer by one.

### Claim 4 (depends on 1)

The method of claim 1, wherein
the buffer is configured to store a predetermined number of mismatch character strings, and
the predetermined number of characters is (the predetermined length−1).

### Claim 5 (depends on 1)

The method of claim 1, wherein
the second data set includes the number of characters in the identified mismatch character string,
the number of characters of the identified mismatch character string is an integer between 1 to (the predetermined length−1),
the determination of whether or not the string matches one of the mismatch character strings in the buffer includes determining one of the (the predetermined length−1) buffers according to the number of characters in the identified mismatch character string, and
the first data set includes an identification number which uniquely identifies each of the (the predetermined length−1) buffers.

### Claim 6 (depends on 1)

The method of claim 1, further comprising storing the identified mismatch character string in the first entry of the buffer.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
using a plurality of the buffers alternately in a time-divisional manner; and
determining, while updating a first buffer in the buffers based on a first mismatch character string which is the identified mismatch character string, whether or not a second mismatch character string which is the identified mismatch character string and is identified following the first mismatch character string matches any of the mismatch character strings in a second buffer in the buffers that is different from the first buffer.

### Claim 8

A compression encoder comprising:
a dictionary type compression circuit configured to output, when a length of an input string is longer than a predetermined length, information indicating a result of comparison between the input string and a string which has appeared previously as compressed data, and output, when the length of the input string is less than the predetermined length, the input string as a mismatch character string;
a buffer configured to store the mismatch character string; and
a match searching circuit configured to determine whether or not a mismatch character string output from the dictionary type compression circuit matches one of the mismatch character strings in the buffer by referring to the buffer, wherein
the match searching circuit is further configured to
output, when a mismatch character string output from the dictionary type compression circuit matches one of the mismatch character strings in the buffer, a first data set including flag information indicating the match, and index information indicating the entry in the buffer where the mismatch character string determined to be a match is stored as the compressed data,
output, when the mismatch character string output from the dictionary type compression circuit does not match any of the mismatch character strings in the buffer, the mismatch character string output from the dictionary type compression circuit to the buffer, and output a second data set including flag information indicating the mismatch and the mismatch character string output from the dictionary type compression circuit as the compression data, and
the buffer is configured to store the mismatch character strings output from the match searching circuit, which is and from the dictionary type compression circuit.

### Claim 9 (depends on 8)

The compression encoder of claim 8, wherein
the match searching circuit is further configured to output the index information of the first data set to a buffer,
the buffer is assigned indexes in ascending order from a first entry to last, and
the buffer is further configured to move the mismatch character string stored in the entry corresponding to the index information in the first data set to the first entry, and move down the index corresponding to the mismatch character string stored in each entry from the first entry to the entry one before the entry indicated by the index information by one.

### Claim 10 (depends on 9)

The compression encoder of claim 9,
wherein the buffer is configured to store, when storing a mismatch character string output from the match searching circuit, the mismatch character string output from the match searching circuit in the first entry by moving down the index corresponding to the mismatch character string stored in each entry of the buffer by one.

### Claim 11 (depends on 8)

The compression encoder of claim 8, wherein
the buffer is configured to store a predetermined number of characters of the mismatch character string, and
the predetermined number of characters is (the predetermined length−1).

### Claim 12 (depends on 8)

The compression encoder of claim 8, wherein
the second data set output as compressed data from the match searching circuit includes the number of characters in the mismatch character string output from the dictionary type compression circuit,
the number of characters of the mismatch character string output from the dictionary type compression circuit is 1 to (the predetermined length−1),
the compression encoder includes the (the predetermined length−1) buffers, and
the match searching circuit is further configured to
determine one of the (the predetermined length−1) buffers according to the number of characters in the mismatch character string output from the dictionary type compression circuit, and
set an identification number uniquely identifying each of the (the predetermined length−1) buffers in the first data set.

### Claim 13 (depends on 8)

The compression encoder of claim 8,
wherein the buffer is further configured to store the mismatch character string output from the match searching circuit in the first entry, regardless of whether or not the mismatch character string output from the match searching circuit matches any of the mismatch character strings in the buffer.

### Claim 14 (depends on 8)

The compression encoder of claim 8, further comprising a plurality of the buffers,
wherein the match searching circuit is further configured to
use the buffers alternately in a time-divisional manner, and
while updating a first buffer in the buffers based on a first mismatch character string, which is a mismatch character string output from the dictionary type compression circuit, use a second buffer in the buffers, determining whether or not the second mismatch character string which is a mismatch character string output from the dictionary type compression circuit and following the first mismatch character string matches one of the mismatch character strings in the second buffer, which is different from the first buffer in the buffers.

### Claim 15 (depends on 14)

The compression encoder of claim 14, wherein
the second mismatch character string is the mismatch character string output from the dictionary type compression circuit following the first mismatch character string,
the updating of the first buffer includes,
when the second mismatch character string output from the dictionary type compression circuit before the first mismatch character string output from the dictionary type compression circuit matches one of the mismatch character strings in the buffer, moving the mismatch character string stored in the entry corresponding to the index information in the first data set corresponding to the second mismatch character string to the first entry, and moving down the index corresponding to the mismatch character string stored in each entry from the first entry to the entry one before the entry indicated by the index information by one, and
when the second mismatch character string does not match any of the mismatch character strings in the buffer, moving down the index corresponding to the mismatch character string stored in each entry of the buffer by one and storing the second mismatch character string in the first entry.

### Claim 16 (depends on 8)

The compression encoder of claim 8,
wherein the information includes information indicating a position of the character string in the dictionary in which the character string which appeared previously is stored and information indicating a match length.

### Claim 17 (depends on 8)

A memory system comprising:
a nonvolatile memory; and
a memory controller configured to control the nonvolatile memory, including a compression encoder of claim 8,
wherein the memory controller is further configured to input the character string to the dictionary type compression circuit and stores data based on the compressed data output from the compression encoder in the non-volatile memory.

### Claim 18 (depends on 8)

A compression and decompression system comprising:
a compression encoder of claim 8; and
a decompression device configured to decompress compressed data compressed by the compression encoder, wherein
the decompression device comprises
a dictionary type decompression circuit,
a character buffer match/mismatch determination circuit configured to obtain the first or second data set from the compressed data, and
a second buffer configured to store the mismatch character string,
the second buffer is assigned indexes in ascending order from a first entry to last, and
the second buffer is further configured to
when the index information contained in the first data set is output from the character buffer match/mismatch determination circuit, output the mismatched character string stored in the entry indicated by the index information to the dictionary type decompression circuit as a character string to be decompressed, move the mismatch character string stored in the entry indicated by the index information to the first entry, and move down the index corresponding to the mismatch character string stored in each entry from the first entry to the entry one before the entry indicated by the index information by one, and
when a mismatch character string in the second data set is output from the character buffer match/mismatch determination circuit, output the mismatch character string to the dictionary type decompression circuit as a string to be decompressed, and moving down the index corresponding to the mismatch character string stored in each entry of the second buffer by one and storing the mismatched character string output from the character buffer match/mismatch determination circuit in the first entry.

### Claim 19 (depends on 12)

A compression and decompression system comprising:
a compression encoder of claim 12; and
a decompression device configured to decompress compressed data compressed by the compression encoder, wherein
the decompression device comprises
a dictionary type decompression circuit,
a character buffer match/mismatch determination circuit configured to obtain the first data set or the second data set from the compression data, and
the (the predetermined length−1) buffers storing the mismatch character string,
each of the (the predetermined length−1) second buffers is assigned an identification number to be uniquely identified,
each of the (the predetermined length−1) second buffers is assigned index in ascending order from a first entry to last,
each of the (the predetermined length−1) second buffers is configured to
when the identification number and the index information contained in the first data set are output from the character buffer match/mismatch determination circuit, determine whether the identification number indicates itself or not, and when it indicates itself, output the mismatched character string stored in the entry indicated by the index information to the dictionary type decompression circuit as the character string to be decompressed, move the mismatched character string stored in the entry indicated by the index information to the first entry, and move down the index corresponding to the mismatch character string stored in each entry from the first entry to the entry one before the entry indicated by the index information by one, and
when the number of characters of the mismatch character string in the second data set and the mismatch character string are output from the character buffer match/mismatch determination circuit, determine whether or not the mismatch character string should be stored by itself based on the number of characters of the mismatch character string, and when it should be stored, output the mismatch character string as the string to be decompressed to the dictionary type decompression circuit, and move down the index corresponding to the mismatch character string stored in each entry by one and to store the mismatch character string to the head entry.

### Claim 20 (depends on 13)

A compression and decompression system comprising:
a compression encoder of claim 13; and
a decompression device configured to decompress compressed data compressed by the compression encoder, wherein
the decompression device comprises
a dictionary type decompression circuit,
a character buffer match/mismatch determination circuit configured to obtain the first data set or the second data set from the compression data, and
a second buffer configured to store the mismatch character string, wherein
the second buffer is assigned indexes in ascending order from a first entry to last,
the second buffer is further configured to
when the index information contained in the first data set is output from the character buffer match/mismatch determination circuit, output the mismatched character string stored in the entry indicated by the index information to the dictionary type decompression circuit as the character string to be decompressed, move the mismatched character string stored in the entry indicated by the index information to the first entry, and move down the index corresponding to the mismatch character string stored in each entry of the second buffer by one, and
when the mismatch character string contained in the second data set is output from the character buffer match/mismatch determination circuit, output the mismatch character string as the string to be decompressed to the dictionary type decompression circuit, and move down the index corresponding to the mismatch character string stored in each entry of the second buffer by one and to store the mismatch character string to the head entry.

### Claim 21 (depends on 14)

A compression and decompression system comprising:
a compression encoder of claim 14; and
a decompression device configured to decompress compressed data compressed by the compression encoder, wherein
the decompression device comprises
a dictionary type decompression circuit,
a character buffer match/mismatch determination circuit configured to obtain the first data set or the second data set from the compression data, and
a second buffer configure to store the mismatch character string,
the character buffer match/mismatch determination circuit is configured to
use the multiple second buffers alternately in a time-divisional manner, and
while updating a first buffer of the buffers based on the first data set or the second data set obtained at the first timing, output to a second buffer of the buffers, the index information contained in the first data set obtained at the second timing following the first timing, or the mismatched character string contained in the second data set.
