论文标题
剪切的de bruijn序列
Cut-Down de Bruijn Sequences
论文作者
论文摘要
切割的de bruijn序列是一个长度$ l $的环状串，其中$ 1 \ leq l \ leq k^n $，使得长度$ n $的每个子字符串最多出现一次。 etzion [理论。 comp。 SCI 44（1986）]给出了一种算法，用于构建二进制切割de bruijn序列，该序列需要$ o（n）$ siply $ n $ bit操作，每个符号生成的符号。在本文中，我们简化了算法并将运行时间提高到使用$ \ Mathcal {O}（O}（n）$ Space生成的$ \ Mathcal {O}（n）$时间。然后，我们通过利用固定密度Lyndon单词的最新排名算法来提供第一种构建二进制切割de bruijn序列的连续规则方法。最后，我们开发了一种算法来生成$ k> 2 $的剪切de bruijn序列，该序列在$ \ mathcal {o}（n）$ time以每符号使用$ \ MATHCAL {O}（o}（n）$空间进行了一些初始化后。虽然我们的$ K $ - ARY算法基于我们简化的Etzion二进制算法的版本，但需要许多非平凡的改编才能推广到较大的字母。
A cut-down de Bruijn sequence is a cyclic string of length $L$, where $1 \leq L \leq k^n$, such that every substring of length $n$ appears at most once. Etzion [Theor. Comp. Sci 44 (1986)] gives an algorithm to construct binary cut-down de Bruijn sequences that requires $o(n)$ simple $n$-bit operations per symbol generated. In this paper, we simplify the algorithm and improve the running time to $\mathcal{O}(n)$ time per symbol generated using $\mathcal{O}(n)$ space. We then provide the first successor-rule approach for constructing a binary cut-down de Bruijn sequence by leveraging recent ranking algorithms for fixed-density Lyndon words. Finally, we develop an algorithm to generate cut-down de Bruijn sequences for $k>2$ that runs in $\mathcal{O}(n)$ time per symbol using $\mathcal{O}(n)$ space after some initialization. While our $k$-ary algorithm is based on our simplified version of Etzion's binary algorithm, a number of non-trivial adaptations are required to generalize to larger alphabets.
