计算的二进制数据相似性

StackOverflow https://stackoverflow.com/questions/579981

题

我已经看到了一些问题在这里关系到确定相似性的文件，但它们都联系到一个特定的领域(图像、声音、文本等等)。技术提供解决方案需要的知识的基础文件格式的文件相比较。我正在寻找一个方法是没有这一要求，在那里任意的二进制文件可以比较的，而不需要理解是什么类型的数据。这就是我想要确定 相似的百分比的两个文件的二进制数据.

得到更详细一点你的工作，即使这是可能适用于很多东西，我有一个具体问题，我的工作。我目前还有一个工作方案，但我不认为这是理想的。可能有许多优化方面的比较方法，以及存储的结果。希望有些人在这里就可以给我一些新的想法。我可能会编辑在一些关于我的前的方法之后几天，但是我不想偏人民的思想有关的问题，告诉你如何，我已经这样做。

这问题我的工作是 克隆检测的视频游戏盘的图像.对于那些没有经验与模拟Rom是垃圾场的数据上的游戏盒。ROM"克隆"通常是一个修改版本相同的游戏，最常见的类型是一个翻译版本。例如，日本与英文版本原 最终幻想 为NES是克隆。该游戏的份额几乎所有的资产(精灵、音乐等等)，但该文本已经翻译。

目前有几个小组的工作保持清单的克隆的各个系统，但是尽我可以告诉大家，这是所有手工完成。我试图要做的就是找到一种方法检测的类似ROM的图像自动地和客观地说，根据相似性，而不是"这些似乎是同样的游戏"。有几个原因检测的克隆，但一个主要动机是用于 固态压缩.这将允许压缩的所有游戏中的克隆一起到同样的档案，与整个压缩的克隆定常常就只有略多于一个光盘。

一些关切问题时要考虑未来与潜在办法：

  • 光碟不同高度在大小，取决于系统。一些较小，但是现代系统可能具有很大的，256MB或更多。一些(？) 系统只有有权力的2作为可能的尺寸，一130MB游戏，在这些系统将有一个256MB rom，很大程度上是空的。注意，正因为如此，一些克隆可具有完全不同的大小，如果一个游戏版本过阈值的和有用的一个仓，是两倍的大小。
  • 目前有成千上万的知的光盘上的许多系统，与大多数系统仍然具有新的释放不断。甚至是年龄较大的系统，是一个重大的ROM-黑客的社区，产生修改的光盘经常。
  • 储存数据相似性对于每个可能对光盘将导致数以百万计的数据行为的任何更受欢迎的系统。系统有5000光盘，将需要25亿行的相似性数据，与一个单一的新的游戏添加另一个5000行。
  • 状态的处理必须将可恢复，所以，如果它被中断，它可以拿起离开的地方。与任何一种方法，很多处理将是必需的，并且假定，整个事情将运行在一批不是安全的。
  • 新的光盘可以在任何时间加入，因此该方法不应该假定，它已经"完成"设置。就是说，即使你已经想出了相似的所有现有的光盘，如果一个新增加(这也可能发生之前处理完全是完成)必须有一个方法比较以往所有的人，以确定哪些(如果有的话)也是一个克隆。
  • 更高的处理速度应予以优先通过准确性(一点)。知道是否有两个光盘94％或96%的相似不是特别重要的，但如果它需要一天的处理比较新的ROM向所有以前的，该程序可能永远不会真正完成。

它是一个有趣的问题上工作，我期待着看到其他什么人可以拿出。让我在评论中知道，如果你想要任何的更多详细信息，并且我会尽力供应。

有帮助吗？

解决方案

它听起来像是你想要的一二三角或许是一种指数的衍生应用的二进制的一个delta(喜欢它的大小)。然后您可以比较这一指数的一些基线的确定实验来决定，如果它是一个"克隆"。

有很多相似之处压缩和三角洲的创作，所以我说你不远了与当前执行情况。

这就是说，成对比的每一个的二进制文件在你的数据库可能是昂贵的(O(n2)，我认为)。我会试图找到一个简单的散列用于确定可能的候选人进行比较。东西在概念上类似于什么spdenne和爱德华是的建议。就是找到一个散列其可以适用于每一个项目一次进行排序列，然后用一个细细的比较项目的哈希近，在列表中。

