De Bruijn Sequence and Universal Cycle Constructions
| Decoding the Granddaddy | Output | ||||||||||
|
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 $\mathcal{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 $\mathcal{D}$ starting at index $r$ (the rank of $\alpha$).
Example
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] (coming soon).
Consider the Granddaddy DB sequence for $n=6$ and $k=2$.
0000001000011000101000111001001011001101001111010101110110111111
The string $\alpha = 010101$ has rank 47.
References
- [KRR16] T. Kociumaka, J. Radoszewski, and W. Rytter. Efficient ranking of Lyndon words and decoding lexicographically minimal de Bruijn sequence. SIAM J. Discrete Math, 30(4):2027-2046, 2016.
- [MEP96] C. Mitchell, T. Etzion, and K. Paterson. A method for constructing decodable de Bruijn sequences. IEEE Transactions on Information Theory, 42(5):1472-1478, 1996.
- [SW17] J. Sawada and A. Williams. Practical algorithms to rank necklaces, Lyndon words, and de Bruijn sequences. Journal of Discrete Algorithms, 43:95-110, 2017.
- [Tul01] J. Tuliani. De Bruijn sequences with efficient decoding algorithms. Discrete Mathematics, 226(1):313-336, 2001.