Регулярные выражения, часть 2

Новый регламент

На оставшееся время курс программирования будет нарезан на маленькие кусочки (по 2-4 занятия), которые я буду называть блоками. Темы блоков будут приблизительно такие (не в хронологическом порядке):

• графические интерфейсы – Tkinter

• добывание информации из сети (urllib, robotparser) и грубая очистка текста
• документация и тесты, исключения, объектно-ориентированное программирование (классы, наследование)
• основы алгоритмов и дискретной математики (сортировка, поиск, деревья, графы)
• работа с полуструктурированными данными (html, xml, json)

За каждый блок будет ставиться оценка. Итоговая оценка за курс будет равна средней оценке за блоки.

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

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

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

Перед (почти) каждым блоком я буду выдавать задание, которое можно выполнить, чтобы получить за блок автомат. Пожалуйста, старайтесь их решать! Если у вас это выйдет, это сэкономит время и вам, и мне!

Регулярные выражения -- это алгоритм классификации

Как мы уже поняли, написать регулярное выражение, которое в точности описывает какие-нибудь реалистичные требования, бывает чрезмерно сложно. Чтобы писать хорошие регулярные выражения нужно понимать, что мы хотим классифицировать, и какие упрощения можно допускать в постановке задачи.

Для любых алгоритмов классификации их находки и ненаходки классифицируют в четыре стопки: True Positive, True Negative, False Positive, False Negative (количества находок в каждой из этих стопок часто обозначают TP, TN, FP, FN, соответственно, и через них определяют понятия полноты, точности, специфичности, селективности). Смысл этих стопок очень прост.

Слова Positive/Negative обозначают: "нашлось или не нашлось". Слова True/False обозначают: "то, что хотели или не то, что хотели".

Возьмём в качестве примера выражение: http://[a-z]+([.][a-z]+)(/[a-z]+)*

Для такого выражения:

• http://www.yandex.ru – это строка, которая является адресом сайта, и она входит в множество находок (строк, описываемых нашим выражением). Она нашлась, и это правильно: это True Positive.

• hello, world! – это строка, которая не является адресом сайта, и она не входит в множество находок. Она не нашлась, и так и должно быть: это True Negative.

• http://example.c/ – домена верхнего уровня .c не существует, так что правильным адресом сайта его назвать нельзя – однако в находках оно есть. То есть оно нашлось, и это не порядок: это False Positive.

• www.yandex.ru или http://web-corpora.net – это строка, которая является адресом сайта, но в множество находок не входит. Она не нашлась, и это неправильно: это False Negative.

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

1. правда ли регулярные выражения – это самый простой и понятный способ решить эту задачу?

2. когда вы написали регулярное выражение: подумайте, а ещё лучше, проверьте на реальных данных есть ли какие-нибудь частые случаи, которые у вас попадают в False Negative или False Positive? (Т.е. когда вы упускаете важные случаи или допускаете слишком много мусорных находок).

Обратные слэши в питонских строках

Мы могли заметить, что в регулярных выражениях обратные слэши играют довольно существенную роль. И, хуже того, иногда их может оказаться много. Напримет, если мы хотим написать регулярное выражение, которое описывает строки, в которых два обратных слэша идут подряд, получится длинно, например: [A-Z]:\\\\([a-z]+\\)*

В данном случае мы написали смысловую строку, описывающую регулярное выражение.

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

   1 regexp = "[A-Z]:\\\\\\\\([a-z]+\\\\)*"
   2 print regexp

Задание: объясните, почему. Адекватным представлением питонской строки можно считать то, как её напечатает print. Как напечатает print нашу строку, если в ней написать просто само регулярное выражение без изменений?

Чтобы не мучиться в этом месте, и видеть регулярное выражение таким, какое оно и есть, в питоне есть специальный тип строк: "raw strings" – в которых питон кладёт в текст строки дословно то, что есть от кавычки до кавычки без каких-либо преобразований. (Собственно, все преобразования, какие делает питон, связаны с обратными слэшами, поэтому можно сказать так, что в raw strings обратные слэши пишутся так же как и слышатся). Для этого перед строкой нужно поставить буквы r вплотную к кавычке:

   1 regexp = r"[A-Z]:\\\\([a-z]+\\)*"
   2 print regexp

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