建造哈希适用于一般情况下已经积极推行的研究课题CS几年。的 LSHKit 软件库，实现了一些算法，这种排序。互联网可访问的纸 找到类似的文件，在一个大文件系统 看来似乎可能是针对多个在比较短的文件，但可能会对你有用。最近的纸 多决议相似哈希 描述一个更强大的算法。它不会出现可以在没有订阅的情况下，虽然。你可能想保留的维基百科上的文章 当地敏感的哈 方便的你浏览其他资源。他们都得到相当的技术和维基百科的入境本身是非常数学的沉重。作为一个更为用户友好的替代你可能可以应用的一些想法(或甚至可执行文件)，从现场的 声学指纹.

如果你愿意放弃一般情况下这是可能的，你可以找到一个简单得多(和更快的)特定领域的散列函数的运作只是为你的光盘。可能涉及的放置的标准或共同的、字节的序列和数值的选择位附近他们。我真的不知道很多关于你的二元格式，但我想象的事情，信号的开始部分中的文件等区域声音、图像或文本。二进制格式经常储存的地址的这些各种各样的区段附近开始的文件。一些还使用链机制存储的地址的第一部分在一个已知的位置随着它的大小。这可以让你移动到一个新的部分，其中还包含一个尺，等等。一点调查可能会让你发现的任何相关的格式，如果你不是已经意识到这一点，并且应该把你自己的方式来建设一个有用的散列。

如果散列函数没有得到你所有的方式(或他们需要输入某种形式的定义的指标/距离的)，然后有几个三角洲二算法和实现可在网。一个我最熟悉所使用的颠复的版本控制系统。它使用一二三角洲的算法被称为xdelta有效地储存的二进制文件的修订。这里有一个直接链接到文件在其储存库，实现它： xdelta.c.有可能是一个工具网，使得这个更易访问。

其他提示

你可能想看看 bsdiff, ，它是二进制的比较/修补的系统。还有一种论点有很多的理论。

使用的一些想法从 剽窃检测 算法。

我的想法：

为了创建一个可比较的"签字"每个ROM，即略有不同的小部分变化，生产的东西就像一个词频率的曲线图，但不是记录的频率的话，你可以散列非常简短的章节，并记录频率的散列值。

不只是散列的一部分，那么下一部分开始从结束的第一部分，而是使用一个滑动窗口，散列的部分开始从字节1，然后散发同一小部分开始从字节的2,然后从字节3，等等。这将否定效果的变量大小不同的部分内ROM。

如果你使用了一个简单的散列函数喜欢异的每个8位字节，因此，你可以很容易地计算的散列的下一个窗口位置异或由当前的散列与出8位，并异或进入的8位。另一个替代的散列函数可以仅仅是使用该指令代码的字长。这可足以建立的静态模式为代码表示机器的指示。重要的是，你想要一散列函数，结果在共同简短的序列在该指令代码得在同一散列值。

你可能会想要较少的散列值更高频率的每一个，但不要去太远或图表将以太平，造成难以比较。同样不要太宽，或你将有许多非常小的频率，使得比较难了。

储存这种图表每ROM。比较频的图表用于两个不同的光盘，通过计算的总和广场的差异频率为每散列值。如果这笔款项为零，则该光盘是有可能的是相同的。进一步远离零点是，少类似的Rom会。

虽然这是已经有很多超过"几天"，我想我也许应该补充我前解决方案中在这里。

Nils Pipenbrinck会在同一方向作为我目前的方法。由于其中一个主要结果找到的克隆是巨大的储蓄从固存档，我想我可能只是试图压缩任何两个光盘在一起，看到多大的空间物保存。我使用了算法在伊兹玛 7zip 这一点。

第一步是压缩每ROM单独地，并注意缩小，然后再尝试归档的任何两个光盘在一起，看看有多少得到的大小不同于他们的个人压缩小。如果结合的尺寸相同的总和个人的尺寸，他们是0%类似，如果是一样的因为他们中的一个(其中最大的一)，它们是相同的。

