从集合中查找多个最大不同的二进制向量

Question

考虑长度为n的所有二进制向量的集合S,其中每个包含正好m个; 所以每个载体都有nm零. 我的目标是从S构造一个数量k的向量,使得这些向量尽可能彼此不同.

举一个简单的例子,取n = 4,m = 2和k = 2,那么可能的解是:[1,1,0,0]和[0,0,1,1].

这似乎是编码理论文献中的一个开放性问题(？).

有没有办法(即算法)找到一个次优但好的解决方案？
汉明距离是在这种情况下使用的正确性能指标吗？

一些想法:
在本文中,作者提出了几种算法来找到向量子集,使得成对汉明距离> =某个值 d.
我已经实现了如下随机方法:取一个 SS,它由 S中的任何向量初始化.然后,我考虑 S中的剩余向量.对于这些矢量中的每一个,我检查该矢量相对于 SS中的每个矢量是否至少具有距离 d.如果是,则将其添加到 SS. 通过取最大可能 d,如果 SS的大小> = k,那么我将 SS视为最优解,并且我从 SS中选择 k个向量的任何子集.使用这种方法,我认为导致 SS将取决于初始向量的识别 SS ; 即有多种解决方案(？). 但是如果 SS的大小< k,怎么办？ 从本文提出的算法中,我只理解了随机算法.我对二进制词典搜索(第2.3节)感兴趣,但我不知道如何实现它(？).

Answer 1

也许你觉得这篇论文很有用(我写的).它包含有效创建位串排列的算法.

例如,inc()算法:

long  inc(long h_in , long m0 , long m1) {
    long  h_out = h_in | (~m1); //pre -mask
    h_out ++;
    // increment
    h_out = (h_out & m1) | m0; //post -mask
    return  h_out;
}

它需要一个输入h_in并返回下一个更高的值,该值至少大于1 h_in并且"匹配"边界m0和m1."匹配"是指:所述结果具有1徘徊无论m0有1,结果具有0徘徊无论m1具有0.不一定是h_in关于mo和的有效价值m1!另外,请注意m0必须按位小于m1,这意味着m0不能1在一个位置m1有一个0.

这可以用于生成具有到给定输入字符串的最小编辑距离的排列:

让我们假设你有0110,你首先将它NEGATE 1001(编辑距离= k).设置'm0 = 1001'和'm1 = 1001'.使用它只会导致'1001'本身.

现在要获得具有编辑距离k-1的所有值,您可以执行以下操作,只需翻转其中一个m0或m1,然后inc()将返回所有位串的有序系列,其具有相差k或k-1.

我知道,不是很有趣,但你可以修改多达k位,inc()将始终与最大允许编辑差异返回所有排列方面m0和m1.

现在,让所有的排列组合,你会用所有可能的组合,重新运行算法m0和m1.

示例:要获得0110具有编辑距离的所有可能排列2,您必须使用以下排列运行inc()m0=0110和m1=0110(为了获得排列,必须扩展位位置,这意味着m0设置为0并m1设置为1:

• 位0和1 扩展:m0=0010和m1=1110
• 第0位和第2位扩展:m0=0100和m1=1110
• 第0位和第3位扩展:m0=0110和m1=1111
• 第1位和第2位扩展:m0=0000和m1=0110
• 第1和第3位扩展:m0=0010和m1=0111
• 第2位和第3位扩展:m0=0100和m1=0111

作为初始值h_0我建议简单使用m0.迭代可以在inc()返回后中止m1.

发明 内容上述算法在O(x)中生成所有x二进制向量,所述二进制向量至少y在位(可配置)上与给定向量不同v.

使用你的n= 的定义number of bits in a vector v,设置y=n正好生成1个向量,它与输入向量完全相反v.因为y=n-1,它将生成n+1向量:n除了一位之外的所有向量和在所有位中不同的1向量的向量.等等的不同价值观y.

**编辑:添加摘要并在上面的文本中用'NEGATE'替换错误的'XOR'.