复杂的布尔表达式优化，范式？

Question

我正在开发一个流规则引擎，我的一些客户有几百条规则，他们想对到达系统的每个事件进行评估。规则是纯（即无副作用）布尔表达式，它们可以任意深度嵌套。

客户在运行时创建、更新和删除规则，我需要动态检测和适应规则的数量。目前，表达式计算在内部 AST 上使用解释器，我还没有开始考虑 codegen。

与往常一样，树中的某些谓词的计算成本比其他谓词要便宜得多，而且我一直在寻找一种算法或数据结构，以便更容易找到便宜的谓词，并且可以有效地解释为控制整个表达。我对这种模式的心理标题是“ANDs all way to the root”，即所有祖先都是ANDs的任何谓词都可以解释为控制。

尽管进行了几天的文献搜索，阅读了有关 ROBDD、CNF、DNF 等的信息，但我还是无法从行业中的常见做法到我的特定用例关闭循环。我发现似乎相关的一件事是布尔表达式索引的分析和优化， 但不清楚如何在不自己实现 BE-Tree 数据结构的情况下应用它，因为似乎没有开源实现。

我一直半开玩笑地向我的团队提到，这些天我们将需要一个 SAT 求解器。我想编写一个遍历树并跟踪每个祖先是 AND 还是 OR 的递归算法可能就足够了，但我一直有“这肯定是一个已解决的问题”的感觉。:)

编辑：与几个朋友交谈后，我想我可能有一个解决方案的草图！

1. 将表达式转换为联合范式，根据定义，其中每个节点都处于有效的短路位置。
2. 使用 Tseitin 算法尽量避免 CNF 变换导致的表达式大小的指数膨胀
3. 对于树中的每个AND，按成本升序排序（即最便宜的到左边）
4. ？？？
5. 利润！^Weval 像往常一样:)

Answer 1

您应该认真考虑编译规则（和谓词）。对于同样的事情，解释器比机器代码慢 10-50 倍。如果规则集不经常更改，这是一个好主意。如果规则可以动态改变，这甚至是一个好主意，因为实际上它们仍然不会改变得很快，尽管现在你的规则编译器已经在线。嗯，只是为了更大的应用程序，内存不再是一个问题了。

使用单独的机器指令进行布尔表达式评估甚至更好。任何复杂的布尔方程都可以编译为叶值上各个机器指令的无分支序列。无分支，无缓存未命中；东西运行得非常快。现在，如果您有昂贵的谓词，您可能希望使用分支来编译代码，以跳过不影响表达式结果的子树（如果它们包含昂贵的谓词）。

在合理范围内，你可以生成任何等效的形式（我会因为使用 CNF 的想法而尖叫到深夜，因为它总是会在你身上爆炸）。您真正想要的是与客户端提供的等效的最短布尔方程（最深的表达式树），因为这将需要最少的机器指令来执行。这可能听起来很疯狂，但您可能会考虑详尽的搜索代码生成，例如，从字面上尝试有可能起作用的每个组合，特别是当方程中的运算符数量相对较小时。VLSI 界一直在努力将布尔方程合成为门时进行各种优化。您应该研究 Espresso 色调布尔逻辑优化器（https://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer）

可能推动表达式求值的一件事实际上是谓词的成本。如果我有公式 A 和 B，并且我知道 A 的评估成本很高并且通常返回 true，那么显然我想评估B 和 A。

您应该考虑公共子表达式求值，以便任何公共子项仅计算一次。当谓词代价昂贵时，这一点尤其重要；你永远不想对同一个昂贵的谓词求值两次。

大约 20 年前，我在 PLC 仿真器（这些基本上是评估布尔方程的桶（如数十万个）告诉工厂执行器何时移动的机器）中使用罗克韦尔自动化的 AND/OR/NOT 的 x86 机器指令实现了这些技巧。它的运行速度超过了罗克韦尔公司的“顶级”PLC，后者拥有定制硬件，但本质上是一个解释器。

您还可以考虑对方程进行增量评估。基本思想不是一遍又一遍地重新评估所有方程，而是仅重新评估输入发生变化的那些方程。详细信息太长，无法在此包含，但我当时申请的一项专利解释了如何做到这一点。请参阅https://patents.google.com/patent/US5623401A/en?inventor=Ira+D+Baxter&oq=Ira+D+Baxter