2022-05-23T04:20:17Zhttps://soar-ir.repo.nii.ac.jp/oaioai:soar-ir.repo.nii.ac.jp:000178272021-10-12T00:36:21Z1221:1222The Huffman Tree Problem with Unit Step FunctionsFujiwara, HiroshiNakamura, TakuyaFujito, Toshihiro© 2015 The Institute of Electronics, Information and Communication Engineerscombinatorial optimizationpolynomial-time algorithmbinary treeoptimal treeHuffman codingA binary tree is regarded as a prefix-free binary code, in which the weighted sum of the lengths of root-leaf paths is equal to the expected codeword length. Huffman's algorithm computes an optimal tree in O(n log n) time, where n is the number of leaves. The problem was later generalized by allowing each leaf to have its own function of its depth and setting the sum of the function values as the objective function. The generalized problem was proved to be NP-hard. In this paper we study the case where every function is a unit step function, that is, a function that takes a lower constant value if the depth does not exceed a threshold, and a higher constant value otherwise. We show that for this case, the problem can be solved in O(n log n) time, by reducing it to the Coin Collector's problem.ArticleIEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES. E98A(6):1189-1196 (2015)IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG2015-06engjournal articleVoRhttp://hdl.handle.net/10091/00018596https://soar-ir.repo.nii.ac.jp/records/17827http://search.ieice.org/http://search.ieice.org/https://doi.org/10.1587/transfun.E98.A.118910.1587/transfun.E98.A.11891745-1337IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCESE98A611891196https://soar-ir.repo.nii.ac.jp/record/17827/files/The_Huffman_Tree_Problem_with_Unit_Step_Functions_fujiwara_nakamura_fujito_IEICE.pdfapplication/pdf1.1 MB2016-02-03