webdonsk.ruКак сделать регулярное выражение не жадным
Добавил пользователь Дмитрий К. Обновлено: 10.09.2024
Операция выбора - | . Два РВ, разделенные '|' - составное РВ , для которого определяется подстрока , соответствующая любому из двух РВ. Например, one , TWO и = соответствуют '=|one|TWO' , а =one , FooBar и Two - не соответствуют. Операция выбора - очень удобное средство, но стоит иметь в виду, что в сложных случаях, в сочетании с повторителем * , она может потребовать немало ресурсов - времени или оперативной памяти, как повезет. Подробнее об этом см. [ 27 ] .
Два частных случая повторителя-интервала: повторитель ?, обозначающий использование предшествующего атомарного РВ не более одного раза (может быть выражен с помощью '' ), и повторитель + , обозначающий использование предшествующего атомарного РВ не менее одного раза ( '' ). Оба частных случая постоянно встречаются в повседневной работе; кроме того, обработка + во многих случаях идет существенно быстрее, чем обработка * , поэтому + стоит использовать вместо * везде, где только возможно.
В расширенном РВ определяются именованные множества символов, вроде '[[:alnum:]]' (ему соответствует одна буква или одна цифра), или '[[:blank:]]' (ему соответствует один разделитель - пробел или табуляция). Все именованные множества описаны в руководстве. Главное достоинство именованных множеств - привязка к национальному языку (если она реализована в утилите, использующей РВ): буквой считается не только латинская, но и - в нашем случае - русская буква. Если то же РВ использовать в немецких настройках, задействованные в этом языке латинские буквы с диакритическими знаками или двойное s тоже будут соответствовать '[[:alpha:]]' или '[[:alnum:]]' . По этой же причине рекомендуется не использовать именованные множества , если установленный язык заранее неизвестен.
К $ и ^ добавлено еще два позиционных оператора , '[[: и '[[:>:]]' , которым соответствует начало и конец слова (здесь уместно процитировать параграф BUGS руководства re_format: "The syntax for word boundaries is incredibly ugly"). Строго говоря, эти позиционные операторы слегка расширяют класс распознаваемых подстрок, потому что результат поиска '[[:>:]]' зависит от символа, который не входит в подстроку-результат, т. е. зависит от контекста.
Новый синтаксис РВ получил название расширенного (extended) регулярного выражения .
Толкование неоднозначностей
Подстрока , соответствующая РВ, выбирается, как уже говорилось, из строки . Это значит, что контекст , внутри которого происходит поиск соответствия, ограничен началом и концом строки . Здесь механизм разбора РВ опирается, с одной стороны, на формальное свойство текстового файла состоять из строк , а с другой стороны, на то, что в языках, используемых в UNIX , конец строки обычно имеет значение строгого разделителя , поэтому задача поиска выражения, состоящего из нескольких строк , встречается нечасто.
Избавиться от неоднозначности при поиске подстроки в строке помогает правило левый-длинный ( leftmost longest , дословный перевод: самая левая - самая длинная). Если в строке встречается несколько подстрок, которые соответствуют РВ, из них будет выбрана в качестве ответа та, что раньше всех начинается, то есть самая левая. Если при этом с одного и того же места в строке начинается несколько подстрок, соответствующих РВ, то среди них будет выбрана самая длинная. Например, из всех возможных соответствий выражению 'a.*d' в строке The syntax for word boundaries is incredibly ugly будет соответствовать подстрока от самого левого a до самого правого d: ax for word boundaries is incred .
Выражению 'B*' в строке BBcBBBd можно найти 17 соответствий (из них одна подстрока BBB , 3 BB , 5 B и 8 пустых подстрок в различных позициях). Правильным ответом будет BB в начале строки , потому что, во-первых, это самая левая из возможных подстрок, а во-вторых, самая длинная (среди допустимых, B и BB ). А вот в строке aBBcBBBd первой будет найдена пустая подстрока , потому что 'B*' имеет cоответствие в самом начале строки , и притом ровно одно: пустую подстроку.
Почему так? Во-первых, 5678 отпадает, потому что есть соответствие, которое лежит ближе к началу строки , - 123 . Во-вторых, будет найдено именно 123 , а не 1 или 12 , потому что 123 - самое длинное из возможных соответствий. В-третьих, начальное '2+' и радо бы захватить для себя всю 123 , но тогда на долю второго не остается ничего, и соответствия всему РВ не получается. Так что оно вынуждено уступить второму '7+' хотя бы один символ - 3 .
Подобное поведение регулярных выражений привело к тому, что во вполне серьезной литературе их называют жадными (greedy). "Жадность" регулярных выражений - удобное свойство, на него всегда можно положиться (в смысле однозначности ответа), однако встречаются задачи, решать которые было бы удобнее, если бы выбиралось самое короткое, а не самое длинное соответствие. Многие инструментарии, использующие регулярные выражения , включают в себя диалекты "нежадных" (non-greedy) РВ, например, вводят "нежадные" повторители . Важно знать, что с помощью "нежадных" РВ можно задать язык, не принадлежащий классу регулярных; это, с одной стороны, заметно расширяет наши возможности (непонятно только, часто ли они бывают востребованы), но, с другой стороны, отменяет все предположения о времени поиска и однозначности результата , сделанные для классического варианта РВ.
Жадность, нежадные, притяжательные квантификаторы в регулярных выражениях Java
В этой статье я использовал пользовательскую программу для проверки регулярного выражения во время теста, а затем переписал его для запуска с eclipse:
Greedy quantifiers are considered "greedy" because they force the matcher to read in, or eat, the entire input string prior to attempting the first match. If the first match attempt (the entire input string) fails, the matcher backs off the input string by one character and tries again, repeating the process until a match is found or there are no more characters left to back off from. Depending on the quantifier used in the expression, the last thing it will try matching against is 1 or 0 characters.
The reluctant quantifiers, however, take the opposite approach: They start at the beginning of the input string, then reluctantly eat one character at a time looking for a match. The last thing they try is the entire input string.
Finally, the possessive quantifiers always eat the entire input string, trying once (and only once) for a match. Unlike the greedy quantifiers, possessive quantifiers never back off, even if doing so would allow the overall match to succeed.
Короче,Жадные квантификаторы соответствуют как можно большему числу символов, Если в регулярном выражении присутствует жадный квантификатор, а когда жадный квантификатор соответствует строке, то жадный квантификатор будет соответствовать всем строкам, которые могут быть сопоставлены. Если все регулярное выражение совпадает успешно, оно заканчивается, если оно неуспешно, жадный квантификаторОтойтиОдин символ, еще раз посмотрите, соответствует ли все регулярное выражение успешно, и так далее. Запустите вышеуказанную программу и введите следующую строку:
Здесь используется жадный квантификатор, и теперь процесс описан подробно: Поскольку. * Жадный алгоритм, он будет пытаться сопоставить максимально возможное количество символов, то есть он соответствует xfooxxxxxxfoo. Но следующий foo не может совпадать, потому что нет оставшихся символов. Поэтому. * НужноОтойтиОдин символ, поэтому. * Соответствует xfooxxxxxxfo, остальные o, foo не могут совпадать. Откат еще раз, оставшиеся oo не могут совпадать, откат, оставшиеся foo, совпадение успешно, все совпадение регулярного выражения успешно.
Следующая диаграмма иллюстрирует этот процесс:
Нежадные квантификаторы будут соответствовать как можно меньшему количеству символов, Если регулярное выражение содержит не жадный квантификатор, то не жадный квантификатор будет соответствовать как можно меньшему количеству символов. Если все регулярное выражение не соответствует, не жадный квантификатор будет соответствовать еще одному. Посмотрите еще раз, полностью ли регулярное выражение Матч успешен, поэтому неоднократно. Запустите программу ниже, чтобы ввести следующую строку:
Процесс таков: Поскольку. * - не жадный,. * - Будет соответствовать как можно меньше, поэтому сначала соответствует 0 символов, но полное совпадение регулярного выражения не выполняется. Следовательно, негладкий квантификатор соответствует еще одному, соответствует x, foo точно соответствует строке foo, поэтому сопоставление успешно. Поскольку программа продолжит сопоставлять оставшиеся строки, она начнет второе сопоставление.
Ниже приведен графический дисплей:
Первый матч с xfoo
Запустите второе сопоставление, удалите сопоставленное, сопоставьте процессу xxxxxxfoo:
Притяжательные квантификаторы похожи на жадные квантификаторы, но процесс отступления отсутствует, поэтому, когда совпадение не удается, оно заканчивается. Запустите вышеуказанную программу и введите следующую строку:
* + Является собственническим квантификатором, но также сопоставляет столько строк, сколько возможно, например жадный квантификатор, поэтому. * + Совпадает со всей строкой xfooxxxxxxfoo, но ни одна из оставшихся строк не сопоставляется с помощью foo, поэтому совпадение не выполняется из-за собственнического квантификатора Процесс отката отсутствует, поэтому совпадение заканчивается непосредственно неудачей.
Сейчас регулярные выражения используются многими текстовыми редакторами и утилитами для поиска и изменения текста на основе выбранных правил. Многие языки программирования уже поддерживают регулярные выражения для работы со строками. Например, Perl и Tcl имеют встроенный в их синтаксис механизм обработки регулярных выражений. Набор утилит (включая редактор sed и фильтр grep), поставляемых в дистрибутивах Unix, одним из первых способствовал популяризации понятия регулярных выражений.
Содержание
Регулярные выражения используются для сжатого описания некоторого множества строк с помощью шаблонов, без необходимости перечисления всех элементов этого множества. При составлении шаблонов используется специальный синтаксис, поддерживающий обычно следующие операции:
Конкретный синтаксис регулярных выражений зависит от реализации.
Регулярные выражения состоят из констант и операторов, которые определяют множества строк и множества операций на них соответственно. На данном конечном алфавите S определены следующие константы:
- (пустое множество) ? обозначает ?
- (пустая строка) e обозначает множество
- (строка) a в S обозначает множество a>
и следующие операции:
- (связь, конкатенация) RS обозначает множество < av | a из R и v из S >. Пример: = .
- (перечисление) R|S обозначает объединение R и S.
- (замыкание Клини, звезда Клини) R* обозначает минимальное надмножество из R, которое содержит e и закрыто связью строк. Это есть множество всех строк, которые могут быть получены связью нуля или более строк из R. Например, * = .
Многие книги используют символы ?, + или ? для перечисления вместо вертикальной черты.
Различные реализации регулярных выражений интерпретируют обратную косую черту перед метасимволами по-разному. Например, egrep и Perl интерпретируют скобки и вертикальную черту как метасимволы, если перед ними нет обратной косой черты и воспринимают их как обычные символы, если черта есть.
Многие диапазоны символов зависят от выбранных настроек локализации. POSIX стандартизовал объявление некоторых классов и категорий символов, как показано в следующей таблице:
| POSIX класс | подобно | Perl | означает |
|---|---|---|---|
| [:upper:] | [A-Z] | символы верхнего регистра | |
| [:lower:] | [a-z] | символы нижнего регистра | |
| [:alpha:] | [A-Za-z] | символы верхнего и нижнего регистра | |
| [:alnum:] | [A-Za-z0-9] | цифры, символы верхнего и нижнего регистра | |
| [A-Za-z0-9_] | \w | цифры, символы верхнего, нижнего регистра и "_" | |
| [^A-Za-z0-9_] | \W | не цифры, символы верхнего, нижнего регистра и "_" | |
| [:digit:] | 8 | \d | цифры |
| [^0-9] | \D | не цифры | |
| [:xdigit:] | [0-9A-Fa-f] | шестнадцатеричные цифры | |
| [:punct:] | [. …] | знаки пунктуации | |
| [:blank:] | [ \t] | пробел и TAB | |
| [:space:] | [ \t\n\r\f\v] | \s | символы пробелов(пропуска) |
| [^ \t\n\r\f\v] | \S | не символы пробелов(пропуска) | |
| [:cntrl:] | [\x00-\x1F\x7F] | символы управления | |
| [:graph:] | [:alnum:] ? [:punct:] | символы печати | |
| [:print:] | [\x20-\x7E] | символы печати и символы пропуска(видимые символы и пробелы) |
Википедия — свободная энциклопедия, в которой каждый может изменить или дополнить любую статью
Эту проблему можно решить двумя способами. Первый состоит в том, что в регулярном выражении учитываются символы, не соответствующие желаемому образцу ( ]*> для вышеописанного случая). Второй заключается в определении квантификатора как нежадного (ленивого, англ. lazy)— большинство реализаций позволяют это сделать, добавив после него знак вопроса.
Например, выражению ( ) соответствует не вся показанная выше строка, а отдельные теги (выделены цветом):
Википедия — свободная энциклопедия, в которой каждый может изменить или дополнить любую статью
Также существуют квантификаторы повышения жадности, то, что захвачено ими однажды, назад уже не отдается. Сверхжадные квантификаторы (possessive quantifiers)
Регулярные выражения в POSIX аналогичны традиционному Unix-синтаксису, но с добавлением некоторых метасимволов:
| + | Указывает на то, что предыдущий символ или группа может повторяться один или несколько раз. В отличие от звёздочки, хотя бы одно повторение обязательно. |
| ? | Делает предыдущий символ или группу необязательной. Другими словами, в соответствующей строке она может отсутствовать, либо присутствовать ровно один раз. |
| | | Разделяет альтернативные варианты регулярных выражений. Один символ задаёт две альтернативы, но их может быть и больше, достаточно использовать больше вертикальных чёрточек. Необходимо помнить, что этот оператор использует максимально возможную часть выражения. По этой причине, оператор альтернативы чаще всего используется внутри скобок. |
Также было отменено использование обратной косой черты: \ становится и \(…\) становится (…).
Регулярные выражения в Perl имеют более богатый и в то же время предсказуемый синтаксис, чем даже в POSIX. По этой причине очень многие приложения используют именно Perl-совместимый синтаксис регулярных выражений.
Регулярные выражения, также называемые regex, синтаксис или, скорее, язык для поиска, извлечения и работы с определенными текстовыми шаблонами большего текста. Он широко используется в проектах, которые включают проверку текста, NLP (Обработка естественного языка) и интеллектуальную обработку текста.
Введение в регулярные выражения
Регулярные выражения, также называемые regex, используются практически во всех языках программирования. В python они реализованы в стандартном модуле re .
Он широко используется в естественной обработке языка, веб-приложениях, требующих проверки ввода текста (например, адреса электронной почты) и почти во всех проектах в области анализа данных, которые включают в себя интеллектуальную обработку текста.
Эта статья разделена на 2 части.
Прежде чем перейти к синтаксису регулярных выражений, для начала вам лучше понять, как работает модуль re .
Итак, сначала вы познакомитесь с 5 основными функциями модуля re , а затем посмотрите, как создавать регулярные выражения в python.
Узнаете, как построить практически любой текстовый шаблон, который вам, скорее всего, понадобится при работе над проектами, связанными с поиском текста.
Что такое шаблон регулярного выражения и как его скомпилировать?
Шаблон регулярного выражения представляет собой специальный язык, используемый для представления общего текста, цифр или символов, извлечения текстов, соответствующих этому шаблону.
Основным примером является \s+ .
Здесь \ s соответствует любому символу пробела. Добавив в конце оператор + , шаблон будет иметь не менее 1 или более пробелов. Этот шаблон будет соответствовать даже символам tab \t .
В конце этой статьи вы найдете больший список шаблонов регулярных выражений. Но прежде чем дойти до этого, давайте посмотрим, как компилировать и работать с регулярными выражениями.
Вышеупомянутый код импортирует модуль re и компилирует шаблон регулярного выражения, который соответствует хотя бы одному или нескольким символам пробела.
Как разбить строку, разделенную регулярным выражением?
Рассмотрим следующий фрагмент текста.
У меня есть три курса в формате “[Номер курса] [Код курса] [Название курса]”. Интервал между словами разный.
Передо мной стоит задача разбить эти три предмета курса на отдельные единицы чисел и слов. Как это сделать?
Их можно разбить двумя способами:
- Используя метод re.split .
- Вызвав метод split для объекта regex .
Оба эти метода работают. Но какой же следует использовать на практике?
Если вы намерены использовать определенный шаблон несколько раз, вам лучше скомпилировать регулярное выражение, а не использовать re.split множество раз.
Поиск совпадений с использованием findall, search и match
Предположим, вы хотите извлечь все номера курсов, то есть 100, 213 и 156 из приведенного выше текста. Как это сделать?
Что делает re.findall()?
В приведенном выше коде специальный символ \ d является регулярным выражением, которое соответствует любой цифре. В этой статье вы узнаете больше о таких шаблонах.
Добавление к нему символа + означает наличие по крайней мере 1 числа.
Подобно + , есть символ * , для которого требуется 0 или более чисел. Это делает наличие цифры не обязательным, чтобы получилось совпадение. Подробнее об этом позже.
В итоге, метод findall извлекает все вхождения 1 или более номеров из текста и возвращает их в список.
re.search() против re.match()
Как понятно из названия, regex.search() ищет шаблоны в заданном тексте.
Но, в отличие от findall , который возвращает согласованные части текста в виде списка, regex.search() возвращает конкретный объект соответствия. Он содержит первый и последний индекс первого соответствия шаблону.
Аналогично, regex.match() также возвращает объект соответствия. Но разница в том, что он требует, чтобы шаблон находился в начале самого текста.
В качестве альтернативы вы можете получить тот же результат, используя метод group() для объекта соответствия.
Как заменить один текст на другой, используя регулярные выражения?
Для изменения текста, используйте regex.sub() .
Рассмотрим следующую измененную версию текста курсов. Здесь добавлена табуляция после каждого кода курса.
Из вышеприведенного текста я хочу удалить все лишние пробелы и записать все слова в одну строку.
Для этого нужно просто использовать regex.sub для замены шаблона \s+ на один пробел .
Предположим, вы хотите избавиться от лишних пробелов и выводить записи курса с новой строки. Чтобы это сделать, используйте регулярное выражение, которое пропускает символ новой строки, но учитывает все другие пробелы.
Это можно сделать, используя отрицательное соответствие (?!\n) . Шаблон проверяет наличие символа новой строки, в python это \n , и пропускает его.
Группы регулярных выражений
Группы регулярных выражений — функция, позволяющая извлекать нужные объекты соответствия как отдельные элементы.
Предположим, что я хочу извлечь номер курса, код и имя как отдельные элементы. Не имея групп мне придется написать что-то вроде этого.
Давайте посмотрим, что получилось.
Я скомпилировал 3 отдельных регулярных выражения по одному для соответствия номерам курса, коду и названию.
Для номера курса, шаблон 3+ указывает на соответствие всем числам от 0 до 9. Добавление символа + в конце заставляет найти по крайней мере 1 соответствие цифрам 0-9. Если вы уверены, что номер курса, будет иметь ровно 3 цифры, шаблон мог бы быть 1 .
Для кода курса, как вы могли догадаться, [А-ЯЁ] будет совпадать с 3 большими буквами алфавита А-Я подряд (буква “ё” не включена в общий диапазон букв).
Для названий курса, [а-яА-ЯёЁ] будем искать а-я верхнего и нижнего регистра, предполагая, что имена всех курсов будут иметь как минимум 4 символа.
Можете ли вы догадаться, каков будет шаблон, если максимальный предел символов в названии курса, скажем, 20?
Теперь мне нужно написать 3 отдельные строки, чтобы разделить предметы. Но есть лучший способ. Группы регулярных выражений.
Поскольку все записи имеют один и тот же шаблон, вы можете создать единый шаблон для всех записей курса и внести данные, которые хотите извлечь из пары скобок ().
Обратите внимание на шаблон номера курса: 2+ , код: [А-ЯЁ] и название: [а-яА-ЯёЁ] они все помещены в круглую скобку (), для формирования группы.
Что такое “жадное” соответствие в регулярных выражениях?
По умолчанию, регулярные выражения должны быть жадными. Это означает, что они пытаются извлечь как можно больше, пока соответствуют шаблону, даже если требуется меньше.
Давайте рассмотрим пример фрагмента HTML, где нам необходимо получить тэг HTML.
Вместо совпадения до первого появления ‘>’, которое, должно было произойти в конце первого тэга тела, он извлек всю строку. Это по умолчанию “жадное” соответствие, присущее регулярным выражениям.
С другой стороны, ленивое соответствие “берет как можно меньше”. Это можно задать добавлением ? в конец шаблона.
Если вы хотите получить только первое совпадение, используйте вместо этого метод поиска search .
Наиболее распространенный синтаксис и шаблоны регулярных выражений
Теперь, когда вы знаете как пользоваться модулем re, давайте рассмотрим некоторые обычно используемые шаблоны подстановок.
Основной синтаксис
| . | Один символ кроме новой строки |
| \. | Просто точка . , обратный слеш \ убирает магию всех специальных символов. |
| \d | Одна цифра |
| \D | Один символ кроме цифры |
| \w | Один буквенный символ, включая цифры |
| \W | Один символ кроме буквы и цифры |
| \s | Один пробельный (включая таб и перенос строки) |
| \S | Один не пробельный символ |
| \b | Границы слова |
| \n | Новая строка |
| \t | Табуляция |
Модификаторы
| $ | Конец строки |
| ^ | Начало строки |
| ab|cd | Соответствует ab или de. |
| [ab-d] | Один символ: a, b, c, d |
| [^ab-d] | Любой символ, кроме: a, b, c, d |
| () | Извлечение элементов в скобках |
| (a(bc)) | Извлечение элементов в скобках второго уровня |
Повторы
| [ab] | 2 непрерывных появления a или b |
| [ab] | от 2 до 5 непрерывных появления a или b |
| [ab] | 2 и больше непрерывных появления a или b |
| + | одно или больше |
| * | 0 или больше |
| ? | 0 или 1 |
Примеры регулярных выражений
Любой символ кроме новой строки
Точки в строке
Любая цифра
Все, кроме цифры
Любая буква или цифра
Все, кроме букв и цифр
Только буквы
Соответствие заданное количество раз
1 и более вхождений
Любое количество вхождений (0 или более раз)
0 или 1 вхождение
Граница слова
Границы слов \b обычно используются для обнаружения и сопоставления началу или концу слова. То есть, одна сторона является символом слова, а другая сторона является пробелом и наоборот.
Например, регулярное выражение \btoy совпадает с ‘toy’ в ‘toy cat’, но не в ‘tolstoy’. Для того, чтобы ‘toy’ соответствовало ‘tolstoy’, используйте toy\b .
Можете ли вы придумать регулярное выражение, которое будет соответствовать только первой ‘toy’в ‘play toy broke toys’? (подсказка: \ b с обеих сторон)
Аналогично, \ B будет соответствовать любому non-boundary( без границ).
Например, \ Btoy \ B будет соответствовать ‘toy’, окруженной словами с обеих сторон, как в ‘antoynet’.
Практические упражнения
1. Извлеките никнейм пользователя, имя домена и суффикс из данных email адресов.
2. Извлеките все слова, начинающиеся с ‘b’ или ‘B’ из данного текста.
3. Уберите все символы пунктуации из предложения
Ответы
\b находится слева от ‘B’, значит слово должно начинаться на ‘B’.
Добавьте flags=re.IGNORECASE , что бы шаблон был не чувствительным к регистру.
Надеемся, информация была вам полезна. Стояла цель — познакомить вас с примерами регулярных выражений легким и доступным для запоминания способом.
Читайте также: