Fully-Online Suffix Tree and Directed Acyclic Word Graph Construction for Multiple Texts

We consider the construction of the suffix tree and the directed acyclic word graph (DAWG) indexing data structures for a collection T of texts, where a new symbol may be appended to any text in T= { T₁, … , T_K} , at any time. This fully-online scenario, which arises in dynamically indexing multi-sensor data, is a natural generalization of the long solved semi-online text indexing problem, where texts T₁, … , T_k are permanently fixed before the next text T_{k + 1} is processed for each k (1 ≤ k< K). We first show that a direct application of Weiner’s right-to-left online construction for the suffix tree of a single text to fully-online multiple texts requires superlinear time. This also means that Blumer et al.’s left-to-right online construction for the DAWG of a single text requires superlinear time in the fully-online setting. We then present our fully-online versions of these algorithms that run in O(Nlog σ) time and O(N) space, where N is the total length of the texts in T and σ is their alphabet size. We then show how to extend Ukkonen’s left-to-right online suffix tree construction to fully-online multiple strings, with the aid of Weiner’s suffix tree for the reversed texts.