比较 – 计算二进制数据相似性

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

为了给你更多的细节，尽管这可能适用于许多事情，我有一个具体的问题，我正在努力。我也目前有一个工作的解决方案，但我不认为它是理想的。在比较方法方面可能有许多优化，并存储结果。希望这里的一些人能够给我一些新的想法。我可能会在几天后编辑一些有关我当前方法的信息，但我不想偏见人们对这个问题的想法，告诉你我已经在做什么。

我工作的问题是克隆检测视频游戏ROM图像。对于那些没有仿真经验的人，ROMs是转储的游戏盒上的数据。 ROM“克隆”通常是相同游戏的修改版本，最常见的类型是翻译版本。例如，日本和英语版本的原始最终幻想的NES是克隆。游戏共享几乎所有的资产(精灵，音乐等)，但文本已经翻译。

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

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

> ROM的大小差异很大，这取决于系统。有些是小的，但现代系统可能有大的，256MB或更多。一些(所有？)系统只有2的权力，尽可能的大小，在这些系统之一上的130MB游戏将有一个256MB的rom，基本上是空的。注意，因为这个，一些克隆可能有非常不同的大小，如果游戏版本超过阈值，并必须使用两倍大小的墨盒。
>在许多系统上目前有数千个已知的ROM，大多数系统仍然有新的不断发布。即使对于旧系统，也有一个主要的ROM黑客社区，经常生产修改的ROM。
>为每个可能的ROM对存储相似性数据将导致任何更流行的系统的数百万行数据。具有5000个ROM的系统将需要2500万行相似性数据，其中一个新游戏添加另外5000行。
>处理状态必须是可恢复的，因此如果它被中断，它可以在其中断的地方拾取。使用任何方法，将需要大量的处理，并且假设整个事务将在一个批次中运行是不安全的。
>可以随时添加新的ROM，因此该方法不应该假设它已经有一个“完整”集。也就是说，即使在已经确定了所有现有ROM之间的相似性之后，如果添加了新的(并且这也可以在先前的处理完全完成之前发生)，则必须存在用于将其与先前的全部比较的方法，以确定它(如果有的话)是一个克隆。
>较高的处理速度应优先于精度(到一点)。知道两个ROM是94％还是96％相似并不是特别重要，但是如果将一个新的ROM与所有先前的ROM进行比较需要一天的处理，该程序可能永远不会真正完成。

这是一个有趣的问题，我期待看到其他人可以想出来。让我知道在评论如果你想要任何更多的细节，我会尽力提供他们。