logo标签列表

从一个集合中找到若干个最大不同二进制向量的方法

algorithmdata-structurescombinatoricsbinary-datahamming-distance
15
考虑一个集合S，其中包含所有长度为n的二进制向量，并且每个向量中恰好包含m个1；因此每个向量中有n-m个0。
我的目标是从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节）很感兴趣，但我不知道如何实现它（？）。

这个标题有误导性，当我读到它时，我以为m=n/2。 - Walter Tross
1
@WalterTross 我同意。我已经编辑了标题。 - din
谢谢@din。现在，这是一个真正的问题吗？如果是，n、m和k的数量级是多少？ - Walter Tross
1
假设：n<25，1<m<10，10<k<100（或10<k<50）。 - din
1
你能定义一下你正在测量的两个向量之间的差异吗？例如，给定向量1001、0101、0110和1010，当与1100进行比较时，它们是否都相距相同的“距离”，因为它们在两个位上都不同？ - Joseph Wood
@JosephWood 是的，它们都距离1100相同。 - din
3个回答
5
也许你会发现这篇论文有用（我是作者）。它包含了高效创建位串排列的算法。
例如，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并返回下一个大于h_in且与边界m0和m1相匹配的更高值。 "匹配"意味着：结果在m0有1的地方也有1，在m1有0的地方有0。请注意，h_in必须是关于mo和m1有效值！此外，请注意，m0必须按位小于m1，这意味着m0不能在m1具有0的位置上具有1。
这可以用于生成与给定输入字符串最小编辑距离的排列：
假设您有0110，您首先将其否定为1001（编辑距离= k）。设置“m0 = 1001”和“m1 = 1001”。使用这将仅导致“1001”本身。
现在，要获得编辑距离k-1的所有值，只需翻转m0或m1中的一个位，然后inc（）将返回一系列有序的所有具有差异k或k-1的位串。
我知道，还不是很有趣，但是您可以修改k个位，并且inc（）将始终返回所有允许的最大编辑差异的排列，与m0和m1有关。
现在，要获取所有排列，您必须使用所有可能的m0和m1组合重新运行算法。
例如：要获取具有编辑距离2的0110的所有可能排列，您必须使用以下排列的m0 = 0110和m1 = 0110运行inc（）（要获取排列，位位置必须“扩展”，这意味着将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

我建议将m0作为h_0的起始值。一旦inc()返回m1，迭代就可以终止。

摘要 以上算法以O(x)的时间复杂度生成所有与给定向量v至少有y个不同位（可配置）的二进制向量x。

使用你定义的n=v向量中的位数，设置y=n将生成一个完全相反的输入向量v。对于y=n-1，它将生成n+1个向量：在所有但一个位上都不同的n个向量和在所有位上都不同的1个向量。以此类推，对于不同的y值。

**编辑：在上面的文本中添加了摘要，并用“否定”替换了错误的“异或”。