现在，这是一个巨大的数字压缩的尝试，需要，所以我有几个优化迄今为止(并希望找出多个):

  1. 优先考虑比较的基础上，如何类似的压缩小。如果ROM一个具有压缩小10M和ROM B有一个压缩小2MB,这是他们无法将任何超过20%的类似，所以比较他们获得真正的结果可以留到以后。运行同样的压缩算法上非常类似的文件往往导致类似大小的结果，因此这样发现了很多克隆人的速度非常快。

  2. 结合上面所述，让上下两个"界限"在可能的相似性之间的任何对光盘。这将允许进一步确定优先次序。如果光碟A和B95%的相似，并Rom B和C中只有2%的相似，然后你已经知道，A和C之间的0%和7%.这是太低是一个克隆，所以这一比较可以被安全地推迟，或者甚至完全忽略了，除非我真的想要知道确切的相似之处的一切。

我认为，一些技术借用的数据压缩可能是有趣的在这里：

假设你有两个文件，A和B。

压缩每个文件分别添加压缩小在一起。然后将这两个文件合并成一个单一的、大型的文件和压缩。

差别的大小会给你一个粗略的估计如何类似的文件。

我建议你尝试的洞穴轮换(bzip2)做的压缩。大多数其他压缩算法只有有限的历史。该博伟特算法的另一方面可以工作在很大块的数据。算法"看到"这两个文件在同一时间和任何相似性将导致更高的压缩比率。

XDelta是非常有用的，为获得体面的二元差异: http://xdelta.org

你可以开始通过存储喜欢的东西 哈希树.它只是需要储存一个这样的组哈希每ROM，所需的存储空间仅仅是成比例(但远低于)的尺寸ROM，假设定块的大小。所选择的方框的大小必须得到足够的粒度，以确保准确性，例如：对于最小尺寸的128MiB、精确度约束的1%和 老虎-128哈希 (类似于什么他们使用检查文件的传送通过DirectConnect)，方框的大小1MiB不罚和可以存储所有的散列在128 * 128 / 8 =2048字节!所以做为10,000个光盘只会要求有关20MiB的空间。此外，您可以选择一个较安全、但更快和/或更小的散列。加入/检查相似的一个新的ROM将需要的东西，如：

  1. 分裂的新ROM分散他们每个人。
  2. 每ROM已经在数据库进行比较(参见下文)其散列新的盘的散列。

比较功能应该检查有相似性。但它应该把每一散列作为一个不可分割的价值，即不要打扰试图找到一个逻辑上的显着差异功能之间的两哈希。只要块的大小足够低和哈希冲突是罕见的足够、准确性是保证通过一个简单的是平等的比较。

正如你看到的，问题是降低到一个更简单一性能：检查小得多的数据集相似性。

两个想法:

  • 考虑组织的文件作为数据流程图，并做了一些规范在这represention.因为你知道设定的指令，这可能是可行的，也许只是打包带起来一个解器和做一些文字处理。
  • 训练的分类器例如 CRM114 可能会方便于给你一个紧凑的表示，给你一些想法是否是二进制文件的有很多共同点。

作为伟伦Flinn所述，可能需要一二三角洲的算法。的 可算法 是一个很好的一个。这是快速和可靠。也见 实用工具的文件.

这里的困难是，因为你是处理可执行代码，简单的改变可以将传播整个ROM。地址和偏移的所有价值观可以改变与另外的一个单一的变量或没有作的指令。这将使甚至阻止基于哈希毫无价值的。

一个快速的和肮脏的解决办法可以破解了一个解决方案 difflib (或相当于w/您最喜欢的语言)，因为它被你的滑动比较，可以处理的数据添加或去除。分ROM为可执行和数据的部分(如果可能)。数据的部分可以直接进行比较和一个 相似的比率计算, 虽然你还是会有问题w/地址或偏移。

可执行的部分是更加有趣。读了该机器的先进电子格式，采取可执行，并把它分成一系列的操作码。留下的操作码和注册的部分，但掩盖掉的"有效载荷"/"立即"部分(其加载的可变地址)。一方面得到的信息相似的比率计算器了。

不幸的是，这仍然是一个O(n^2)操作的数量的光盘你轨道，但是可以缓解与(增)集群或一个频率基于比较了减少的数额比较的需要。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top