Welcome to the Sux Project and Sux4J!

Introduction

Sux is an umbrella nickname for the results of my fiddling with the implementation of basic succinct data structures in C++, Java, and Rust.

This repository contains the Java code and references to some papers. Please have a look at the other repositories for the main highlights in each language.

This is free software. The Rust and Java code is distributed under either the GNU Lesser General Public License 2.1+ or the Apache Software License 2.0. The C++ code is distributed under the GNU General Public License 3.0+ with a Runtime Library Exception (as the C standard library).

Building

You need Ant and Ivy. Then, run ant ivy-setupjars jar.

Papers

• A paper on the broadword techniques used in the rank/select code, and in particular about the broadword implementation of select queries implemented in <A HREF="https://dsiutils.di.unimi.it/docs/it/unimi/dsi/bits/Fast.html#select(long,int)"><code>Fast.select()</code></A>.

• A paper on the theory of monotone minimal perfect hashing.

• An experimental paper on monotone minimal perfect hashing.

• A paper on the current implementation of static and minimal perfect hash functions.

• A paper on the current implementation of compressed static functions.

• A paper on the C++ implementation dynamic ranking and selection using compact Fenwick trees.

• A paper on the C++ implementation of RecSplit.

• A paper on the Rust implementation of functions and filters based on ε-cost sharding.