Publications
- Gonzalo Navarro and Veli Makinen, Compressed Full-Text Indexes, Technical Report TR/DCC-2006-6, Department of Computer Science, University of Chile, 2006.
[ftp://ftp.dcc.uchile.cl/pub/users/gnavarro/survcompr2.ps.gz]
- Roberto Grossi and Jeffrey Vitter, Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching, SIAM Journal on Computing, 2005.
[http://www.di.unipi.it/~grossi/PAPERS/sicomp05.pdf]
- Meng He, J. Ian Munro and S. Srinivasa Rao, A Categorization Theorem on Suffix Arrays with Applications to Space Efficient Text Indexes, Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005.
[http://www.cs.uwaterloo.ca/~mhe/research/soda2005.ppt]
- Veli Makinen and Gonzalo Navarro, Succinct Suffix Arrays based on Run-Length Encoding, Nordic Journal of Computing, 12(1), pp. 40-66, 2005.
[http://www.dcc.uchile.cl/~gnavarro/ps/njc05.ps.gz]
[http://www.cs.helsinki.fi/u/vmakinen/papers/njc05.ps.gz]
- Gonzalo Navarro and Veli Makinen, Compressed Full-Text Indexes, Technical Report TR/DCC-2005-7, Department of Computer Science, University of Chile, 2005.
[ftp://ftp.dcc.uchile.cl/pub/users/gnavarro/survcompr.ps.gz]
[http://www.cs.helsinki.fi/u/vmakinen/papers/njc05.ps.gz]
- Roberto Grossi, Ankur Gupta and Jeffrey Vitter, When Indexing Equals Compression: Experiments with Compressing Suffix Arrays and Applications, Proceedings of the 15th Annual SIAM/ACM Symposium on Discrete Algorithms, pp. 636-645, 2004.
[http://www.di.unipi.it/~grossi/PAPERS/soda04.pdf]
[http://www.cs.duke.edu/~jsv/Papers/GGV04.TextIndexingExperimentsJournal.pdf]
- Veli Makinen, Gonzalo Navarro and Kunihiko Sadakane, Advantages of Backward Searching - Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays, Proceedings of the 15th Annual Symposium on Algorithms and Computation, LNCS 3341, Springer-Verlag, pp. 681-692, 2004.
[http://citeseer.ist.psu.edu/694744.html]
[http://www.cs.helsinki.fi/u/vmakinen/papers/isaac04.ps.gz]
[http://www.dcc.uchile.cl/~gnavarro/ps/isaac04.ps.gz]
- Veli Makinen and Gonzalo Navarro, Compressed Compact Suffix Arrays, Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching, LNCS 3109, Springer-Verlag, pp. 420-433, 2004.
[http://citeseer.ist.psu.edu/662541.html]
[http://www.cs.helsinki.fi/u/vmakinen/papers/ccsa_cpm.ps.gz]
[http://www.dcc.uchile.cl/~gnavarro/ps/cpm04.2.ps.gz]
- Veli Makinen and Gonzalo Navarro, New Search Algorithms and Time/Space Tradeoffs for Succinct Suffix Arrays, Technical Report C-2004-20, Department of Computer Science, University of Helsinki, 2004.
[http://www.cs.helsinki.fi/u/vmakinen/papers/ssa_tech_2004.ps.gz]
- Roberto Grossi, Ankur Gupta and Jeffrey Vitter, High-Order Entropy-Compressed Text Indexes, Proceedings of the 14th Annual SIAM/ACM Symposium on Discrete Algorithms, pp. 841-850, 2003.
[http://citeseer.ist.psu.edu/571573.html]
[http://www.di.unipi.it/~grossi/PAPERS/sodaconf03FINAL-LATEST.pdf]
[http://www.cs.duke.edu/~jsv/Papers/GGV03.entropy.ps.gz]
[http://www.cs.duke.edu/~jsv/Papers/GGV03.entropy.pdf]
- Wing-Kai Hon, Kunihiko Sadakane and 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, pp. 251-260, 2003.
[http://www.comp.nus.edu.sg/~ksung/papers/focs-csa.ps]
- Wing-Kai Hon, Tak-Wah Lam, Kunihiko Sadakane and Wing-Kin Sung, Constructing Compressed Suffix Arrays with Large Alphabets, Proceedings of the 14th Annual International Symposium on Algorithms and Computation, LNCS 2906, Springer-Verlag, pp. 240-249, 2003.
[http://www.comp.nus.edu.sg/~ksung/papers/isaac-csa.ps]
- Tak-Wah Lam, Kunihiko Sadakane, Wing-Kin Sung and Siu-Ming Yiu, A Space and Time Efficient Algorithm for Constructing Compressed Suffix Arrays, Proceedings of the 8th Annual International Conference on Computing and Combinatorics, LNCS 2387, Springer-Verlag, pp. 401-410, 2002.
[http://citeseer.ist.psu.edu/659613.html]
- Kunihiko Sadakane and Tetsuo Shibuya, Indexing Huge Genome Sequences for Solving Various Problems, Proceedings of the 12th Genome Informatics, pp. 175-183, 2001.
[http://citeseer.ist.psu.edu/sadakane01indexing.html]
[http://www.hgc.jp/~tshibuya/papers/giw01(CSA).pdf]
- Roberto Grossi and Jeffrey Vitter, Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching, Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pp. 397-406, 2000.
[http://citeseer.ist.psu.edu/grossi00compressed.html]
[ftp://ftp.di.unipi.it/pub/Papers/grossi/stoc00.ps.gz]
[http://www.cs.duke.edu/~jsv/Papers/GrV00.text_indexing.ps.gz]
[http://www.cs.duke.edu/~jsv/Papers/GrV00.text_indexing.pdf]
[http://www.cs.duke.edu/~jsv/Papers/GrV00.text_indexing_slides.ps.gz]
[http://www.cs.duke.edu/~jsv/Papers/GrV00.text_indexing_slides.pdf]
- Kunihiko Sadakane, Compressed Text Databases with Efficient Query Algorithms based on the Compressed Suffix Array, Proceedings of the 11th International Conference on Algorithms and Computation, LNCS 1969, Springer-Verlag, pp. 410-421, 2000.
[http://citeseer.ist.psu.edu/sadakane00compressed.html]
- Kunihiko Sadakane, Algorithms on Strings based on the Compressed Suffix Arrays, IPSJ SIG Notes SIGAL-74-10, 2000.
[http://citeseer.ist.psu.edu/456871.html]
- Wing-Kai Hon, Tak-Wah Lam, Kunihiko Sadakane, Wing-Kin Sung and Siu-Ming Yiu, A Space and Time Efficient Algorithm for Constructing Compressed Suffix Arrays, Algorithmica,
[http://www.cs.purdue.edu/homes/wkhon/papers/HLSSY05.pdf]
Source Code
日本語の資料