一个正则表达式,永远不会与任何内容匹配

167
你有什么想法 - 一个永远不会被任何字符串匹配的正则表达式是什么样子的?
编辑:为什么我想要这个?首先,因为我觉得思考这样一个表达式很有趣,其次,因为我需要它用于一个脚本。
在那个脚本中,我将一个字典定义为Dictionary<string, Regex>。这个字典包含了一个字符串和一个表达式。
基于这个字典,我创建了一些方法,它们都只使用这个字典作为参考来完成它们的工作,其中一个方法是将正则表达式与解析后的日志文件进行匹配。
如果匹配到一个表达式,就会向另一个Dictionary<string, long>添加一个由该表达式返回的值。因此,为了捕获字典中没有匹配到表达式的任何日志消息,我创建了一个名为"unknown"的新组。
将所有没有匹配到其他任何内容的内容都添加到这个组中。但为了防止"unknown"表达式(出于偶然)与日志消息不匹配,我必须创建一个几乎肯定永远不会匹配的表达式,无论我给它什么字符串。

1
请注意,证明否定命题非常困难。 - Lasse V. Karlsen
5
有趣。你会在哪里使用这样的正则表达式? - Charlie Salts
3
我在这里记录一下,上面许多评论和对这个问题的回答最初来自于我提出的一个问题:http://stackoverflow.com/questions/1845078/what-regular-expression-can-never-match。Marc Gravell将它们合并了,我认为这使得许多回复在没有精确原始上下文的情况下有点奇怪,甚至有些评论似乎毫无意义。(可能还会夺走未来的声望分数。)我建议具有如此详细背景的问题永远不可能是“完全重复”的。无论如何... - Peter Hansen
3
此问题已添加到Stack Overflow正则表达式FAQ,位于“高级Regex-Fu”下。 - aliteralmind
7
请注意,证明否定命题非常困难——这是一个被广泛认为却显然错误的观点...因为自从欧几里得证明质数无上限以来,我们就已经知道了这一点。任何P的证明都是(not P)的证明。真正的情况是,证明经验普遍规律(包括肯定和否定的)非常困难,比如“所有乌鸦都是黑色的”或“没有乌鸦是白色的”。算法是分析性的,而不是经验性的,因此这是对虚假规则的特别恶劣的误用。例如,证明模式'a'不匹配任何以'b'开头的字符串并不是“非常困难”的问题。 - Jim Balter
显示剩余15条评论
30个回答

7

这个似乎可以工作:

$.

2
这与费迪南德·贝耶的例子类似。 - Gumbo
10
它将在点匹配换行模式下进行匹配。 - Tim Pietzcker
在Perl中,这将实际匹配当前输入行号[$。]。在这种情况下,您必须采用$(.)或更等效的$(?.)。 - Brad Gilbert
在 POSIX BRE 语法中,$. 将匹配一个字面上的 $ 后跟任何字符,因为 $ 在该模式中无效作为锚点。 - phils

5

这种方法对于Python和其他许多语言无效,但是在Javascript正则表达式中,[]是一个有效的字符类,不能匹配。 因此,无论输入什么内容,以下代码都应该立即失败:

var noMatch = /^[]/;

我更喜欢它比/$a/,因为对我来说,它清晰地传达了它的意图。至于何时需要它,我需要它是因为我需要一个基于用户输入动态编译模式的备用方案。当模式无效时,我需要用一个不匹配任何内容的模式替换它。简化后,它看起来像这样:

try {
    var matchPattern = new RegExp(someUserInput);
}
catch (e) {
    matchPattern = noMatch;
}

5
最快的方法是:
r = re.compile(r'a^')
r.match('whatever')

'

'a' 可以是任何非特殊字符('x','y')。Knio的实现可能更加纯粹,但是这个实现对于所有不以您选择的任何字符(而不是'a')开头的字符串都会更快,因为它不会在第二个字符后匹配,而是在第一个字符后匹配。

'

在我的情况下,(.^) 大约比 (\x00^) 慢10%。 - Peter Hansen
1
我接受这个答案,因为使用除 \n 以外的任何值作为字符都保证不匹配,并且我认为它比 (?!x)x 选项稍微更易读(鉴于相对较少的正则表达式专家),尽管我也投了那个选项的赞成票。在我的情况下,无论选择哪个选项,我都需要一个注释来解释它,所以我想我会将我的原始尝试调整为 '\x00NEVERMATCHES^'。我得到了这个答案的不匹配保证,同时保留了我的原始自我记录性。感谢所有人的回答! - Peter Hansen
3
这实际上起作用吗?如果是这样,是谁决定与Unix不同?在Unix正则表达式中,“^”只有作为第一个字符时才是特殊的,类似地,“$”也是如此。对于任何Unix工具来说,该正则表达式将匹配包含文本字符串“a^”的任何内容。 - JaakkoK
嘿,这是一个不错的攻击。我从未针对那个字面字符串进行过测试。 - Adam Nelson
哦,如果那个破坏了Unix正则表达式,那么你会喜欢 >^ - CubicleSoft

5

空正则表达式

