集合および文字列を効率よく操作するための決定グラフに関する研究

DOI 機関リポジトリ (HANDLE) NDLデジタルコレクション

書誌事項

タイトル
集合および文字列を効率よく操作するための決定グラフに関する研究
タイトル別名
  • Studies on Decision Diagrams for Efficient Manipulation of Sets and Strings
著者
伝住, 周平
学位授与大学
北海道大学
取得学位
博士(情報科学)
学位授与番号
甲第11749号
学位授与年月日
2015-03-25

説明

In many real-life problems, we are often faced with manipulating discrete structures.Manipulation of large discrete structures is one of the most important problems in computer science. For this purpose, a family of data structures calleddecision diagrams is used. The origin of the decision diagrams is binary decision diagram (BDD)proposed by Bryant in 1980s. BDD is a data structure to represent and manipulate Boolean functionsefficiently. As a variant of BDD, Minato proposedzero-suppressed binary decision diagram (ZDD). ZDD is a data structure for manipulating families of sets. In 2010, another descendant of BDD, sequence binary decision diagram (sequence BDD), is proposed byLoekito et al. This decision diagram represents sets of strings and allow computing string set operations, too.In this thesis, we study sequence BDD and ZDD. First, we show fundamental properties of sequence BDDs, such as the characterization of minimal sequence BDDs byreduced sequence BDDs, non-trivial relationships between sizes of minimal sequence BDDs and minimal Acyclic Deterministic Finite Automata, the complexities of minimization, Boolean set operations, and sequence BDD construction. Secondly, we alsodefine complete inverted files based on sequence BDD for directed acyclic graphs (DAGs).A complete inverted file is an abstract data type that provides various functions for text retrieval. We propose new complete inverted files calledSeqBDD-FPs for both texts and DAGs. We also present algorithms to construct them and to retrieve occurrence information from them. Thirdly, we pointed out the problem that is to build index for familiesof sets in order to store them compactly and allow fast searching. Then, we introduce DenseZDD, a compressed index for static ZDDs to solve a problem that current techniques for storing ZDDs require a huge amount of memory and membership operations are slow. Our technique not only indexes set families compactly but also executes fast membership operations. We also propose a hybrid method of DenseZDD and ordinaryZDDs to allow for dynamic indices.

詳細情報 詳細情報について

問題の指摘

ページトップへ