Optimal suffix selection

ABSTRACT

Given a string S[1·s n], the suffix selection problemis to find the kth lexicographically smallest amongst the n suffixes S[i·s n], for i=1,...,n. In particular, the fundamental question is if selection can be performed more efficiently than sorting all the suffixes.

If one considered n numbers, they can be sorted using Θ(n log n) comparisonsand the classical result from 70's is that selection can be done using O(n) comparisons. Thus selection is provably more efficient than sorting, for n numbers.

Suffix sorting can be done using Θ(n log n) comparisons, but does suffix selection need suffix sorting? We settle this fundamental problem by presenting an optimal, deterministic algorithm for suffix selection using O(n) comparisons.

REFERENCES

• 1: M. Blum, R. Floyd, V. Pratt, R. Rivest, and R. Tarjan. Time bounds for selection. J. Comput. System Sci., 7:448--61, 1973.
• 2: M. Farach, Optimal suffix tree construction with large alphabets, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.137, October 19-22, 1997
• 3: Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
• 4: J. Karkkainen and P. Sanders. Simple linear work suffix array construction. In Proc. Int. Colloquium on Automata, Languages and Programming, volume 2719 of Lecture Notes in Computer Science, pages 943--955, 2003.
• 5: Toru Kasai , Gunho Lee , Hiroki Arimura , Setsuo Arikawa , Kunsoo Park, Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications, Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, p.181-192, July 01-04, 2001
• 6: D.K. Kim, J.S. Sim, H. Park, and K. Park. Linear-time construction of suffix arrays. In Proc. Annual Symp. on Combinatorial Pattern Matching, volume 2676 of Lecture Notes in Computer Science, pages 186--199, 2003.
• 7: P. Ko and S. Aluru. Space efficient linear time construction of suffix arrays. In Proc. Annual Symposium on Combinatorial Pattern Matching, volume 2676 of Lecture Notes in Computer Science, pages 200--210, 2003.
• 8: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, SIAM Journal on Computing, v.22 n.5, p.935-948, Oct. 1993 [doi>10.1137/0222058]
• 9: Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
• 10: P. Weiner. Linear pattern matching algorithms. In IEEE Symposium on Foundations of Computer Science (FOCS), 1973.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
order statistics, selection, strings, suffixes