2

下面包含一个非常快速和优雅的 Rabin 指纹的 Java 实现 https://github.com/themadcreator/rabinfingerprint

然而，可用于优化实现的最大多项式是 54 位。

我想减少出错的概率。

Rabin [1] 提出了两种降低错误概率的方法： • 通过增加 k 的值来降低错误输出的概率。这将需要更大的字长。• 概率也可以通过使用相同k 次的两个不同的不可约多项式P1(t) 和P2(t) 来降低。然后通过交织步骤运行该算法两次，一次使用 P1(t)，另一次使用 P2(t)。由于错误概率是独立的......（来自 CMPUT690 Term Project）

如果我运行该算法两次，如何在不破坏目标的情况下组合 2 个指纹以降低出错概率？

  • 只需添加或倍增 2 个指纹？
  • 使用第一次运行的输出作为第二次运行的基本指纹？

我不清楚什么是“交错步骤”。我需要将指纹保存为 64 位长的数字。

谢谢。

4

1 回答 1

2

你不能。Rabin 建议使用不同的不可约多项式有效地运行该算法两次，然后将输出连接起来，在您的情况下这将为您提供 108 位。问题是，没有办法将其压缩到 64 位而不丢掉大部分的错误减少：根据鸽巢原理，任何算法所希望的绝对最低错误概率是

  • 使用 56 位指纹时大约 1/2^56
  • 使用 64 位指纹时大约为 1/2^64
  • 使用 128 位指纹时大约 1/2^128

并且由于 Rabin 的算法接近这些界限，从 54 位指纹到 64 位指纹最多可以减少 ~2^10 = ~1,000 倍的误差。

如果这种改进值得你花时间，你最好的选择是计算两个 54 位指纹，丢弃它们每个的最高 20 位（得到两个 32 位指纹），然后将它们连接起来得到 64位指纹。

于 2013-12-29T20:12:24.950 回答