出于缓存原因规范化布尔表达式。有没有比真值表更有效的方法?

normalize boolean expression for caching reasons. is there a more efficient way than truth tables?

提问人:user733321 提问时间:5/1/2011 最后编辑:user733321 更新时间:5/2/2011 访问量:2685

问:

我目前的项目是一个具有布尔检索功能的高级标签数据库。使用布尔表达式查询记录,如下所示(例如,在音乐数据库中):

funky-music and not (live or cover)

这应该在音乐数据库中产生所有时髦的音乐,但不能产生歌曲的现场或翻唱版本。

当涉及到缓存时,问题在于存在等效但结构不同的查询。例如,应用 de Morgan 规则,上面的查询可以这样写:

funky-music and not live and not cover

这将产生完全相同的记录,但当缓存通过对查询字符串进行哈希处理来实现时,会导致中断缓存。

因此,我的第一个意图是创建一个查询的真值表,然后可以将其用作缓存键,因为等效表达式构成了同一个真值表。不幸的是,这是不切实际的,因为真值表随着输入(标签)的数量呈指数增长,我不想限制一个查询中使用的标签数量。

另一种方法是遍历语法树,应用布尔代数定义的规则来形成(最小)规范化表示,这似乎也很棘手。

因此,总体问题是:有没有一种可行的方法可以实现对等效查询的识别,而不需要电路最小化或真值表(编辑:或任何其他NP硬算法)?

ne plus ultra 将识别已经缓存的子查询,但这不是主要目标。

算法 规范 遍历布尔 逻辑

评论

0赞 Dan 5/1/2011
使用按位键 -- 例如。set bit 0 if funky|bit 6 0 = live/1 = studio|bit 8 rap|bit 9 pop 那么你使用按位运算来确定查询时的键表示有意义吗?
0赞 Dan 5/1/2011
这是移动开发 API 中的常见模式 -- createScreen(long style_element),其中长style_element是所述按位操作的最终结果,并为所述 Screen 对象规定了数不清的(真正的 lol)样式元素
0赞 user733321 5/2/2011
这将是将信息存储在数据库中的一种节省内存的方法。但这是一个完全不同的话题。
0赞 Dan 5/2/2011
每个 long 代表所选属性集合的唯一 ID -- 也许我不明白你的问题哈哈 -- neeeed coffeeee
1赞 user733321 5/2/2011
好吧,至少我不明白:D

答:

1赞 mcdowella 5/1/2011 #1

用于确定查询是否等同于“False”的通用且有效的算法可用于有效地解决 NP 完全问题,因此您不太可能找到一个。

您可以尝试将查询转换为规范形式。由于上述原因,总会有一些查询在转换为任何给定形式时都非常昂贵,但您可能会发现,在实践中,某些形式在大多数时候都运行良好 - 如果它变得太难,您总是可以在转换中途放弃。

你可以看看 http://en.wikipedia.org/wiki/Conjunctive_normal_formhttp://en.wikipedia.org/wiki/Disjunctive_normal_form http://en.wikipedia.org/wiki/Binary_decision_diagram

评论

0赞 user733321 5/2/2011
创建您提到的那些形式还涉及创建真值表。因此,我可以简单地使用真值表的规范化形式(输入和组合排序)的哈希值作为缓存键。似乎最好的方法是为涵盖少于 10 个标签左右的查询创建一个“最佳”哈希值,而对于包含更多标签的查询,则创建一个更简单但不是最佳算法的哈希值。
0赞 mcdowella 5/2/2011
您应该能够纯粹象征性地获得这些形式中的任何一种。给定任何两种形式的表达式,您可以通过 AND 或 OR 计算出组合这些表达式的结果,结果将采用相同的形式。你可以用 NOT 做同样的事情。在某些情况下,结果会很复杂,但这是可能的。对于 BDD,应该有库来做到这一点 - 例如参见 javabdd.sourceforge.net/apidocs/net/sf/javabdd/BDD.html。因此,您可以通过组合各个变量的表示来构建表示。
0赞 user733321 5/2/2011
但我看不出这将如何规避对 NP 完备算法的需求。
1赞 Antti Huima 5/2/2011 #2

您可以将查询转换为连词范式 (CNF)。它是布尔公式的规范、简单表示,通常是 SAT 求解器的基础。

最有可能的是,“大型”查询将有很多连词(而不是很多不连词),因此 CNF 应该可以很好地工作。

评论

0赞 user733321 5/2/2011
因此,构建“非最坏情况查询”的 CNF 会比 NP 简单吗?你有关于如何实现转换的参考吗?常见的算法似乎涉及太复杂的真值表。
0赞 blubb 5/2/2011 #3

Quine-McCluskey 算法应该可以实现您正在寻找的目标。它类似于 Karnaugh 的地图,但更容易在软件中实现

评论

0赞 user733321 5/2/2011
与 antti.huima 相同。它太复杂了,效率不高,对吧?