Генерация хеш-функций программно

Question

У меня есть очень старый устаревший процедурный код, который принимает 10 или около того перечислимых входных данных [i0, i1, i2, ... i9] и генерирует 170 нечетных перечислимых выходных данных [r0, r1, ... r168, r169].Под перечислением я подразумеваю, что каждый отдельный вход и выход имеет свой собственный набор различных наборов значений, например [красный, зеленый, желтый] или [да, нет] и т. Д.

Я собираю всю таблицу состоянийиспользуя существующий код, и вместо того, чтобы ломать голову над ними вручную, мне было интересно, существует ли алгоритмический способ определения подходящей функции для получения каждого результата из 10 входов.Обратите внимание, что не все входные столбцы могут потребоваться для определения отдельного выходного столбца, т. Е. R124 может зависеть только от i5, i6 и i9.

Это не непрерывные функции, и я ожидаю, что в конечном итоге у меня получится какой-то подход с использованием функции хеширования, но я подумал, знает ли кто-нибудь о более повторяемом процессе, который я должен использовать вместо этого?(Если бы был какой-то подход, аналогичный карте Карно, для недвоичных функций с несколькими значениями ;-))

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. Ваш алгоритм начнёт с переключения набора значений этой переменной.

Затем для каждого значения вы повторяете этот процесс, чтобы получить каскадные вложенные условия.

Как правило, это приводит к довольно компактному набору каскадных вложений, если условия, которые будут сосредоточены на входных переменных, сообщают вам как можно больше, как можно быстрее, с минимальным количеством ветвей, которыми вы можете управлять.

---

Теперь это предполагало, что у вас было полное перечисление. Но что, если вы этого не сделаете?

Ответ на этот вопрос заключается в том, что описанный мною анализ может быть выполнен для случайной выборки из вашего возможного набора входных данных. Поэтому, если вы запустите свой код, скажем, с 10 000 случайных входов, то вы получите довольно хорошие энтропии для вашего первого уровня. Повторите с 10 000 каждой из ваших веток на втором уровне, и то же самое произойдет. Продолжайте, пока это возможно в вычислительном отношении.

Если есть хорошие шаблоны для поиска, вы быстро найдете множество шаблонов в форме: «Если вы добавите то и другое, вот результат, который вы всегда получаете». Если есть достаточно короткий набор вложенных if, которые дают правильный вывод, вы, вероятно, найдете его. После этого у вас возникает вопрос о том, нужно ли на самом деле вручную проверять надежность каждого сегмента или полагать, что если вы не смогли найти каких-либо исключений с 10 000 случайных входов, то их не найти.

---

Хитрый подход к валидации. Если вы можете найти программное обеспечение для фаззинга, написанное для вашего языка, запустите программное обеспечение для фаззинга, чтобы попытаться выявить все возможные внутренние пути выполнения для каждого сегмента, который вы найдете. Если программное обеспечение fuzzing решит, что вы не можете получить ответы, отличные от того, который, по вашему мнению, лучше всего подходит для вышеуказанного подхода, то вы, вероятно, можете ему доверять.

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();
    }
}