Computer product, generating apparatus, and generating method for generating Huffman tree, and computer product for file compression using Huffman tree

A generating apparatus comprising:

• at least one processor configured to:
• tabulate a number of character data types for each compression code length specified by an occurrence probability corresponding to an appearance rate of each character data appearing in an object file;
• determine an upper limit length N of compression code length assigned to the character data, among compression code lengths from a minimum compression code length to a maximum compression code length and based on the total number of character data types;
• correct the number of character data types for the upper limit length N, to the sum of the numbers of character data types for the compression code lengths equal to or greater than the upper limit length N;
• and
• construct a 2N-branch nodeless Huffman tree with the maximum branch number defined by the upper limit length N, the 2N-branch nodeless Huffman tree including leaves that are compression codes having compression code lengths corresponding to respective occurrence probabilities of the character data, based on the numbers of character data types for the respective compression code lengths after correction.

A generating method executed by a computer that includes a storage device that stores an object file, the generating method comprising:

• tabulating, by a tabulating unit, a number of character data types for each compression code length specified by an occurrence probability corresponding to an appearance rate of each character data appearing in the object file;
• determining, by a determining unit, an upper limit length N of compression code length assigned to the character data, among compression code lengths from a minimum compression code length to a maximum compression code length and based on the total number of character data types;
• correcting, by a correcting unit, the number of character data types tabulated at the tabulating for the upper limit length N determined at the determining, to the sum of the numbers of character data types for the compression code lengths equal to or greater than the upper limit length N;
• and
• constructing, by a constructing unit, a 2N-branch nodeless Huffman tree with the maximum branch number defined by the upper limit length N, the 2N-branch nodeless Huffman tree including leaves that are compression codes having compression code lengths corresponding to respective occurrence probabilities of the character data, based on the numbers of character data types for the respective compression code lengths after the correction at the correcting.

A non-transitory computer-readable recording medium storing therein a compression program that causes a computer to execute a process comprising:

• tabulating a number of character data types for each compression code length specified by an occurrence probability corresponding to an appearance rate of each character data appearing in one or a plurality of object files;
• determining an upper limit length N of compression code length assigned to the character data, among compression code lengths from a minimum compression code length to a maximum compression code length and based on the total number of character data types;
• correcting the number of character data types tabulated at the tabulating for the upper limit length N determined at the determining, to the sum of the numbers of character data types for the compression code lengths equal to or greater than the upper limit length N;
• and
• constructing a 2N-branch nodeless Huffman tree with the maximum branch number defined by the upper limit length N, the 2N-branch nodeless Huffman tree including leaves that are compression codes having compression code lengths corresponding to respective occurrence probabilities of the character data, based on the numbers of character data types for the respective compression code lengths after the correction at the correcting;
• and
• compressing the one or the plurality of object files using the 2N-branch nodeless Huffman tree.