Регулярное выражение, которому никогда ничего не будет соответствовать

Это может показаться глупым вопросом, но я долго разговаривал с некоторыми из моих коллег-разработчиков, и подумать об этом было забавно.

Так; о чем вы думаете - как выглядит регулярное выражение, которое никогда не будет сопоставлено ни одной строкой!

Изменить : почему я хочу это? Ну, во-первых, потому что мне интересно придумывать такое выражение, а во-вторых, потому что оно мне нужно для сценария.

В этом скрипте я определяю словарь как Dictionary<string, Regex>. Как видите, он содержит строку и выражение.

На основе этого словаря я создаю методы, которые все используют этот словарь только как справочник о том, как они должны выполнять свою работу, один из них сопоставляет регулярные выражения с проанализированным файлом журнала.

Если выражение найдено, к другому Dictionary<string, long>добавляется значение, возвращаемое выражением. Итак, чтобы поймать любые сообщения журнала, которые не соответствуют выражению в словаре, я создал новую группу под названием «unknown».

В эту группу добавляется все, что не совпало ни с чем другим. Но чтобы предотвратить несовпадение "неизвестного" -выражения (случайно) с лог-сообщением, мне пришлось создать выражение, которое наверняка никогда не будет совпадать, независимо от того, какую строку я ему задаю.

Итак, вот моя причина для этого «не настоящего вопроса» ...

На самом деле это довольно просто, хотя это зависит от реализации / flags *:

$a

Соответствует символу aпосле конца строки. Удачи.

ВНИМАНИЕ:
это дорогое выражение - оно просканирует всю строку, найдет привязку конца строки и только после этого не найдет aи вернет отрицательное совпадение. (См. Комментарий ниже для более подробной информации.)

^* Первоначально я не особо задумывался о регулярном выражении в многострочном режиме, где $также соответствует конец строки. Фактически, он будет соответствовать пустой строке прямо перед новой строкой , поэтому обычный символ, например, aникогда не может появиться после $.

Кредитное плечо negative lookahead:

>>> import re
>>> x=r'(?!x)x'
>>> r=re.compile(x)
>>> r.match('')
>>> r.match('x')
>>> r.match('y')

этот RE является противоречивым в терминах и поэтому никогда ни с чем не будет соответствовать.

ПРИМЕЧАНИЕ.
В Python re.match () неявно добавляет якорь начала строки ( \A) в начало регулярного выражения. Этот якорь важен для производительности: без него будет сканироваться вся строка. Те, кто не использует Python, захотят явно добавить якорь:

\A(?!x)x

Тот, который был пропущен:

^\b$

Он не может совпадать, потому что пустая строка не содержит границы слова. Протестировано на Python 2.5.

смотреть по сторонам:

(?=a)b

Для новичков в регулярных выражениях: положительный взгляд в будущее (?=a)гарантирует, что следующий символ есть a, но не меняет местоположение поиска (или не включает 'a' в совпадающую строку). Теперь, когда подтверждено совпадение следующего символа a, оставшаяся часть regex ( b) соответствует только в том случае, если это следующий символ b. Таким образом, это регулярное выражение соответствует только в том случае, если символ одновременно aи bодновременно.

a\bc, где \b- выражение нулевой ширины, соответствующее границе слова.

Он не может появляться в середине слова, к которому мы его заставляем.

$.

.^

$.^

(?!)

Максимальное соответствие

a++a

По крайней мере, за одним, aза которым следует любое количество a, без возврата. Затем попробуйте сопоставить еще один a.

или Независимое подвыражение

Это эквивалентно помещению a+независимого подвыражения, за которым следует другое a.

(?>a+)a

Perl 5.10 поддерживает специальные управляющие слова, называемые «глаголами», которые заключены в (*...)последовательность. (Сравните со (?...)специальной последовательностью.) Среди них есть (*FAIL)глагол, который немедленно возвращается из регулярного выражения.

Обратите внимание, что глаголы также реализованы в PCRE вскоре после этого, поэтому вы можете использовать их в PHP или других языках, используя библиотеку PCRE. (Однако вы не можете использовать Python или Ruby. Они используют свой собственный движок.)

