提问人:user733321 提问时间:5/1/2011 最后编辑:user733321 更新时间:5/2/2011 访问量:2685
出于缓存原因规范化布尔表达式。有没有比真值表更有效的方法?
normalize boolean expression for caching reasons. is there a more efficient way than truth tables?
问:
我目前的项目是一个具有布尔检索功能的高级标签数据库。使用布尔表达式查询记录,如下所示(例如,在音乐数据库中):
funky-music and not (live or cover)
这应该在音乐数据库中产生所有时髦的音乐,但不能产生歌曲的现场或翻唱版本。
当涉及到缓存时,问题在于存在等效但结构不同的查询。例如,应用 de Morgan 规则,上面的查询可以这样写:
funky-music and not live and not cover
这将产生完全相同的记录,但当缓存通过对查询字符串进行哈希处理来实现时,会导致中断缓存。
因此,我的第一个意图是创建一个查询的真值表,然后可以将其用作缓存键,因为等效表达式构成了同一个真值表。不幸的是,这是不切实际的,因为真值表随着输入(标签)的数量呈指数增长,我不想限制一个查询中使用的标签数量。
另一种方法是遍历语法树,应用布尔代数定义的规则来形成(最小)规范化表示,这似乎也很棘手。
因此,总体问题是:有没有一种可行的方法可以实现对等效查询的识别,而不需要电路最小化或真值表(编辑:或任何其他NP硬算法)?
ne plus ultra 将识别已经缓存的子查询,但这不是主要目标。
答:
用于确定查询是否等同于“False”的通用且有效的算法可用于有效地解决 NP 完全问题,因此您不太可能找到一个。
您可以尝试将查询转换为规范形式。由于上述原因,总会有一些查询在转换为任何给定形式时都非常昂贵,但您可能会发现,在实践中,某些形式在大多数时候都运行良好 - 如果它变得太难,您总是可以在转换中途放弃。
你可以看看 http://en.wikipedia.org/wiki/Conjunctive_normal_form、http://en.wikipedia.org/wiki/Disjunctive_normal_form http://en.wikipedia.org/wiki/Binary_decision_diagram。
评论
您可以将查询转换为连词范式 (CNF)。它是布尔公式的规范、简单表示,通常是 SAT 求解器的基础。
最有可能的是,“大型”查询将有很多连词(而不是很多不连词),因此 CNF 应该可以很好地工作。
评论
Quine-McCluskey 算法应该可以实现您正在寻找的目标。它类似于 Karnaugh 的地图,但更容易在软件中实现。
评论
下一个:摩尔机的状态图和过渡表
评论