Подписаться  на наше издание быстро и дешевле чем где-либо Вы можете прямо сейчас! Подписаться!

 

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


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


Вот и я о том же: одно дело регулярные выражения использовать, а другое — знать, как они реализованы. Удовольствие второго порядка, чем сейчас и займемся.


Кого ловить будем?


Регулярные выражения, выражаясь регулярно, относятся к теории распознавания образов. Кстати, я был шокирован, когда вполне приличные люди доказывали мне, что распознавание картинок — это образы, а вот распознавание, скажем, звука — уже нет. Вот интересно, как это компьютер различает значение битов — где у нас картинки с непонятным девушками в романтических позах, а где матерные диктофонные частушки? Интересно было бы у компьютера об этом спросить — только самому же и ответ придется программить. Поскольку компьютер не понимает наших условностей, а понимает биты и байты :).


Def. Если байты несут информацию — значит, это сигнал. Под словом "информация" мы подразумеваем нечто субъективно полезное для человека — компу же все едино. Объективно полезной информации не существует в принципе, хотя "теологи" могут, конечно, попариться от такой идеи. Ну или, если более обтекаемо, скажем, что в отсутствие наблюдателя стоимость информации всегда будем принимать равной нулю — а это равнозначно ее отсутствию. Что такое сигнал и как его отделить от шума, знает только человек (или кто там у нас наблюдатель). Распознавание любого сигнала (в данном случае — цифрового, но вообще-то не факт) будем называть распознаванием образов. О’кэй? Двигаемся дальше.


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


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


Во-первых, алгоритм regexp отвечает на вопрос, совпадает ли подстрока с текстом: будем считать, что это реализуется условной функцией/методом Match(), хотя в Perl записывается совсем по-другому. Скажем, Regexp("ф").Match("фыва") равно TRUE, то бишь "есть такая буква".


Второй вопрос: что совпало? Например, Regexp("б.*?a").Match("бабагаламага") точно вернет совпадение — но что совпадет? В реальной жизни, поскольку применяется "быстрое" совпадение, совпадет первое "ба", но мог бы быть и весь текст "бабагаламага", поскольку он удовлетворяет шаблону так же, как и "баба".

 

Сложная, но умная реализация regexp могла бы возвращать список всех возможных совпадений, хотя за эффективность такой системы я не поручусь — и, кроме того, что бы вы делали с этим списком? Понадобился бы новый алгоритм по нахождению искомой подстроки.


С вопросом "что совпало?" соседствует и вопрос "что с этим делать?". Существует две распространенные линии поведения.


Первая, очень популярная: как в Perl, копировать найденный фрагмент или фрагменты в рамках предопределенных глобальных переменных. Собственно, есть три такие переменные: что найдено, текст до совпадения и после. Плюс по одной переменной для каждой "захваченной" группы: скажем, после m/(r.+l)/ от "Unreal Tournament" в переменную $1 попадет "real". В самом регулярном выражении то же самое обозначается как \1. Эти переменные называются обратными ссылками. Обратные ссылки имеют неоценимое значение при разборе вложенных структур, в частности — HTML и XML, поскольку позволяют найти тэги со всеми вложенными тэгами, на впадая при этом в словоблудие. Возьмем классический пример:

 

 Regexp("< H([1-6]) >.*?< /H\1 >","i")

 

Это обозначает "найти все заголовки, начинающиеся тэгом от < H1 > до < H6 > и закрывающиеся парным, такого же уровня. Условно говоря, второй параметр "i" приказывает не обращать внимания на регистр символов. Эти же обратные ссылки могут быть использованы и как часть строк замены. Аналогично, хоть и более понятно, работают обратные ссылки в DOT.NET — там обратным ссылкам можно давать нормальные имена переменных.


Иногда, однако, реализация иная: текст поиска после совпадения просто усекается, в буфере текста остается только то, что находится ниже совпавшей строки. Я встречал такой подход в NQL; кроме того, по здравому размышлению, так же работает и заLOOPленный (выполняющий поиск в цикле) grep. Таким образом, очень легко наладить поиск нескольких вхождений в цикле и даже вложенные поиски. Например, несколько таблиц, каждая из которых разбивается на строки, потребуют, в лучшем случае, простой рекурсии.


