算法来检测冗余规则 [英] Algorithm to detect redundant rules

问题描述

我在寻找一种算法来检测多余的规则。

I am looking for an algorithm to detect redundant rules.

规则有输入参数的固定数目和每个参数具有不同的域

Rules have a fixed number of input parameters and each parameter has a distinct domain.

考虑三个规则参数颜色，材料和尺寸：

Consider three rule parameters Color, Material and Size:

• 颜色：红，绿，蓝
• 材料：木材，玻璃，铝
• 尺寸：小，中，大

• Color: Red, Green, Blue
• Material: Wood, Glass, Aluminium
• Size: Small, Medium, Large

每个规则可以在任意值的参数或匹配多个值相匹配。在首先规则匹配的所有的参数值被选中。有没有的否定的规则，但域是固定的，因此否定可以通过添加的所有其他人来实现的。

Each rule can match on multiple values of a parameter or match on any value. The first rule that matches all parameters values is selected. There are no negation rules, but the domain is fixed, so a negation can be achieved by added all others.

       +--------------------------------------------------++-----------------
       |                   Rule Parameters                || Rule Action
       +----------------+------------------+--------------++-----------------
       | Color          | Material         | Size         || ==> Price
       +----------------+------------------+--------------++-----------------
Rule 1 | Red            | Wood, Glass      | Large        || $100
Rule 2 | Red            | Aluminium        | Large        || $200
Rule 3 | Blue or Green  | Wood             | Medium       || $300
Rule 4 | Red            | ** Any **        | Large        || $400  <== Redundant
Rule 5 | ** Any **      | ** Any **        | ** Any **    || $500

第4条是多余的，由于第1和第2冗余规则的组合是之前从来没有的因（组合）匹配的规则统治的 EM>这条规则。该规则操作未在冗余检查评估。

Rule 4 is redundant due to a combination of Rule 1 and 2. A redundant rule is a rule that will never be matched due to (a combination) of rules defined before that rule. The rule action is not evaluated in the redundancy check.

如何实现这个有效（在Java中）？它应该支持1000个规则，10个参数，每个100个值。规则，参数和参数值是从一个数据库中读出（即它们不能是硬codeD）。

How to implement this efficiently (in Java)? It should support 1000 rules with 10 parameters with 100 values each. The rules, parameters and parameter values are read from a database (ie. they cannot be hard-coded).

这个问题的效率的是，有 100 ^ 10个组合输入参数（每个参数有100个值域）。该算法需要在规则编辑器图形用户界面，以支持正在创建规则的用户。它应该找到秒钟之内的所有多余的规则。

The issue with efficiency is that there are 100^10 combinations of input parameters (each parameter has a domain of 100 values). The algorithm is needed in the rule editor gui, to support the user that is creating the rules. It should find all redundant rules within seconds.

我创建了一个信息库，以测试提出了解决方案： https://github.com/qlp/redundant -rules 目前仅BDD的实现，这是失败与这种规模的问题。也许我的BDD的实施可以改善？

I've created a repository to test proposed solutions: https://github.com/qlp/redundant-rules Currently only a BDD implementation, which is failing with a problem of this size. Maybe my BDD implementation can be improved?

推荐答案

从本质上讲，你与执行决策树任务。树的每个级别对应于每个参数，并且在每个级别，将会有每一个值，该参数可容纳的节点。在叶级，你将存储的规则操作，这是适用的。

Essentially, you're tasked with implementing a decision tree. Each level of the tree corresponds to each parameter, and at each level, there will be a node for each value that the parameter could hold. At the leaf level, you would store the rule action that was applicable.

例如，在色彩层次，你有3个节点，红，蓝，绿。其中每一个都会有3个孩子（在物质层面）木材，玻璃，铝。其中每一个都会有3个孩子（小，中，大）。你会构建该树的基础上学习从数据库的参数和值。

For example, at the Color level, you'd have 3 nodes, Red, Blue, Green. Each of those would have 3 children (on the Material level) Wood, Glass, Aluminum. Each of those would have 3 children (Small, Medium, Large). You would construct this tree based on learning the parameters and values from the database.

在树的构建，你会从数据库中读取，一次一个的规则，并存储了规则操作'在每个叶片（在此情况下，在尺寸级别）。如果是想申请在叶子已经有一个操作的规则，那么出现混淆哪些规则将适用。对于你的问题，你说，你会采取这一应用的第一个规则 - 这样你就不会改变存储的规则。

Once the tree is constructed, you'd read the rules from the database, one at a time, and store the 'rule action' at each of the leaves (in this case, at the Size level). If there was a rule that wanted to apply at a leaf that already had an action, then there is an ambiguity about which rule would apply. For your problem you stated that you'd take the first rule that applied - so you would not change the rule stored.

如果有一个规则，其中对每一个叶子它有一个行动已经有了另外一个定义的动作，那么该规则将是多余的，根据你的榜样。

If there was a rule, where for each of the leaves it had an action for there already was a defined action, then that rule would be 'redundant' according to your example.

这篇关于算法来检测冗余规则的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！