c – 正则表达式的算法 – 在或的组合

我只会提供高级别的描述,而不是代码.

>首先,你想使用计算机科学基础的一个众所周知的等价,即(简单)正则表达式等同于有限状态机.

(回想一下,有限状态机本质上是一个流程图,其中从每个节点开始,字母表中的每个字母都有一个标记的边缘到某个特定的其他节点(或者可能是它的一个循环).此外,还有一些子集.状态称为“接受集”,流程图中的某个特定状态是起始状态.字符串被称为在有限状态机中引入路径,通过从开始状态开始并连续跟随标记边缘.如果最终状态在accept集中,则机器接受字符串,否则拒绝字符串.
经典结构表明,从任何正则表达式我们可以构造一个类似大小的有限状态机,并且从任何有限状态机我们可以构造一个类似大小的正则表达式.对应于正则表达式的任何语言(所有有限字符串的子集)称为“常规”,并且当且仅当它对应于有限状态机时,语言是常规的.)

例如,如果我有一个字母{a,b,c}和正则表达式(a | b)*,它对应于具有两个状态的机器.起始状态具有标记为a的循环,标记为b的循环和标记为第二状态的c的箭头.第二个状态有三个循环,所以如果你去那里就会陷入困境.接受集仅包含开始状态.

程序的第一步是将正则表达式转换为相应的有限状态机. (可能是某些现有的正则表达式库基本上已经这样做了,我认为PCRE可能,虽然我不确定.)
>给定一个有限状态机,我想构造一个相应的随机矩阵.在这个矩阵中,每个状态都有一行,每个状态有一列,每个条目都是概率.在条目(i,j)处的概率p_ {i,j}等于如果我处于状态i并且我读取随机字母的概率,则我接下来进入状态j.因此,对于我给出的例子,矩阵是

[2/3 1/3]
[0 1]
>如果你想知道长度为k的字符串,那么使用矩阵求幂,计算矩阵M ^ k,其中M是上面的概率转移矩阵.
>最后,如果q是开始状态,则为接受集中的每个状态s添加所有条目M ^ k_ {q,s}.这些概率的总和恰好等于正则表达式接受长度为k的随机串的概率.因此,您可以通过乘以N ^ k来获得此类字符串的数量,其中N是字母表中的字母数.

我认为这种算法的存在并不难,但它也不是微不足道的,我曾经在计算类理论的期末考试中给出了一个更难的版本作为额外的学分问题.我不知道它的任何现有实现,有兴趣知道.

当你使用矩阵求幂时,你可以通过这种方式对天真的方法进行一些显着的加速.这允许你快速地为大k做.

我不知道是否有一个更有效,近似的解决方案,它会很有趣.我想随机抽样总会给你一些东西,但也许有某种光谱算法,基于矩阵M或其他东西的奇异值分解.

注意：如果你真的想要实现它,我猜你不应该使用浮点数,矩阵M实际上应该是一个整数矩阵.基本上你会将它乘以N,其中N是字母表中的字母数.然后你会跳过将总和乘以N ^ k.我认为使用概率更容易理解,但在该版本中,M ^ k_ {i,j}将只计算从i到j的长度为k的路径的数量.

注意：正如评论中所指出的,对于任何固定的正则表达式,该算法是k的位数的多项式,因此即使对于大k也是如此.尽管在正则表达式的大小中,它在最坏的情况下是指数 – 为了处理大而复杂的正则表达式,你应该使用某种DFA最小化我想如果你想使用这个方法.对于问题中显示的简单正则表达式,我认为应该没问题.