Регулярное выражение, которое никогда не сравнится ни с чем
Это может звучать как глупый вопрос, но я долго разговаривал с некоторыми из моих коллег-разработчиков, и это звучало забавно.
Так; что вы думаете - как выглядит Regex, который никогда не будет сопоставлен ни с одной строкой!
Редактировать: Почему я хочу это? Ну, во-первых, потому что мне интересно думать о таком выражении, а во-вторых, потому что он мне нужен для сценария.
В этом сценарии я определяю словарь как Dictionary<string, Regex>, Это содержит, как вы видите, строку и выражение.
Основываясь на этом словаре, я создаю методы, которые все используют этот словарь только как ссылку на то, как они должны выполнять свою работу, один из них сопоставляет регулярные выражения с анализируемым лог-файлом.
Если выражение соответствует, другое Dictionary<string, long> добавляется значение, которое возвращается выражением. Итак, чтобы перехватить любые сообщения журнала, которые не соответствуют выражению в словаре, я создал новую группу под названием "неизвестно".
К этой группе добавляется все, что не соответствует ничему другому. Но для того, чтобы "неизвестное" выражение не совпадало (случайно) с лог-сообщением, мне пришлось создать выражение, которое наверняка никогда не будет совпадать, независимо от того, какую строку я ему даю.
Таким образом, у вас есть причина для этого "ненастоящего вопроса"...
30 ответов
На самом деле это довольно просто, хотя это зависит от реализации / 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, оставшаяся часть регулярного выражения (b) соответствует только если следующий символ b, Таким образом, это регулярное выражение соответствует, только если символ a а также b в то же время.
a\bc, где \b является выражением нулевой ширины, которое соответствует границе слова.
Оно не может появиться в середине слова, к которому мы его принуждаем.
\B\b
\b соответствует границам слов - позиция между буквой и буквой (или границей строки).\B является его дополнением - оно соответствует положению между двумя буквами или между не-буквами.
Вместе они не могут соответствовать ни одной позиции.
Смотрите также:
Максимальное совпадение
a++a
Хотя бы один a с последующим любым количеством aПрошло без возврата. Затем попробуйте сопоставить еще один a,
или независимое подвыражение
Это эквивалентно положению a+ в независимом подвыражении, сопровождаемом другим a,
(?>a+)a
Perl 5.10 поддерживает специальные контрольные слова, называемые "глаголы", которые заключены в (*...) последовательность. (Сравнить с (?...) особая последовательность.) Среди них она включает (*FAIL) глагол, который сразу возвращается из регулярного выражения.
Обратите внимание, что глаголы также реализованы в PCRE вскоре после этого, так что вы можете использовать их в PHP или других языках, используя библиотеку PCRE. (Вы не можете в Python или Ruby, однако. Они используют свой собственный движок.)
Так много хороших ответов!
Подобно ответу @nivk, я хотел бы поделиться сравнением производительности для Perl для различных вариантов несоответствующего регулярного выражения.
- Входные данные: псевдослучайные строки 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
- Введите: /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)
Самый быстрый будет:
r = re.compile(r'a^')
r.match('whatever')
'a' может быть любым не специальным символом ('x','y'). Реализация Knio может быть немного более чистой, но эта будет быстрее для всех строк, начинающихся не с того символа, который вы выбрали вместо "a", потому что в этих случаях он не будет совпадать после первого символа, а не после второго.
Это не будет работать для Python и многих других языков, но в регулярном выражении Javascript, [] является допустимым классом символов, который не может быть сопоставлен. Таким образом, следующее не должно произойти немедленно, независимо от того, что ввод:
var noMatch = /^[]/;
Мне нравится это лучше чем /$a/ потому что для меня это ясно говорит о его намерениях. А что касается того, когда вам это когда-нибудь понадобится, мне это нужно, потому что мне нужен запасной вариант для динамически скомпилированного шаблона, основанного на пользовательском вводе. Когда шаблон недействителен, мне нужно заменить его на шаблон, который ничего не соответствует. Упрощенно это выглядит так:
try {
var matchPattern = new RegExp(someUserInput);
}
catch (e) {
matchPattern = noMatch;
}
Пустое регулярное выражение
Лучшее регулярное выражение, которое никогда ничего не соответствует, - это пустое регулярное выражение. Но я не уверен, что все движки регулярных выражений примут это.
Невозможное регулярное выражение
Другое решение - создать невозможное регулярное выражение. я нашел это$-^Для вычисления требуется всего два шага независимо от размера вашего текста ( https://regex101.com/r/yjcs1Z/1).
Для справки:
$^а также$.сделать 36 шагов для вычисления -> O(1)\b\Bзанимает 1507 шагов в моем примере и увеличивается с количеством символов в вашей строке -> O(n)
Более популярная ветка по этому вопросу:
Python не примет это, но Perl:
perl -ne 'print if /(w\1w)/'
Это регулярное выражение должно (теоретически) пытаться соответствовать бесконечному (четному) числу wс, потому что первая группа (()s) возвращается в себя. Perl, похоже, не выдает никаких предупреждений даже под use strict; use warnings;, поэтому я предполагаю, что это по крайней мере правильно, и мое (минимальное) тестирование не соответствует чему-либо, поэтому я отправляю его для вашей критики.
Все примеры с использованием средства сопоставления границ следуют одному и тому же рецепту. Рецепт блюда:
Возьмите любой из граничных сопоставителей: ^,$,\b,\A,\Z,\z
Делайте противоположное тому, для чего они предназначены
Примеры:
^ и \ A предназначены для начала, поэтому не используйте их в начале
^ --> .^
\A --> .\A
\ b соответствует границе слова, поэтому используйте его между
\b --> .\b.
$, \Z и \ z предназначены для конца, поэтому не используйте их в конце
$ --> $.
\Z --> \Z.
\z --> \z.
Другие включают использование просмотра вперед и назад, которые также работают по той же аналогии: если вы даете положительный или отрицательный взгляд вперед, за которым следует что-то противоположное
(?=x)[^x]
(?!x)x
Если вы положительно или отрицательно оглядываетесь назад, следуя чему-то противоположному
[^x](?<=x)
x(?<!x)
Их могло быть еще больше таких узоров и таких аналогий.
Увидев некоторые из этих замечательных ответов, комментарий @arantius (относительно времени $x против x^ против (?!x)x) на принятый в настоящее время ответ заставил меня задуматься над некоторыми решениями, приведенными до сих пор.
Используя строчный стандарт @arantius 275k, я запустил следующие тесты на 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' Backspace символ. Однако, к моему удивлению, '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
Как уже упоминали профессионалы, это зависит от движков регулярных выражений и, конечно же, эталон производительности зависит от многих вещей, включая устройство.
Но в качестве справки о производительности для
ECMAScript (Java/Javascript)или же
PCRE (PHP)лучший сверху вниз:
-
[]|^[](Самый быстрый) [Только ECMAScript] -
$^(не многострочный флаг) (Быстро) -
[^\S\s]|^[^\S\s]|^[^\W\w]|^[^\D\d](Быстро) -
.^(не многострочный флаг) (Быстро) -
(?!\x00)\x00|^(?!\x00)\x00|(?!\0)\0(Быстро) -
(?!a)a -
(?!)(Медленный) -
(?=b)a(Медленный) - Другие примеры, такие как
\b\Bи т.д... (Самый медленный)
Живая попытка Javascript (не очень точно)
_Примечание:
^знак равно
\A(PCRE) = при запуске (не многострочный) подробнее
(*FAIL)
или же
(*F)
С помощью PCRE и PERL вы можете использовать этот глагол управления возвратом, который вынуждает паттерн немедленно потерпеть неудачу.
Я полагаю, что
\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время до отказа должно быть постоянным.
Вот небольшое улучшение ответа Книо :
r"\A(?!)"
Что это делает: означает «неудачное сопоставление, если пустая строка существует в текущей позиции в строке для сопоставления». В логике регулярных выражений везде в строке, которая должна быть сопоставлена, есть пустые строки : перед первым символом, между каждой парой символов и после последнего символа. Поэтому всегда не совпадает.
Добавление\Aповышает скорость общей ошибки сопоставления, предотвращая попытку механизма регулярных выражений(?!)во всех возможных позициях в строке для сопоставления. Эта версия всегда не будет соответствовать постоянному времени по сравнению с временем O (длина строки) для версии Knio. (Конечно, это не проблема, если вы используетеre.match, но вам может понадобиться это сre.searchвместо...)
\A[^\w\W]
Работает независимо от флагов регулярных выражений.
Согласно regex101: для пустой входной строки 0 шагов. Для всех остальных входных строк ровно 2 шага.
Детская площадка Котлина: https://pl.kotl.in/hdbNH73It
А что вместо регулярного выражения, просто используйте всегда ложное выражение 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
Конечно, это не интеллектуальная задача, а больше похоже на программирование клейкой ленты.
'[^0-9a-zA-Z...]*'
и заменить... всеми печатными символами;). Это для текстового файла.
new Regex(Guid.NewGuid().ToString())
Создает шаблон, содержащий только буквенно-цифровые символы и '-'(ни один из которых не является специальным символом регулярного выражения), но статистически невозможно, чтобы одна и та же строка появлялась где-либо ранее (потому что в этом весь смысл GUID.)