c++ - 计算两个字符串有多少相似？

Question

我有一个函数可以计算两个给定字符串的方差。有没有更快的方法(或算法)来做这样的事情？

请记住，我的字符串中的每个字母都加载了 DNA，这意味着它们是 A 或 T 或 C 或 G 之一:

unsigned __int8 dis(char* FirstString, char* SecondString)
{
    unsigned __int8 distanceIndex = 0;
    for (unsigned __int8 i = 0; i < l; i++)
    {
        if (FirstString[i] != SecondString[i])
            distanceIndex++;
    }
    return distanceIndex;
}

Answer 1

虽然我还是怀疑字符串比较真的是the bottleneck你的项目，我忍不住接受挑战......

你所有的序列都是13 chars long . DNA 序列仅包含字母 ATCG，可以在 2 位内进行编码。您可以将每个 DNA 序列存储在一个 32 位值中，让计算机并行进行比较:

• 异或组合这些值以获得位差
• 将 AND 归一化子集(奇数位、偶数位)移位和 OR 组合为 将位差异转化为碱基差异
• 计算设置位以获得DNA序列距离

根据计算机体系结构，可能会有位计数功能 在 CPU 中实现。更多详情有问题的答案:How to count the number of set bits in a 32-bit integer?

这里是核心函数:

int distV(const unsigned va, const unsigned vb)
{
    const unsigned x = va ^ vb;
    const unsigned bn = ((x & 0xaaaaaaaa) >> 1 ) | (x & 0x55555555);
    return __builtin_popcount(bn);
}

参见 full GCC-4.3.2 demo使用长度为 16 的序列。我测量了比较本身的性能增量为 4(不包括编码)。