抱歉，但我不确定我是否完全理解了你回答中的所有想法。你能否用简单的话来描述一下你的算法能够找到什么？我的意思是，它能找到一组例如 k 个向量，它们彼此之间差异最大吗？ - din
我添加了一个摘要并修正了一个单词。回答你的问题，不，它不能找到一组例如k个向量，这些向量彼此之间最大程度地不同。相反，它会找到所有与单个给定向量（但彼此之间不同）具有（可配置的）最小汉明距离的向量。如果我误解了你的请求，很抱歉...？ - TilmannZ
实际上，如问题所述，我正在寻找一种方法来找到一组最大差异（即距离）的k个向量子集。您的算法是一种低计算复杂度的方法，可以找到所有与给定向量至少有一定距离d的向量；这是一个有趣的方法，谢谢。除了您的算法外，人们还可以使用穷举搜索来找到这些向量。然而，问题在于如何找到彼此最大不同的k个向量。也许我在这里漏掉了什么... - din
4
我不确定最大化汉明距离之和是否是获取“最大不同”二进制向量集的最佳标准，但我强烈怀疑它是。此外，我强烈怀疑我将要介绍的算法确切地产生了一组k个向量，这些向量最大化了具有m个1和n-m个0的n位向量的汉明距离之和。不幸的是，我没有时间证明它（当然，我可能是错的-如果是这样，您将得到一个“次优但好”的解决方案，根据您的要求）。
警告：在接下来的内容中，我假设结果集不能包含相同的向量。
我提出的算法如下：
从只有一个向量的结果集开始，重复添加剩余向量中与已经在结果集中的所有向量的汉明距离之和最大的一个向量。当结果集包含k个向量或所有可用向量都已添加时停止。
请注意，结果集的汉明距离之和不取决于第一个或任何后续向量的选择。
我发现“暴力”方法是可行的，考虑到您在评论中提到的限制：
n<25，1
“暴力”方法在数组中以“字典顺序”预先计算所有向量，并保持相同大小的数组最新，该数组包含每个具有相同索引的向量到已在结果集中的所有向量的总汉明距离。在每次迭代中，更新总汉明距离，并选择具有当前结果集的最大总汉明距离的所有向量中的第一个（按“字典顺序”）。将所选向量添加到结果集中，并移动数组以填充其位置，从而有效地减小它们的大小。
以下是我在Java中提出的解决方案。如果需要，它旨在易于转换为任何过程性语言。计算n个项目中的m个组合的部分可以由库调用替换。以下Java方法具有相应的C / C ++宏，使用现代CPU上的快速专用处理器指令： Long.numberOfTrailingZeros→__builtin_ctzl，Long.bitCount→__builtin_popcountl。
package waltertross.bits;

public class BitsMain {

    private static final String USAGE =
        "USAGE: java -jar <thisJar> n m k (1<n<64, 0<m<n, 0<k)";

    public static void main (String[] args) {

        if (args.length != 3) {
            throw new IllegalArgumentException(USAGE);
        }
        int n = parseIntArg(args[0]); // number of bits
        int m = parseIntArg(args[1]); // number of ones
        int k = parseIntArg(args[2]); // max size of result set
        if (n < 2 || n > 63 || m < 1 || m >= n || k < 1) {
            throw new IllegalArgumentException(USAGE);
        }
        // calculate the total number of available bit vectors
        int c = combinations(n, m);
        // truncate k to the above number
        if (k > c) {
            k = c;
        }
        long[] result   = new long[k]; // the result set (actually an array)
        long[] vectors  = new long[c - 1]; // all remaining candidate vectors
        long[] hammingD = new long[c - 1]; // their total Hamming distance to the result set
        long firstVector = (1L << m) - 1; // m ones in the least significant bits
        long lastVector  = firstVector << (n - m); // m ones in the most significant bits
        result[0] = firstVector; // initialize the result set
        // generate the remaining candidate vectors in "lexicographical" order
        int size = 0;
        for (long v = firstVector; v != lastVector; ) {
            // See http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
            long t = v | (v - 1); // t gets v's least significant 0 bits set to 1
            // Next set to 1 the most significant bit to change,
            // set to 0 the least significant ones, and add the necessary 1 bits.
            v = (t + 1) | (((~t & -~t) - 1) >>> (Long.numberOfTrailingZeros(v) + 1));
            vectors[size++] = v;
        }
        assert(size == c - 1);
        // chosenVector is always the last vector added to the result set
        long chosenVector = firstVector;
        // do until the result set is filled with k vectors
        for (int r = 1; r < k; r++) {
            // find the index of the new chosen vector starting from the first
            int chosen = 0;
            // add the distance to the old chosenVector to the total distance of the first
            hammingD[0] += Long.bitCount(vectors[0] ^ chosenVector);
            // initialize the maximum total Hamming distance to that of the first
            long maxHammingD = hammingD[0];
            // for all the remaining vectors
            for (int i = 1; i < size; i++) {
                // add the distance to the old chosenVector to their total distance
                hammingD[i] += Long.bitCount(vectors[i] ^ chosenVector);
                // whenever the calculated distance is greater than the max,
                // update the max and the index of the new chosen vector
                if (maxHammingD < hammingD[i]) {
                    maxHammingD = hammingD[i];
                    chosen = i;
                }
            }
            // set the new chosenVector to the one with the maximum total distance
            chosenVector = vectors[chosen];
            // add the chosenVector to the result set
            result[r] = chosenVector;
            // fill in the hole left by the chosenVector by moving all vectors
            // that follow it down by 1 (keeping vectors and total distances in sync)
            System.arraycopy(vectors,  chosen + 1, vectors,  chosen, size - chosen - 1);
            System.arraycopy(hammingD, chosen + 1, hammingD, chosen, size - chosen - 1);
            size--;
        }
        // dump the result set
        for (int r = 0; r < k; r++) {
            dumpBits(result[r], n);
        }
    }

