Variable length coding device and memory system

A method of controlling a nonvolatile memory, the method comprising:

• generating a frequency table based on frequencies of occurrence of input symbols for each symbol, the frequency table including N symbols, and N frequencies of occurrence that are associated with the N symbols, respectively;
• generating a Huffman tree based on the frequency table;
• determining N code lengths that corresponds to the N symbols, respectively, based on the Huffman tree;
• selecting, from the N symbols, a first symbol corresponding to a first code length, the first code length being included in the N code lengths, the first code length being longer than a maximum code length;
• selecting, from the N symbols, a second symbol corresponding to a second code length, the second code length being shorter than the maximum code length;
• changing the second code length corresponding to the second symbol to a code length that is obtained by adding one to the second code length;
• changing the first code length corresponding to the first symbol to a code length that is equal to the changed second code length;
• determining N variable length codes that are assigned to the N symbols, respectively, based on the N code lengths in which the changed first code length and the changed second code length are included;
• converting each of the input symbols into a variable length code, based on the N variable length codes that are assigned to the N symbols, respectively;
• and
• writing, into the nonvolatile memory, data including the variable length code into which each of the input symbols is converted, wherein
• N is an integer of two or more, and
• the variable length code into which each of the input symbols is converted has a bit length between one bit length and the maximum code length inclusive.