Data decompression device, memory system, and data decompression method
According to one embodiment, a data decompression device decodes a code included in compressed data into a symbol. The data decompression device includes a first code length generation unit and a second code length generation unit. The first code length generation unit generates a first code length of a first code included in the compressed data by arithmetic calculation. The second code length generation unit generates a second code length of a second code by using a table. The second code is included in the compressed data. The second code is subsequent to the first code. The table indicates at least the first code and the second code length that is associated with the first code.
1. A data decompression device that decodes a code included in compressed data into a symbol, the data decompression device comprising:
a first code length generation unit configured to generate a first code length of a first code included in the compressed data by arithmetic calculation; and
a second code length generation unit configured to generate a second code length of a second code by using a table, the second code being included in the compressed data, the second code being subsequent to the first code, the table indicating at least the first code and the second code length that is associated with the first code.
2. The data decompression device according to claim 1 , wherein
the first code is a prefix code.
3. The data decompression device according to claim 1 , wherein
the table indicates one or more codes of a first type and one or more code lengths of codes of a second type that are associated with the one or more codes of the first type, respectively, the one or more codes of the first type being assigned to all or a part of types of symbols, respectively, that occur in the compressed data, and
the second code length generation unit is configured to:
detect a code of the one or more codes of the first type that matches the first code by using the table; and
generate, as the second code length, a code length of a code of the second type that is associated with the detected code by using the table.
4. The data decompression device according to claim 3 , wherein
each of the one or more codes of the first type is a code that is assigned to a dictionary match length symbol.
5. The data decompression device according to claim 4 , wherein
each of the one or more codes of the first type is a code that is assigned to the dictionary match length symbol and is associated with a code length of a code of the second type that is one or more bits.
6. The data decompression device according to claim 1 , further comprising
an adder configured to acquire either a code length of a code word that corresponds to a dictionary mismatch symbol or a code length of a code word that corresponds to a dictionary match length symbol by adding the first code length and the second code length,
wherein the second code length generation unit configured to generate 0 as the second code length in a case where the first code is a code assigned to the dictionary mismatch symbol.
7. The data decompression device according to claim 6 , wherein
the acquired code length of the code word is used to identify, in the compressed data, a start position of a code word subsequent to the code word having the acquired code length.
8. The data decompression device according to claim 1 , further comprising
an adder configured to:
in a case where the first code is a code assigned to a dictionary mismatch symbol, acquire the first code length as a code length of a code word corresponding to the dictionary mismatch symbol; and
in a case where the first code is a code assigned to a dictionary match length symbol, acquire a code length of a code word corresponding to the dictionary match length symbol by adding the first code length and the second code length.
9. The data decompression device according to claim 1 , wherein
the first code is a code that is obtained by performing canonical Huffman coding on a corresponding dictionary mismatch symbol or a dictionary match length symbol.
10. A memory system comprising:
the data decompression device according to claim 1 ;
a nonvolatile memory; and
a control unit configured to read the compressed data from the nonvolatile memory.
11. A data decompression method of a data decompression device that decodes a code included in compressed data into a symbol, the data decompression method comprising:
generating a first code length of a first code included in the compressed data by arithmetic calculation; and
generating a second code length of a second code by using a table, the second code being included in the compressed data, the second code being subsequent to the first code, the table indicating at least the first code and the second code length that is associated with the first code.
12. The data decompression method according to claim 11 , wherein
the first code is a prefix code.
13. The data decompression method according to claim 11 , wherein
the table indicates one or more codes of a first type and one or more code lengths of codes of a second type that are associated with the one or more codes of the first type, respectively, the one or more codes of the first type being assigned to all or a part of types of symbols, respectively, that occur in the compressed data, and
the data decompression method further comprises:
detecting a code of the one or more codes of the first type that matches the first code by using the table; and
generating, as the second code length, a code length of a code of the second type that is associated with the detected code by using the table.
14. The data decompression method according to claim 13 , wherein
each of the one or more codes of the first type is a code that is assigned to a dictionary match length symbol.
15. The data decompression method according to claim 14 , wherein
each of the one or more codes of the first type is a code that is assigned to the dictionary match length symbol and is associated with a code length of a code of the second type that is one or more bits.
16. The data decompression method according to claim 11 , further comprising:
acquiring either a code length of a code word that corresponds to a dictionary mismatch symbol or a code length of a code word that corresponds to a dictionary match length symbol by adding the first code length and the second code length; and
generating 0 as the second code length in a case where the first code is a code assigned to the dictionary mismatch symbol.
17. The data decompression method according to claim 16 , wherein
the acquired code length of the code word is used to identify, in the compressed data, a start position of a code word subsequent to the code word having the acquired code length.
18. The data decompression method according to claim 11 , further comprising:
in a case where the first code is a code assigned to a dictionary mismatch symbol, acquiring the first code length as a code length of a code word corresponding to the dictionary mismatch symbol; and
in a case where the first code is a code assigned to a dictionary match length symbol, acquiring a code length of a code word corresponding to the dictionary match length symbol by adding the first code length and the second code length.
19. The data decompression method according to claim 11 , wherein
the first code is a code that is obtained by performing canonical Huffman coding on a corresponding dictionary mismatch symbol or a dictionary match length symbol.
20. The data decompression method according to claim 11 , further comprising
reading the compressed data from a nonvolatile memory.