\B\b

\bсовпадает с границами слова - позиция между буквой и не буквой (или границей строки).
\Bявляется его дополнением - соответствует положению между двумя буквами или между небуквами.

Вместе они не могут соответствовать ни одной позиции.

Смотрите также:

• Границы слов
• Этот шаблон не соответствует нескольким позициям
• вдохновение

Кажется, это работает:

$.

Как насчет $^или может быть (?!)? 

Самыми быстрыми будут:

r = re.compile(r'a^')
r.match('whatever')

'a' может быть любым неспециальным символом ('x', 'y'). Реализация Knio может быть немного более чистой, но эта будет быстрее для всех строк, не начинающихся с любого символа, который вы выберете вместо 'a', потому что в этих случаях он не будет соответствовать после первого символа, а не после второго.

Python не примет это, но Perl будет:

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

Это регулярное выражение должно (теоретически) пытаться сопоставить бесконечное (четное) количество ws, потому что первая группа ( ()s) рекурсивно сама в себя. Кажется, что Perl не выдает никаких предупреждений, даже если он находится ниже use strict; use warnings;, поэтому я предполагаю, что он, по крайней мере, действителен, и мое (минимальное) тестирование ни с чем не соответствует, поэтому я отправляю его для вашей критики.

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

Это не сработает для Python и многих других языков, но в регулярном выражении Javascript []это допустимый класс символов, который не может быть сопоставлен. Таким образом, следующее должно немедленно выйти из строя, независимо от того, какой ввод:

var noMatch = /^[]/;

Мне он нравится больше, чем /$a/потому, что он ясно передает свое намерение. А что касается того, когда он вам когда-нибудь понадобится, он мне понадобился, потому что мне нужен был запасной вариант для динамически скомпилированного шаблона, основанного на вводе пользователя. Когда шаблон недействителен, мне нужно заменить его шаблоном, который ничего не соответствует. В упрощенном виде это выглядит так:

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

Все примеры с использованием средства сопоставления границ следуют одному и тому же рецепту. Рецепт блюда:

1. Возьмите любой из граничных сопоставителей: ^, $, \ b, \ A, \ Z, \ z

2. Делайте противоположное тому, для чего они предназначены

Примеры:

^ и \ A предназначены для начала, поэтому не используйте их в начале

^ --> .^
\A --> .\A

\ b соответствует границе слова, поэтому используйте его между

\b --> .\b.

$, \ Z и \ z предназначены для конца, поэтому не используйте их в конце

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

Другие включают использование просмотра вперед и назад, которые также работают по той же аналогии: если вы даете положительный или отрицательный взгляд вперед, за которым следует что-то противоположное

(?=x)[^x]
(?!x)x

Если вы положительно или отрицательно оглядываетесь назад, следуя чему-то противоположному

[^x](?<=x)
x(?<!x)

Их могло быть еще больше таких узоров и таких аналогий.

Столько хороших ответов!

Подобно ответу @nivk, я хотел бы поделиться сравнением производительности Perl для разных вариантов никогда не совпадающего регулярного выражения.

1. Вход: псевдослучайные строки ascii (25000 различных строк, длина 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

2. Введите: / usr / share / dict / words (100 000 английских слов).

Скорость регулярного выражения:

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

(Ubuntu на Intel i5-3320M, ядро ​​Linux 4.13, Perl 5.26)

я полагаю, что

\Z RE FAILS! \A

охватывает даже случаи, когда регулярное выражение включает такие флаги, как MULTILINE, DOTALL и т. д.

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

Я считаю (но я не тестировал его), что независимо от длины (> 0) строки между \Zи \A, время до отказа должно быть постоянным.

(*FAIL)

или

(*F)

С PCRE и PERL вы можете использовать эту команду управления возвратом, которая заставляет шаблон немедленно отказывать.

Увидев некоторые из этих замечательных ответов, комментарий @arantius (относительно времени $xvs x^vs (?!x)x) на принятый в настоящее время ответ заставил меня захотеть примерить некоторые из решений, приведенных на данный момент.

Используя стандарт строки 275k @ arantius, я провел следующие тесты на Python (v3.5.2, IPython 6.2.1).

TL; DR: 'x^'и 'x\by'являются самыми быстрыми как минимум в ~ 16 раз, и, вопреки выводам @arantius, (?!x)xбыли среди самых медленных (~ в 37 раз медленнее). Так что вопрос скорости, безусловно, зависит от реализации. Если скорость важна для вас, проверьте сами на своей предполагаемой системе.

ОБНОВЛЕНИЕ: очевидно большое расхождение между временем 'x^'и 'a^'. См. Этот вопрос для получения дополнительной информации и предыдущее редактирование более медленных таймингов с 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)

