SDSL - Succinct Data Structure Library

sdsl is an open source C++ library of efficient succinct data structures. The goals of the library are:

Providing a base set of easy to use succinct data structures (like the data structures of the stl) for the development of more complex succinct data structures (like compressed suffix arrays and trees).
High performance through a generic design of the whole library.
Reliability through unit test and a good documentation.

See the documentation for details.

Download the latest version: sdsl-0.9.8 (October 2011)

Installation:

1. a) download the libdivsufsort of Yuta Mori from

   http://code.google.com/p/libdivsufsort/

   b) unpack libdivsufsort-2.0.1.tar.gz into a directory libdivsufsort-2.0.1 and change into that directoy

   open the CMakeList.txt file with an editor and

change the option BUILD_DIVSUFSORT64 from OFF to ON

   c) create a build directory (in libdivsufsort-2.0.1)

   d) cd build

   e) cmake .. -DCMAKE_INSTALL_PREFIX=${HOME}

   f) make

   g) make install

2. a) goto the build directory /path/to/sdsl/build

   b) cmake .. -DCMAKE_INSTALL_PREFIX=${HOME}

   c) make

   d) make install

You can now compile your program example.cc by

g++ -O3 -DNDEBUG -funroll-loops -I${HOME}/include/ -L${HOME}/lib/ -o example example.cc ${HOME}/lib/libsdsl.a -ldivsufsort -ldivsufsort64

or download sdsl_tutorial.tar.gz to compile some examples.

New features of version 0.7.5:

We now use the divsufsort algorithm of Yuta Mori to construct the indexes.
The calculation of matching statistics in backward direction
Implementation of the range-min-max-tree of Sadakane and Navarro.

New features of version 0.7.0: A support data structure for balanced parentheses sequences proposed by Geary et. al (CPM 2004): balanced_parentheses_support_g .

The results of an experimental study of different succinct Range Minimum Query Data Structures are available here. The source code of the experimental study and an installation description is available here. If you want to execute the experiments you should also download the test inputs.

Download older source:

sdsl-0.9 (October 2010)
sdsl-0.7.5 (January 2010)

sdsl-0.7.0 (August 2009, Spire Version)

sdsl-0.6.tar.gz (Januar 2009)
sdsl-0.6.3.tar.gz (March 2009)
sdsl-0.6.4.tar.gz (July 2009)

Programming Language: ISO C++
Supported Platforms: Linux, Unix

This software is licenced under the GPL.