Регулярное выражение для соответствия строке, не содержащей слова - PullRequest
Новая
       221

Регулярное выражение для соответствия строке, не содержащей слова

3957 голосов
/ 02 января 2009

Я знаю, что можно сопоставить слово, а затем отменить совпадения, используя другие инструменты (например, grep -v). Однако возможно ли сопоставить строки, которые не содержат конкретного слова, например, hede, используя регулярное выражение?

Введите: 

hoho
hihi
haha
hede

Код: 

grep "<Regex for 'doesn't contain hede'>" input

Желаемый вывод: 

hoho
hihi
haha

Ответы [ 28 ]

5374 голосов
/ 02 января 2009

Понятие, что регулярное выражение не поддерживает обратное сопоставление, не совсем верно. Вы можете имитировать это поведение, используя негативные осмотры: 

^((?!hede).)*$

Приведенное выше регулярное выражение будет соответствовать любой строке или строке без разрыва строки, не , содержащей (под) строку 'hede'. Как уже упоминалось, это не то, что регулярное выражение «хорошо» (или должно делать), но все же, возможно возможно.

И если вам также нужно сопоставить символы разрыва строки, используйте модификатор DOT-ALL (трейлинг s в следующем шаблоне): 

/^((?!hede).)*$/s

или используйте его в строке: 

/(?s)^((?!hede).)*$/

(где /.../ - это разделители регулярных выражений, т.е. не являются частью шаблона)

Если модификатор DOT-ALL недоступен, вы можете имитировать то же поведение с классом символов [\s\S]: 

/^((?!hede)[\s\S])*$/

Объяснение

Строка - это просто список n символов. До и после каждого символа есть пустая строка. Таким образом, список из n символов будет содержать n+1 пустых строк. Рассмотрим строку "ABhedeCD": 

    ┌──┬───┬──┬───┬──┬───┬──┬───┬──┬───┬──┬───┬──┬───┬──┬───┬──┐
S = │e1│ A │e2│ B │e3│ h │e4│ e │e5│ d │e6│ e │e7│ C │e8│ D │e9│
    └──┴───┴──┴───┴──┴───┴──┴───┴──┴───┴──┴───┴──┴───┴──┴───┴──┘

index    0      1      2      3      4      5      6      7

где e - пустые строки. Регулярное выражение (?!hede). смотрит вперед, чтобы увидеть, не видно ли подстроки "hede", и если это так (то есть что-то еще видно), то . (точка) будет соответствовать любому символу, кроме разрыва строки , Осмотры также называются утверждениями нулевой ширины , поскольку они не потребляют каких-либо символов. Они только утверждают / подтверждают что-то.

Итак, в моем примере каждая пустая строка сначала проверяется, чтобы увидеть, нет ли впереди "hede", прежде чем символ будет использован . (точка). Регулярное выражение (?!hede). сделает это только один раз, поэтому оно будет объединено в группу и повторено ноль или более раз: ((?!hede).)*. Наконец, начало и конец ввода привязываются, чтобы убедиться, что весь вход используется: ^((?!hede).)*$

Как видите, ввод "ABhedeCD" завершится ошибкой, потому что на e3 регулярное выражение (?!hede) завершится неудачно (там - "hede" впереди!).

672 голосов
/ 17 марта 2011

Обратите внимание, что решение для не начинается с"hede" : 

^(?!hede).*$

обычно намного эффективнее, чем решение, не содержит , содержит"hede" : 

^((?!hede).)*$

Первый проверяет «hede» только в первой позиции входной строки, а не в каждой позиции.

189 голосов
/ 02 января 2009

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

ETA О, перечитывая вопрос, grep -v это, вероятно, то, что вы имели в виду под "опциями инструментов".

141 голосов
/ 10 мая 2014

Ответ: 

^((?!hede).)*$

Пояснение:

