java - 生成没有给定大小的重复子数组的长字节数组

Question

我想生成一个长字节数组，其中没有重复的大小为 N 的子序列。 N 很小，通常在 3 到 8 之间。

显然生成一个任意长的数组是不可行的:在大约 2^(8*N) 字节后，将有 2^(8*N) 子序列present 所以不会有任何唯一的留下来使用(因为有 2^(8*N) 个大小为 N 的唯一字节序列)。现在这是此类数组长度的上限，但不一定是下限)。我不需要可能的最长序列或类似的东西:例如，N == 4 的 1,000,000 个值可能就足够了，但至少应该可以检测到序列何时太长在某种生成策略下的唯一性。

理想情况下，生成策略很简单，就像在添加每个字节时检查每个先前的子序列一样。

我将 Java 放在具体位置，因为这是我目前正在使用它的地方，但这个概念确实适用于任何语言。

Answer 1

用户的关键观察harold in the comments , 是你可以创建一个最大序列而不用 de Bruijn sequence 重复元素N 的顺序。

这样的序列(它们不是唯一的)恰好包含所有可能的 N 元素子序列一次，因此将是一个没有 N 元素重复子序列的最大序列。

剩下的问题是，是否可以相当简单地生成此类序列的前缀，答案是肯定的。

按照本 blog post 中描述的方法进行操作可以生成所有 Lyndon Words大小为 N 或更小的数组，按字典顺序排列，并连接所有长度除以 N 的数组以创建我们想要的数组。

在 Java 中，字母表只是 256 字节的值，上述链接中的代码适用于处理固定长度的 byte[]，如下所示:

/**
 * Use an order-n de-Bruijn sequence to fill a byte array such that no n-length sub-array is repeated.
 */
public static void trucatedDeBruijnBytes(int n, byte[] arr) {
    int written = generateLyndonBytes(1, 1, 256, new byte[n + 1], arr, 0);
    if (written != arr.length) {
        throw new RuntimeException("Can't generate a unique sequence of length " + arr.length + ", max is " + written);
    }
}

private static int generateLyndonBytes(int t, int p, int k, byte[] a, byte[] output, int oidx) {
    if (t == a.length) {
        if((a.length-1)%p==0) {
            int len = Math.min(p, output.length - oidx);
            System.arraycopy(a, 1, output, oidx, len);
            oidx += len;
        }
    } else {
        a[t] = a[t-p]; 
        assert a[t] < k;
        if ((oidx = generateLyndonBytes(t+1,p, k, a, output, oidx)) == output.length) {
            return oidx;
        }
        for(int j = (a[t-p] & 0xFF) + 1; j < k; j++) {
            assert(j >= 0 && j < k);
            a[t] = (byte)j;
            assert a[t] < k;
            if ((oidx = generateLyndonBytes(t+1,t, k, a, output, oidx)) == output.length) {
                return oidx;
            }
        }
    }
    return oidx;
}

这可能可以进一步优化，但它已经相对有效:它只使用少量固定状态(byte[] a 数组，其大小为 N + 1 ) 加上有限数量的递归(通常最多 N + 1 调用深度)和一些数学来“就地”生成所有值。比保留所有已见 N 序列的哈希值以执行重复数据删除的解决方案要好得多!

出于好奇，下面是 N == 2 序列的第一位:

[0, 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0, 9, 0, 10, 0, 11, 0, 12, 0, 13, 0, 14, 0, ..., 125, 0, 126, 0, 127, 0, -128, 0, -127, ..., 0, -3, 0, -2, 0, -1, 1, 1, 2, 1, 3, 1, 4, 1, 5, ...]

所以 0 后跟一个简单的递增序列 0, i, 0, i + 1, ... 512 字节然后是序列 1, i , 1, i + 1, ... 等等。