В остальных Perl-подобных системах явно дается ответ на вопрос: что делать со множественными совпадениями? Список совпадений возвращается динамическим набором — например, списком в Perl и коллекцией в DOT.NET. Вроде неплохой ход, но как это будет работать с иерархическими структурами неизвестного уровня вложения? Для таких структур более подойдет пошаговое прохождение, вроде доморощенного SAX.


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


Наконец, последнее — среда поиска, или набор ключей поиска, если угодно. Самые распространенные параметры — это "игнорировать ли различие прописных и строчных букв", "считать ли перевод строки символом" и "возвращать ли все совпадения за один раз". Более сложные вещи, способные при отладке поставить дыбом ваши редеющие волосы — это подстановка вычисляемых выражений в регулярные выражения в Perl и даже "подстановка в подстановку", если уж на то пошло. Мы не будем заниматься такими интересными, но малоэффективными вещами. Хотите подвыражения? а) вычисляйте; б) подставляйте; в) получайте результат.


Девертисмент


Мы собирались разобраться в регулярных выражениях с точки зрения кода. Конечно, простой ход — закачать исходники Perl или grep. Но там, я вам скажу, скучновато читать. В наличии — манера письма на C, которую я бы назвал дедовской, вплоть до дедовщины, со множеством историзмов и побочных соображений, вроде арифметики ссылок. Поэтому в качестве инструмента разработки (точнее — демонстрации) я решил выбрать Java. Отличный язык высокого уровня. Можно даже сказать — самого высокого. К тому же Sun Microsystems просто умоляет использовать его при каждом возможном случае. А мы выполняем такие желания :).


С другой стороны, Microsoft Corporation очень просит не использовать их продукты без голограммы и письменного разрешения, а также без отчислений в фонд пострадавших от жадности. Тоже выполняем: Visual Studio — с глаз долой, MS Office — прочь, Visual Basic — в ад к чертям, в обнимку с DOT.NET. Буквально уговорили, отцы, хе-хе…


Итак, Java. Чем хороша эта самая Java так это своей многолетней недоразвитостью в сфере регулярных выражений. Точнее, даже не так — медлительностью разработчиков. Горячие калифорнийские парни никак не могли (вплоть до версии 1.4 JRE) написать эти самые регулярные выражения. То ли жара там стояла сильная, то ли девочки в бикинях отвлекали — но на разработку пакета java.util.rgex ушло целых пять лет (если считать, конечно, от даты выхода первой версии Java и предположить, что тогда же разработчики и начали разработку этого regex, в чем я сомневаюсь). Что приятно: Java всегда была бесплатной, вместе со средствами разработки, компиляторами, документацией и сервером приложений на ее же основе. Так что люди поступали благородно — что сделали, то сделали, не обессудьте и примите как есть.


А в это же время, закованный в три холодильника на полном морозе сидел другой человек, Стивен Брандт. Человек, кстати, по жизни занимается черными дырами. И уж не важно, по какой причине (то ли ему просто делать больше нечего было), но он не постеснялся и написал собственный движок регулярных выражений на чисто-Java. Называется этот пакет com.stevesoft.pat, сайт расположен здесь: www.javaregex.com/home.html.


Этот пакет — один из нескольких (может, и десятков), связанных с регулярными выражениями, который не просто пережил многие релизы, но и продолжает развиваться, кое в чем даже превосходя Sun’овский вариант. Отчасти потому, что многие уже использовали его код во времена, когда другого еще не было. В числе друзей и почитателей этой библиотеки — Borland и Oracle, каковой факт, конечно, делает создателю честь, а также позволяет надеяться, что это то, что нам нужно. И, конечно же, это Open Source — то есть source прилагается, а также и бинарии с пользовательской документацией.


Для понимания дальнейшего прошу закачать исходники. Или найдите их на нашем диске — что даже предпочтительнее.


Снизу-вверх: классификация и уплотнение


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


Классификация — часто первая операция на входе экспертных систем. Вместо того чтобы оперировать непонятным значением "196 см", можно просто транслировать его в предметную категорию "высокий мэн". Нечто подобное делается и функциями уплотнения информации. Разница невелика: собственно классификация и есть вариант такой функции — но заданной таблично. Функция же может быть задана формулой. Например, функция "квадрат" отображает вещественные числа в положительные, а значит значительно уменьшает (потенциально, конечно) количество так называемых экспертных состояний. Другой пример: перед распознаванием текста отсканированное изображение часто переводится в монохромное или вообще однобитовое представление. Явное отсечение лишней информации, шума — и таким образом "на дне" остается больше полезного сигнала. Такое преобразование происходит с помощью функции, а не таблично.

 


