我有一个类似以下示例的“或”模式： (XYZ) | (XYAB) | (XAK) | (MAJK) | (单克隆抗体) | (MZ)。 我的问题是我的实际问题的 OR'ed 操作数的数量是巨大的，并且会导致大量的内存消耗问题。
但是，形成模式本身的条目很少（X、Y、Z、A、B、K、M 和 J）。因此，将该模式转换（优化）为如下模式： (X ((Y (Z | (AB))) | (AK))) | (M ((A ((JK) | B)) | Z)) ，很可能会解决我的记忆问题。
我需要一种算法来获取输入模式（可能是字符串）并生成优化的模式（也可能是字符串）。
请注意(XA)|(XB) = X(A|B). 基于这个属性，我可以建议以下贪婪的解决方案：
令P为表达式，X为P :中最常见的条目P = (XR1)|(XR2)|...|(XRn)|Q。然后，从括号中取出X ， P可以表示为P = XR | Q，其中R = (R1|R2|...|Rn)。完成后，递归求解R和Q的问题。
一般来说，布尔表达式的简化是 NP-hard 的（例如，参见Is minimization of boolean expressions NP-Complete?）。
如果您最多有 8 个文字或非否定变量，则最多有 256 个可能的min-terms，这不是一个很大的数字，所以我想您的变量多于 8 个。考虑使用Quine-McCluskey 方法来简化你的表达，而不是一些特别的方法。或者，如果变量的数量很大但不是很大（例如，小于 64 的某个小的倍数），则在您读入它们时将每个最小项表示为位掩码和 OR 项，而不是象征性地进行评估。
通过regex标签的使用，我推断出要优化的表达式是正则表达式，而不是布尔表达式。
正则表达式可以很容易地简化为 DFA（状态机），尽管状态的数量在正则表达式的大小上可能是指数级的。获得 DFA 后，您可以使用一种著名的算法来最小化 DFA；O(n log n)在州n的数量中做到这一点并不难。
一个好的正则表达式库应该能够为您完成所有这些，但很多都没有。你可能想看看Ragel。
如果您的正则表达式的 DFA 实际上比正则表达式大得多（这种情况很少见但并非完全未知），您可能会发现上述过程确实会炸毁内存。出于这个原因，许多正则表达式库没有执行完整的 DFA 缩减；相反，它们仅简化为 NFA，然后懒惰地执行 powerset 构造，缓存结果。这应该以增加扫描时间为代价避免内存问题。
显示指数爆炸的正则表达式示例：
A(A|B)(A|B)(A|B)(A|B)(A|B)(A|B)
对应的 DFA 必须至少有 32 个状态（即 2 5其中5是(A|B).