有没有办法在c#.net中的两个字节数组上生成二进制差异？

Question

我试图比较内存中的两个字节数组并产生一个数据结构以保持差异,这样对于字节数组B和保持差异的数据结构,可以重新创建字节数组A.

字节数组的大小始终相同且相对较小.字节数组表示位图,其大小通常在1000x1000x32到128x128x32之间.

可以组合/用于重构字节阵列A的速度和效率(来自CPU时间pov)是最重要的,其中数据结构保持差异和第二字节阵列可以组合/用于重建字节阵列A. 差异对象的生成同样有效并不重要.

现在我的解决方案是使用二进制搜索+ md5散列方法来构建图像内部最小差异单位的列表,并将原始字节数据与其在字节数组A内的偏移量的引用打包.

即我为Image A的字节数组生成散列并将其与Image B的字节数组的散列进行比较,如果它不匹配我将图像水平分割成两半并散列每个块然后比较图像之间的这些散列,这个过程是然后递归重复,直到所有不匹配的块达到最小大小,如32x32x32和/或最大分割数.一旦块被标记为匹配,它就不再是递归搜索的一部分.一旦识别出所有差异,它们将被添加到更改列表中,然后该列表就是差异对象.

有没有内置的方法来有效地产生我正在寻找的结果？或者是否有任何图书馆可以完成这项工作？

---

笔记:

• 这是一个学习项目(适用于WCF,WPF和许多其他技术),
• 它是一个VNC风格的系统 - 因此图像是窗口的快照,并将通过LAN连接发送.
• 重构字节数组A必须高效的原因是客户端可以连接到多个服务器,并且每个服务器可以服务多个窗口,因此客户端可以监视/与30多个窗口交互.
• 我想在每个窗口中为任何变化的内容实现3 fps +.

Answer 1

如果保证它们的大小相同 - 实际上是相同的维度 - 那么我就没有看到所有这些哈希和二进制搜索以及其他开销的重要性.你可以简单地在一个循环中比较两个字节,如果它们不匹配,在你的diff中添加一个"点",包含索引和A中的值.要反转过程,你不要需要查看每个字节,因为您已经有索引.

如果两个数组相差仅比1个字节,那么你最终会得到一个大小为5个字节的diff结构(假设你使用Int32作为索引),并且需要1次迭代才能将B变回A通常,对于diff,过程是O(n),对于恢复,过程是O(m),其中m是实际改变的点的总数.我不是数据结构方面的专家,但我怀疑你能否提出更有效的方法.

所以,像这样:

Diff GetDiff(byte[] a, byte[] b)
{
    Diff diff = new Diff();
    for (int i = 0; i < a.Length; i++)
    {
        if (a[i] != b[i])
        {
            diff.Points.Add(new DiffPoint(i, a[i]));
        }
    }
    return diff;
}

// Mutator method - turns "b" into the original "a"
void ApplyDiff(byte[] b, Diff diff)
{
    foreach (DiffPoint point in diff.Points)
    {
        b[point.Index] = point.Value;
    }
}

// Copy method - recreates "a" leaving "b" intact
byte[] ApplyDiffCopy(byte[] b, Diff diff)
{
    byte[] a = new byte[b.Length];
    int startIndex = 0;
    foreach (DffPoint point in diff.Points)
    {
        for (int i = startIndex; i < point.Index; i++)
        {
            a[i] = b[i];
        }
        a[point.Index] = point.Value;
        startIndex = point.Index + 1;
    }
    for (int j = startIndex; j < b.Length; j++)
    {
        a[j] = b[j];
    }
    return a;
}

struct DiffPoint
{
    public int Index;
    public byte Value;

    public DiffPoint(int index, byte value) : this()
    {
        this.Index = index;
        this.Value = value;
    }
}

class Diff
{
    public Diff()
    {
        Points = new List<DiffPoint>();
    }

    public List<DiffPoint> Points { get; private set; }
}

这里有很多循环,ApplyDiffCopy但如果你解决了,你会发现它实际上每个点只执行一次操作.当然,如果你不需要副本而只是想改变B,那么ApplyDiff如果实际差异不大,第一种方法会非常快.

显然我在这里没有做太多的错误检查.您可能希望在防御性方面编写您的版本(验证数组长度等)

如果我正确地理解了这里的假设和你想要解决的问题,那么原始ApplyDiff方法将是恢复原始图像的最快方法.