优化一个巨大的 “OR” 模式

我有一个 “或” 如以下示例的模式： （X Y Z）| （X Y A B）| （X A K）| （M A J K）| （M A B）| （M Z）。 我的问题是，我真正的问题OR'ed操作数是巨大的，并导致大内存消耗问题。然而，形成图案本身的条目很少（X，Y，Z，A，B，K，M和J）。因此，将该模式转换（优化）为如下模式： （X（（Y（Z |（A B）））|（A K）））| （M（（A（（J K）| B））| Z）） ，很可能会解决我的记忆问题。优化一个巨大的 “OR” 模式

我需要一种算法来采取输入模式（如串也许）和产生优化的一个（如串也可能）。

来源

2013-05-01 Hesham Eraqi

对不起，我们在这里没有帮助，你可以自己写，如果你遇到问题并且有疑问就回来， – kapa 2013-05-01 14:36:29

甚至用什么语言？因为这很容易，如果我知道我在回答什么，只需要我一两分钟就可以到 – AngryDuck 2013-05-01 14:43:36

我试过解决这个问题，但失败了。也许它需要额外的努力。 @AngryDuck我需要的算法不是代码。这可能看起来微不足道，但我没有实现它。 – 2013-05-01 14:46:06

请注意，(XA)|(XB) = X(A|B)。在此基础上的财产，我可以建议如下贪婪的解决方案：

让P是表达，X在P最常见的条目：P = (XR1)|(XR2)|...|(XRn)|Q。然后，以X了括号，P可以表示为P = XR | Q，其中R = (R1|R2|...|Rn)。完成后，递归解决问题R和Q。

来源

2013-05-01 14:47:07

这听起来是合乎逻辑的答案。谢谢:) – 2013-05-01 15:50:04

如果这些是序列，那么'（AX）|（BX）=（A | B）X'也是正确的，但是你的方法不会简化这些。（如果他们是布尔值也是如此，但更容易处理：在开始之前将所有元素放在一致的顺序中） – rici 2013-05-01 17:57:35

通常，布尔表达式的简化是NP-hard的（参见，例如，Is minimization of boolean expressions NP-Complete?）。

如果你有最多8文字或非否定变量，最多有256种可能min-terms，这是不是一个巨大的数字，所以我想你有很多更多的变数比8.考虑使用Quine-McCluskey Method简化您的表达而不是一些特别的方法。或者，如果变量的数量很大但不是很大（例如，小于64的小数倍），则将每个最小项表示为一个位掩码，并且在读取它们时一起表示OR项，而不是象征性地进行评估。

来源

2013-05-01 15:04:08

从使用的regex标签的，我推断这是要优化的表达式是正则表达式，而不是一个布尔表达式。

正则表达式可以很容易地简化为DFA（状态机），尽管状态数量可能是指数正则表达式的大小。获得DFA后，您可以使用其中一种众所周知的算法minimizing DFAs;在O(n log n)中执行此操作并不困难，其中n是州的数量。

一个好的正则表达式库应该能够为你做所有这些，但许多不这样做。你可能想看看Ragel。

如果DFA的正则表达式实际上比正则表达式，这是罕见的，但不是完全未知的要大很多，你可能会发现，上述过程不会炸毁内存。由于这个原因，许多正则表达式库不执行完整的DFA减少;相反，他们只是减少到一个NFA，然后懒洋洋地执行电力公司的建设，缓存结果。这应该以增加扫描时间为代价来避免内存问题。

一个正则表达式的一个例子，其示出了指数吹胀：

A(A|B)(A|B)(A|B)(A|B)(A|B)(A|B)

相应的DFA必须至少有32种状态（即，2 其中5是(A|B)重复数

来源

2013-05-01 15:40:57 rici

谢谢。我会看看Ragel，并会回复你:) – 2013-05-01 16:31:34

优化一个巨大的 “OR” 模式

回答

相关问题