WEKO3
-
RootNode
アイテム
The Huffman Tree Problem with Unit Step Functions
http://hdl.handle.net/10091/00018596
http://hdl.handle.net/10091/00018596dba3c995-2959-4a3a-8749-a6c627d1fb70
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
The_Huffman_Tree_Problem_with_Unit_Step_Functions_fujiwara_nakamura_fujito_IEICE.pdf (1.1 MB)
|
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2016-02-03 | |||||||||||
| タイトル | ||||||||||||
| タイトル | The Huffman Tree Problem with Unit Step Functions | |||||||||||
| 言語 | ||||||||||||
| 言語 | eng | |||||||||||
| DOI | ||||||||||||
| 関連識別子 | https://doi.org/10.1587/transfun.E98.A.1189 | |||||||||||
| 関連名称 | 10.1587/transfun.E98.A.1189 | |||||||||||
| キーワード | ||||||||||||
| 主題 | combinatorial optimization, polynomial-time algorithm, binary tree, optimal tree, Huffman coding | |||||||||||
| 資源タイプ | ||||||||||||
| 資源 | http://purl.org/coar/resource_type/c_6501 | |||||||||||
| タイプ | journal article | |||||||||||
| 著者 |
Fujiwara, Hiroshi
× Fujiwara, Hiroshi
× Nakamura, Takuya
× Fujito, Toshihiro
|
|||||||||||
| 信州大学研究者総覧へのリンク | ||||||||||||
| 氏名 | Fujiwara, Hiroshi | |||||||||||
| URL | http://soar-rd.shinshu-u.ac.jp/profile/ja.OmSVOFnU.html | |||||||||||
| 出版者 | ||||||||||||
| 出版者 | IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG | |||||||||||
| 引用 | ||||||||||||
| 内容記述 | IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES. E98A(6):1189-1196 (2015) | |||||||||||
| 書誌情報 |
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 巻 E98A, 号 6, p. 1189-1196, 発行日 2015-06 |
|||||||||||
| 抄録 | ||||||||||||
| 内容記述 | 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. | |||||||||||
| 資源タイプ（コンテンツの種類） | ||||||||||||
| ISSN | ||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||
| 収録物識別子 | 1745-1337 | |||||||||||
| 他の資源との関係：URI | ||||||||||||
| 識別子タイプ | URI | |||||||||||
| 関連識別子 | http://search.ieice.org/ | |||||||||||
| 関連名称 | http://search.ieice.org/ | |||||||||||
| 権利 | ||||||||||||
| 権利情報 | © 2015 The Institute of Electronics, Information and Communication Engineers | |||||||||||
| 出版タイプ | ||||||||||||
| 出版タイプ | VoR | |||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||
| WoS | ||||||||||||
| URL | http://gateway.isiknowledge.com/gateway/Gateway.cgi?&GWVersion=2&SrcAuth=ShinshuUniv&SrcApp=ShinshuUniv&DestLinkType=FullRecord&DestApp=WOS&KeyUT=000359466600007 | |||||||||||
Share
Cite as
Fujiwara, Hiroshi, Nakamura, Takuya, Fujito, Toshihiro, 2015, The Huffman Tree Problem with Unit Step Functions: IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, 1189–1196 p.
Loading...