Исходный текст regex.c является довольно стабильным — последние правки,
учитывающие кодировку UTF-8, были внесены еще в 1999 году


А при чем здесь регулярные выражения? Очень просто — два огромных файла, составляющие половину размера проекта: Bits.java и CaseMgr.java являются просто таблицами. Первая — типичный классификатор, позволяет для любого символа UTF8 узнать, является ли он символом (а многие и не являются), буквой, цифрой, пробельным символом и т.д. Это делается в табличном виде, поскольку буквы многих языков, и украинского в том числе, не представлены одним диапазоном целых чисел.
Второй файл — CaseMgr.java — содержит сжимающие функции типа "преобразование регистра символов". При этом преобразовании возможных вариантов станет значительно меньше, три различных символа превратятся в один "случай" — а значит, что-то сможет работать эффективнее, где–то понадобится меньше сравнений. Кстати, здесь есть и избыточность: если прописной вариант символа — буква, то и большой тоже наверняка буква. Уже можно сэкономить — на данных. Можно и наоборот: сначала проверить "на букву", а потом конвертировать регистр. Многие символы при этом можно не преобразовывать. На самом деле применяются еще более хитрые методы оптимизации.

 


AnyJ — инструмент №1 для Java-хакера, исследующего открытый код


К этой же категории классификаторов и иже с ними относятся еще два класса: Ctrl и Prop. Последний предоставляет "высокоуровневый" эксплойт на тему Bits. Ну действительно, кто же станет копаться в битах, а вот спросить "не цифра ли это?" — совсем другое дело. Кроме того, есть класс UniValidator, от которого происходит масса мини-классов, описанных в начале файла Regex.java — тоже перепевки на те же темы. Все они используют Prop и CaseMgr в качестве низкоуровневой основы. Я бы, конечно, инкапсулировал это немного лучше…


Мы не зря начали с таких низкоуровневых операций, как классификация и преобразование информации: как уже было сказано, они, как правило, предваряют любой цикл принятия решений, распознавания образов или автоматизированной экспертизы (по сути — три взгляда на один процесс). Заодно мы отбросили 148 Кб тривиального текста, и осталось-то всего 226 Кб, причем многие исходники "весят" меньше килобайта. Вот что значит Java!


Главное звено: Pattern


Теперь, запасшись дюжиной полезных методов для классификации, переходим к глобальной структуре приложения (библиотеки — или пакета, если угодно). Для создания UML-иллюстраций я воспользовался несложным софтом Cadifra UML Editor. Он позволяет рисовать иерархии классов в стандартной нотации — я нарочно не генерирую такие схемы автоматически, чтобы по мере рисования быть in-conf с кодом. Софт лежит на нашем диске, Там же — схемы в первозданном виде, а то еще подумаете, что я их где-то срисовал :).


Самый главный класс — нет, не Regex, хотя и он тоже нужен. Главный, в смысле "отец народов",— это виртуальный класс Pattern. Каждый образец может быть простым или сложным (составным). Поэтому регулярное выражение — это последовательность образцов, каждый из которых может быть регулярным выражением:

 

регэкс:список регвыражений, регвыражение: примитивный образец ИЛИ регэкс

 

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

 

Pattern next=null,parent=null;

 

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


Кстати, а вот и обход всего дерева (пока только в-хвост-и-наверх) — в одну строку:

 

public Pattern getNext() {
 return next != null ? next :(parent == null ? null : parent.getNext());
}

 

Проверка "хвоста" на предмет удовлетворения образцу тоже выглядит несложно:

 

public int nextMatch(int i,Pthings pt) {
 Pattern p = getNext();
 return p==null ? i : p.matchInternal(i,pt);
}

 

Комментарий советует: если метод matchInternal() находит совпадение, то в качестве результата верните nextMatch(), и -1 в противном случае. Всего-то: если совпало, то совпадай дальше. Конечно, в реальной жизни все будет сложнее.


Еще два интересных места в этом пазле проясняются по мере изучения класса Pattern. Метод matchInternal(int, Pthings) является тем механизмом, который сравнивает данный образец в данной позиции. Pthings — это как раз условия сравнения, начиная от самого текста (тоже… условие), флажки, вроде "игнор регистра", а также список обратных ссылок, "нажитых" к моменту, когда курсор сравнения продвинулся до данного условия. Также обратите внимание на tuple (пару значений) patInt: одно значение обозначает целое (положительное) число; второе, логическое, хранит особый флажок "бесконечность". В результате получается значение и диапазоном целые-плюс-бесконечность.

 


