java - 大比较任务的估计

Question

我在大学里有一个编程任务，需要通过逐字节比较数百个文件(好文件和坏文件，小于一兆字节)来找到恒定长度的共享字符串。

假设我要进行比较的全面覆盖，并且我实际上将每个文件与其他文件进行比较，是否有可能在几分钟内实际完成此任务？

我已经尝试了简单的算法，并且几天来我一直在改进它，而且我似乎无法在几个小时内下降。

到目前为止我做了什么:

CPU:

我在本地对不同的比较和缓冲区大小进行了基准测试，看看哪个最适合我的需求。

我不保留签名本身，只保留对它的引用(通过与文件大小相同的 boolean 数组 - 也帮助我不再比较已排除的索引)。

我目前正在系统中安装可调用比较任务，希望它不会造成太多开销或同步问题。

虚拟内存:

我根据可用的可用内存(System.freeMemory() - 手动指定后大约 2GB)确定缓冲区大小，以防止抖动，并且我已经在每个文件保存的信息之间进行合理的(在我看来)权衡

算法:

在对文件结构进行静态分析后，我尝试仅比较可疑位置中的字节子集(JAR 文件，我没有进入字节码，因为我不知道如何从字节码推断相关性 - 我只比较“classes.dex”)。

<小时/>

鉴于这肯定是一项常见任务，我是否遗漏了一些非常明显的东西？有人告诉我，对签名进行哈希处理可能会更快，但我怀疑这比等待比较结束并稍后通过引用存储它们要快(一旦比较本身(即瓶颈)结束，这会非常快)。对我来说，散列似乎是一个很大的虚拟机占用风险。

据说这应该在“合理的时间内”运行，目的是找到文件(或接近它)的最佳(最小)超集(涵盖大多数坏文件，没有好文件)。在我看来，在听到一些人声称已经完成了它之后，我已经离题很远了。

如果需要更多信息，请询问，我会将其编辑到帖子中。

<小时/>

我计划使用 this Trie 的实现，以防我忘记更新它，我希望遇到此问题的您可以利用它(或此项目中的其他内容)来满足您的需求!

Answer 1

如果你想覆盖所有字符串，你需要的是一个trie。它是一棵树，其中每个节点都是一个字符串的一个字节。最终节点将报告字符串出现的次数。

如果你有“Dog”，“Dad”，“Dod”，“Dog”，你会以类似的方式结束

 D
 | -------
 |       |
 a       o-------
 |       |      |
 |       |      |
 d(1)    d(1)   g(2)

由于字符串具有固定长度n，因此每个级别 i 最多有 256^i 个节点，因此总数为 256^0 + 256^1 + ... + 256^n(这是上限)个节点。