algorithm - 以编程方式生成“哈希”函数

Question

我有一些非常古老的遗留程序代码，它需要 10 个左右的枚举输入 [i0, i1, i2, ... i9] 并生成 170 个奇数枚举输出 [r0, r1, ... r168, r169]。通过枚举，我的意思是每个单独的输入和输出都有自己的一组不同的值集，例如 [ red, green, yellow ] 或 [ yes, no ] 等。

我正在使用现有代码将整个状态表放在一起，而不是手动费解它们，我想知道是否有一种算法方法可以确定适当的函数以从 10 个输入中获取每个结果。请注意，并非所有输入列都可能需要确定单个输出列，即 r124 可能仅依赖于 i5、i6 和 i9。

这些不是连续函数，我希望我最终可能会采用某种散列函数方法，但我想知道是否有人知道我应该使用更可重复的过程？（如果只有一些类似于多值非二进制函数的卡诺图方法;-)）

标签： algorithmhash

Answer 1

如果您愿意实际枚举所有可能的输入/输出序列，这里有一个解决这个问题的理论方法，应该是相当有效的。

首先，考虑输出的熵。假设您有n可能的输入序列，并且是作为输出x[i]获得的方式数。i让p[i] = float(x[i])/float(n[i])熵为- sum(p[i] * log(p[i]) for i in outputs)。（注意，由于p[i] < 1是log(p[i])负数，因此熵是正的。还要注意，如果p[i] = 0我们假设它p[i] * log(p[i]) 也是零。）

熵的数量可以被认为是预测结果所需的信息量。

现在这是关键问题。根据输入的信息，哪个变量为我们提供了关于输出的最多信息？

如果特定变量v具有in[v]可能的值，则指定的信息量v为log(float(in[v]))。我已经描述了如何计算整个输出集的熵。对于 的每个可能值，v我们可以计算该值的整个输出集的熵v。已知v信息量是总集的熵减去的各个值的熵的平均值v。

v选择给你最佳比率的变量information_gained_from_v/information_to_specify_v。您的算法将从打开该变量的一组值开始。

然后对于每个值，重复此过程以获得级联嵌套 if 条件。

这通常会导致一组相当紧凑的级联嵌套 if 条件，这些条件将专注于输入变量，这些变量尽可能快地告诉您，并且您可以管理尽可能少的分支。

---

现在这假设您有一个全面的枚举。但如果你不这样做呢？

答案是我描述的分析可以针对您可能的一组输入的随机样本进行。因此，如果您使用 10,000 个随机输入运行您的代码，那么您将为您的第一级提供相当好的熵。在您的第二级重复 10,000 个分支，同样的情况也会发生。只要计算上可行就继续。

如果有好的模式可以找到，你会很快找到很多形式的模式，“如果你把这个和那个放在一起，这就是你总是得到的输出。” 如果有一组相当短的嵌套 if 可以提供正确的输出，那么您可能会找到它。之后，您需要决定是手动验证每个存储桶是否可靠，还是相信如果您在 10,000 个随机输入中找不到任何异常，那么就找不到任何异常。

---

验证的棘手方法。如果您可以找到为您的语言编写的模糊测试软件，请运行模糊测试软件，目标是尝试为您找到的每个存储桶梳理出所有可能的内部执行路径。如果 fuzzing 软件认为您无法从上述方法中获得与您认为最好的答案不同的答案，那么您可能可以信任它。