^ начало строки, ( сгруппировать и записать в \ 1 (0 или более раз (соответствует максимально возможному количеству)),
(?! смотрите вперед, чтобы увидеть, если нет,

hede ваша строка,

) конец просмотра, . любой символ, кроме \ n,
)* конец \ 1 (Примечание: поскольку вы используете квантификатор для этого захвата, в \ 1 будет сохраняться только последнее ПОСЛЕДНЕЕ повторение захваченного шаблона)
$ перед необязательным \ n и концом строки

96 голосов
/ 02 сентября 2011

Приведенные ответы отлично, просто академический балл:

Регулярные выражения в значении теоретических компьютерных наук НЕ МОГУТ сделать это так. Для них это должно было выглядеть примерно так: 

^([^h].*$)|(h([^e].*$|$))|(he([^h].*$|$))|(heh([^e].*$|$))|(hehe.+$)

Это только соответствует ПОЛНОМУ. Делать это для под-матчей было бы еще более неловко.

54 голосов
/ 04 января 2013

Если вы хотите, чтобы тест регулярного выражения только не удался, если вся строка совпадает, будет работать следующее: 

^(?!hede$).*

например. - Если вы хотите разрешить все значения, кроме «foo» (то есть «foofoo», «barfoo» и «foobar» пройдут, но «foo» завершится ошибкой), используйте: ^(?!foo$).*

Конечно, если вы проверяете на точное равенство, лучшим общим решением в этом случае является проверка на равенство строк, т.е. 

myStr !== 'foo'

Вы можете даже поставить отрицание за пределы теста, если вам нужны какие-либо функции регулярного выражения (здесь, нечувствительность к регистру и согласование диапазона): 

!/^[a-f]oo$/i.test(myStr)

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

53 голосов
/ 05 августа 2015

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

Vcsn поддерживает этот оператор (который он обозначает {c}, постфикс).

Сначала вы определяете тип своих выражений: например, метки - это буквы (lal_char), которые можно выбрать от a до z (определение алфавита при работе с дополнением, конечно, очень важно), и "значение", вычисленное для каждого слова, является просто логическим: true слово принято, false, отклонено.

В Python: 

In [5]: import vcsn
        c = vcsn.context('lal_char(a-z), b')
        c
Out[5]: {a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z} → ?

затем вы вводите выражение: 

In [6]: e = c.expression('(hede){c}'); e
Out[6]: (hede)^c

преобразовать это выражение в автомат: 

In [7]: a = e.automaton(); a

The corresponding automaton

наконец, преобразуйте этот автомат обратно в простое выражение. 

In [8]: print(a.expression())
        \e+h(\e+e(\e+d))+([^h]+h([^e]+e([^d]+d([^e]+e[^]))))[^]*

, где + обычно обозначается |, \e обозначает пустое слово, а [^] обычно пишется . (любой символ). Итак, с небольшим переписыванием ()|h(ed?)?|([^h]|h([^e]|e([^d]|d([^e]|e.)))).*.

Вы можете увидеть этот пример здесь и попробовать Vcsn онлайн там .

50 голосов
/ 02 января 2009

Вот хорошее объяснение того, почему нелегко отрицать произвольное регулярное выражение. Однако я должен согласиться с другими ответами: если это не гипотетический вопрос, тогда регулярное выражение здесь не правильный выбор.

41 голосов
/ 13 августа 2014

Тесты

Я решил оценить некоторые из представленных опций и сравнить их производительность, а также использовать некоторые новые функции. Сравнительный анализ на .NET Regex Engine: http://regexhero.net/tester/

Контрольный текст:

Первые 7 строк не должны совпадать, поскольку они содержат искомое выражение, а нижние 7 строк должны совпадать! 

Regex Hero is a real-time online Silverlight Regular Expression Tester.
XRegex Hero is a real-time online Silverlight Regular Expression Tester.
Regex HeroRegex HeroRegex HeroRegex HeroRegex Hero is a real-time online Silverlight Regular Expression Tester.
Regex Her Regex Her Regex Her Regex Her Regex Her Regex Her Regex Hero is a real-time online Silverlight Regular Expression Tester.
Regex Her is a real-time online Silverlight Regular Expression Tester.Regex Hero
egex Hero egex Hero egex Hero egex Hero egex Hero egex Hero Regex Hero is a real-time online Silverlight Regular Expression Tester.
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRegex Hero is a real-time online Silverlight Regular Expression Tester.

