TCS-TR-A-11-53Date: Sat Apr 30 21:55:10 2011 Title: Efficient Algorithms on Sequence Binary Decision Diagrams for Manipulating Sets of Strings Authors: Shuhei Denzumi, Ryo Yoshinaka, Shin-ichi Minato, and Hiroki Arimura Contact:
Abstract. We consider sequence binary decision diagrams (sequence BDD or SDD, for short), which are compact representation for manipulating sets of strings, proposed by (Loekito, et al., Knowl.~Inf.~Syst., 24(2), 235-268, 2009). An SDD resembles to an acyclic DFA in binary form with different reduction rules from one for DFAs. In this paper, we study the power of SDDs for storing and manipulating sets of strings on shared and reduced SDDs. Particularly, we first give the characterization of minimal SDDs as reduced SDDs. Then, we present simple and efficient algorithms for various problems related to reduced and shared SDDs: on-the-fly and off-line minimization, dynamic string set construction, and factor SDD construction. Finally, we run experiments on real data sets that show the efficiency and usefulness of SDDs in large-scale string processing. ©Copyright 2011 Authors |