介绍
最近，我们一直在努力构建下一个版本的Corporearn，这是一种使用归一化压缩距离（NCD）的科学工具包，以在任何类型的数据中找到相似性模式。简而言之，这是一个合理的相似性度量（当使用普通压缩机时），其中它根据其压缩大小比较2个对象之间的相似性，并且具有以下属性：
它是对称的：[MATH] NCD（X，Y）= NCD（Y，X）[/MATH] NCD通过更改X和Y的顺序不变。
它满足了三角形的不等式：[MATH] NCD（X，Y） + NCD（Y，Z）> = NCD（X，Z）[/MATH] [/MATH]
[MATH] NCD（X，Y）[/MATH]将在[MATH] [0，1] [/MATH]之间，其中0指示两个对象相同，而1表示两个对象完全不同。
这是NCD公式：
[MATH] 大NCD（x，y）= frac {c（xy） - min（c（x），c（y））} { max（c（x），c（y））} [/MATH]
在哪里：
[MATH] C [/MATH]：是普通数据压缩机。
由于x和y是文件或字符串
我们将x和y的串联写为xy
C函数返回输入字节中的压缩大小。
[MATH] C（XY）[/MATH]：串联在一起时的压缩大小是x和y的压缩大小
[MATH] C（X）[/MATH]是X的压缩大小，而[Math] C（Y）[/Math]是Y的压缩大小
[MATH] Max（C（X），C（Y））[/MATH]在分母中为我们提供了X和Y之间的最大压缩大小。通过划分此值，我们可以使我们的[数学] NCD [/MATH]得分介于0和1之间（因此“标准化”一词）
为什么要超越GZIP？
我们采用的第一种压缩算法来计算NCD分数是GZIP，但是GZIP的问题是，它仅与小文件相当，即[MATH] size（x） + size（y）<= 32 kb [/MATH]，如果将两个文件串联在一起，则NCD分数大于32kb，则NCD得分不准确。这是因为NCD通过依靠基础压缩算法来检测数据中的冗余来计算相似性得分，在这里，如果我们使用GZIP，并且对文件大小大于可以接受的窗口，则输入的某些部分可能会被忽略。如果我们有两个大小100kb的文件，但是窗口只有32kb，那么我们看不出两个文件是否相同，因为窗口太小。
我们从GZIP开始，因为它是最简单的压缩机。用户反馈让我们知道有兴趣分析较大的文件，因此我们已经开始添加具有较大或无限窗口尺寸的更高级和现代数据压缩机。我们添加的下一个选项是使用LZMA，它也是GZIP之类的基于字典的压缩算法，但提供了最大的窗口大小高达4GB，因此NCD得分可以正确反映更大的文件大小。但是，LZMA的速度可能比GZIP对应物慢10倍，而我们的Corporarn Toolkit允许用户一次输入多个文件，并且文件尺寸可能很大。因此，有一些有效的动机添加一些小型优化，以使LZMA版本的工作速度更快，即使工作量更高。
一些小的优化
我要指出的第一件事是，有一个属性[MATH] NCD（X，X）= 0 [/MATH]，因为相同的内容应始终在0接近0。如果有5个不同的文件，则NCD矩阵将具有[MATH] N * N = 25 [/MATH [/MATH]带有[Math] N [/Math]作为输入文件的数量。如前所述，[MATH] NCD（X，Y）= NCD（Y，X）[/MATH]，因为它们是对称的，因此我们只能计算[MATH] NCD（X，Y）[/MATH]，然后将此值用于[Math] NCD（y，y，x）[/MATH] [/MATH]。当输入大小变大时，这些小型优化可以帮助很多。
现在，我们想使用LZMA压缩选项尝试NCD，我们的输入文件现在是4种不同语言的通用人权声明（UDOHR）的一些翻译版本，每个文件约为200kb。但是，从开始计算的那一刻起，我花了大约22秒的时间才能显示出NCD分数，就用户体验而言，这确实很糟糕。我们计划很快就会添加一些更快的压缩算法，但是在此之前我们可以做的另一种优化可以为我们将添加的所有压缩算法带来互惠互利，稍后将添加一些缓存，以在NCD计算器中添加一些缓存。在这里，当用户将文件上传到我们的系统中时，第一次没有缓存，则需要执行一些实际的计算。但是，如果以后再次使用了一些相同的文件内容，我们需要创建一个机制来跳过这些文件计算以呈现更好的性能。因此，在考虑2个文件[MATH] X，Y [/MATH]时，我们可以缓存[MATH] X [/MATH]，[MATH] Y [/MATH]和[MATH]（XY]（XY）[/MATH]的压缩大小，因此无需冗余计算。但是存在一个问题，如果这些文件的任何内容都会更改，并且我们的缓存不够聪明，无法确定同一文件名称具有不同的内容？
循环冗余检查
这就是循环冗余检查（CRC）发挥作用的地方。这是一种轻巧的错误检测算法，该算法计算给定输入的固定尺寸校验和。这主要用于错误检测，但是我们也可以在NCD计算器中使用它，以检查我们的输入文件内容是否已更改。因此，我们应该牢记的CRC有2个属性：
如果2个文件的内容不同，那么它确实会生成2种不同的哈希。
如果两个文件之间的哈希相同，则内容可能是相同的（但不确定是由于哈希碰撞引起的）
在这里，我们循环浏览每个文件内容中的所有部分，并计算CRC哈希值。即使是计算CRC的[MATH] O（MATH] O（N）[/MATH]时间复杂性，但它非常快，因为它在每个计算上使用[Math] XOR [/MATH]操作。除了性能考虑之外，我们还希望确保在与CORCC的CRC中用作缓存机制时，它在使用中的缓存机制时可以正常运行，因为我们用于CRC的位数将确定我们的CRC算法可以保持多少不同的值，因为我们在位级别使用它。
首先，如果我们选择8位，例如，CRC-8，那么我们的[MATH] 2^8 = 256 [/MATH]的总共有不同的值。那么，将5个不同的文件输入到我们的CRC-8且没有碰撞的概率是多少？
假设我们有[MATH] X_1，X_2，X_3，X_4，X_5 [/MATH]来表示我们拥有的文件内容。 [MATH] CRC（X_I）[/MATH]将为我们提供文件的哈希值，其中内容[Math] X_i [/Math]。从生日问题中，我们可以找出没有碰撞的可能性：
第一个文件内容将具有100％没有碰撞，因为它之前没有哈希内容，因此它是[MATH] frac {256} {256} = 1 [/MATH]。第二个需要避免第一个哈希，然后第二次没有碰撞的可能性是[Math] frac {256 - 1} {256} [/MATH]。使用相同的模式，最后一个是[Math] frac {256-4} {256} [/MATH]。因为每个文件的哈希是依赖的，因此我们需要在这种情况下使用概率规则，从而产生最终结果：
[MATH] frac {256} {256} cdot frac {255} {256} {256} cdot frac {254} {256} {256} cdot cdot frac {253} {256} {256} {256} {256} cdot cdot frac frac {252} {252} {256} {256} {0.96 = 0.96 = 0.96}
因此，可以肯定地说，如果有5个文件，则存在[Math] 96 ％[/MATH]的概率，没有碰撞。但是，如果我们尝试使用20个文件怎么办？因此，我们的计算看起来像这样：
[MATH] p = frac {256 times 255 times 254 times dots times times（256 - 19）} {256^{20}} = prod_ {i = 0}^{19}^{19} {19} left（1 - frac {i} {i} {256} {256} {256} {{256} {{256} {{256} {{256} right）= 0.47]因此，如果我们有20个文件，则几乎存在[MATH] 47 ％[/MATH]的机会。
Even with just 20 files, it has shown us the probability of high collision, and the problem could get worse since we want our cache to be there mostly forever, since simply just a very small mapping between the hash value to the content size (eg hashVal - > fileContentSize), so if users keep using our system, the number of cached files would become huge, potentially up to thousands of files (here we don't store the file content, just the file size of it).因此，让我们尝试使用CRC-16，看看如果有1000个文件，没有碰撞的机会是什么：
[MATH] ： prod _ {i = 0}^{999} ： left（：1 ： - ： - ： frac {i} {i} {2^{16}}}}}} ：： right）
因此，如果我们已经有995个缓存的文件，然后我们有5个新文件，我们想找到相似性得分的分数，那么几乎可以肯定地有碰撞，因为没有碰撞的概率甚至小于[Math] 1 ％[/MATH]，然后损坏NCD指标。
这就是为什么我们需要更大的2个价值的功率。在这种情况下，我们将选择32位（即CRC-32），这意味着我们总共有[MATH] 2^{32} [/MATH]值。然后，使用相同的公式，我们将获得1000个文件的无碰撞和[MATH] 90 ％[/MATH]无碰撞的30000个文件的概率的概率[Math] 99.9 ％[/MATH]的值。因此，将此位值用于CRC非常实用，因为我们的下一个版本仍在其启动中，还有更多。
CRC-32
我们已经最终确定了32位用于CRC，现在让我们深入了解其在表面水平下的工作细节。 But first, let's revise some concepts in binary arithmetic, there are 3 fundamental operations we're probably familiar with when dealing with bit manipulation, let's have 2 decimal values [math]x:and:y[/math] and the [math]b_x[/math] is the binary representation of [math]x[/math] and [math]b_y[/math] is the binary representation of [math]y[/math], then这些属性将始终保持：
[MATH] B_X ：和：B_Y = B_Z [/MATH]其中[MATH] B_Z [/MATH]始终[MATH] <= min（b_x，b_y）[/MATH]
[MATH] B_X ：或：B_Y = B_Z [/MATH]其中[MATH] B_Z [/MATH]始终[MATH]> = MAX（B_X，B_Y）[/MATH]
但是，使用[数学] XOR [/MATH]操作，2个二进制数字的结果并不总是遵循较大或较小的模式，而是本质上似乎是随机的，这完全适合于错误检测和捕获数据中的变化。
Conceptually, the CRC-32 algorithm performs polynomial division in the Galois Field GF(2): it's a mathematical system consisting of just 2 elements 0 and 1 (ig [math]GF(2) = {0, 1}[/math]), where the input message (augmented with zeros) serves as the dividend and a standardized generator polynomial serves as the divisor.在此字段中，加法和减法是等效的，并使用XOR操作实现。
该算法通过位处理输入消息，维护运行计算。当电流值的最显着位（MSB）为1时，它表明当前的多项式程度等于或超过发生器多项式程度。此时，该算法通过左移动电流值（乘以x），然后与发电机多项式应用XOR操作来执行多项式算术。这个过程一直迭代，直到处理了增强消息的所有位。
最终结果是该多项式划分的其余部分（这是通过使用[Math] Xor（ oplus）[/Math]操作的加法和减法完成的。 CRC-32的标准发电机多项式具有以下形式：
[MATH] g（x）= x^{32} + x^{26} + x^{23} + x^{22} + x^{16} + x^{12} + x^{12} + x^{11} + x^{10} + x^{10} + x^8 + x^8 + x^7 + x^7 + x^5 + x^4 + x^4 + x^2 + x + x + x + x + x + x + x + x + x + x + x + 1 [ +]
在任何位置[MATH] X_I [/MATH]值必须为1或0。如果位置[MATH] I [/MATH]在上述表达式的RHS中呈现[MATH] X_I [/MATH]的值将为1。在这种情况下，[MATH] X_ {32} = 1 [/MATH]，[MATH] X_ {26} = 1 [/MATH]，[MATH] X_ {23} = 1 [/MATH]等。如果表达式中不存在[数学] i [/MATH]的位置，则该位置上的相应二进制表示为0。从该规则中，我们现在可以获得生成器多项式的完整32位，即[MATH] 1000001001100000111111111111111111111111 [/MATH]，该二位数将等于[Math] 0x04C11DB7 [/Mathim]，该二位数将等于[Math] 0x04c11db7 [/Mathim]。
CRC-32实施
让我们在打字稿中实现CRC-32的基本版本：
class BasicCRC32 { private static readonly POLYNOMIAL = 0x04C11DB7; private static readonly INITIAL_VALUE = 0xFFFFFFFF; public static calculate(data: Uint8Array): number { let crc = BasicCRC32.INITIAL_VALUE; for (const byte of data) { // Process each byte crc ^= (byte < < 24); // Process each bit of the byte for (let bit = 0; bit < 8; bit++) { if (crc & 0x80000000) { crc = ((crc < < 1) ^ BasicCRC32.POLYNOMIAL) >>>0; } else { crc = (crc < < 1) >>>0; } } } return (crc ^ BasicCRC32.INITIAL_VALUE) >>>0; } } class BasicCRC32 { private static readonly POLYNOMIAL = 0x04C11DB7 ; private static readonly INITIAL_VALUE = 0xFFFFFFFF ; public static calculate ( data : Uint8Array ) : number { let crc = BasicCRC32. INITIAL_VALUE ; for ( const byte of data) { // Process each byte crc ^= (byte < < 24 ); // Process each bit of the byte for ( let bit = 0 ; bit < 8 ; bit ++ ) { if (crc & 0x80000000 ) { crc = ((crc < < 1 ) ^ BasicCRC32. POLYNOMIAL ) > > > 0 ; } else { crc = (crc < < 1 ) > > > 0 ; } } } return (crc ^ BasicCRC32. INITIAL_VALUE ) > > > 0 ; }}在calculate函数内部，我们首先将CRC分配给初始值，其中32位设置为1。在循环内，我们按顺序通过每个byte 。 (byte < < 24)将将当前字节24位置向左移动，将MSB带有byte值，其余的24位将填充0。然后，我们[Math] XOR XOR [/MATH]具有当前CRC值；没有这个，先前计算的信息将丢失。
当除数多项式的程度小于或等于股息多项式时，我们可以执行多项式分裂。在内部循环中，我们检查当前[Math] CRC [/MATH]的MSB是否具有[Math] Anded [/Math]的发电机多项式的程度，并使用[MATH] 0x80000000 [/MATH]。如果是这种情况，我们将每一点移动一位，然后使用多项式常数进行[MATH] OPLUS [/MATH]操作。否则，我们只需剩下一个位即可处理下一个位，而没有[Math] Xoring [/Math]。最后，我们再将CRC值一次翻转一次以获得最终结果，因为它是CRC-32规范的一部分，因此[MATH] >>> [/MATH]操作将使CRC值始终非负值。
与CRC-32的Corlarn 2.0
在“自定义文件上传”选项卡中，我上传了4个不同的语言文件，即英语，法语，俄语和西班牙语，以通过这些语言的UDOHR翻译来衡量它们的相似性，这是第一个使用LZMA输出的NCD计算，该矩阵和四重奏树在22秒后：
接下来，我们要在树上添加越南语并仍然保留现有的越南语，在这种情况下，我们已经拥有使用CRC-32缓存的计算语言的NCD值，因此矩阵中的16个条目保持完整，现在我们只需要计算9个条目，因为我们总共有5 * 5 * 5 NCD入口时，添加了5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * ncd语言。
只有8秒钟来计算9个新条目而不缓存，这些翻译需要我们30秒。
即使是8秒也不是一个良好的用户体验，但是当我们可以将一些工程和计算机科学应用于实际工作时，我们更倾向于证明CRC-32在我们的NCD计算器中的适用性。我们知道某些压缩算法（例如LZMA）的加载时间问题，此处显示。我们将很快解决这个问题，将来会有关于我们的科学工艺的更多有趣的博客文章！感谢您的阅读！