1K-3
順序なし2分木の効率的な符号
○岩田梢江，中野眞一，石渡史朗（群馬大）
本研究はグラフの効率的な表現方法に関するものである．
グラフG を再構成できる‘0’,‘1’からなる文字列をG の符号という．
順序なし2分木の符号として，既に高々5/3n + 1 bitの符号が知られている．
ここで，木の点の個数をn とする．
本研究では，n点を持つ順序なし2分木のより効率的な高々1.4n + 4 bitの符号を提案する．各点の子の個数に注目し，9種類に分け，符号を割り当てることにより，高々1.4n + 4bitの効率的な符号を得る．また，符号化と復号はO(n)時間およびO(n)領域しかかからない．