复杂的布尔表达式优化，正常形式？
Complex Boolean expression optimization, normal forms?
我正在开发流式规则引擎，我的一些客户有几百条规则，他们希望对到达系统的每个事件进行评估。规则是纯（即non-side-effecting）布尔表达式，可以任意深度嵌套。
客户在运行时创建、更新和删除规则，我需要动态检测和适应规则的数量。目前，表达式求值在内部 AST 上使用解释器，我还没有开始考虑 codegen。
一如既往，树中的一些谓词比其他谓词更容易评估，我一直在寻找一种算法或数据结构，可以更容易地找到便宜的谓词，并且是有效地解释为控制整个表达式。我对这种模式的心理标题是“ANDs all the way to the root”，即所有祖先都是 ANDs 的任何谓词都可以解释为控制。
尽管进行了几天的文献搜索，阅读了有关 ROBDD、CNF、DNF 等的信息，但我仍然无法从行业中的常见做法到我的特定用例来关闭循环。我发现似乎相关的一件事是 Analysis and optimization for boolean expression indexing
但不清楚如何在不自己实现 BE-Tree 数据结构的情况下应用它，因为似乎没有开源实现。
我一直 half-jokingly 向我的团队提及，有一天我们将需要一个 SAT 求解器。我想编写一个遍历树并跟踪每个祖先是 AND 还是 OR 的递归算法可能就足够了，但我一直有“这肯定是一个已解决的问题”的感觉。 :)
编辑：与几个朋友交谈后，我想我可能有一个解决方案的草图！
- 将表达式转换为合取范式，其中，根据定义，每个节点都在有效的short-circuit位置。
- 使用 Tseitin 算法尽量避免 CNF 变换导致表达式大小呈指数级增长
- 对于树中的每个 AND，按成本升序排序（即最便宜的到左边）
- ???
- 盈利！^我们一如既往:)
你应该认真考虑编译规则（和谓词）。对于同样的事情，解释器比机器代码慢 10-50 倍。如果规则集不经常更改，这是一个好主意。如果规则可以动态更改甚至是一个好主意，因为在实践中它们仍然不会很快更改，尽管现在您的规则编译器已经在线。嗯，只需要一个更大的应用程序，内存就不是什么大问题了。
使用单个机器指令的布尔表达式求值甚至更好。任何复杂的布尔方程都可以在叶值上以单个机器指令的无分支序列进行编译。没有分支，没有缓存未命中；东西 运行 非常快。现在，如果您有昂贵的谓词，您可能希望编译带有分支的代码以跳过不影响表达式结果的子树，如果它们包含昂贵的谓词。
在合理的范围内，您可以生成任何等效形式（我会 运行 为使用 CNF 的想法尖叫到深夜，因为它总是让您大吃一惊）。你真正想要的是最短的布尔方程（最深的表达式树）等同于客户提供的，因为这将需要最少的机器指令来执行。这听起来可能很疯狂，但您可能会考虑穷举搜索代码生成，例如，逐字逐句地尝试每一种有可能起作用的组合，尤其是当等式中的运算符数量相对较少时。将布尔方程合成为门时，VLSI 界一直在努力进行各种优化。您应该查看 Espresso hueristic 布尔逻辑优化器 (https://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer)
可能驱使您进行表达式评估的一件事就是谓词的成本。如果我有公式 A 和 B，并且我知道 A 的计算成本通常 and returns true，那么显然我想评估 B 和 A。
您应该考虑公共子表达式求值，以便任何公共子项只计算一次。当一个人有昂贵的谓词时，这一点尤其重要；您永远不想对同一个昂贵的谓词求值两次。
我在 PLC 仿真器中实现了这些技巧（这些基本上是评估桶 [如数十万] 布尔方程的机器，告诉工厂执行器何时移动）使用 AND/OR/NOT 罗克韦尔自动化的 x86 机器指令大约20年前。它超越了罗克韦尔的“高级”PLC，后者具有定制硬件但本质上是一个解释器。
您还可以考虑对方程式进行增量评估。基本思想不是一遍又一遍地重新计算所有方程，而是仅重新计算输入 已更改 的那些方程。细节太长，无法包含在这里，但我当时所做的一项专利解释了如何做。参见 https://patents.google.com/patent/US5623401A/en?inventor=Ira+D+Baxter&oq=Ira+D+Baxter
我正在开发流式规则引擎，我的一些客户有几百条规则，他们希望对到达系统的每个事件进行评估。规则是纯（即non-side-effecting）布尔表达式，可以任意深度嵌套。
客户在运行时创建、更新和删除规则，我需要动态检测和适应规则的数量。目前，表达式求值在内部 AST 上使用解释器，我还没有开始考虑 codegen。
一如既往，树中的一些谓词比其他谓词更容易评估，我一直在寻找一种算法或数据结构，可以更容易地找到便宜的谓词，并且是有效地解释为控制整个表达式。我对这种模式的心理标题是“ANDs all the way to the root”，即所有祖先都是 ANDs 的任何谓词都可以解释为控制。
尽管进行了几天的文献搜索，阅读了有关 ROBDD、CNF、DNF 等的信息，但我仍然无法从行业中的常见做法到我的特定用例来关闭循环。我发现似乎相关的一件事是 Analysis and optimization for boolean expression indexing 但不清楚如何在不自己实现 BE-Tree 数据结构的情况下应用它，因为似乎没有开源实现。
我一直 half-jokingly 向我的团队提及，有一天我们将需要一个 SAT 求解器。我想编写一个遍历树并跟踪每个祖先是 AND 还是 OR 的递归算法可能就足够了，但我一直有“这肯定是一个已解决的问题”的感觉。 :)
编辑：与几个朋友交谈后，我想我可能有一个解决方案的草图！
- 将表达式转换为合取范式，其中，根据定义，每个节点都在有效的short-circuit位置。
- 使用 Tseitin 算法尽量避免 CNF 变换导致表达式大小呈指数级增长
- 对于树中的每个 AND，按成本升序排序（即最便宜的到左边）
- ???
- 盈利！^我们一如既往:)
你应该认真考虑编译规则（和谓词）。对于同样的事情，解释器比机器代码慢 10-50 倍。如果规则集不经常更改，这是一个好主意。如果规则可以动态更改甚至是一个好主意，因为在实践中它们仍然不会很快更改，尽管现在您的规则编译器已经在线。嗯，只需要一个更大的应用程序，内存就不是什么大问题了。
使用单个机器指令的布尔表达式求值甚至更好。任何复杂的布尔方程都可以在叶值上以单个机器指令的无分支序列进行编译。没有分支，没有缓存未命中；东西 运行 非常快。现在，如果您有昂贵的谓词，您可能希望编译带有分支的代码以跳过不影响表达式结果的子树，如果它们包含昂贵的谓词。
在合理的范围内，您可以生成任何等效形式（我会 运行 为使用 CNF 的想法尖叫到深夜，因为它总是让您大吃一惊）。你真正想要的是最短的布尔方程（最深的表达式树）等同于客户提供的，因为这将需要最少的机器指令来执行。这听起来可能很疯狂，但您可能会考虑穷举搜索代码生成，例如，逐字逐句地尝试每一种有可能起作用的组合，尤其是当等式中的运算符数量相对较少时。将布尔方程合成为门时，VLSI 界一直在努力进行各种优化。您应该查看 Espresso hueristic 布尔逻辑优化器 (https://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer)
可能驱使您进行表达式评估的一件事就是谓词的成本。如果我有公式 A 和 B，并且我知道 A 的计算成本通常 and returns true，那么显然我想评估 B 和 A。
您应该考虑公共子表达式求值，以便任何公共子项只计算一次。当一个人有昂贵的谓词时，这一点尤其重要；您永远不想对同一个昂贵的谓词求值两次。
我在 PLC 仿真器中实现了这些技巧（这些基本上是评估桶 [如数十万] 布尔方程的机器，告诉工厂执行器何时移动）使用 AND/OR/NOT 罗克韦尔自动化的 x86 机器指令大约20年前。它超越了罗克韦尔的“高级”PLC，后者具有定制硬件但本质上是一个解释器。
您还可以考虑对方程式进行增量评估。基本思想不是一遍又一遍地重新计算所有方程，而是仅重新计算输入 已更改 的那些方程。细节太长，无法包含在这里，但我当时所做的一项专利解释了如何做。参见 https://patents.google.com/patent/US5623401A/en?inventor=Ira+D+Baxter&oq=Ira+D+Baxter