comparison - 计算二进制数据相似度

Question

我在这里看到了一些与确定文件相似性相关的问题，但它们都与特定域(图像、声音、文本等)相关联。作为解决方案提供的技术需要了解所比较文件的基础文件格式。我正在寻找的是一种没有此要求的方法，其中可以比较任意二进制文件，而无需了解它们包含的数据类型。也就是说，我正在寻找确定 两个文件二进制数据的相似度百分比 .

为了提供更多细节供您处理，尽管这可能适用于许多事情，但我确实有一个正在处理的特定问题。我目前也有一个可行的解决方案，但我认为它并不理想。在比较方法和存储结果方面可能有很多优化。希望这里的一些人能给我一些新的想法。几天后我可能会编辑一些关于我当前方法的信息，但我不想通过告诉你我已经在做的事情来影响人们对这个问题的看法。

我正在处理的问题是 视频游戏 ROM 图像的克隆检测 .对于那些没有仿真经验的人来说，ROM 是游戏卡带上数据的转储。 ROM“克隆”通常是同一游戏的修改版本，最常见的类型是翻译版本。例如，NES 的原始最终幻想的日语和英语版本是克隆。游戏共享几乎所有的 Assets ( Sprite 、音乐等)，但文本已被翻译。

目前有几个小组致力于维护各种系统的克隆列表，但据我所知，这一切都是手动完成的。我试图做的是找到一种方法来自动客观地检测相似的 ROM 图像，基于数据相似性而不是“这些看起来像同一个游戏”。检测克隆有多种原因，但主要动机之一是与 Solid compression 一起使用。 .这允许将所有游戏克隆一起压缩到同一个存档中，整个压缩克隆集通常只占用比单个 ROM 之一略多的空间。

提出潜在方法时需要考虑的一些问题:

ROM 的大小差异很大，具体取决于系统。有些很小，但现代系统可能有很大的，256MB 或更多。一些(所有？)系统只有 2 的幂次方大小，其中一个系统上的 130MB 游戏将有 256MB 的 rom，基本上是空的。请注意，因此，如果游戏版本超过阈值并且必须使用两倍大小的卡带，则某些克隆可能具有截然不同的大小。

目前在许多系统上有数千个已知的 ROM，大多数系统仍在不断发布新的 ROM。即使对于较旧的系统，也有一个主要的 ROM 黑客社区经常生成修改后的 ROM。

为每对可能的 ROM 存储相似性数据将导致任何更流行系统的数百万行数据。一个有 5000 个 ROM 的系统需要 2500 万行相似性数据，而一个新游戏又需要增加 5000 行。

处理的状态必须是可恢复的，以便如果它被中断，它可以从中断的地方恢复。使用任何方法都需要进行大量处理，假设整个事情将在一个批次中运行是不安全的。

可以随时添加新的 ROM，因此该方法不应假设它已经具有“完整”集。也就是说，即使您已经计算出所有现有 ROM 的相似性，如果添加一个新 ROM(这也可能发生在之前的处理完全完成之前)，必须有一种方法将其与所有以前的 ROM 进行比较，以确定哪个(如果有的话)它是一个克隆。

更高的处理速度应该优先于精度(在一定程度上)。知道两个 ROM 的相似度是 94% 还是 96% 并不是特别重要，但是如果将新 ROM 与之前的所有 ROM 进行比较需要一天的处理时间，则程序可能永远不会真正完成。

这是一个有趣的问题，我期待着看到其他人能想出什么。如果您需要更多详细信息，请在评论中告诉我，我会尽力提供。

Answer 1

听起来您想要一个二进制增量，或者可能是从二进制增量的应用程序派生的索引(比如它的大小)。然后，您可以将此索引与您通过实验确定的某个基线进行比较，以确定它是否是“克隆”。

压缩和增量创建之间有很多相似之处，所以我想说您与当前的实现相距不远。

话虽如此，数据库中每个二进制文件的成对比较可能非常昂贵(我认为 O(n2))。我会尝试找到一个简单的哈希来识别可能的比较候选对象。概念上类似于 spdenne 和 Eduard 所建议的。也就是说，找到一个可以应用于每个项目一次的散列，对该列表进行排序，然后对散列在列表中最接近的项目使用更细粒度的比较。

多年来，构建对一般情况有用的哈希一直是 CS 中积极追求的研究课题。 LSHKit软件库实现了一些此类算法。互联网无障碍论文 FINDING SIMILAR FILES IN A LARGE FILE SYSTEM似乎它可能更多地针对比较文本文件，但可能对您有用。最近的论文Multi-resolution similarity hashing描述了一个更强大的算法。但是，如果没有订阅，它似乎无法访问。您可能希望将维基百科文章保留在 Locality Sensitive Hashing 上在您浏览其他资源时非常方便。它们都非常技术性，而且维基百科条目本身在数学上非常繁重。作为对用户更友好的替代方案，您可以应用来自 Acoustic Fingerprinting 领域的一些想法(甚至可执行文件)。 .

如果您愿意放弃一般情况，您很可能会找到一个更简单(更快)的特定于域的哈希函数，它仅适用于您的 ROM。可能涉及标准或通用字节序列的放置以及它们附近的选择位的值。我不太了解您的二进制格式，但我正在想象一些表示文件中部分开始的东西，例如声音、图像或文本区域。二进制格式经常将这些类型的部分的地址存储在文件开头附近。有些还使用链接机制将第一部分的地址及其大小存储在已知位置。这允许您移动到下一部分，其中还包含大小等。如果您还没有意识到任何相关的格式，那么一点调查可能会让您发现任何相关的格式，并且应该让您走上构建之路一个有用的哈希。

如果散列函数不能让您一路顺利(或者它们需要某种输入来定义度量/距离)，那么网络上有几种二进制增量算法和实现可用。我最熟悉的一种是 subversion 版本控制系统使用的。它使用称为 xdelta 的二进制增量算法来有效地存储二进制文件修订。这是直接指向其存储库中实现它的文件的链接:xdelta.c .网络上可能有一个工具可以使这更易于访问。