Content on this page requires a newer version of Adobe Flash Player.

Get Adobe Flash player

 
  Difusión
block
 
ball
   
ball
   
ball
   
ball
   
  Software

General Trees

The link below contains different implementations for representing general trees with succinct data structures [Arroyuelo, Cánovas, Navarro and Sadakane 2010], achieving 2n + o(n) bits of space and obtaining constant time for a fairly complete set of operations.

Download here

Suffix Trees

The Suffix tree is an extremely important data structure for stringology, with a wealth of applications in bioinformatics. In the next link is a recent implementation of a Compressed Suffix Tree structure [Cánovas and Navarro 2010], offering both practical times and affordable space.

Download here

Re-Pair Compression and Decompression

This is an efficient, fully linear-time, and easy-to-use implementation of the compressor RePair [Larson and Moffat 2000]. It includes the original and a heuristically balanced variant. It outputs the dictionary as a sequence of pairs, so one can input them to a more efficient dictionary compressor.

Download here

Libcds: Library of Compact Data Structures (external link)

This is a large project comprising implementations of various compact data structures for manipulating bitmaps, sequences, trees, suffix trees, etc. It contains code contributed by my (ex)students Diego Arroyuelo, Rodrigo Cánovas, Francisco Claude, Rodrigo González, and more to come.

This project is hosted at the ReCoded site (http://libcds.recoded.cl).

Pizza&Chili Site: Compressed Full-Text Indexing Corpus and Testbed (external link)

The Pizza&Chili Site contains free compressed full-text index implementations and testing test collections. It is a joint effort with Paolo Ferragina, University of Pisa, and our students Rodrigo González and Rossano Venturini, plus several others that contributed later.

It is hosted at a Chilean (http://pizzachili.dcc.uchile.cl) and an Italian (http://pizzachili.di.unipi.it) mirror.

  Highlights
 

Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile.
Calle Beauchef 850, Santiago, Chile
Telefono:(56-02) 9784713 | contacto@icdb.cl