由于缓存原因，将布尔表达式标准化。有没有比真值表更有效的方法？

| 我当前的项目是具有布尔检索功能的高级标记数据库。正在使用类似这样的布尔表达式来查询记录（例如在音乐数据库中）： 
funky-music and not (live or cover)
它将产生音乐数据库中所有时髦的音乐，但不包含歌曲的现场或翻唱版本。 当涉及到缓存时，问题在于存在相同但结构不同的查询。例如，应用de Morgan \规则，上面的查询可以这样写： 
funky-music and not live and not cover
例如，如果通过对查询字符串进行哈希处理来实现缓存，则这将产生完全相同的记录，但会导致中断缓存。 因此，我的首要目的是创建查询的真值表，然后将其用作缓存键，因为等效表达式形成了相同的真值表。不幸的是，这是不切实际的，因为真值表随输入（标签）的数量呈指数增长，我不想限制一个查询中使用的标签的数量。 另一种方法可能是遍历语法树，应用由布尔代数定义的规则以形成（最小）规范化表示，这似乎也很棘手。 因此，总的问题是：是否存在一种可行的方法来实现等效查询的识别，而无需电路最小化或真值表（编辑：或任何其他具有NP难点的算法）？ ne plus ultra将识别已经缓存的子查询，但这不是主要目标。     
2020-02-25 4 条评论
分享

没有找到相关结果

    已邀请:

    敦肌

    一种确定查询是否等同于“ 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。     
    2020-02-25 0 0
    分享

    吠强祷豪硅

    您可以将查询转换为合取范式（CNF）。它是布尔公式的规范，简单表示形式，通常是SAT求解器的基础。 最有可能的“大”查询将具有许多连词（而不是许多析取物），因此CNF应该可以很好地工作。     
    2020-02-25 0 0
    分享

    响摔衅幸

    Quine-McCluskey算法应该可以满足您的需求。它类似于卡诺地图，但更易于在软件中实现。     
    2020-02-25 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.036412954330444