高效存储和评估大量布尔表达式

Question

我有一个包含20,000个布尔表达式的庞大集合。它们由AND、OR和NOT运算符组成，以及大量布尔变量A1、A2、A3......（大约1000个）。大多数表达式仅包含这些变量中的5个，最多不超过20个。

给定变量的赋值（A1=true，A2=false，A3=false......），我必须找到那些计算结果为false的表达式。

使用相同的表达式集将对多个（10-100）赋值进行评估。

为此目的：

1. 我应该如何将表达式存储到磁盘上，以便快速加载和解析它们（我目前将它们作为一些专门的DSL或更规范化（但速度很慢）的关系数据结构，但我可以更改它）？

2. 是否有用于评估此类表达式的快速算法/数据结构可供使用？

3. JVM上是否存在实现？

- Jens Schauder

---

你看过Lucene吗？至于算法...可以看一下稀疏位集（java.util.Bitset类不是稀疏的，但非常快速，对于你处理的相对较小的数字可能还可以）。 - Stevie

看一下二叉决策图（BDDs）。它们专门设计用于简化和验证集成电路的布尔逻辑。 - wildplasser

@ChrisGerken 我更新了问题：同一组表达式将用于多个（10-100）赋值的计算。 - Jens Schauder

@wildplasser 看起来是一个有用的结构，但我如何构建一个好的结构呢？维基百科上说这是 NP 难的，而且存在有效的启发式算法，但没有提示是什么。 - Jens Schauder

只有排序是NP完全问题。大多数“随机”问题都会合理地形成；只有少数会很恶劣。我预计你的“多根”问题将来自这个家族中的好类型。Bryant论文是一个很好的介绍，必读之作。 - wildplasser

Answer 1

你可能需要将表达式转换为合取范式并合并类似项。然后，您可以将表达式双向映射到一组术语，其中任何一个术语的计算结果为false都意味着整个表达式的计算结果为false。对于每个变量的赋值，从一组表达式开始，评估CNF术语，直到其中一个术语计算结果为false。如果该术语为false，则涉及该术语的所有表达式也将为false，因此这些表达式也可以从该组中删除。 无法在未查看表达式的情况下确定此方法是否适用于您的情况-对于具有1000个变量和20000个表达式的情况，它们可能没有许多共同的CNF术语。 在Java之外，对于更大数量的表达式，DNF可能更有用，因为它在GPU上的实现很明显。

- Pete Kirkham

Answer 2

这个问题的标准操作程序是将表达式以字符串形式存储在逆波兰表示法（RPN）中，然后编写一个简单的堆栈机器解析器来评估它们。

通常情况下，RPN字符串可以被评估得几乎和已经在内存中的AST（抽象符号树）一样快。而且，堆栈机器解析器非常容易编写。

- RBarryYoung

Answer 3

你似乎很喜欢Java，但是你考虑过将这些东西传递给一个具有eval()函数的语言吗？这可能会将问题简化为在文件中保存表达式并对其进行评估。请注意，如果您不信任（表达式的来源），这会带来安全隐患！

Jython是一个不错的选择，但可能还有其他几种语言可以轻松解决这个问题。

如果你非常喜欢Java，你可能可以实现一个递归下降解析器来处理布尔代数。但这需要更多的工作。

- user1277476

---

我对Java有一定的依赖性，甚至更依赖JVM，因为其他任何语言都会在这里引起知识和部署问题。只要结果快速，我不害怕实现解析器。 - Jens Schauder

Answer 4

更新：以下网站code可能会有所帮助。

将您的表达式列表转换为源代码，以便创建一个函数。当使用变量值调用该函数时，它将评估所有函数并返回哪些表达式计算结果为false。编译该函数，然后为不同的变量值调用它。

我曾经做过类似的事情，并使用了Python。我需要编写的唯一解析和解释是将输入布尔运算符'&', '|', '~'转换为它们在Python中的等效项。

对于Python解决方案来说，您的问题规模似乎相当不错。

- Paddy3118

---

关于这个链接：对我来说，1000个输入参数的真值表听起来不是一个好主意。 - Jens Schauder

这个问题不是关于生成真值表的。链接中有用于表示和评估布尔表达式的代码。有时候你需要提取你需要的内容，因为完整的答案并没有直接给出。 - Paddy3118

Answer 5

你可以建立一个索引，对于每个变量，记录两组表达式，其中一组是变量正向出现的表达式，另一组是变量负向出现的表达式。根据变量的值，收集那些可能会由于此变量变为假的表达式（如果变量设置为假，则为正向出现；反之为负向出现）。 编辑：这些只是候选项，您仍然需要评估它们以确定它们是否真的变为假。

这是否有助于与仅评估所有表达式相比取决于您表达式的结构以及有多少表达式评估为假。

- starblue

---

表达式(a&b)|(!a&c)对于a来说是在正集还是负集中？如果给定一组值a、b、c，如何收集相应的表达式而不必完全评估它们？ - Pete Kirkham

@Pete Kirkham 表达式中会同时存在正负，因为 a 在路径到达表达式根节点时既有偶数次否定也有奇数次否定。 - starblue

那么如果a是false，如何同时判断表达式的真假呢？ - Pete Kirkham

Answer 6

尝试将它们转换为CNF，并使用MiniSat检查表达式是否为真或假。

- Maurice