    private static int parseIntArg(String arg) {
        try {
            return Integer.parseInt(arg);
        } catch (NumberFormatException ex) {
            throw new IllegalArgumentException(USAGE);
        }
    }

    private static int combinations(int n, int m) {
        // calculate n over m = n! / (m! (n - m)!)
        // without using arbitrary precision numbers
        if (n <= 0 || m <= 0 || m > n) {
            throw new IllegalArgumentException();
        }
        // possibly avoid unnecessary calculations by swapping m and n - m
        if (m * 2 < n) {
            m = n - m;
        }
        if (n == m) {
            return 1;
        }
        // primeFactors[p] contains the power of the prime number p
        // in the prime factorization of the result
        int[] primeFactors = new int[n + 1];
        // collect prime factors of each term of n! / m! with a power of 1
        for (int term = n; term > m; term--) {
            collectPrimeFactors(term, primeFactors, 1);
        }
        // collect prime factors of each term of (n - m)! with a power of -1
        for (int term = n - m; term > 1; term--) {
            collectPrimeFactors(term, primeFactors, -1);
        }
        // multiply the collected prime factors, checking for overflow
        int combinations = 1;
        for (int f = 2; f <= n; f += (f == 2) ? 1 : 2) {
            // multiply as many times as requested by the stored power
            for (int i = primeFactors[f]; i > 0; i--) {
                int before = combinations;
                combinations *= f;
                // check for overflow
                if (combinations / f != before) {
                    String msg = "combinations("+n+", "+m+") > "+Integer.MAX_VALUE;
                    throw new IllegalArgumentException(msg);
                }
            }
        }
        return combinations;
    }

    private static void collectPrimeFactors(int n, int[] primeFactors, int power) {
        // for each candidate prime that fits in the remaining n
        // (note that non-primes will have been preceded by their component primes)
        for (int i = 2; i <= n; i += (i == 2) ? 1 : 2) {
            while (n % i == 0) {
                primeFactors[i] += power;
                n /= i;
            }
        }
    }

    private static void dumpBits(Long bits, int nBits) {
        String binary = Long.toBinaryString(bits);
        System.out.println(String.format("%"+nBits+"s", binary).replace(' ', '0'));
    }
}

算法在n=5，m=2，k=4的数据如下：
result
00011   00101 00110 01001 01010 01100 10001 10010 10100 11000 vectors
          0→2   0→2   0→2   0→2   0→4   0→2   0→2   0→4   0→4 hammingD
                                    ^                         chosen
00011   00101 00110 01001 01010 10001 10010 10100 11000
01100     2→4   2→4   2→4   2→4   2→6   2→6   4→6   4→6
                                    ^
00011   00101 00110 01001 01010 10010 10100 11000
01100     4→6   4→8   4→6   4→8   6→8   6→8   6→8
10001             ^

00011   00101 01001 01010 10010 10100 11000
01100       6     6     8     8     8     8
10001
00110

样例输出（n=24，m=9，k=20）：
[wtross ~/Dropbox/bits]$ time java -jar bits-1.0-SNAPSHOT.jar 24 9 20
000000000000000111111111
000000111111111000000000
111111000000000000000111
000000000000111111111000
000111111111000000000000
111000000000000000111111
000000000111111111000000
111111111000000000000000
000000000000001011111111
000000111111110100000000
111111000000000000001011
000000000000111111110100
001011111111000000000000
110100000000000000111111
000000001011111111000000
111111110100000000000000
000000000000001101111111
000000111111110010000000
111111000000000000001101
000000000000111111110010

real    0m0.269s
user    0m0.244s
sys     0m0.046s