最好的不匹配任何内容的正则表达式是一个空的正则表达式。但我不确定所有的正则表达式引擎都会接受它。

无法匹配的正则表达式

另一种解决方法是创建一个无法匹配的正则表达式。我发现 $-^ 只需要两步计算就能完成,而不管您的文本大小如何 (https://regex101.com/r/yjcs1Z/1)。

参考资料:

  • $^$. 需要36步计算 -> O(1)
  • \b\B 在我的样本中需要1507步,并随着字符串中字符数的增加而增加。-> O(n)

更多关于这个问题的热门讨论:


5

好的回答很多!

与 @nivk 的答案类似,我想分享一下不同类型永远不匹配的正则表达式在 Perl 中的性能比较。

  1. 输入:伪随机ascii字符串(25,000个不同的行,长度为8-16):

正则表达式速度:

Total for   \A(?!x)x: 69.675450 s, 1435225 lines/s
Total for       a\bc: 71.164469 s, 1405195 lines/s
Total for    (?>a+)a: 71.218324 s, 1404133 lines/s
Total for       a++a: 71.331362 s, 1401907 lines/s
Total for         $a: 72.567302 s, 1378031 lines/s
Total for     (?=a)b: 72.842308 s, 1372828 lines/s
Total for     (?!x)x: 72.948911 s, 1370822 lines/s
Total for       ^\b$: 79.417197 s, 1259173 lines/s
Total for         $.: 88.727839 s, 1127041 lines/s
Total for       (?!): 111.272815 s, 898692 lines/s
Total for         .^: 115.298849 s, 867311 lines/s
Total for    (*FAIL): 350.409864 s, 285380 lines/s
  1. 输入:/usr/share/dict/words(10万个英语单词)。

正则表达式速度:

Total for   \A(?!x)x: 128.336729 s, 1564805 lines/s
Total for     (?!x)x: 132.138544 s, 1519783 lines/s
Total for       a++a: 133.144501 s, 1508301 lines/s
Total for    (?>a+)a: 133.394062 s, 1505479 lines/s
Total for       a\bc: 134.643127 s, 1491513 lines/s
Total for     (?=a)b: 137.877110 s, 1456528 lines/s
Total for         $a: 152.215523 s, 1319326 lines/s
Total for       ^\b$: 153.727954 s, 1306346 lines/s
Total for         $.: 170.780654 s, 1175906 lines/s
Total for       (?!): 209.800379 s, 957205 lines/s
Total for         .^: 217.943800 s, 921439 lines/s
Total for    (*FAIL): 661.598302 s, 303540 lines/s

(在Intel i5-3320M上运行的Ubuntu,Linux内核版本为4.13,Perl版本为5.26)


这是一些在此处涵盖的方法的JavaScript比较:https://jsperf.com/regex-that-never-matches - thdoan

4

Python不支持,但是Perl可以:

perl -ne 'print if /(w\1w)/'

这个正则表达式理论上应该尝试匹配无限(偶数)数量的w,因为第一组(即())会递归到自己。即使在启用了use strict; use warnings;的情况下,Perl似乎也没有发出任何警告,因此我认为它至少是有效的,而我的(最小化)测试未能匹配任何内容,所以我提交它供您批评。


1
理论总是很好,但在实践中,如果正则表达式的描述中包含“无限”一词,我想我可能会感到担忧! - Peter Hansen
perl -Mre=debug -e'"www wwww wwwww wwwwww" =~ /(w\1w)/' - Brad Gilbert
@BradGilbert - 在这里运行(5.10,有点过时)会产生“正则表达式失败”的结果,正如OP所请求的那样。它在你的系统上匹配吗? - Chris Lutz

4

[^\d\D] or (?=a)b or a$a or a^a


注意,(?!x)x是上面提供的第一个答案。谢谢。 - Peter Hansen
是的,看起来我对其他回答者扫得太快了。 - Bart Kiers

3
看到一些很棒的回答后,@arantius的评论(关于定时$x vs x^ vs (?!x)x)对目前接受的答案产生了影响,让我想测试一下目前为止给出的解决方案。
使用@arantius的275k行标准,在Python(v3.5.2,IPython 6.2.1)中运行了以下测试。 总之: 'x^''x\by'是最快的,速度至少快16倍,与@arantius的发现相反,(?!x)x是最慢的(慢约37倍)。因此,速度问题肯定与实现有关。如果速度对您很重要,请在提交之前在您的系统上自行测试。 更新:显然,"x^"和"a^"的时间差异很大。请参见this question以获取更多信息,并查看先前的编辑,其中包括使用"a"而不是"x"的较慢时间。
In [1]: import re

In [2]: with open('/tmp/longfile.txt') as f:
   ...:     longfile = f.read()
   ...:     

In [3]: len(re.findall('\n',longfile))
Out[3]: 275000

In [4]: len(longfile)
Out[4]: 24733175

In [5]: for regex in ('x^','.^','$x','$.','$x^','$.^','$^','(?!x)x','(?!)','(?=x)y','(?=x)(?!x)',r'x\by',r'x\bx',r'^\b$'
    ...: ,r'\B\b',r'\ZNEVERMATCH\A',r'\Z\A'):
    ...:     print('-'*72)
    ...:     print(regex)
    ...:     %timeit re.search(regex,longfile)
    ...:     
------------------------------------------------------------------------
x^
6.98 ms ± 58.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
------------------------------------------------------------------------
.^
155 ms ± 960 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
------------------------------------------------------------------------
$x
111 ms ± 2.12 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
------------------------------------------------------------------------
$.
111 ms ± 1.76 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
------------------------------------------------------------------------
$x^
112 ms ± 1.14 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
------------------------------------------------------------------------
$.^
113 ms ± 1.44 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
------------------------------------------------------------------------
$^
111 ms ± 839 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
------------------------------------------------------------------------
(?!x)x
257 ms ± 5.03 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
------------------------------------------------------------------------
(?!)
203 ms ± 1.56 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
------------------------------------------------------------------------
(?=x)y
204 ms ± 4.84 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
------------------------------------------------------------------------
(?=x)(?!x)
210 ms ± 1.66 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
------------------------------------------------------------------------
x\by
7.41 ms ± 122 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
------------------------------------------------------------------------
x\bx
7.42 ms ± 110 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
------------------------------------------------------------------------
^\b$
108 ms ± 1.05 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
------------------------------------------------------------------------
\B\b
387 ms ± 5.77 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
------------------------------------------------------------------------
\ZNEVERMATCH\A
112 ms ± 1.52 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
------------------------------------------------------------------------
\Z\A
112 ms ± 1.38 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

第一次运行时,我忘记了对最后三个表达式进行原始字符串处理,因此'\b'被解释为退格符'\x08'。然而,令我惊讶的是,'a\x08c'比之前最快的结果还要快!公平地说,它仍然能匹配那段文本,但我认为这仍然值得注意,因为我不确定为什么它更快。
In [6]: for regex in ('x\by','x\bx','^\b$','\B\b'):
    ...:     print('-'*72)
    ...:     print(regex, repr(regex))
    ...:     %timeit re.search(regex,longfile)
    ...:     print(re.search(regex,longfile))
    ...:     
------------------------------------------------------------------------
y 'x\x08y'
5.32 ms ± 46.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
None
------------------------------------------------------------------------
x 'x\x08x'
5.34 ms ± 66.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
None
------------------------------------------------------------------------
$ '^\x08$'
122 ms ± 1.05 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
None
------------------------------------------------------------------------
\ '\\B\x08'
300 ms ± 4.11 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
None

我的测试文件是使用"...可读内容和无重复行"公式创建的(在Ubuntu 16.04上)。
$ ruby -e 'a=STDIN.readlines;275000.times do;b=[];rand(20).times do; b << a[rand(a.size)].chomp end; puts b.join(" "); end' < /usr/share/dict/words > /tmp/longfile.txt

$ head -n5 /tmp/longfile.txt 
unavailable speedometer's garbling Zambia subcontracted fullbacks Belmont mantra's
pizzicatos carotids bitch Hernandez renovate leopard Knuth coarsen
Ramada flu occupies drippings peaces siroccos Bartók upside twiggier configurable perpetuates tapering pint paralyzed
vibraphone stoppered weirdest dispute clergy's getup perusal fork
nighties resurgence chafe

2
\B\b 在性能方面非常糟糕(与未锚定到位置的每个模式一样,但此模式特别糟糕)。尝试对 ^\B\b 进行基准测试。 - phils

3
所有涉及边界匹配器的示例都遵循相同的步骤。 步骤: 1. 选择任何一个边界匹配器:^,$,\b,\A,\Z,\z 2. 做与它们的本意相反的事情
举例: ^ 和 \A 是用于匹配开头的,所以不要将它们用于匹配开头。
^ --> .^
\A --> .\A

\b匹配单词边界,因此在两个单词之间使用它

原始答案翻译成"最初的回答"

\b --> .\b.

$、\Z和\z是用于结尾的,因此不要在结尾使用它们。

“Original Answer”翻译成中文为“最初的回答”。

$ --> $.
\Z --> \Z.
\z --> \z.

其他方法涉及使用向前和向后查找,它们与相同的类比原理一起工作: 如果您提供正向或负向查找,然后跟随相反的内容

注:Original Answer翻译成“最初的回答”未被包含在需要翻译的内容中。
(?=x)[^x]
(?!x)x

如果您在某个相反的东西后面跟随正向或负向回顾,则为“最初的回答”。
[^x](?<=x)
x(?<!x)

他们可能存在更多的这种模式和类比。最初的回答。

3
我相信:
\Z RE FAILS! \A

即使正则表达式包含MULTILINE、DOTALL等标志,也会被覆盖。

>>> import re
>>> x=re.compile(r"\Z RE FAILS! \A")
>>> x.match('')
>>> x.match(' RE FAILS! ')
>>>

我相信(但我没有进行基准测试),在\Z\A之间的字符串长度(>0)不论是什么,时间到故障的时间应该是恒定的。


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