The Huffman Tree Problem with Unit Step Functions

Hiroshi FUJIWARA; Takuya NAKAMURA; Toshihiro FUJITO

doi:10.1587/transfun.E98.A.1189

The Huffman Tree Problem with Unit Step Functions

Hiroshi FUJIWARA, Takuya NAKAMURA, Toshihiro FUJITO

Full Text Views

0

Share
Cite this

Summary :

A 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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E98-A No.6 pp.1189-1196

Publication Date: 2015/06/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E98.A.1189

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Authors

Hiroshi FUJIWARA
  Shinshu University
Takuya NAKAMURA
  Toyohashi University of Technology
Toshihiro FUJITO
  Toyohashi University of Technology

Keyword

combinatorial optimization, polynomial-time algorithm, binary tree, optimal tree, Huffman coding

Cite this

Copy

Hiroshi FUJIWARA, Takuya NAKAMURA, Toshihiro FUJITO, "The Huffman Tree Problem with Unit Step Functions" in IEICE TRANSACTIONS on Fundamentals, vol. E98-A, no. 6, pp. 1189-1196, June 2015, doi: 10.1587/transfun.E98.A.1189.
Abstract: A 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E98.A.1189/_p

Copy

@ARTICLE{e98-a_6_1189,
author={Hiroshi FUJIWARA, Takuya NAKAMURA, Toshihiro FUJITO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={The Huffman Tree Problem with Unit Step Functions},
year={2015},
volume={E98-A},
number={6},
pages={1189-1196},
abstract={A 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.},
keywords={},
doi={10.1587/transfun.E98.A.1189},
ISSN={1745-1337},
month={June},}

Copy

TY - JOUR
TI - The Huffman Tree Problem with Unit Step Functions
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1189
EP - 1196
AU - Hiroshi FUJIWARA
AU - Takuya NAKAMURA
AU - Toshihiro FUJITO
PY - 2015
DO - 10.1587/transfun.E98.A.1189
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E98-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2015
AB - A 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.
ER -