algorithm - 标识文件的最少字节

Question

我目前正在做一个小项目，结果证明这是一个挑战。这是设置:我有一个相当旧的处理器，用于各种产品。大约有 500 个不同的固件版本用于各种应用程序。它们有时相差几个字节~1k，其他时候只有 5%。现在我想通过为它创建一个唯一的标识符来识别每个版本。我有可用的固件二进制文件作为工作和训练的文件。

目标是，当有任何设备经过时，我想读出尽可能少的已安装固件字节，因为 9600 波特的连接速度相当慢。尽管固件总共只有 64k 左右，但完全读取它需要相当长的时间(由于协议(protocol)开销、时钟速度等原因，大约需要 5 分钟)

我在考虑一些逻辑，它会解析存储的固件文件并确定哪些字节可用于唯一标识它。每当设备经过时，它都会依次读取每个指纹字节，这与旧的 T9 文本预测非常相似，以缩小候选范围，直到找到正确的固件。为此，我需要建立一个包含最优化的指纹字节集的数据库。但是如何训练呢？如何找到超过 500 个文件的最重要字节？

到目前为止，我已经尝试对文件进行统计分析并找到文件之间差异最大的前 50 个字节。问题是，即使占用 50 个字节，我也会得到创建相同散列的多个版本。

非常欢迎任何可能解决问题的建议或算法!如果您对此有一个完全不同的想法，我很乐意听听!

Answer 1

识别值可能不同的所有字节位置。然后找到“最有效的拆分器”，即探测值会将当前集合拆分为最小子集(在 minmax 意义上)或更多子集的位置。

然后递归地对每个子集重复整个过程。这将产生一个决策树，为您提供(希望是短的)字节序列进行测试。

这是一种启发式方法，可能不是最优的，我希望

• 计算过程不会太长(虽然它会一次性运行)，
• 它与最佳状态相差不远。

假设每次拆分都是平衡的，但每次都产生两个子集，则测试序列不会超过 10 个字节。