Publications
- Ge Nong, Sen Zhang and Wai Hong Chan, Two Efficient Algorithms for Linear Suffix Array Construction, 2008.
[http://www.cs.sysu.edu.cn/nong/index.files/Two%20Efficient%20Algorithms%20for%20Linear%20Suffix%20Array%20Construction.pdf]
- Gianni Francheschini and S. Muthukrishnan, In-Place Suffix Sorting, Proceedings of the 34th International Colloquium on Automata, Languages and Programming, 2007.
[http://www.cs.rutgers.edu/~muthu/fm072.pdf]
- Jesper Larsson and Kunihiko Sadakane, Faster Suffix Sorting, Theoretical Computer Science, 2007.
[http://eprints.csce.kyushu-u.ac.jp/33/1/sscamera.ps]
- Ge Nong and Sen Zhang, Optimal Lightweight Construction of Suffix Arrays, Proceedings of the 10th Workshop on Algorithms and Data Structures, LNCS 4619, pp. 613-624, 2007.
[http://www.cs.sysu.edu.cn/nong/index.files/optimal%20lightweight%20construction%20of%20suffix%20array.pdf]
- Klaus-Bernd Schurmann, Suffix Arrays in Theory and Practice, 2007.
[http://bieson.ub.uni-bielefeld.de/volltexte/2007/1179/pdf/Dissertation_Klaus-Bernd_Schuermann.pdf]
- Rudolf Ahlswede, Bernhard Balkenhol, Christian Deppe and Martin Frohlich, A Fast Suffix-Sorting Algorithm, General Theory of Information Transfer and Combinatorics, LNCS 2676, Springer-Verlag, pp. 719-734, 2006.
[http://www.math.uni-bielefeld.de/ahlswede/homepage/public/193.pdf]
- Juha Karkkainen, Fast BWT in Small Space by Blockwise Suffix Sorting, Theoretical Computer Science, 2006.
[http://www.cs.helsinki.fi/juha.karkkainen/publications/tcs06-revised.ps.gz]
- Michael Maniscalco and Simon Puglisi, Faster Lightweight Suffix Array Construction, Proceedings of the 17th Australasian Workshop on Combinatorial Algorithms, pp. 16-19, 2006.
[http://goanna.cs.rmit.edu.au/~sjp/awoca2006.pdf]
- Simon Puglisi, William Smyth and Andrew Turpin, A Taxonomy of Suffix Array Construction Algorithms, ACM Computing Surveys, 2006.
[http://www.computing.edu.au/~smyth/survey.ps]
[http://www.cas.mcmaster.ca/~bill/tax.ps]
- Dror Baron and Yoram Bresler, Anti-Sequential Suffix Sorting for BWT-Based Data Compression, IEEE Transactions on Computers, 54(4), pp. 385-397, 2005.
[http://www-old.ece.rice.edu/~drorb/pdf/116140-2-nobios.pdf]
- Roman Dementiev, Juha Karkkainen, Jens Mehnert and Peter Sanders, Better External Memory Suffix Array Construction, Proceedings of the 7th Workshop on Algorithm Engineering and Experiments, 2005.
[http://www.mpi-sb.mpg.de/~sanders/papers/DKMS05.pdf]
[http://www.siam.org/meetings/alenex05/papers/08rdementiev.pdf]
- Juha Karkkainen, Peter Sanders and Stefan Burkhardt, Linear work suffix array construction, Journal of ACM, 2005.
[http://www.cs.helsinki.fi/juha.karkkainen/publications/jacm05-revised.pdf]
- Simon Puglisi, William Smyth and Andrew Turpin, The Performance of Linear Time Suffix Sorting Algorithms (extended abstract), Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, pp. 358-367, 2005.
[http://www.computing.edu.au/~smyth/pst.ps]
- Simon Puglisi, Exposition and analysis of a suffix sorting algorithm, Technical report CAS-05-02-WS, Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada, 2005.
[http://www.computing.edu.au/~puglissj/msufsort.ps]
- Klaus-Bernd Schurmann and Jens Stoye, An Incomplex Algorithm for Fast Suffix Array Construction, Proceedings of the 7th Workshop on Algorithm Engineering and Experiments, 2005.
[http://www.techfak.uni-bielefeld.de/~stoye/cpublications/alenex2005final.pdf]
[http://www.siam.org/meetings/alenex05/papers/07kschuermann.pdf]
- Mohamed Ibrahim Abouelhoda, Stefan Kurtz and Enno Ohlebusch, Replacing suffix trees with enhanced suffix arrays, Journal of Discrete Algorithms, 2(1), pp. 53-86, 2004.
[http://www.computing.edu.au/~smyth/ako04.pdf]
[http://www.zbh.uni-hamburg.de/staff/kurtz/papers/AboKurOhl2004.pdf]
[http://theorie.informatik.uni-ulm.de/Personen/eo/PAPERS/JDA04.pdf]
- Antonitio, Patrick Ryan, William Smyth, Andrew Turpin and Xiaoyang Yu, New Suffix Array Algorithms --- Linear But Not Fast?, Proceedings of the 15th Australasian Workshop on Combinatorial Algorithms, pp. 148-156, 2004.
[http://www.cas.mcmaster.ca/~bill/antonitio.ps]
[http://www.computing.edu.au/~smyth/arsty04.ps]
- Juha Karkkainen, Fast BWT in small space by blockwise suffix sorting, Proceedings DIMACS Working Group on The Burrows-Wheeler Transform: Ten Years Later, pp. 12-13, 2004.
[http://www.cs.helsinki.fi/juha.karkkainen/publications/bwt04.pdf]
[http://dimacs.rutgers.edu/Workshops/BWT/karkkainen.pdf]
- Sunglim Lee and Kunsoo Park, Efficient Implementations of Suffix Array Construction Algorithms, Proceedings of the 15th Australasian Workshop on Combinatorial Algorithms, pp. 64-72, 2004.
[http://www.computing.edu.au/~smyth/lp04.ps]
- Giovanni Manzini, Two Space Saving Tricks for Linear Time LCP Array Computation, Proceedings of the 9th Scandinavian Workshop on Algorithm Theory, pp. 372-383, 2004.
[http://www.mfn.unipmn.it/~manzini/papers/lcptr.pdf]
- Stefan Burkhardt and Juha Karkkainen, Fast Lightweight Suffix Array Construction and Checking, Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching, LNCS 2676, Springer, pp. 55-69, 2003.
[http://citeseer.ist.psu.edu/566305.html]
[http://www.cs.helsinki.fi/juha.karkkainen/publications/cpm03.pdf]
[http://www.mpi-sb.mpg.de/~stburk/PUBLICATIONS/cpm_03.ps]
- Juha Karkkainen and Peter Sanders, Simple Linear Work Suffix Array Construction, Proceedings of the 30th International Colloquium on Automata, Languages and Programming, LNCS 2719, Springer, pp. 943-955, 2003.
[http://citeseer.ist.psu.edu/arkk03simple.html]
[http://www.cs.helsinki.fi/juha.karkkainen/publications/icalp03.pdf]
- Dong Kyue Kim, Jeong Seop Sim, Heejin Park and Kunsoo Park, Linear-time construction of suffix arrays, Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching, pp. 186-199, 2003.
[http://www.computing.edu.au/~smyth/linear3.ps]
- Pang Ko and Srinivas Aluru, Space-efficient linear time construction of suffix arrays, Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching, pp. 200-210, 2003.
[http://www.public.iastate.edu/~kopang/myPaper/SpaceELTCoSA%5BKA%5D_CPM.pdf]
[http://vulcan.ee.iastate.edu/~aluru/publications/p/CPM-2003-LinearTimeSuffixArrays.pdf]
[http://www.computing.edu.au/~smyth/linear1.ps]
- Giovanni Manzini and Paolo Ferragina, Engineering a lightweight suffix array construction algorithm, Technical Report, 2003.
[http://www.mfn.unipmn.it/~manzini/lightweight/lightweight_TR.pdf]
- Mohamed Ibrahim Abouelhoda, Stefan Kurtz and Enno Ohlebusch, The Enhanced Suffix Array and its Applications to Genome Analysis, Proceedings of the 2nd Workshop on Algorithms in Bioinformatics, LNCS 2452, Springer-Verlag, pp. 449-463, 2002.
[http://www.computing.edu.au/~smyth/ako02.pdf]
[http://www.techfak.uni-bielefeld.de/~kurtz/PS/ABO:KUR:OHL:2002.pdf]
[http://www.zbh.uni-hamburg.de/staff/kurtz/papers/AboKurOhl2002.pdf]
[http://theorie.informatik.uni-ulm.de/Personen/eo/PAPERS/WABI02.pdf]
- Mohamed Ibrahim Abouelhoda, Enno Ohlebusch and Stefan Kurtz, Optimal Exact String Matching Based on Suffix Arrays, Proceedings of the 9th International Symposium on String Processing and Information Retrieval, LNCS 2476, Springer-Verlag, pp. 31-43, 2002.
[http://www.techfak.uni-bielefeld.de/~kurtz/PS/ABO:OHL:KUR:2002.pdf]
[http://www.zbh.uni-hamburg.de/staff/kurtz/papers/AboOhlKur2002.pdf]
[http://theorie.informatik.uni-ulm.de/Personen/eo/PAPERS/SPIRE02.pdf]
- Giovanni Manzini and Paolo Ferragina, Engineering a lightweight suffix array construction algorithm, Proceedings of the 10th European Symposium on Algorithms, LNCS 2461, Springer, pp. 698-710, 2002.
[http://www.mfn.unipmn.it/~manzini/papers/esa02.ps.gz]
[http://www.mfn.unipmn.it/~manzini/papers/esa02.pdf]
- Tsai-Hsing Kao, Improving Suffix-Array Construction Algorithms with Applications, Master's thesis, Department of Computer Science, Gunma University, Japan, 2001.
[http://citeseer.ist.psu.edu/692550.html]
[http://www.isl.cs.gunma-u.ac.jp/Yokoo/dataroom/paper/00/thkao/thesis.ps]
- Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo Arikawa and Kunsoo Park, Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications, Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, LNCS 2089, Springer-Verlag, pp. 181-192, 2001.
[http://www.cs.iastate.edu/~cs548/references/linear_lcp.pdf]
- Toru Kasai, Hiroki Arimura and Setsuo Arikawa, Efficient Substring Traversal with Suffix Arrays, DOI-Technical Report of the Informatics Department of Kyushu University, 2001.
[http://citeseer.ist.psu.edu/522862.html]
- Kunihiko Sadakane, Unifying Text Search And Compression Suffix Sorting, Block Sorting and Suffix Arrays, PhD thesis, University of Tokyo, 2000.
[http://citeseer.ist.psu.edu/sadakane00unifying.html]
- Joao Paulo Kitajima and Gonzalo Navarro, A Fast Distributed Suffix Array Generation Algorithm, Proceedings of the String Processing and Information Retrieval Symposium and International Workshop on Groupware, pp. 97-104, 1999.
[http://citeseer.ist.psu.edu/551897.html]
[http://www.dcc.uchile.cl/~gnavarro/ps/spire99.3.ps.gz]
- Jesper Larsson and Kunihiko Sadakane, Faster Suffix Sorting, Technical report LU-CS-TR:99-214, Department of Computer Science, Lund University, Sweden, 1999.
[http://citeseer.ist.psu.edu/larsson99faster.html]
[http://www.larsson.dogma.net/ssrev-tr.pdf]
[http://www.larsson.dogma.net/ssrev-tr.ps.gz]
- Jesper Larsson, Structures of String Matching and Data Compression, PhD thesis, Department of Computer Science, Lund University, Sweden, 1999.
[http://citeseer.ist.psu.edu/larsson99structures.html]
[http://www.larsson.dogma.net/thesis.pdf]
[http://www.larsson.dogma.net/thesis.ps.gz]
- Jesper Larsson, Notes On Suffix Sorting, Technical report LU-CS-TR:98-204, Lund University, Sweden, 1998.
[http://citeseer.ist.psu.edu/larsson98notes.html]
[http://www.larsson.dogma.net/tr204.pdf]
[http://www.larsson.dogma.net/tr204.ps.gz]
- Kunihiko Sadakane, A fast algorithm for making suffix arrays and for Burrows-Wheeler transformation, Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, pp. 129-138, 1998.
[http://citeseer.ist.psu.edu/larsson99faster.html]
[http://www-imai.is.s.u-tokyo.ac.jp/PAPERS/Sada98b.ps]
- Jon Bentley and Robert Sedgewick, Fast Algorithms for Sorting and Searching Strings, Proceedings of the 8th annual ACM-SIAM symposium on Discrete algorithms, pp. 360-369, 1997.
[http://citeseer.ist.psu.edu/bentley97fast.html]
[http://www.cs.princeton.edu/~rs/strings/paper.ps]
[http://www.cs.princeton.edu/~rs/strings/paper.pdf]
- Joao Paulo Kitajima, Gonzalo Navarro, Berthier Ribeiro and Nivio Ziviani, Distributed Generation of Suffix Arrays: a Quicksort-Based Approach, Proceedings of the 4th South American Workshop on String Processing, Valparaiso, Chile, pp. 53-59, 1997.
[http://citeseer.ist.psu.edu/46787.html]
[http://www.dcc.ufmg.br/~berthier/conference_papers/wsp_1997.pdf]
- Gonzalo Navarro, Joao Paulo Kitajima, Berthier Ribeiro and Nivio Ziviani, Distributed Generation of Suffix Arrays, Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching, LNCS 1264, pp. 102-115, 1997.
[http://citeseer.ist.psu.edu/navarro97distributed.html]
[http://www.dcc.uchile.cl/~gnavarro/ps/cpm97.ps.gz]
[http://www.dcc.ufmg.br/~berthier/conference_papers/cpm_1997.pdf]
- Udi Manber and Gene Myers, Suffix arrays: A new method for on-line string searches, SIAM Journal on Computing, 22(5), pp. 935-948, 1993.
[http://www.cs.arizona.edu/people/udi/suffix.ps]
[http://webglimpse.net/pubs/suffix.pdf]
Source Code
日本語の資料