You will find here the source of the code used to run experiments for the article Uncommon suffix tries (a previous version is available on HAL), which provides an example of a suffix trie whose height increases faster than a power of $n$ and another one whose saturation level is negligible with respect to $\log n$. Both are built from VLMC (Variable Length Markov Chain) probabilistic sources; they are easily extended to families of sources having the same properties.

Authors of the article:
Peggy Cénac, Brigitte Chauvin, Frédéric Paccaut, Nicolas Pouyanne.
Author of the software:
Maxence Guesdon

See the Science code manifesto for reasons why providing the source code associated to an article is good.

Using the code

The code is hosted on Github.

To use the code, you must have the following software installed:

Get the source code:

  • using git: 
    git clone https://github.com/zoggy/vlmc-suffix-trie.git
  • or from an archive that you extract.

Go to the source code directory and type: 

make all laws

This will compile the source code and some predefined laws. Then, typing the following command will produce the figures inserted in the article: 

sh RSA-2012.sh
ls rsa_2012_heights.jpg rsa_2012_2_saturations.jpg