An efficient algorithm for constructing a Sequence Binary Decision Diagram representing a set of reversed sequences

摘要

A trie is a data structure representing a set of sequences by sharing the same prefixes between sequences. Thanks to this sharing, prefix searches on a trie is performed efficiently. Constructing a trie representing a set of reversed sequences is useful for suffix searches on the original sequences. This is because a prefix search on reversed sequences corresponds to a suffix search on the original sequences. A Sequence Binary Decision Diagram (SeqBDD) also represents a set of sequences compactly by sharing the same prefixes between the sequences. In addition, a SeqBDD can share suffixes between the sequences unlike a trie. Thus, it is desirable to construct a SeqBDD representing a set of the reversed sequences from a given SeqBDD efficiently for a suffix search on the SeqBDD. To this end, we propose a method visiting each node in a SeqBDD only one time since it visits the nodes based on the topological sorting. Hence, our method is more efficient than a simple recursive method that visits the same nodes many times. The experimental results show that our method constructs a SeqBDD representing a set of reversed sequences more efficiently than a simple recursive method when there are many common prefixes and/or suffixes in given sequences. In addition, we propose two novel applications of the reversed SeqBDDs.