将复杂的过滤器规则简化为可比较的形式 [英] Reducing complex filter rules to a comparable form

问题描述

我想确定整数输入数组是否匹配一组规则。

匹配器

Matcher 是通过一组帮助器方法构建的，用于描述输入数据的规则。这些规则本质上是整数数组上的逻辑门：

  AND（1，2）//需要同时存在1和2在输入数组中。 
 OR（3，4，5）//要求输入数组中存在3 OR 4 OR 5。 
 NOR（6，7）//要求输入数组中不存在6 NOR 7。 
 XOR（8，9）//要求输入数组中存在8（X）OR 9，但不能两者都存在。 
  

因此，鉴于输入数组，我可以这样说：

  [0，1，2，3] 
  

我可以构建一个 Matcher ，例如：

  AND（OR （0，1），AND（1，2）NOR（4））
  

与输入，因为输入满足：

  OR（0，1）// 0或1存在
 AND（ 1，2）// 1和2都存在
 NOR（4）// 4不存在
  

并且每个累积地满足总体的 AND 规则。

问题

我需要将匹配器简化为仍然描述规则的最简单，最基本的形式。例如，给定上述匹配项，样本减少量可能为：

 规则= {
或：[1， 2]，
 xor：[]，//没有XOR 
或：[4] 
} 
  

每个规则有三个子规则数组，由整数或规则组成

请注意OR为空，因为无论如何都需要 1 ，这意味着 OR（0，1）=> [0，1] 是多余的，因为必须满足。

因为 Matcher s必须具有可比性（我需要能够确定基本规则之间的等价关系），当我达到以下条件时，它会变得更加复杂：

  input = [1、2、5、9、11、12、13、14、17] 
 
 XOR（OR（AND（1，2），NOR（3， 4），XOR（3 11），AND（11、14）），AND（1、5、17））
  

现在，其中很多是多余的和/或自相矛盾的，所以我想我能做的就是首先将其放入树状结构中，然后递归并减少不必要的条目。我有什么更好的方法吗？

我特别在寻找确定性的东西（任何表示相同事物产生相同最终归约形式的输入规则） ）。如果有更好的方法来表达此问题，我很感兴趣，并且如果规则相互矛盾，则reduce可以打破并抛出异常。

解决方案

您实际要处理的内容这是命题逻辑。根据命题在输入数组中是否存在，将其视为假或真整数。

您的约束（XOR，AND等）随后形成逻辑是否可以满足的公式。实际上，对于任何给定的公式都很难弄清楚它是否可以满足要求。但是，乍一看，这应该与您无关，因为您只需要检查给定的输入是否满足该公式即可。

不幸的是，您实际上要问的是如何确定两个命题公式是否相等。事实证明，这同样困难： https://math.stackexchange.com/questions/1050127/how-to-effective-determine-if-any-two-propositional-formulas-are-equivalent

I want to determine whether or not an input array of integers "matches" a set of rules.

The Matcher

The Matcher is built from a set of helper methods to describe rules for input data. These rules are essentially logic gates on arrays of integers:

AND(1, 2) // Requires both 1 AND 2 be present in the input array.
OR(3, 4, 5) // Requires that 3 OR 4 OR 5 be present in the input array.
NOR(6, 7) // Requires that neither 6 NOR 7 be present in the input array.
XOR(8, 9) // Requires that either 8 (X)OR 9 be present in the input array, but not both.

Thus, I could say that, given the input array:

[0, 1, 2, 3]

I could build a Matcher like:

AND(OR(0, 1), AND(1, 2) NOR(4))

Which would match the input, because the input satisfies:

OR(0, 1) // 0 or 1 is present
AND(1, 2) // Both 1 and 2 are present
NOR(4) // 4 is not present

And each of those cumulatively satisfies the overarching AND rule.

The Problem

I need to reduce matchers to the simplest and most basic form that still describes the rules. For example, given the above matcher, a sample reduction could be:

rules = {
  or: [1, 2],
  xor: [], // No XORs
  nor: [4]
}

Each rule has three arrays of sub-rules, comprised of integers or rules.

Notice that the ORs are empty, because 1 is required anyways, which means OR(0, 1) => [0, 1] is redundant because it must be satisfied.

Since Matchers need to be comparable (I need to be able to determine an equivalence between the underlying rules), it becomes a bit more complicated when I get to:

input = [1, 2, 5, 9, 11, 12, 13, 14, 17]

XOR(OR(AND(1, 2), NOR(3, 4), XOR(3 11), AND(11, 14)), AND(1, 5, 17))

Now, a large amount of that is redundant and/or contradictory, so what I was thinking I could do was first place it into a tree-like structure, and then recurse it and reduce unnecessary entries. Any ideas for a better way to do this?

I'm specifically looking for something deterministic (any set of input rules that mean the same thing yield the same final reduced form). If there is a better way to express this problem, I'm interested, and if rules are contradictory it's fine for the reducer to break and throw an exception. This is intended for occasional use in the program, so performance is not much of an issue.

解决方案

What you are actually dealing with here is propositional logic. Consider the integer your propositions being either false or true depending on whether they are present in the input array.

Your constraints (XOR, AND, etc.) then form a logical formula that is either satisfiable or not. It is in fact hard to figure out for any given formula whether it is satisfiable. However, at first sight this shouldn't concern you because you only have to check whether a given input satisfies the formula.

Unfortunately what you are actually asking is how you can determine whether two propositional formulas are equivalent. It turns out this is equally hard: https://math.stackexchange.com/questions/1050127/how-to-efficiently-determine-if-any-two-propositional-formulas-are-equivalent

这篇关于将复杂的过滤器规则简化为可比较的形式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！