Применение регулярных выражений в питоне

За работу с регулярными выражениями в питоне отвечает модуль re.

С помощью регулярных выражений мы можем решать несколько разных задач:

re.findall

Первая задча: поиск всех подстрок входной строки, которые удовлетворяют регулярному выражению. (Т.е. входят в множество строк, описываемых им).

Это делает функция re.findall. Функция получает на вход регулярное выражение и текст, в котором мы хотим его искать, и возвращает список находок:

   1 import re
   2 
   3 lowercase_words = re.findall(r"[a-z]+", "This old man,\nHe plays one,\nHe plays knick-knack on my thumb")
   4 print lowercase_words

   1 import re
   2 print re.findall(r"[a-z]+([a-z]{2})", "With a knick-knack paddiwhack,\n Give a dog a bone,\nThis old man came rolling home")

   1 import re
   2 print re.findall(r"([a-z]+)([a-z]{2})", "This old man came rolling home.")

re.sub

Вторая задача: мы хотим найти в тексте подстроку и заменить её на что-нибудь.

Это делает функция re.sub. Она получает на вход регулярное выражение, строку подстановки, и входной текст, в котором она будет искать. Функция возвращает текст, в котором все находки регулярного выражения заменены на строку подстановки:

   1 import re
   2 print re.sub(r"[a-z]+", "smurf", "This old man, he plays two, he plays knick-knack on my shoe...")

В строке подстановки мы можем попросить питон использовать некоторые части исходной строки, найденной регулярным выражением. В качестве границ интересующих нас частей строк питон использует скобки в регулярном выражении. Скобки нумеруются начиная с единицы в порядке открывающих скобок. Считается, что всё выражение целиком вдобавок ограничено ещё одной невидимой нулевой парой скобок. Мы можем в строке подстановки обращаться к содержимому соответствующей пары скобок с помощью обозначания: обратный слэш и номер скобки. Очевидно, для этого тоже удобнее использовать "raw-strings":

   1 import re
   2 print re.sub(r"[aeiouy]", r"\1l\l", "This old man, he plays two, he plays knick-knack on my shoe...")

re.match

Третья потребность: проверить, принадлежит ли строка заданному множеству. (Например, это нужно если мы токенизировали текст и хотим выделить тип токенов "дата", тип токенов "ссылка на веб" и т.п.)

Для этого в питоне есть почти эквивалентные функции: re.match и re.search, которые принимают на вход регулярное выражение и строку и выдают нужный нам ответ. (Разница между ними следующая: re.match проверяет, что строка начинается с подстроки, удовлетворяющей регулярному выражению, а re.search проверяет, что в строке есть хотя бы где-то хотя бы одна подстрока, удовлетворяющая регулярному выражению).

   1 import re
   2 import utils
   3 tokens = utils.tokenize("This old man, he plays three, he plays knick-knack on my knee...")
   4 for token in tokens:
   5     if re.match(r"^[a-zA-Z]+-[a-zA-z]+$", token):
   6         print token

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

• ^ обозначает начало строки

• $ обозначает конец строки

re.split

Четвёртая потребность: разбить строку на куски от подстроки из множества до подстроки из множества.

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

   1 import re
   2 print re.split(r"[.,!]|[.]{3}", "This old man, he plays four, he plays knick-knack on my door... With a")

   1 import re
   2 parts = re.split(r"(do(g))? a", "With a knick-knack, paddiwhack, give a dog a bone, this old man came rolling home")
   3 print parts
   4 print parts[::3]

Для самостоятельного изучения

В питонских регулярных выражениях есть ещё несколько очень полезных возможностей, которыми я пользуюсь очень редко, но очень доволен:

• есть короткие сокращения для полезных символов: любая буква \w, любая цифра \d, граница слова \b...

• можно давать скобкам имена, и обращаться к ним по именам, а не по номерам
• можно писать регулярное выражение с комментариями внутри него к разным частям
• можно вытаскивать из питона данные про отдельные находки регулярных выражений

Литература

• Очень хорошо и полно питонский синтаксис регулярных выражений и способы работы с ними описаны в стандартной документации питона: http://docs.python.org/2.7/library/re.html

• http://regexone.com/ интерактивные уроки по регулярным выражениям остаются полезными