
Studies on Decision Diagrams for Efficient Manipulation of Sets and StringsStudies on Decision Diagrams for Efficient Manipulation of Sets and Strings 集合および文字列を効率よく操作するための決定グラフに関する研究 
"/伝住, 周平/"伝住, 周平
Description
In many reallife 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 called
decision 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 functions
efficiently. As a variant of BDD, Minato proposed
zerosuppressed 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 by
Loekito 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 by
reduced sequence BDDs, nontrivial 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 also
define 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 called
SeqBDDFPs 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 families
of 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 ordinary
ZDDs to allow for dynamic indices.
97p
Hokkaido University（北海道大学）. 博士(情報科学)
FullText
http://eprints.lib.hokudai.ac.jp/dspace/bitstream/2115/58738/1/Shuhei_Denzumi.pdf