在您的限制条件下（n=24，m=9，k=99），最困难的情况需要在我的Mac上花费约550毫秒。
通过一些优化，例如通过移动较短的数组块来使算法更快。值得注意的是，在Java中，我发现向“上”移动比向“下”移动要慢得多。
请问您能否解释一下如何初始化“结果集”？我猜想使用您的解决方案，结果集取决于您用来初始化集合的向量（？）。由于我不熟悉Java，如果您能为代码的每个部分添加描述，或者提供伪代码算法，我将不胜感激。 - din
结果集以“字典顺序”中的第一个向量初始化。其他向量是通过从已经在结果集中的向量中选择具有最大总汉明距离的第一个（按“字典顺序”）来添加的。我提供的示例输出有助于可视化。输出序列是固定的，并在第k个向量处截断。我编写的代码在其主要部分中非常类似于C代码（顺便说一句，我从我提供的bithacks URL中直接粘贴了代码行）。无论如何，我会尽快改进答案。 - Walter Tross
@din 我尝试澄清算法，并在代码中添加了许多注释。计算C(n, m) = n! / (m! (n-m)!)的部分，如果有一个可以完成相同工作的库函数，则可能完全是多余的，因此我认为它本身很有趣，但对于您的问题并不重要。如果您需要进一步澄清，请告诉我。 - Walter Tross
如果我理解正确的话，您正在按字典顺序排序向量，并选择第一个向量（按此顺序），该向量最大化与结果集中向量的汉明距离之和。这个排序很重要吗？如果我使用随机排序并选择产生与结果集的汉明距离最大的向量（如果有多个向量，则随机选择一个），会怎样呢？ - din
不，顺序完全不重要。您可以使用随机顺序并随机选择一个向量，只要它与结果集具有最大的汉明距离即可。字典序的优点是易于生成，并且在调试时易于遵循。 - Walter Tross
显示剩余2条评论
3

更新的答案

从Walter Tross代码的示例输出中可以看出，生成随机解决方案可以简化为以下步骤：

首先选定任意向量作为起始点，例如n=8、m=3、k=5：

A:   01001100

每一步之后，将向量求和以得到每个位置被使用的次数：

SUM: 01001100

然后，对于下一个向量，将数字放置在已使用最少的位置（在本例中为零次），例如：

B:   00110001

需要获取：

A:   01001100  
B:   00110001
SUM: 01111101

接下来，还剩下两个最少使用的位置，所以对于下一个向量中的三个数字，使用这两个位置，然后将第三个数字放在任何位置：

C:   10010010

获得:

A:   01001100  
B:   00110001
C:   10010010
SUM: 11121111  (or reset to 00010000 at this point)

接下来，对于下一个向量，您有7个最少使用的位置（在求和中的那些位置），因此选择任意3个，例如：

D:   10100010

想要获得：

A:   01001100  
B:   00110001
C:   10010010
D:   10100010
SUM: 21221121

最后一个向量，请选择其中 4 个最少使用的位置之一，例如：

E:   01000101

生成所有解决方案，只需在每个步骤中生成每个可能的向量：
A:   11100000, 11010000, 11001000, ... 00000111

接着，例如当 A 和 SUM 为 11100000 时：

B:   00011100, 00011010, 00011001, ... 00000111

例如，当B为00011100，SUM为11111100时：

C:   10000011, 01000011, 00100011, 00010011, 00001011, 00000111

例如，当C为10000011且SUM为21111111时：

D:   01110000, 01101000, 01100100, ... 00000111

最后，例如当D为01110000且SUM为22221111时：

E:   00001110, 00001101, 00001011, 00000111

这将导致C(8,3)×C(5,3)×C(8,1)×C(7,3)×C(4,3)=56×10×8×35×4=627,200种n=8，m=3，k=5的解决方案。
实际上，您需要添加一个避免重复向量的方法，并避免让自己陷入困境。因此，我认为这不会比沃尔特的答案更简单。
初始答案 - 存在主要问题
（我将假设m不大于n / 2，即1的数量不大于0的数量。否则，请使用对称方法。）
当k×m不大于n时，显然存在最优解，例如：
n=10, m=3, k=3:  
A: 1110000000  
B: 0001110000  
C: 0000001110

当汉明距离都为2×m时：

|AB|=6, |AC|=6, |BC|=6, total=18

