University homepage Suomenkielinen versio puuttuu Inte på svenska In english
University of Helsinki Department of Computer Science
 

Department of Computer Science

GCSA

GCSA [2, 3] is a compressed suffix array for finite languages. The implementation now supports general alphabet and multiple automata. The most up-to-date description of GCSA can be found in [3].

See README in the package for further information.

The implementation is available for download under the MIT / X11 License. Our implementation of RLCSA [1, 3] is required for compiling GCSA. (The current version of GCSA should always work with the current version of RLCSA.)

Return to the SuDS homepage.

News

  • 2012-12-07 A new version with support for general alphabet and multiple automata.
  • 2012-06-11 Information about the data sets used in the experiments.
  • 2012-02-14 Simpler and faster index. More space-efficient construction.
  • 2011-08-23 Vastly improved construction algorithm.
  • 2011-01-17 A new version that is significantly faster, and supports approximate searching.
  • 2010-10-13 The implementation of GCSA is now available.

Downloads

  • Current version (December 2012).
  • December 2012. GCSA now supports general alphabet and multiple automata. There is also a program for merging multiple automata into a single file, making them reverse deterministic when necessary. Requires December 2012 version of RLCSA.
  • February 2012. A simpler version of GCSA that is theoretically 2x (instead of 3x) slower than a regular CSA. Construction uses in-place sorting that is more space-efficient but slightly slower. Requires February 2012 version of RLCSA. This version was used in the experiments in [3].
  • August 2011. This implementation was used in the full version of [2]. Contains a vastly improved construction algorithm. Requires August 2011 version of RLCSA.
  • January 2011. A new improved version with faster basic operations and support for approximate searching. This version was used in [2]. Requires January 2011 version of RLCSA.
  • October 2010. The original version. Works with RLCSA (October 2010).

Data

The alignment of the four assemblies of human chromosome 18 is available for download. See [2] for a description of the alignment. The read set used in the experiments in [2, 3] is not publicly available.

References

  1. Veli Mäkinen, Gonzalo Navarro, Jouni Sirén, and Niko Välimäki: Storage and Retrieval of Highly Repetitive Sequence Collections.
    Journal of Computational Biology 17(3):281-308, 2010.
    [Article] [Preprint]
  2. Jouni Sirén, Niko Välimäki, and Veli Mäkinen: Indexing Finite Language Representation of Population Genotypes.
    Proc. WABI 2011, Springer LNCS 6833, pp. 270-281, Saarbrücken, Germany, September 5-7, 2011.
    [Article] [Preprint] [Full version]
  3. Jouni Sirén: Compressed Full-Text Indexes for Highly Repetitive Collections (PhD Thesis).
    Department of Computer Science, Series of Publications A, Report A-2012-5, University of Helsinki, June 2012.
    [Thesis]

Jouni.Siren@cs.helsinki.fi


Feedback | Faculty homepage | University homepage