ハフマン木の最適領域の隣接性について

• Item type: SIG Technical Reports(1)
• 公開日: 2004-03-19
• タイトル: ハフマン木の最適領域の隣接性について
• タイトル / 言語: en
• タイトル: Adjacency of optimal region of Huffman tree
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 電気通信大学大学院情報システム学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Systems, University of Electro - Communications
• 著者名: 大西建輔
• 著者名(英): Kensuke, Onishi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ハフマン木は有用なデータ構造としてこれまで多くの研究がなされている．キーとその重みが与えられた場合にハフマン木は簡単に計算をすることができることはよく知られている．重み付き拡張二分木が最適であるとは，他の全ての拡張二分木の中でその二分木が最も重み付き路長和を最小にする場合である．拡張二分木の最適領域とは，重み空間の領域であり，その中に含まれる重みはその二分木を最適とする．本論文では，ハフマン木の最適領域の性質についての研究を行う．レベルベクタとは，拡張二分木のそれぞれの葉までの路長をベクトルとして表現した形式であり，本稿ではレベルベクタとハフマン木を同一視する．まず どの最適領域も非空かつ、凸集合であることを示す．また，2つのハフマン木の最適領域が隣接しているとは ある重みが存在し，その重みでその2つのハフマン木だけが最適になると定義する．この最適性の必要十分条件が次の2つであることを証明する：1) 葉のレベル差が高々1である；2) その2つのハフマン木のレベルベクタの和が他のどの2つのレベルベクタの和としても表されない．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Huffman tree has been studied as useful data structure. For given keys and their weights, the tree structure can be constructed easily. An extended binary tree with the weights is optimal if the tree has smallest weighted external path length among all extended binary trees. Consider the weight space and an extended binary tree. Optimal region of the extended binary tree is defined by a region of the weight space such that the tree with any weight in the region is optimal. In this paper we investigate properties of optimal regions. Huffman tree is expressed as level vector which is defined by integer vector whose element is the path length to each node of the tree. We show that each optimal region is non-empty and convex through level vector. Two Huffman trees are adjacent if there is a weight such that the only two trees are optimal for the weight. We show that the necessary and sufficient condition of adjacency is that 1) the difference of level between each leaf is at most one; 2) the sum of two level vectors of trees is not equal to the sum of any other two level vectors.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2004, 号 34(2003-AL-094), p. 101-108, 発行日 2004-03-19
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会