SDSL - Succinct Data Structure Library

Note: The library has moved to github. The current version and documentation is now available at Opens external link in new windowhttps://github.com/simongog/sdsl-lite

 

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

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

    Creative Commons License
    This software is licenced under the GPL.