java - 计算字符串的所有 1-hamming 距离邻居的最快方法？

Question

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

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

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

    // 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 库，但没有想到什么。如果有任何建议，我将不胜感激。

Answer 1

试试这个方法:

将 key 转换为三进制数(基数为 3)。即 0=0, 1=1, *=210 位三进制给出 0..59049 的范围，适合 16 位。

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

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

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

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

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

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