Suffix Vector: A Space-Efficient Suffix Tree Representation

Krisztián Monostori¹, Arkady Zaslavsky¹, and István Vajk²

¹ School of Computer Science and Software Engineering, Monash University, Melbourne
900 Dandendong Rd, Caulfield East VIC3145, Australia

{Krisztian.Monostori, Arkady.Zaslavsky}@csse.monash.edu.au

² Department of Automation and Applied Informatics,
Budapest University of Technology and Economics
1111 Budapest, Goldmann György tér 3. IV.em.433., Hungary

vajk@aut.bme.hu

Abstract.
This paper introduces a new way of representing suffix trees. The basic idea behind the representation is that we are storing the nodes of the tree along with the string itself, thus edge labels can directly be read from the string. The new representation occupies less space than the best-known representation to date in case of English text and program files, though it requires slightly more space in case of DNA sequences. We also believe that our representation is clearer and thus implementing algorithms on it is easier. We also show that our representation is not only better in terms of space but it is also faster to retrieve information from the tree. We theoretically compare the running time of the matching statistics algorithm on both representations.