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.7.5 (January 2010)

Installation:

Download sdsl-0.7.5
Download libdivsufsort
tar -xzf sdsl-0.7.5.tar.gz
bunzip libdivsufsort-1.2.3.tar.bz
tar -xf libdivsufsort-1.2.3
mv libdivsufsort-1.2.3 sdsl-0.7.5/src/
cd sdsl-0.7.5/src/libdivsufsort-1.2.3/
./configure && make
cd ../..
./configure && make
set the LD_LIBRARY_PATH to the src/sdsl/libdivsufsort-1.2.3/lib/.libs directory

Example programs are located in the example directory.

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.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.