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

Question

我有一些非常古老的遗留过程代码，它需要10个左右的枚举输入[i0，i1，i2，... i9]并生成170个枚举输出[r0，r1，... r168，r169]。通过枚举，我的意思是每个单独的输入和输出具有其自己的一组不同的值集，例如[红色，绿色，黄色]或[是，否]等

我正在使用现有的代码整理整个状态表，而不是手工弄乱它们，我想知道是否有一种算法方法来确定从10个输入获得每个结果的适当函数。注意，可能不需要所有输入列来确定单个输出列，即r124可能仅依赖于i5，i6和i9。

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

Answer 1

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

首先，考虑输出的entropy。假设你有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条件。

这通常会导致一组相当紧凑的级联嵌套，如果条件将集中在输入变量上，尽可能快地告诉您，并尽可能少地管理分支。

---

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

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

如果有好的模式可供查找，你会很快找到很多形式的模式，“如果你把它放在另一个，那么这就是你总是得到的输出。”如果有一组相当短的嵌套ifs给出正确的输出，你可能会找到它。在那之后，您有一个问题，即决定是否实际验证每个存储桶是否可靠，或者相信如果您找不到10,000个随机输入的任何异常，则无法找到任何存储空间。

---

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

Answer 2

算法非常简单。给定每个输入的可能值，我们可以生成所有可能的输入向量。然后，根据每个输出，我们可以消除无论输出无关的输入。结果，我们可以得到一个矩阵，显示所有输入组合的输出值，不包括对给定输出无关的输入。

样本输入格式（下面的代码片段）：

var schema = new ConvertionSchema()
{
    InputPossibleValues = new object[][]
    {
        new object[] { 1, 2, 3, }, // input #0
        new object[] { 'a', 'b', 'c' }, // input #1
        new object[] { "foo", "bar" }, // input #2
    },
    Converters = new System.Func<object[], object>[]
    {
        input => input[0], // output #0
        input => (int)input[0] + (int)(char)input[1], // output #1
        input => (string)input[2] == "foo" ? 1 : 42, // output #2
        input => input[2].ToString() + input[1].ToString(), // output #3
        input => (int)input[0] % 2, // output #4
    }
};

样本输出：

离开后面转换的核心。 Linqpad片段的完整代码是：http://share.linqpad.net/cknrte.linq。

public void Reverse(ConvertionSchema schema)
{
    // generate all possible input vectors and record the resul for each case
    // then for each output we could figure out which inputs matters

    object[][] inputs = schema.GenerateInputVectors();

    // reversal path
    for (int outputIdx = 0; outputIdx < schema.OutputsCount; outputIdx++)
    {
        List<int> inputsThatDoNotMatter = new List<int>();

        for (int inputIdx = 0; inputIdx < schema.InputsCount; inputIdx++)
        {
            // find all groups for input vectors where all other inputs (excluding current) are the same
            // if across these groups outputs are exactly the same, then it means that current input
            // does not matter for given output

            bool inputMatters = inputs.GroupBy(input => ExcudeByIndexes(input, new[] { inputIdx }), input => schema.Convert(input)[outputIdx], ObjectsByValuesComparer.Instance)
                .Where(x => x.Distinct().Count() > 1)
                .Any();

            if (!inputMatters)
            {
                inputsThatDoNotMatter.Add(inputIdx);
                Util.Metatext($"Input #{inputIdx} does not matter for output #{outputIdx}").Dump();
            }
        }

        // mapping table (only inputs that matters)
        var mapping = new List<dynamic>();

        foreach (var inputGroup in inputs.GroupBy(input => ExcudeByIndexes(input, inputsThatDoNotMatter), ObjectsByValuesComparer.Instance))
        {
            dynamic record = new ExpandoObject();

            object[] sampleInput = inputGroup.First();

            object output = schema.Convert(sampleInput)[outputIdx];

            for (int inputIdx = 0; inputIdx < schema.InputsCount; inputIdx++)
            {
                if (inputsThatDoNotMatter.Contains(inputIdx))
                    continue;

                AddProperty(record, $"Input #{inputIdx}", sampleInput[inputIdx]);

            }

            AddProperty(record, $"Output #{outputIdx}", output);

            mapping.Add(record);
        }

        // input x, ..., input y, output z form is needed
        mapping.Dump();
    }
}