Sparse Text Indexing in Small Space

Abstract

In this work, we present efficient algorithms for constructing sparse suffix trees, sparse suffix arrays, and sparse position heaps for b arbitrary positions of a text T of length n while using only O(b) words of space during the construction.

Attempts at breaking the naïve bound of Ω(nb) time for constructing sparse suffix trees in O(b) space can be traced back to the origins of string indexing in 1968. First results were not obtained until 1996, but only for the case in which the b suffixes were evenly spaced in T. In this article, there is no constraint on the locations of the suffixes.

Our main contribution is to show that the sparse suffix tree (and array) can be constructed in O(nlog ²b) time. To achieve this, we develop a technique that allows one to efficiently answer b longest common prefix queries on suffixes of T, using only O(b) space. We expect that this technique will prove useful in many other applications in which space usage is a concern. Our first solution is Monte Carlo, and outputs the correct tree with high probability. We then give a Las Vegas algorithm, which also uses O(b) space and runs in the same time bounds with high probability when b = O(√ n). Additional trade-offs between space usage and construction time for the Monte Carlo algorithm are given.

Finally, we show that, at the expense of slower pattern queries, it is possible to construct sparse position heaps in O(n + blog b) time and O(b) space.

References

1. Miklós Ajtai, János Komlós, and Endre Szemerédi. 1983. An O(nlog n) sorting network. In Proceedings of the 15th STOC. 1--9.
2. Arne Andersson, N. Jesper Larsson, and Kurt Swanson. 1996. Suffix trees on words. In Proceedings of the 7th CPM. Lecture Notes in Computer Science, Vol. 1075. 102--115.
3. Arne Andersson, N. Jesper Larsson, and Kurt Swanson. 1999. Suffix trees on words. Algorithmica 23, 3, 246--260.
4. Kenneth E. Batcher. 1968. Sorting networks and their applications. In Proceedings of the AFIPS Spring JCC. 307--314.
5. Jon L. Bentley and Robert Sedgewick. 1997. Fast algorithms for sorting and searching strings. In Proceedings of the 8th SODA. 360--369.
6. Stefan Burkhardt and Juha Kärkkäinen. 2003. Fast lightweight suffix array construction and checking. In Proceedings of the 14th CPM. Lecture Notes in Computer Science, Vol. 2676. 55--69.
7. Maxime Crochemore and Wojciech Rytter. 1991. Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays. Theoretical Computer Science 88, 1, 59--82.
8. Andrzej Ehrenfeucht, Ross M. McConnell, Nissa Osheim, and Sung-Whan Woo. 2011. Position heaps: A simple and dynamic text indexing data structure. Journal of Discrete Algorithms 9, 1, 100--121.
9. Paolo Ferragina and Johannes Fischer. 2007. Suffix arrays on words. In Proceedings of the 18th CPM. Lecture Notes in Computer Science, Vol. 4580. 328--339.
10. Nathan J. Fine and Herbert S. Wilf. 1965. Uniqueness theorems for periodic functions. Proceedings of the AMS 16, 1, 109--114.
11. Johannes Fischer, Tomohiro I, and Dominik Köppl. 2015. Deterministic sparse suffix sorting on rewritable texts. In arXiv:1509.07417.
12. Shunsuke Inenaga and Masayuki Takeda. 2006. On-line linear-time construction of word suffix trees. In Proceedings of the 17th CPM. Lecture Notes in Computer Science, Vol. 4009. 60--71.
13. Juha Kärkkäinen and Esko Ukkonen. 1996. Sparse suffix trees. In Proceedings of the 2nd COCOON. Lecture Notes in Computer Science, Vol. 1090. 219--230.
14. Richard M. Karp, Raymond E. Miller, and Arnold L. Rosenberg. 1972. Rapid identification of repeated patterns in strings, trees and arrays. In Proceedings of the 4th STOC. ACM, 125--136.
15. Richard M. Karp and Michael O. Rabin. 1987. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development 31, 2, 249--260.
16. Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo Arikawa, and Kunsoo Park. 2001. Linear-time longest-common-prefix computation in suffix arrays and its applications. In Proceedings of the 12th CPM. Lecture Notes in Computer Science, Vol. 2089. 181--192.
17. Roman Kolpakov, Gregory Kucherov, and Tatiana A. Starikovskaya. 2011. Pattern matching on sparse suffix trees. In Proceedings of the 1st CCP. 92--97.
18. Udi Manber and Gene Myers. 1993. Suffix arrays: A new method for on-line string searches. SIAM Journal on Computing 22, 5, 935--948.
19. Donald R. Morrison. 1968. PATRICIA—practical algorithm to retrieve information coded in alphanumeric. Journal of the ACM 15, 4, 514--534.
20. Mike Paterson. 1990. Improved sorting networks with O(log N) depth. Algorithmica 5, 1, 65--92.
21. Tomohiro I, Juha Kärkkäinen, and Dominik Kempa. 2014. Faster sparse suffix sorting. In Proceedings of the 31st STACS. 386--396.
22. Takashi Uemura and Hiroki Arimura. 2011. Sparse and truncated suffix trees on variable-length codes. In Proceedings of the 22nd CPM. Lecture Notes in Computer Science, Vol. 6661. 246--260.
23. Peter Weiner. 1973. Linear pattern matching algorithms. In Proceedings of the 14th FOCS (SWAT). 1--11.
24. Dan E. Willard. 1983. Log-logarithmic worst-case range queries are possible in space Θ(N). Information Processing Letters 17, 2, 81--84.

Index Terms

• Theory of computation

  • Design and analysis of algorithms

    • Data structures design and analysis

      • Pattern matching

      • Sorting and searching