EuroPython 2018

Succinct data structures for python

Speaker(s) Konstantin Ignatov

This is a presentation of and call for participation in development and testing of Python bindings to Succinct Data Structure Library.

From Wikipedia: Succinct data structures can represent an object (such as a bitvector or a tree) in space close to the information-theoretic lower bound of the object while supporting operations of the original object efficiently. The theoretical time complexity of an operation performed on the classical data structure and the equivalent succinct data structure are (most of the time) identical.

Currently bindings are provided for:

  • Mutable bit-compressed vectors
  • Immutable compressed integer vectors
  • Immutable compressed bit (boolean) vectors
  • Rank and select operations on bitvectors
  • Wavelet trees
  • Comressed suffix arrays

Original library: Most of examples from SDSL cheat sheet and SDSL tutorial are implemented.

in on Thursday 26 July at 16:05 See schedule


  1. Gravatar
    Could also work as a poster.
    — Stefan Behnel,

New comment