On the Implementation of Compact DAWG's

摘要

There are several data structures that allow searching for a pattern P in a preprocessed text T in time dependent just on the length of P. In this paper we present an implementation of CDAWG's -Compact Direct Acyclic Word Graphs. While the previous implementations of CDAWG's required from 7n to 23n bytes of memory space, ours achieves 1.7n to 5n for a text T of length n. The implementation is suitable for large data files, since it minimizes the number of disk accesses. If disk accesses are not to be optimized, space requirements can be further decreased.