我们研究了在字母表 $\Sigma$ 大小为 $\sigma$ 的后继双特征字符串，这是 de Bruijn 字符串的一种最小分支类比，并探讨了可能的最少 Burrows-Wheeler 变换（BWT）运行次数。
在一个阶数为 $k$ 的 de Bruijn 字符串中，每个 $(k-1)$-gram 具有所有 $\sigma$ 个右扩展；而在这里，每个 $(k-1)$-gram 只有两个右扩展，由一个后继规则决定，同时也强制需要两个左扩展。
对于阶数 $3$，我们构造了一个显式的族 $B_\sigma^{(3)}$，对于每个 $\sigma \ge 2$，其循环 BWT 有 $r_c = \sigma^2 + 2$ 次运行。适当的终止线性化具有相同的运行计数 $r = r_c = \sigma^2 + 2$，而最小后缀集的大小为 $\chi = 2\sigma^2 + 1$。
比率 $\chi/r = 2 - 3/(\sigma^2 + 2)$ 几乎饱和了已知界限 $\chi/r \le 2$，我们之前已证明这一界限是渐近紧的。与我们之前的通用构造相比，这一改进将差距从 $O(1/\sigma)$ 提升至 $O(1/\sigma^2)$。
我们还展示了阶数为 $3$ 的模式在存在原始三项式 $x^3 - x + c$ 的情况下，作为规范线性反馈移位寄存器（LFSR）de Bruijn 序列的块状两行投影出现。
对于更高阶数，我们证明了一个一般下界 $r_c \ge \sigma^{k-1} + 2$，适用于每个 $\sigma \ge 3$，并分析了使用最后到第一（LF）置换的边界合并更高阶候选者：对于 $k = 4$ 和所有 $\sigma \ge 3$，它失败，而验证的 $k = 5$ 实例对于 $\sigma \in \{3,4\}$ 产生的 $\chi/r$ 比率超过 $1.96$。
博主点评： 本文对后继双特征字符串的深入研究揭示了 Burrows-Wheeler 变换的运行特性，尤其是在阶数为 3 的情况下，通过构造显式字符串族展现了其应用潜力。这一研究不仅拓展了理论边界，还在实现上提供了优化思路，值得进一步关注与探讨。