当k×m大于n时，连续向量之间海明距离差最小的解决方案提供了最大的总距离。
n=8, m=3, k=4:
A: 11100000
B: 00111000
C: 00001110
D: 10000011
|AB|=4, |AC|=6, |AD|=4, |BC|=4, |BD|=6, |CD|=4, total=28  


n=8, m=3, k=4:
A: 11100000
B: 00011100
C: 00001110
D: 00000111
|AB|=6, |AC|=6, |AD|=6, |BC|=2, |BD|=4, |CD|=2, total=26

因此，实际上，你需要取m×k并查看它比n大多少，我们称之为x = m×k−n，这个x就是重叠的次数，即一个向量与前一个向量在同一位置上有1的次数。然后，您将重叠均匀分布在不同的向量上，以最大化总距离。
在上面的示例中，x = 3×4−8 = 4，我们有4个向量，因此我们可以均匀地分布重叠，并且每个向量在与前一个向量相同的位置上都有1。
为了生成所有唯一的解决方案，您可以：
- 计算x = m×k−n，并生成x分成k部分的所有分区，其中最小可能的最大值：
n=8, m=3, k=5  ->  x=7  
22111, 21211, 21121, 21112, 12211, 12121, 12112, 11221, 11212, 11122  
(discard partitions with value 3)
  • 生成所有要用作向量A的向量，例如：
A: 11100000, 11010000, 11001000, 11000100, ... 00000111
  • 对于每一个向量A，生成所有比向量A小的字典序向量B，并且与向量A有相同数量的重叠1（在本例中为1和2），例如：
A: 10100100
overlap=1:  
B: 10011000, 10010010, 10010001, 10001010, 10001001, 10000011, 01110000, ... 00000111
overlap=2:  
B: 10100010, 10100001, 10010100, 10001100, 10000110, 10000101, 01100100, ... 00100101
  • 对于每一个，生成所有的向量C，以此类推，直到你有k个向量的集合。当生成最后一个向量时，你必须考虑与前一个和下一个（即第一个）向量的重叠。

我认为将x分成k个部分视为二叉树处理是最好的：

                   1                                      2
      11                      12                    21         22
111        112           121       122        211       212    221
1112   1121   1122   1211   1212   1221   2111   2112   2121   2211
11122  11212  11221  12112  12121  12211  21112  21121  21211  22111

当创建解决方案时，遍历此树，以便每个向量只需要生成一次。

我认为这种方法仅适用于某些n、m和k的值；我不确定它是否可以适用于一般情况。

我认为这个方法得到的结果与Walter的方法相同，但他的方法看起来更容易编写。但是看他的输出示例，我认为你可以简单地将所有向量相加，然后将1放在最少使用的位置以生成解决方案中的下一个向量。 - m69 ''snarky and unwelcoming''
据我所知，这不是一个问题，例如当n=4，m=2，k=3时，[1100，0110，0011]和[1100，0011，1100]的汉明距离总和都为8。 - m69 ''snarky and unwelcoming''
@m69，我对你关于最小距离的说法很感兴趣。然而，在你的例子中，你考虑了1100和0011，然后你拿1100来说最小汉明距离是0。但是，在这种情况下，你考虑了两次相同的向量（1100），这是不正确的。我的意思是，一旦你在集合中有一个向量（例如1100），你就不能再考虑它了。我没有找到一个例子来证明你的说法成立，即对于两个向量，它们与集合的总汉明距离最大且相同，它们的最小汉明距离不相同。 - din
@din 啊，我忽略了一个事实，即结果不能包含相同的向量。无论如何，我很晚才看到你的问题，并且仍在消化问题的所有细节。我可能会在接下来的几天进一步更新我的答案。您是对生成所有解决方案感兴趣，还是只对随机生成一个解决方案感兴趣？均匀分布是否重要？ - m69 ''snarky and unwelcoming''
只要没有比这更好的解决方案，一个解决方案就足够了；也许这就是你所说的“均匀分布重要”吧（？）。 - din
在这种情况下，沃尔特的解决方案可能是最好的。我越看我的初始答案，我越觉得它只适用于某些n、m和k的值。 - m69 ''snarky and unwelcoming''
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接