A taxonomy of suffix array construction algorithms

ABSTRACT

In 1990, Manber and Myers proposed suffix arrays as a space-saving alternative to suffix trees and described the first algorithms for suffix array construction and use. Since that time, and especially in the last few years, suffix array construction algorithms have proliferated in bewildering abundance. This survey paper attempts to provide simple high-level descriptions of these numerous algorithms that highlight both their distinctive features and their commonalities, while avoiding as much as possible the complexities of implementation details. New hybrid algorithms are also described. We provide comparisons of the algorithms' worst-case time complexity and use of additional space, together with results of recent experimental test runs on many of their implementations.

REFERENCES

• 1: Mohamed Ibrahim Abouelhoda , Stefan Kurtz , Enno Ohlebusch, Replacing suffix trees with enhanced suffix arrays, Journal of Discrete Algorithms, v.2 n.1, p.53-86, March 2004 [doi>10.1016/S1570-8667(03)00065-0]
• 2: Apostolico, A. 1985. The myriad virtues of subword trees. In Combinatorial Algorithms on Words. NATO ASI Series F12. Springer-Verlag, Berlin, Germany, 85--96.
• 3: Dror Baron , Yoram Bresler, Antisequential Suffix Sorting for BWT-Based Data Compression, IEEE Transactions on Computers, v.54 n.4, p.385-397, April 2005 [doi>10.1109/TC.2005.56]
• 4: Jon L. Bentley , M. Douglas McIlroy, Engineering a sort function, Software—Practice & Experience, v.23 n.11, p.1249-1265, Nov. 1993 [doi>10.1002/spe.4380231105]
• 5: Jon L. Bentley , Robert Sedgewick, Fast algorithms for sorting and searching strings, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.360-369, January 05-07, 1997, New Orleans, Louisiana, United States
• 6: Burkhardt, S. and Kärkkäinen, J. 2003. Fast lightweight suffix array construction and checking. In Proceedings of the 14th Annual Symposium CPM 2003, R. Baeza-Yates, E. Chávez, and M. Crochemore, Eds. Lecture Notes in Computer Science, vol. 2676. Springer-Verlag, Berlin, Germany, 55--69.
• 7: Burrows, M. and Wheeler, D. J. 1994. A block sorting lossless data compression algorithm. Tech. Rep. 124, Digital Equipment Corporation, Palo Alto, CA.
• 8: Crauser, A. and Ferragina, P. 2002. A theoretical and experimental study on the construction of suffix arrays in external memory. Algorithmica 32, 1--35.
• 9: 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
• 10: Paolo Ferragina , Roberto Grossi, The string B-tree: a new data structure for string search in external memory and its applications, Journal of the ACM (JACM), v.46 n.2, p.236-280, March 1999 [doi>10.1145/301970.301973]
• 11: Roberto Grossi , Jeffrey Scott Vitter, Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching, SIAM Journal on Computing, v.35 n.2, p.378-407, 2005 [doi>10.1137/S0097539702402354]
• 12: Hart, M. 1997. Project Gutenberg. http://www.gutenberg.net.
• 13: Wing-Kai Hon , Kunihiko Sadakane , Wing-Kin Sung, Breaking a Time-and-Space Barrier in Constructing Full-Text Indices, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.251, October 11-14, 2003
• 14: Hideo Itoh , Hozumi Tanaka, An Efficient Method for in Memory Construction of Suffix Arrays, Proceedings of the String Processing and Information Retrieval Symposium & International Workshop on Groupware, p.81, September 21-24, 1999
• 15: Kärkkäinen, J. and Sanders, P. 2003. Simple linear work suffix array construction. In Proceedings of the 30th International Colloquium Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 2971. Springer-Verlag, Berlin, Germany, 943--955.
• 16: Juha Kärkkäinen , Peter Sanders , Stefan Burkhardt, Linear work suffix array construction, Journal of the ACM (JACM), v.53 n.6, p.918-936, November 2006 [doi>10.1145/1217856.1217858]
• 17: Richard M. Karp , Raymond E. Miller , Arnold L. Rosenberg, Rapid identification of repeated patterns in strings, trees and arrays, Proceedings of the fourth annual ACM symposium on Theory of computing, p.125-136, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804905]
• 18: 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
• 19: Khmelev, D. V. 2003. Program suffsort version 0.1.6. http://www.math.toronto.edu/dkhmelev/PROGS/tacu/suffsort-eng.html.
• 20: Kim, D. K., Jo, J., and Park, H. 2004. A fast algorithm for constructing suffix arrays for fixed-size alphabets. In Proceedings of the 3rd Workshop on Experimental and Efficient Algorithms (WEA 2004), C. C. Ribeiro and S. L. Martins, Eds. Springer-Verlag, Berlin, Germany, 301--314.
• 21: Kim, D. K., Sim, J. S., Park, H., and Park, K. 2003. Linear-time construction of suffix arrays. In Proceedings of the 14th Annual Symposium Combinatorial Pattern Matching, R. Baeza-Yates, E. Chávez, and M. Crochemore, Eds. Lecture Notes in Computer Science, vol. 2676. Springer-Verlag, Berlin, Germany, 186--199.
• 22: Kim, D. K., Sim, J. S., Park, H., and Park, K. 2005. Constructing suffix arrays in linear time. J. Discrete Algorithms 3, 126--142.
• 23: Ko, P. 2006. Linear time suffix array. http://www.public.iastate.edu/~kopang/progRelease/homepage.html.
• 24: Ko, P. and Aluru, S. 2003. Space efficient linear time construction of suffix arrays. In Proceedings of the 14th Annual Symposium CPM 2003, R. Baeza-Yates, E. Chávez, and M. Crochemore, Eds. Lecture Notes in Computer Science, vol. 2676. Springer-Verlag, Berlin, Germany, 200--210.
• 25: Ko, P. and Aluru, S. 2005. Space efficient linear time construction of suffix arrays. J. Disc. Algor. 3, 143--156.
• 26: Stefan Kurtz, Reducing the space requirement of suffix trees, Software—Practice & Experience, v.29 n.13, p.1149-1171, Nov. 1999 [doi>10.1002/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O]
• 27: Larsson, J. N. and Sadakane, K. 1999. Faster suffix sorting. Tech. Rep. LU-CS-TR:99-214 {LUNFD6/(NFCS-3140)/1-20/(1999)}, Department of Computer Science, Lund University, Sweden.
• 28: Lee, S. and Park, K. 2004. Efficient implementations of suffix array construction algorithms. In AWOCA 2004: Proceedings of the 15th Australasian Workshop on Combinatorial Algorithms, S. Hong, Ed. 64--72.
• 29: Malyshev, D. 2006. DARK the universal archiver based on BWT-DC scheme. http://darchiver.narod.ru/.
• 30: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.319-327, January 22-24, 1990, San Francisco, California, United States
• 31: 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]
• 32: Maniscalco, M. A. 2005. MSufSort. http://www.michael-maniscalco.com/msufsort.htm.
• 33: Maniscalco, M. A. and Puglisi, S. J. 2006. Faster lightweight suffix array construction. In Proceedings of 17th Australasian Workshop on Combinatorial Algorithms, J. Ryan and Dafik, Eds. Univ. Ballavat, Ballavat, Victoria, Australia, 16--29.
• 34: Maniscalco, M. A. and Puglisi, S. J. 2007. An efficient, versatile approach to suffix sorting. ACM J. Experiment. Algor. To appear.
• 35: Manzini, G. 2004. Two space saving tricks for linear time LCP computation. In Proceedings of 9th Scandinavian Workshop on Algorithm Theory (SWAT '04), T. Hagerup and J. Katajainen, Eds. Lecture Notes in Computer Science, vol. 3111. Springer-Verlag, Berlin, Germany, 372--383.
• 36: Giovanni Manzini , Paolo Ferragina, Engineering a Lightweight Suffix Array Construction Algorithm, Algorithmica, v.40 n.1, p.33-50, June 2004 [doi>10.1007/s00453-004-1094-1]
• 37: McIlroy, M. D. 1997. ssort.c. http://cm.bell-labs.com/cm/cs/who/doug/source.html.
• 38: McIlroy, P. M., Bostic, K., and McIlroy, M. D. 1993. Engineering radix sort. Comput. Syst. 6, 1, 5--27.
• 39: Mori, Y. 2006. DivSufSort. http://www.homepage3.nifty.com/wpage/software/libdivsufsort.html.
• 40: J. Ian Munro, Tables, Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science, p.37-42, December 18-20, 1996
• 41: Na, J. C. 2005. Linear-time construction of compressed suffix arrays using O(nlogn)-bit working space for large alphabets. In Proceedings of the 16th Annual Symposium Combinatorial Pattern Matching, A. Apostolico, M. Crochemore, and K. Park, Eds. Lecture Notes in Computer Science, vol. 3537. Springer-Verlag, Berlin, Germany, 57--67.
• 42: Gonzalo Navarro , Veli Mäkinen, Compressed full-text indexes, ACM Computing Surveys (CSUR), v.39 n.1, p.2-es, 2007 [doi>10.1145/1216370.1216372]
• 43: Simon J. Puglisi , William F. Smyth , Andrew Turpin, The Performance of Linear Time Suffix Sorting Algorithms, Proceedings of the Data Compression Conference, p.358-367, March 29-31, 2005 [doi>10.1109/DCC.2005.87]
• 44: K. Sadakane, A Fast Algorithms for Making Suffix Arrays and for Burrows-Wheeler Transformation, Proceedings of the Conference on Data Compression, p.129, March 30-April 01, 1998
• 45: Schürmann, K. and Stoye, J. 2005. An incomplex algorithm for fast suffix array construction. In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX05). SIAM, 77--85.
• 46: Julian Seward, On the Performance of BWT Sorting Algorithms, Proceedings of the Conference on Data Compression, p.173, March 28-30, 2000
• 47: Sim, J. S., Kim, D. K., Park, H., and Park, K. 2003. Linear-time search in suffix arrays. In Proceedings of the 14th Australasian Workshop on Combinatorial Algorithms, M. Miller and K. Park, Eds. (Seoul, Korea), 139--146.
• 48: Ranjan Sinha , Justin Zobel, Cache-conscious sorting of large sets of strings with dynamic tries, Journal of Experimental Algorithmics (JEA), 9, 2004 [doi>10.1145/1005813.1041517]
• 49: Smyth, B. 2003. Computing Patterns in Strings. Pearson Addison-Wesley, Essex, England.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

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

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Keywords:
Burrows--Wheeler transform, Suffix array, suffix sorting, suffix tree