Пока нарисуете такую схемку — будете знать о классах почти все


Остальные методы Pattern — некоторые служебные делишки, вроде добавления образца к родителю или добавления нового образца к списку. Кстати, здесь нелишним будет заметить, что преобразование строки регулярного выражения в такую связанную структуру называется компиляцией regexp.

 


Pthings — состояние движка, включая сам текст, ключи, курсор и "марки"

 

Мы не будем рассматривать синтаксический разбор regexp — это скучная и ничем не примечательная операция. Скажем только, что основная работа происходит в методе Regex::compile1.


Некоторые "горячие" образцы


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


Например, посмотрим на самый простой oneChar. Первое открытие, не относящееся к регулярным выражениям, это наличие не двух, а трех регистров букв: верхний, нижний и заглавный. Честно говоря — (век живи — век учись), первый раз слышу. Сравнение internalMatch читается легко: совпадает символ, или, если указан "игнор регистра", то выражение может совпадать с одной из двух других букво-форм. Ну а дальше — ret = nextMatch(pos+1,pt). Раньше курсорчик pos продвигала принимающая сторона, а теперь вот, как в Perl,— вызывающая.


К этой же категории "однозначных" (minChars==maxChars==1) относится и очень популярный образец любого символа ".", описанный в классе Any. Фактически, не проходит только два варианта: "мы уже за последним символом" или "мы в строке, под нами CR, а флаги говорят, что CR — это не любой символ". В остальных случаях никаких проверок не производится, курсор просто переводится на следующий символ.


Возьмем что-нибудь посложнее: например, обработку метасимвола "в конце строки" ($) или "не в конце" (\Z). Этим образцом (а фактически двумя) занимается класс End. Обратите внимание на параметр в конструкторе — это как раз тип образца "да-нет". Конец строки, как видите, бывает двояким: то ли мы вообще вышли за ее пределы (бывает, если строка вообще не заканчивается CR, одинокая или последняя в тексте), то ли "под курсором" как раз находится перевод строки (по тексту — первый вариант).


Заслуживает внимания pt.mFlag — это флаг multiline. Если он установлен, мы игнорируем все "\n", для нас конец строки — это только "за текстом". Как результат — мы можем найти regexp, который будет начинаться на одной строке — а заканчиваться на другой.


Как можно догадаться, есть аналогичный образец Start — он является "зеркальным" отражением End и обрабатывает метасимволы ^ и \A. Логично, что эти метасимволы не переводят курсор и устанавливают maxChars==0.


Существуют также образцы, которые можно назвать вырожденными.


Первый — NoPattern — не удовлетворяет ничему, matchInternal() всегда возвращает -1. Этот образец используется для пустого регулярного выражения, чтобы не включать проверку Regex.Pattern==null в операцию поиска _search.


Второй — NullPatten — является ответом на команду "сравнить с ничем", как в выражении "hello|world|". Синтаксически такое выражение по соглашению является корректным, но что сравнивать после второго ИЛИ? NullPattern далает "ничего" — а именно:

 

public int matchInternal(int p,Pthings pt) {return nextMatch(p,pt);}


Образцы-контейнеры


Все приводимые до сих под образцы были "листочками", то есть не имели ни дочерних элементов, ни средств их адресации — вы-то помните, что стандартный Pattern::getNext() перемещается только "в-хвост-и-наверх" и ни один из простых образцов это не переопределяет. "Лазейку" к дочерним элементам открывает класс PatternSub, который не делает ничего, кроме определения дополнительного поля Pattern sub. Это и есть указатель на дочерние образцы.


Яркий представитель абстрактного контейнера PatternSub — класс Multi. Это именно та "бестия", которая обрабатывает метасимволы +, *, ?, {1,10}, {5,}, {5} и так далее. То есть это как раз то, что позволяет сравнивать некоторый образец заданное количество раз, где "заданное" может принимать значения от 0 до бесконечности. Как вам, конечно, известно, "+" можно записать как {1,}, *{0,}, а "?" — как {0,1}. То, что повторяется (а это может быть регэкс любой сложности), как раз и является дочерним образцом.


