如何生成符合给定正则表达式的随机字符串?

20

重复:

生成与正则表达式匹配的随机字符串

不,这不是我想要的。我正在寻找一种易于实现且通用的方法。这比随机生成密码要困难得多。


我想创建一个应用程序,它接受一个正则表达式,并展示10个随机生成的匹配该表达式的字符串。这有助于人们更好地了解他们的正则表达式,并决定是否安全用于验证目的。有人知道如何轻松地做到这一点吗?

一个显而易见的解决方案是编写(或窃取)一个正则表达式解析器,但这似乎超出了我的能力范围。

我再次强调,我正在寻找一种易于实现且通用的方法。

编辑:暴力破解方法行不通。假设随机字符串只是[a-z0-9]{10} 并且每秒迭代100万次,则需要65年才能迭代所有10位字符字符串的空间。


我认为没有简单的方法来做到这一点...也许可以使用机械土耳其? :) - Greg
你有特定的正则表达式想法吗?还是你正在寻找适用于任何正则表达式变体的通用解决方案?因为除非你限制自己只使用没有扩展的真正正则表达式,否则你不会找到一个在Perl和.NET中都能工作的正则表达式。 - Welbog
好的,我希望有一个通用解决方案来处理单个变量,尤其是我使用的那种,即将 Perl 正则表达式实现到 PHP 中。 - Michał Tatarynowicz
一般来说,这个问题是#P难的。https://www.researchgate.net/publication/220780342_Counting_and_Random_Generation_of_Strings_in_Regular_Languages - user5675395
5个回答

24

将您的正则表达式解析为确定有限状态机(DFA),然后随机遍历DFA直到进入接受状态,每次转换输出一个字符。每次遍历都会产生一个与表达式匹配的新字符串。

但是,对于那些不真正符合正则表达式规则的“常规”表达式(例如带有反向引用的表达式),这种方法就不适用了。这取决于您需要的表达式类型。


@Richard E.,确定有限状态自动机? - Rob Wells
这听起来一点也不容易 :) - Michał Tatarynowicz
1
@DFA:如果你进入了一个不接受状态的分支,而且没有任何转移可以到达接受状态,那么你就必须重新开始。显然,如果存在这样的分支,它必须从状态集中被删除。使用图算法很容易找到它们,这应该是相当简单的。 - Welbog
1
@饼干:这就是正则表达式的工作原理。即使你找到了一个为你完成这项工作的库,它也很可能是这样工作的。它会按照正则表达式所代表的结构进行遍历,但是以相反的顺序进行;生成一个字符串而不是消耗一个字符串,它恰好能够满足你的需求。 - Welbog
@welbog:完全正确,我只是提醒这个问题。你的答案是通用的 :))) - dfa
显示剩余7条评论

7

您是否知道PHP中类似的东西吗? - Michał Tatarynowicz
用Perl编写,使用一些Perl到可执行文件的工具进行编译,然后从PHP中调用它。 - Thomas L Holaday
是的,我想如果你使用单一语言部署会更容易 :) - Michał Tatarynowicz
尝试使用这个PHP库。它似乎支持比String::Random更多的正则表达式格式。 - Tamlyn
另外还有一个PHP库 - spinkus
显示剩余2条评论

0

一种可能实际可行的但相当丑陋的解决方案是利用现有的正则表达式诊断选项。一些正则表达式库具有确定正则表达式未能匹配的位置的能力。在这种情况下,您可以使用一种形式的暴力破解,但是每次只使用一个字符,并尝试获取更长(并进一步匹配)的字符串,直到获得完全匹配。这是一种非常丑陋的解决方案。但是,与标准的暴力破解解决方案不同,它在像ab这样的字符串上失败也会告诉您是否存在一个字符串ab.*可以匹配(如果不存在,请停止并尝试ac。如果存在,则尝试更长的字符串)。这在所有正则表达式库中可能都不可行。

好消息是,从教学角度来看,这种解决方案可能非常酷。实际上,它的效果可能类似于dfa解决方案,但无需考虑dfa的要求。

请注意,您不会想使用随机字符串来使用此技术。但是,如果您在树中跟踪已测试的内容,则可以使用随机字符作为起点,因此效果相同。


有趣的想法,我会去看看。 - Michał Tatarynowicz

-1
如果你的唯一标准是方法简单且通用,那么没有什么比蛮力更简单和通用了。 :)
for (i = 0; i < 10; ++i) {
    do {
        var str = generateRandomString();
    } while (!myRegex.match(str));
    myListOfGoodStrings.push(str);
}

当然,这是一种非常愚蠢的做法,大多数情况下只是一个玩笑。

我认为你最好的选择是尝试编写自己的基本解析器,教它遇到你预期遇到的事物(例如:字母和数字范围、重复/可选字符……不用担心后顾之忧等)。


1
我想要一个算法,它能在时间结束之前真正地完成运行。我希望它运行时间在1秒以内,肯定可以做到。 - Michał Tatarynowicz
嘿,你应该更明确些:p 不管怎样,我在回答的第二部分中考虑到了这个问题。 - nickf
写自己的解析器是我想要避免的事情 :) - Michał Tatarynowicz

-2

普适性标准是不可能的。给定正则表达式"^生存还是毁灭,这是个问题:$",将不会有十个唯一的随机字符串匹配。

对于非退化情况:

moonshadow提供的Perl的String::Random链接就是答案。一个从stdin读取RegEx并将String::Random的十次调用输出写入stdout的Perl程序是微不足道的。使用Perl2exe将其编译为Windows或Unix exe,并从PHP、Python或其他语言中调用它。

另请参见基于正则表达式的随机文本生成器


你给出的例子对我来说绝对不是一个特殊情况,反而非常简单。第一个字符只能匹配'T',第二个字符只能匹配'o',以此类推。如果所有版本都相同,那就没问题。 - Michał Tatarynowicz

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接