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

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

这是一个 O(n) 算法。

比较两个字符串之间的相等性（或本例中的距离）的最有效算法是 O(n)。

Answer 2

您可以通过避免通过索引进行随机访问来使其稍微快一些，您实际上只需要顺序访问字符串。

不过我不确定编译器是否可以为您优化它。

Answer 3

你可以空出 if:

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

但我怀疑这是否重要

Answer 4

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

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

异或组合这些值以获得位差
将 AND 归一化子集（奇数位、偶数位）移位和 OR 组合为将位差异转化为碱基差异
对设置的位进行计数，得到DNA序列距离

根据计算机体系结构，可能会有位计数功能在 CPU 中实施。更多详情有问题的答案：如何计算 32 位中设置位的数量整数？

这里是核心函数：

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);
}

查看使用长度为 16 的序列的 full GCC-4.3.2 demo。我测量了比较本身的性能增量为 4 倍（不包括编码）。

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

calculating how much two strings are similar?

c++

algorithm

processing-efficiency

cpu-speed