论文标题
优先组和偏好的de bruijn序列的有效结构
Efficient constructions of the Prefer-same and Prefer-opposite de Bruijn sequences
论文作者
论文摘要
Eldert等人[AIEE Transactions 77（1958）]首先提出了贪婪的偏爱de bruijn序列结构。作为一种贪婪的算法，它具有一个主要的缺点：它需要一个指数量的空间来存储长度$ 2^n $ de bruijn序列。尽管在过去60年中，对De Bruijn序列进行了大量研究，但为Prefer-Same de Bruijn序列找到有效的结构仍然是一个诱人的开放问题。在本文中，我们通过提出有效的算法来使用$ o（n）$ $ o（n）$ o（n）$ o（n）$ space构建它，以揭示优选de bruijn序列的基础结构，并解决开放问题。遵循类似的方法，我们还提出了一种有效的算法来构建优选的bruijn序列。
The greedy Prefer-same de Bruijn sequence construction was first presented by Eldert et al.[AIEE Transactions 77 (1958)]. As a greedy algorithm, it has one major downside: it requires an exponential amount of space to store the length $2^n$ de Bruijn sequence. Though de Bruijn sequences have been heavily studied over the last 60 years, finding an efficient construction for the Prefer-same de Bruijn sequence has remained a tantalizing open problem. In this paper, we unveil the underlying structure of the Prefer-same de Bruijn sequence and solve the open problem by presenting an efficient algorithm to construct it using $O(n)$ time per bit and only $O(n)$ space. Following a similar approach, we also present an efficient algorithm to construct the Prefer-opposite de Bruijn sequence.