Здесь же реализуется логика жадного или минимального поиска, этим заведует MatchFewest. Собственно, сама обработка реализуется другим классом — Multi_stage2. Рассказать, что там творится, в двух словах не получится.


Самое главное разобраться в лукавом цикле. Обратите первое внимание на GetNext() — метод возвращает nextRet, который тут же, в конструкторе, указывает на this. Кто не понял — это цикл. Сам мультик2 никогда не вызывает свой GetNext — вместо этого он хочет super.GetNext, то есть обычный переход дальше. А вот когда вложенный регэкс постарается "свалить" по parent.getNext(), его будет ждать большой облом.

Все, как всегда, заключено в matchInternal — и, конечно, большую часть занимают проверки, не совпало ли меньше или больше, чем было задано рамками {a,b}. Собственно, количество совпадений хранится в count.


Часто встречаемая функция testMatch() — это финализированный метод Pattern. Важная операция — это создание копии "марок", то есть обратных ссылок для каждой предварительной версии. Дело в том, что во время поиска мы можем долго "совпадать" и по ходу "подклеивать марки", то есть создавать переменные обратных ссылок. В какой-то момент мы можем решить, что нашли более "жирное" совпадение, так что старые марки нам ни к чему,— но потом "обломиться" и вернуться к последнему надежному варианту:


int ret = p.matchInternal(pos,pt);
if(ret < 0) pt.marks = tab;
return ret;

 

Обратите внимание — здесь очень "косоугольная" рекурсия: мы вызываем статический метод суперкласса, который вызывает опять-таки matchIntrnal() субкласса, который вызовет к жизни новый цикл. Если вы поймете этот механизм, то все остальное в этой жизни будет только проще.


Все остальное


"Все остальное", то есть не рассмотренные здесь вопросы, включает: перебор вариантов OR, сохранение и использование обратных ссылок, а также обработку замены. Как известно, шаблоны поиска и замены не совпадают, так что там своя, похожая иерархия, основанная на классе ReplaceRule. Кроме того, данная реализация включает дополнительные возможности, такие как разбор входного потока, а также некоторые вещи "not in Perl 5". Поскольку там все очень похоже, то при желании разберетесь.


Как видите, в этом мире еще много сложного, и регулярные выражения — это один из таких случаев. Главная сложность — это наличие выбора, стоящего перед вами как разработчиком. Какие возможности реализовать? Сделать код быстрым или исчерпывающим? Использовать стандартные методы (и какого уровня) — или переписать код с нуля самому?


В результате возвращаемся в начало: прежде чем учить компьютер выполнять наши желания, нам придется самим "распознать" эти желания. А это тоже, так сказать, удовольствие высшего порядка.

2005.08.30
19.03.2009
В IV квартале 2008 г. украинский рынок серверов по сравнению с аналогичным периодом прошлого года сократился в денежном выражении на 34% – до $30 млн (в ценах для конечных пользователей), а за весь календарный год – более чем на 5%, до 132 млн долл.


12.03.2009
4 марта в Киеве компания Telco провела конференцию "Инновационные телекоммуникации", посвященную новым эффективным телекоммуникационным технологиям для решения задач современного бизнеса.


05.03.2009
25 февраля в Киеве компания IBM, при информационной поддержке "1С" и Canonical, провела конференцию "Как сохранить деньги в условиях кризиса?"


26.02.2009
18-19 февраля в Киеве прошел юбилейный съезд ИТ-директоров Украины. Участниками данного мероприятия стали ИТ-директора, ИТ-менеджеры, поставщики ИТ-решений из Киева, Николаева, Днепропетровска, Чернигова и других городов Украины...


19.02.2009
10 февраля в Киеве состоялась пресс-конференция, посвященная итогам деятельности компании "DiaWest – Комп’ютерний світ" в 2008 году.


12.02.2009
С 5 февраля 2009 г. в Киеве начали работу учебные курсы по использованию услуг "электронного предприятия/ учреждения" на базе сети информационно-маркетинговых центров (ИМЦ).


04.02.2009
29 января 2009 года в редакции еженедельника "Computer World/Украина" состоялось награждение победителей акции "Оформи подписку – получи приз!".


29.01.2009
22 января в Киеве компания "МУК" и представительство компании Cisco в Украине провели семинар для партнеров "Обзор продуктов и решений Cisco Small Business"

 

 
 
Copyright © 1997-2008 ИД "Комиздат".