我有一个问题,作为输入,我有一个大字节数组(通常长度大于 1K),它具有计算的 CRC32。我需要用不同的值替换一小块数组,并重新计算 CRC。有没有一种有效的方法可以在不遍历整个原始字节数组的情况下执行此操作?我怀疑在数学上可以将原始 CRC、要替换的字节、新字节作为输入,并使用循环大小只是要替换的字节数的算法计算新 CRC,但它超出了我的范围专业知识,因此,只是一个怀疑。谢谢,
最佳答案
是的,这是可以做到的。尽管在 1K 字节级别,在整个过程中重新计算 CRC 很可能会更快。
正如德米特里·鲁巴诺维奇 (Dmitry Rubanovich) 所指出的,您可以使用 CRC 是一个线性函数,其中加法被异或替换的事实。但是,您可以做得更好,而不仅仅是避免重新计算直到第一次更改。无论您在哪里有一个没有变化的长字符串,它是两个消息的异或中的一长串零,您可以在 O(log(n)) 时间而不是 O(log(n)) 时间内计算该字符串的 CRC 变化(n) 时间。
这样做的方法是生成一系列 32x32 位矩阵,每个矩阵代表 2 的幂零字节应用于 CRC。例如。 1、2、4、8 等零字节。这可以提前完成,生成一个静态表。然后,例如,为了将 CRC 演化为 137 个零,您将当前 CRC 作为位 vector 乘以 128、8 和 1 个零的矩阵。矩阵乘法在GF(2)之上,即加法被异或代替,乘法被和运算代替。
您可以在 zlib function for combining CRC's 中查看如何完成此操作的示例。
使用指令计数的快速计算表明,对于长度超过约 300 字节的零字符串,对数方法平均会更快。
关于c++ - 替换少量字节时如何在大字节数组上重新计算CRC32,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/34601950/