4

我正在尝试计算 n 个节点图中每个节点之间的汉明距离。此图中的每个节点都有一个相同长度 (k) 的标签，用于标签的字母表是 {0, 1, *}。'*' 用作无关符号。例如，标签 101*01 和 1001*1 之间的汉明距离等于 1（我们说它们仅在第 3 个索引处不同）。

我需要做的是找到每个节点的所有 1 汉明距离邻居，并准确报告这两个标签在哪个索引处不同。

我正在逐个字符地将每个节点标签与所有其他节点标签进行比较，如下所示：

    // Given two strings s1, s2
    // returns the index of the change if hd(s1,s2)=1, -1 otherwise.

    int count = 0;
    char c1, c2;
    int index = -1;

    for (int i = 0; i < k; i++)
    {
        // do not compute anything for *
        c1 = s1.charAt(i);
        if (c1 == '*')
            continue;

        c2 = s2.charAt(i);
        if (c2 == '*')
            continue;

        if (c1 != c2)
        {
            index = i;
            count++;

            // if hamming distance is greater than 1, immediately stop
            if (count > 1)
            {
                index = -1;
                break;
            }
        }
    }
    return index;

我可能有几百万个节点。k 通常在 50 左右。我使用的是 JAVA，这种比较需要 n*n*k 时间并且运行缓慢。我考虑使用尝试和 VP 树，但无法弄清楚哪种数据结构适用于这种情况。我还研究了 Simmetrics 库，但什么都没有出现在我的脑海中。我真的很感激任何建议。

4

3 回答 3

1

试试这个方法：

将键转换为三进制数（以 3 为底）。即 0=0, 1=1, *=2 10 位三进制为您提供 0..59049 的范围，适合 16 位。

这意味着其中两个将形成一个 32 位字。创建一个包含 40 亿个条目的查找表，返回这两个 10 位三元词之间的距离。

您现在可以使用查找表通过一次查找检查密钥的 10 个字符。如果您使用 5 个字符，则 3^5 会为您提供 243 个适合一个字节的值，因此查找表将只有 64 KB。

通过使用移位操作，您可以创建不同大小的查找表来平衡内存和速度。

这样，您可以优化循环以更快地中止。

要获得第一个差异的位置，您可以使用第二个查找表，其中包含两个关键子字符串的第一个差异的索引。

如果您有数百万个节点，那么您将有许多以相同的子字符串开头。尝试将它们分类到存储桶中，其中一个存储桶包含以相同键开头的节点。这里的目标是使桶尽可能小（以减少 n*n）。

于 2015-04-09T16:05:36.657 回答
1

代替 / 附加到字符串，存储 1 位的掩码和 * 位的掩码。可以使用 BitSet，但让我们尝试不使用。

static int mask(String value, char digit) {
    int mask = 0;
    int bit = 2; // Start with bits[1] as per specification.
    for (int i = 0; i < value.length(); ++i) {
        if (value.charAt(i) == digit) {
            mask |= bit;
        }
        bit <<= 1;
    }
    return mask;
}

class Cell {
    int ones;
    int stars;
}

int difference(Cell x, Cell y) {
    int distance = 0;
    return (x.ones & ~y.stars) ^ (y.ones & ~x.stars);
}

int hammingDistance(Cell x, Cell y) {
    return Integer.bitCount(difference(x, y));
}

boolean differsBy1(Cell x, Cell y) {
    int diff = difference(x, y);
    return diff == 0 ? false : (diff & (diff - 1)) == 0;
}

int bitPosition(int diff) {
    return Integer.numberOfTrailingZeroes(diff);
}
于 2015-07-10T07:18:29.147 回答
0

有趣的问题。没有通配符符号会很容易。

如果通配符是字母表中的常规字符，那么对于给定的字符串，您可以枚举所有 k 汉明距离 1 字符串。然后在多映射中查找这些字符串。例如，对于 101，您查找 001,111 和 100。

无关符号使您无法进行该查找。但是，如果构建多映射以使每个节点都由其所有可能的键存储，则您可以再次进行该查找。因此，例如 1*1 存储为 111 和 101。因此，当您查找 10* 时，您会查找 000,010,011,001,111，它会找到由 111 存储的 1*1。

这样做的好处还在于您可以将所有标签存储为整数而不是三元结构，因此使用 int[3] 作为键值，您可以使用任何 k < 96。

性能将取决于多地图的支持实现。理想情况下，您会为密钥大小 < 32 使用哈希实现，并为上述任何内容使用树实现。通过树实现，所有节点都连接到它们的距离为 1 的邻居O(n*k*log(n))。构建多映射需要O(n * 2 ^ z)任何z字符串的最大通配符数。如果通配符的平均数量较低，这应该是可接受的性能损失。

编辑：您还可以通过将汉明距离 1 邻居插入到多地图中来提高所有节点的查找性能，O(n*log(n))但这可能只会使其大小爆炸。

注意：我是在午休时间输入的。我还没有检查细节。

于 2015-07-10T06:39:37.823 回答