В первый раз, когда я запустил это, я забыл rиспользовать последние 3 выражения, поэтому это '\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

Пустое регулярное выражение

Лучшее регулярное выражение, которое никогда ничего не соответствует, - это пустое регулярное выражение. Но я не уверен, что все движки регулярных выражений примут это.

Невозможное регулярное выражение

Другое решение - создать невозможное регулярное выражение. Я обнаружил, что $-^для вычисления требуется всего два шага независимо от размера вашего текста ( https://regex101.com/r/yjcs1Z/1 ).

Для справки:

• $^и $.сделайте 36 шагов для вычисления -> O (1)
• \b\B занимает 1507 шагов в моем образце и увеличивается с количеством символов в вашей строке -> O (n)

Более популярная ветка по этому вопросу:

• Регулярное выражение * не * соответствует никаким символам

Может быть, это?

/$.+^/

'[^0-9a-zA-Z...]*'

и замените ... всеми печатными символами;). Это для текстового файла.

Как насчет того, чтобы вместо регулярного выражения просто использовать оператор if всегда ложно? В javascript:

var willAlwaysFalse=false;
if(willAlwaysFalse)
{
}
else
{
}

Переносимое решение, которое не будет зависеть от реализации регулярного выражения, - просто использовать постоянную строку, которая, как вы уверены, никогда не появится в сообщениях журнала. Например, создайте строку на основе следующего:

cat /dev/urandom | hexdump | head -20
0000000 5d5d 3607 40d8 d7ab ce72 aae1 4eb3 ae47
0000010 c5e2 b9e8 910d a2d9 2eb3 fdff 6301 c85f
0000020 35d4 c282 e439 33d8 1c73 ca78 1e4d a569
0000030 8aca eb3c cbe4 aff7 d079 ca38 8831 15a5
0000040 818b 323f 0b02 caec f17f 387b 3995 88da
0000050 7b02 c80b 2d42 8087 9758 f56f b71f 0053
0000060 1501 35c9 0965 2c6e 03fe 7c6d f0ca e547
0000070 aba0 d5b6 c1d9 9bb2 fcd1 5ec7 ee9d 9963
0000080 6f0a 2c91 39c2 3587 c060 faa7 4ea4 1efd
0000090 6738 1a4c 3037 ed28 f62f 20fa 3d57 3cc0
00000a0 34f0 4bc2 3067 a1f7 9a87 086b 2876 1072
00000b0 d9e1 6b8f 5432 a60e f0f5 00b5 d9ef ed6f
00000c0 4a85 70ee 5ec4 a378 7786 927f f126 2ec2
00000d0 18c5 46fe b167 1ae6 c87c 1497 48c9 3c09
00000e0 8d09 e945 13ce 7da2 08af 1a96 c24c c022
00000f0 b051 98b3 2bf5 4d7d 5ec4 e016 a50d 355b
0000100 0e89 d9dd b153 9f0e 9a42 a51f 2d46 2435
0000110 ef35 17c2 d2aa 3cc7 e2c3 e711 d229 f108
0000120 324e 5d6a 650a d151 bc55 963f 41d3 66ee
0000130 1d8c 1fb1 1137 29b2 abf7 3af7 51fe 3cf4

Конечно, это не интеллектуальная задача, это больше похоже на программирование изоленты .

new Regex(Guid.NewGuid().ToString())

Создает шаблон, содержащий только буквенно-цифровые -символы и ' ' (ни один из которых не является специальными символами регулярных выражений), но статистически невозможно, чтобы та же строка появлялась где-либо раньше (потому что в этом весь смысл GUID).