Regex Her
egex Hero
egex Hero is a real-time online Silverlight Regular Expression Tester.
Regex Her is a real-time online Silverlight Regular Expression Tester.
Regex Her Regex Her Regex Her Regex Her Regex Her Regex Her is a real-time online Silverlight Regular Expression Tester.
Nobody is a real-time online Silverlight Regular Expression Tester.
Regex Her o egex Hero Regex  Hero Reg ex Hero is a real-time online Silverlight Regular Expression Tester.

Результаты:

Результаты - это итерации в секунду в качестве медианы 3 прогонов - Большее число = Лучше 

01: ^((?!Regex Hero).)*$                    3.914   // Accepted Answer
02: ^(?:(?!Regex Hero).)*$                  5.034   // With Non-Capturing group
03: ^(?>[^R]+|R(?!egex Hero))*$             6.137   // Lookahead only on the right first letter
04: ^(?>(?:.*?Regex Hero)?)^.*$             7.426   // Match the word and check if you're still at linestart
05: ^(?(?=.*?Regex Hero)(?#fail)|.*)$       7.371   // Logic Branch: Find Regex Hero? match nothing, else anything

P1: ^(?(?=.*?Regex Hero)(*FAIL)|(*ACCEPT))  ?????   // Logic Branch in Perl - Quick FAIL
P2: .*?Regex Hero(*COMMIT)(*FAIL)|(*ACCEPT) ?????   // Direct COMMIT & FAIL in Perl

Поскольку .NET не поддерживает глаголы действий (* FAIL и т. Д.), Я не смог протестировать решения P1 и P2.

Резюме:

Я пытался протестировать большинство предложенных решений, возможна некоторая оптимизация для определенных слов. Например, если первые две буквы строки поиска не совпадают, ответ 03 можно расширить до ^(?>[^R]+|R+(?!egex Hero))*$, что приводит к небольшому приросту производительности.

Но наиболее читаемым и быстродействующим решением в целом представляется 05 с условным выражением или 04 с положительным квантификатором. Я думаю, что Perl-решения должны быть еще быстрее и более легко читаемыми.

41 голосов
/ 14 июля 2014

С отрицательным прогнозом регулярное выражение может соответствовать чему-то, не содержащему определенного шаблона. На это отвечает и объясняет Барт Киерс. Отличное объяснение!

Тем не менее, с ответом Барта Киерса, нападающая часть будет проверять от 1 до 4 символов вперед при сопоставлении с любым отдельным символом. Мы можем избежать этого и позволить части предпросмотра проверить весь текст, убедиться, что нет «хеде», и тогда нормальная часть (. *) Может съесть весь текст за один раз.

Вот улучшенное регулярное выражение: 

/^(?!.*?hede).*$/

Обратите внимание, что ленивый квантификатор в отрицательной заглядывающей части является необязательным, вместо него вы можете использовать (*) жадный квантификатор, в зависимости от ваших данных: если 'hede' присутствует и в начальной половине текста, ленивый квантификатор может быть быстрее; в противном случае жадный квантификатор будет быстрее. Однако, если «hede» не присутствует, оба будут равны медленно.

Вот демонстрационный код .

Для получения дополнительной информации о Lookahead, пожалуйста, ознакомьтесь с замечательной статьей: Освоение Lookahead и Lookbehind .

Также, пожалуйста, ознакомьтесь с RegexGen.js , генератором регулярных выражений JavaScript, который помогает создавать сложные регулярные выражения. С помощью RegexGen.js вы можете создать регулярное выражение более читабельным способом: 

var _ = regexGen;

var regex = _(
    _.startOfLine(),             
    _.anything().notContains(       // match anything that not contains:
        _.anything().lazy(), 'hede' //   zero or more chars that followed by 'hede',
                                    //   i.e., anything contains 'hede'
    ), 
    _.endOfLine()
);
Страница:
...