2024-03-29T23:10:22Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000917862024-03-29T05:26:34Z01164:02592:07086:07157
写像枝を用いた系列二分決定グラフの効率化An Efficient Sequence Binary Decision Diagrams with Mapping Edgesjpnhttp://id.nii.ac.jp/1001/00091770/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=91786&item_no=1&attribute_id=1&file_no=1Copyright (c) 2013 by the Information Processing Society of Japan北海道大学情報科学研究科北海道大学情報科学研究科/JST ERATO湊離散構造処理系プロジェクト立命館大学情報理工学研究科青木, 洋士湊, 真一山下, 茂二分決定グラフ(Binary Decision Diagram, BDD)は,論理関数を効率良く処理することができるグラフである.BDD処理系のメモリ効率は,節点数に依存する.BDDの節点数を削減する手法として,BDDに属性枝を付与する手法が提案されている.BDDに属性枝を付与すると,同じ部分グラフの数が増加し,同一の節点が効率良く共有される.一方,系列二分決定グラフ(Sequence Binary Decision Diagram, SeqBDD) は,文字列集合を表現するデータ構造である.SeqBDDは,変数の出現順序や構築ルールがBDDと異なる.このため,SeqBDDは,BDDとは違った節点の共有手法を適用できる可能性がある.本稿では,属性枝を付与した新しいSeqBDDの節点の共有手法を提案する.実験により,SeqBDDに対して提案した属性枝の手法を適用すると,節点数を削減することができ,さらに,特定のSeqBDDの演算を高速化できることを確認した.A Binary Decision Diagram (BDD) gives efficient boolean function manipulations. The memory efficiency of BDDs depends on the number of their nodes. We can reduce the number of nodes of BDDs by adding attributed edges: nodes are shared efficiently since the number of the same sub-graphs increases when attributed edges are used. Sequence Binary Decision Diagram (SeqBDD) is a data structure that represents a set of strings. SeqBDDs are different from BDDs with respect to the variable ordering and the construction rules. Therefore, there may be another approach to share nodes of SeqBDDs. In this paper, we propose a new technique for sharing nodes of SeqBDDs with attributed edges. Our experimental results show that our attributed edge reduce the number of nodes of SeqBDDs and make some oprations of a SeqBDD fast.AN1009593X研究報告アルゴリズム(AL)2013-AL-14423182013-05-102013-04-24