德布鲁因序列（De Bruijn Sequence）原理
德布鲁因序列是组合数学中的一种特殊循环序列，核心作用是用最短长度覆盖某一进制下所有长度为 $n$ 的子串，广泛应用于编码理论、密码学、三维重建（如结构光编码）、通信同步等领域。
一、 定义与数学表达
对于基（进制）k 和子串长度 n，德布鲁因序列记为 B(k,n)，满足以下核心性质：
- 序列由 k 种字符组成（如 k=2 时为 {0,1}，k=3 时为 {0,1,2}）。
- 序列的最小长度为 L = k^n（循环序列的线性展开长度为 k^n + n - 1）。
- 所有长度为 n 的 k 进制子串在序列中恰好出现一次（循环意义下）。
示例
- 当 k=2, n=2 时，德布鲁因序列 B(2,2) 为 {0011}（循环序列），线性展开为 00110，包含所有 2 位二进制子串 {00,01,11,10}。
- 当 k=2, n=3 时，B(2,3) 可表示为 00010111，循环后包含全部 8 种 3 位二进制子串 {000,001,010,011,100,101,110,111}。
二、 核心构造原理
德布鲁因序列的构造等价于求解有向德布鲁因图的欧拉回路，这是最经典且通用的构造方法，步骤如下：
1. 构建德布鲁因图 G(k,n)
-
顶点：每个顶点对应一个长度为 n-1 的 k 进制字符串。
例如 k=2,n=3 时，顶点集合为 {00,01,10,11}（共 k^{n-1}=4 个顶点）。 -
边：每个边对应一个长度为 n 的 k 进制字符串。
例如 k=2,n=3 时，顶点 00 可指向 00（边标签 000）和 01（边标签 001）。
2. 寻找欧拉回路
德布鲁因图的关键性质：每个顶点的入度等于出度（均为 $k$），因此图中必存在一条欧拉回路（经过每条边恰好一次的回路）。
3. 生成德布鲁因序列
将欧拉回路中所有边的第一个字符按顺序拼接，即可得到德布鲁因序列 $B(k,n)$。
示例（$k=2,n=3$）
- 欧拉回路：$00\rightarrow00\rightarrow01\rightarrow10\rightarrow01\rightarrow11\rightarrow11\rightarrow10$
- 边标签依次为：$000,001,010,101,011,111,110,100$
- 取每条边的第一个字符：$0,0,0,1,0,1,1,1$ → 序列 $00010111$，即 $B(2,3)$。
三、 关键性质
- 最短性：覆盖所有 $k^n$ 个长度为 $n$ 的子串，所需的最短序列长度为 $k^n$（循环序列），这是其他序列无法超越的极限。
- 循环性：线性展开的德布鲁因序列长度为 $k^n + n - 1$，循环移位后仍为德布鲁因序列。
- 唯一性：对于给定的 $k$ 和 $n$，德布鲁因序列的数量为 $\frac{(k!){k{n-1}}}{k^n}$（由组合数学推导）。例如 $k=2,n=3$ 时，共有 2 种不同的 $B(2,3)$ 序列。
四、 三维重建中的应用（结构光编码）
五、 与格雷码的区别
| 特性 | 德布鲁因序列 | 格雷码 |
|---|---|---|
| 核心目标 | 覆盖所有长度为 $n$ 的子串 | 相邻编码仅有 1 位差异 |
| 序列长度 | $k^n$（循环） | $k^n$（线性） |
| 应用场景 | 结构光高精度编码、通信同步 | 位置检测、增量式编码 |