Decoding (ranking/unranking) the Granddaddy DB sequence
Given a DB sequence $\mathcal{D}$ of order $n$, the rank of a string $\alpha$ (of length $n$) is the starting index where $\alpha$ appears in $D$. If $\alpha$ is a prefix of $\mathcal{D}$ then it has rank 1. If $\alpha$ starts at the last symbol of $\mathcal{D}$ and wraps around then it has rank $k^n$.
Unranking is the process of determining the string $\alpha$ in $D$ starting at index $r$ (the rank of $\alpha$).
Example Consider the Granddaddy DB sequence for $n=6$ and $k=2$.
0000001000011000101000111001001011001101001111010101110110111111
The string $\alpha = 010101$ has rank 47.
The only DB sequence construction presented in this project that has an efficient (polynomial-time) decoding algorithm is the Granddaddy [KRR16,SW17]. The ranking
requires $O(n^2)$-time and the unranking requires $O(n^3 \log k)$-time (unit-cost RAM model) in the provided implementation based on [SW17]. The algorithms are based on efficient ranking algorithms for necklaces and Lyndon words. The only other known efficient decoding algorithms are for inter-leaved or inductive constructions [MEP96,Tul01]. Further background on other (inefficient) decoding methods is given in [MEP96].