Abstract
Suffix trees are inherently asymmetric: prefix extensions only cause a few updates, while suffix extensions affect all suffixes causing a wave of updates. In his elegant linear-time on-line suffix tree algorithm Ukkonen relaxed the prevailing suffix tree representation and introduced two changes to avoid repeated structural updates and circumvent the inherent complexity of suffix extensions: (1) open ended edges that enjoy gratuitous leaf updates, and (2) the omission of implicit nodes. In this paper we study the implicit nodes as the suffix tree evolves. We partition the suffix tree’s edges into collections of similar edges called bands, where implicit nodes exhibit identical behavior, and generalize the notion of open ended edges to allow implicit nodes to “float” within bands, only requiring updates when moving from one band to the next, adding up to only O(n) updates. We also show that internal implicit nodes are separated from each other by explicit suffix tree nodes and that all external implicit nodes are related to the same periodicity. These new properties may be used to keep track of the waves of implicit node updates and to build the suffix tree on-line in amortized linear time, providing access to all the implicit nodes in worst-case constant time.
Work partially supported by the European Research Council (ERC) Project SFEROT, by the Israeli Science Foundation Grant 347/09, by the 7th Framework Programme of the EU (Network of Excellence “EuroNF: Anticipating the Network of the Future - From Theory to Design”) and by MIUR, the Italian Ministry of Education, University and Research, under Project AlgoDEEP.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Amir, A., Farach, M., Idury, R., Poutré, J.L., Schäffer, A.: Improved Dynamic Dictionary-Matching. Information and Computation 119, 258–282 (1995)
Apostolico, A.: The Myriad Virtues of Subword Trees. In: Apostolico, A., Galil, Z. (eds.) Combinatorial Algorithms on Words. NATO ASI Series F, vol. 12, pp. 85–96. Springer, Berlin (1985)
Apostolico, A., Preparata, F.: Optimal Off-line Detection of Repetitions in a String. Theoret. Comput. Sci. 22, 297–315 (1983)
Bender, M.A., Cole, R., Demaine, E.D., Farach-Colton, M., Zito, J.: Two Simplified Algorithms for Maintaining Order in a List. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 152–164. Springer, Heidelberg (2002)
Berstel, J.: Transductions and Context-Free Languages. Teubner-Verlag (1979) Revised version is available electronically as, http://www-igm.univ-mlv.fr~berstel/LivreTransductions/LivreTransductions14dec2009.pdf
Breslauer, D., Hariharan, R.: Optimal Parallel Construction of Minimal Suffix and Factor Automata. Parallel Processing Letters 6(1), 35–44 (1996)
Cohen, H., Porat, E.: Range Non-overlapping Indexing. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 1044–1053. Springer, Heidelberg (2009)
Crochemore, M.: Transducers and Repetitions. Theoret. Comput. Sci. 12, 63–86 (1986)
Crochemore, M., Rytter, W.: Text Algorithms. Oxford University Press, Oxford (1994)
Dietz, P.F., Sleator, D.D.: Two Algorithms for Maintaining Order in a List. In: STOC, pp. 365–372. ACM, New York (1987)
Dori, S., Landau, G.M.: Construction of Aho Corasick Automaton in Linear Time for Integer Alphabets. Inf. Process. Lett. 98(2), 66–72 (2006)
Farach, M.: Optimal Suffix Tree Construction with Large Alphabets. In: FOCS, pp. 137–143 (1997)
Farach-Colton, M., Ferragina, P., Muthukrishnan, S.: On the Sorting-Complexity of Suffix Cree construction. J. ACM 47(6), 987–1011 (2000)
Fine, N., Wilf, H.: Uniqueness Theorems for Periodic Functions. Proc. Amer. Math. Soc. 16, 109–114 (1965)
Giegerich, R., Kurtz, S.: From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction. Algorithmica 19(3), 331–353 (1997)
Gusfield, D.: Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)
Gusfield, D., Stoye, J.: Linear Time Algorithms for Finding and Representing all the Tandem Repeats in a String. J. Comput. Syst. Sci. 69(4), 525–546 (2004)
Kärkkäinen, J., Sanders, P., Burkhardt, S.: Linear Work Suffix Array Construction. J. ACM 53(6), 918–936 (2006)
Kim, D.K., Sim, J.S., Park, H., Park, K.: Constructing Suffix Arrays in Linear Time. J. Discrete Algorithms 3(2-4), 126–142 (2005)
Ko, P., Aluru, S.: Space Efficient Linear Time Construction of Suffix Arrays. J. Discrete Algorithms 3(2-4), 143–156 (2005)
Kolpakov, R.M., Kucherov, G.: Finding Maximal Repetitions in a Word in Linear Time. In: FOCS, pp. 596–604 (1999)
Kosaraju, S.: Computation of Squares in a String. In: Crochemore, M., Gusfield, D. (eds.) CPM 1994. LNCS, vol. 807, pp. 146–150. Springer, Heidelberg (1994)
Manber, U., Myers, E.W.: Suffix Arrays: A New Method for On-line String Searches. SIAM J. Comput. 22(5), 935–948 (1993)
McCreight, E.: A Space Economical Suffix Tree Construction Algorithm. J. Assoc. Comput. Mach. 23, 262–272 (1976)
Salson, M., Lecroq, T., Léonard, M., Mouchard, L.: A Four-Stage Algorithm for Updating a Burrows-Wheeler Transform. Theor. Comput. Sci. 410(43), 4350–4359 (2009)
Salson, M., Lecroq, T., Léonard, M., Mouchard, L.: Dynamic Extended Suffix Arrays. J. Discrete Algorithms 8(2), 241–257 (2010)
Shibuya, T.: Constructing the Suffix Tree of a Tree with a Large Alphabet. In: Aggarwal, A.K., Pandu Rangan, C. (eds.) ISAAC 1999. LNCS, vol. 1741, pp. 225–236. Springer, Heidelberg (1999)
Tsakalidis, A.K.: Maintaining Order in a Generalized Linked List. Acta Inf. 21, 101–112 (1984)
Ukkonen, E.: On-line Construction of Suffix Trees. Algorithmica 14(3), 249–260 (1995)
Weiner, P.: Linear Pattern Matching Algorithms. In: Proc. 14th Symposium on Switching and Automata Theory, pp. 1–11 (1973)
Westbrook, J.: Fast Incremental Planarity Testing. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol. 623, pp. 342–353. Springer, Heidelberg (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Breslauer, D., Italiano, G.F. (2011). On Suffix Extensions in Suffix Trees. In: Grossi, R., Sebastiani, F., Silvestri, F. (eds) String Processing and Information Retrieval. SPIRE 2011. Lecture Notes in Computer Science, vol 7024. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24583-1_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-24583-1_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-24582-4
Online ISBN: 978-3-642-24583-1
eBook Packages: Computer ScienceComputer Science (R0)