te7*_*te7 6 c++ regex algorithm
我正在开发一个C++应用程序来首先解析正则表达式字符串,然后用它执行一些计算.是否有任何现有算法可以输出长度为L的字符串数N,这些字符串可以被给定的正则表达式识别,例如(a|ab)* | (aa|bb)*？或者是否有一个我可以使用的数学公式,例如涉及阶乘的公式？我只想得到这些正则表达式短语对于给定数字L可以识别的字符串数N.例如,正则表达式可以识别(a|ab)*多少长度为5(L)的字符串.我认为答案是5.但是对于大量的LI,我想知道是否有任何算法或数学表达式可以计算出来.
这是一个基于矩阵求幂的高效算法,您可以使用它来计算这些数字.
我只会提供高级别的描述,而不是代码.
首先,您希望使用计算机科学基础的一个众所周知的等价物,即(简单)正则表达式等效于有限状态机.
(回想一下,有限状态机本质上是一个流程图,其中从每个节点开始,字母表中的每个字母都有一个标记的边缘到某个特定的其他节点(或者可能是它的一个循环).此外,还有一些子集.状态称为"接受集",流程图中的某个特定状态是起始状态.字符串被称为在有限状态机中引入路径,通过从开始状态开始并连续跟随标记边缘.accepts如果最终状态在accept集中,则机器为字符串rejects否则是字符串.经典结构表明,从任何正则表达式我们可以构造一个类似大小的有限状态机,并且从任何有限状态机我们可以构造一个类似大小的正则表达式.对应于正则表达式的任何语言(所有有限字符串的子集)称为"常规",并且当且仅当它对应于有限状态机时,语言是常规的.)
例如,如果我有一个字母{a,b,c}和正则表达式(a|b)*,它对应于具有两个状态的机器.起始状态具有标记a的循环b,标记的循环和标记c为第二状态的箭头.第二个状态有三个循环,所以如果你去那里就会陷入困境.接受集仅包含开始状态.
程序的第一步是将正则表达式转换为相应的有限状态机.(可能是某些现有的正则表达式库基本上已经这样做了,我认为PCRE可能,虽然我不确定.)
给定一个有限状态机,我想构造一个相应的随机矩阵.在这个矩阵中,每个状态都有一行,每个状态有一列,每个条目都是概率.概率p_{i,j}在入境(i,j),等于概率,如果我在状态i,我读了随机的信,我去国家j未来.因此,对于我给出的例子,矩阵是
[2/3 1/3]
[0 1]
如果你想知道长度的字符串k,那么使用矩阵求幂,计算矩阵M^k,其中M是上面的概率转移矩阵.
最后,如果q是开始状态,则将接受集中M^k_{q, s}每个状态的所有条目相加s.这些概率的总和恰好等于k正则表达式接受随机字符串长度的概率.所以,你可以通过复接得到这样的字符串的数量N^k哪里N是在你的字母数.
我认为这种算法的存在并不难,但它也不是微不足道的,我曾经在计算类理论的期末考试中给出了一个更难的版本作为额外的学分问题.我不知道它的任何现有实现,有兴趣知道.
当你使用矩阵求幂时,你可以通过这种方式对天真的方法进行一些显着的加速.这可以让你k快速做到这一点.
我不知道是否有一个更有效,近似的解决方案,它会很有趣.我想随机抽样总会给你一些东西,但也许有某种光谱算法,基于对矩阵M或其他东西进行奇异值分解.
注意:如果你真的想要实现它,我想你不应该使用浮点数,矩阵M实际上应该是一个整数矩阵.基本上你会被乘以N哪里N是在你的字母数.你可以N^k稍后再跳过这个总和.我认为使用概率更容易理解,但在那个版本中,M^k_{i,j}只是在计算number of paths from i to j of length k.
注意:正如评论中所指出的,这个算法是k任何固定正则表达式的位数的多项式,因此即使对于大型也是如此k.尽管在正则表达式的大小中,它在最坏的情况下是指数 - 为了处理大而复杂的正则表达式,你应该使用某种DFA最小化我想如果你想使用这个方法.对于问题中显示的简单正则表达式,我认为应该没问题.