свежий взгляд на regexp-ы (программистское)

[avva]

Я весьма рекомендую эту статью: Regular Expression Matching Can Be Simple And Fast всем, кто интересуется программированием и компьютерными науками. У автора статьи есть, как говорят по-английски, agenda, определенная пропагандистская цель: он хочет убедить нас, что наиболее распостраненный способ распознавания регулярных выражений - путем детерминистского поиска с возвратом (backtracking) - неправильное решение, и лучше использовать более редкий метод прогона недетерминистского автомата.

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

Что же касается утверждения автора, он меня не убедил, но заинтриговал. Конечно, тот факт, что с некоторыми "патологическими" regexp-ами обычные методы справляются только за экспоненциальное время хорошо известен. На практике программистам приходится их избегать: переписывать по-другому, менять логику итд. Но неясно, стоит ли преимущество того, что у нас гарантированно не будет "патологических" случаев определенной потери скорости в "обычных" случаях. Интуитивно мне кажется, что такая потеря, в среднем, неизбежна. Автор старательно обходит этот вопрос стороной, предлагая измерения только одного патологического случая. Кроме того, без некоторых дополнительных возможностей, кроме собственно сравнения строки по regexp-у, современные языки не могут обойтись - например, автоматической поимки вложенных паттернов в переменные ($1, $2 итд. в Перле). Автор упоминает, что есть возможность достичь этого и в методе недетерминистского прогона, что мне кажется интересным (потому что неочевидно, как к этому подойти); постараюсь пойти по его ссылкам и разобраться в подробностях.

Мнения и комментарии, как обычно, приветствуются.

Comments

[a7sharp9.livejournal.com]

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

оффтоп

[alesk.livejournal.com]

Анатолий, обращаюсь к вам, как гуру Perl. Не знаете ли вы, почему вот такой код:
----- test.pl -----
#!/usr/bin/perl -w
use strict;
print $_ for ('a' .. 'я');
-------------------

работает так:
-------------------
alexx@srv:~/src/ico$ ./test.pl
abcdefghijklmnopqrstuvwxyz
-------------------
?

[plumqqz.livejournal.com]

Автор несколько запутался - у перла как раз NFA. DFA встречается много где, и он ищет все эти радости за гарантированное время. В общем, очень мило и очень наивно.

[cmm.livejournal.com]

у регекспов есть 2 оправданных применения:

1. интерактивный поиск в текстовых редакторах (поскольку нехилая вероятность false positives в этом случае совершенно неважна, как и точность вообще).

2. когда нужно написать токенизатор, производительность которого реально критична.

за применения регекспов в прочих контекстах надо пороть.

[avva.livejournal.com]

Автор не запутался, это вы запутались. Когда говорят, что у перла NFA, подразумеваеся, что теоретическая модель - NFA; но это везде так. Вопрос в том, как эта NFA симулируется. Перл идр. симулируют с помощью детерминистского пробега и backtracking; это можно назвать подходом DFA. Автор предлагает одновременный параллельный пробег всех состояний NFA - тогда гарантировано линейное время. Воплотить этот пробег можно, в свою очередь, в том числе и путем перевода NF-автомата в другой DFA, состояниями которого являются множества состояний исходного автомата - это тоже можно назвать "подходом DFA", но означает совсем другое.

[captain-solo.livejournal.com]

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

[plumqqz.livejournal.com]

В общем, автор пытается сделать то, что уже есть. Ну, может быть, у него получится лучше, хотя я сомневаюсь. На самом деле куда как интереснее было бы прочитать про рожденный IBM спецпроцессор для регулярных выражений - может, расскажет кто?

Re: оффтоп

[nchaly.livejournal.com]

может быть, use locale надо?

Re: оффтоп

[alesk.livejournal.com]

пробовали, не помогает:
==========
#!/usr/bin/perl -w
use strict;
use locale;
use POSIX qw(locale_h);
my $locale = "ru_RU.KOI8-R";
my $new_locale = setlocale(LC_ALL, $locale);
warn "Unable to set locale '$locale!' Falling to '$new_locale'" if ( $locale ne $new_locale );
print $_ for ('a' .. 'я');
==========
$ ./test.pl
abcdefghijklmnopqrstuvwxyz

[eterevsky.livejournal.com]

Про это уже давным-давно писал Джефри Фриддл в своей общераспространённой книге про регулярные выражения (http://regex.info/). Насколько я понимаю, в перле простые регулярные выражения проверяются именно конечным автоматом. В то же время в нём очень трудно (если вообще возможно) искать выражения типа /(a*b)c\1/, то есть те, в которых есть внутренние ссылки на уже найденные подстроки.

[eterevsky.livejournal.com]

Секундочку. DFA как раз работает явно за линейное время. Это следует из самой сущности конечного автомата: получили символ -- перешли в состояние, готовы получать следующий символ. Backtracking же вообще никаким конечным автоматом не является.

[plumqqz.livejournal.com]

C:\Program Files>perl -e "print 'ok' if 'aabcaab' =~ /(a*b)c\1/"
ok

[faceted-jacinth.livejournal.com]

Поигрался немножко с шарповым движком, он сам по себе достаточно хорошо оптимизирует - авторский пример с развёрнутым (а?){n}a{n} он даже и не подумал делать через бектрекинг, равно как и парочку других, которые пришли мне в голову. Хотя, конечно, патологические случаи есть, как-то раз даже сам натыкался на глюк, когда он "(.*)$" в конце регекса зачем-то пытался бэктрэкать, давая квадратичное время, может уже поправили.
Я это к тому, что вообще нормальные современные движки преобразуют НКА в ДКА, оставляя, правда, по пути точки бэктрекинга, но, наверное, только в тех случаях, когда начинает экспоненциально расти размер автомата.

Ещё у автора есть забавный пассаж:
"Some might argue that this test is unfair to the backtracking implementations, since it focuses on an uncommon corner case. This argument misses the point: given a choice between an implementation with a predictable, consistent, fast running time on all inputs or one that usually runs quickly but can take years of CPU time (or more) on some inputs, the decision should be easy."
который выдаёт довольно специфический подход. Мы ж не на алгоритм сортировки смотрим, которому злодейка-реальность может скормить худший случай, тут те inputs, от которых зависит производительность, задаём лично мы.

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

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

[faceted-jacinth.livejournal.com]

Имеется в виду, что процедура преобразования NFA в DFA может дать экспоненциальное количество состояний (причём за экспоненциальное время). Там же всё преобразование в том и состоит, что для n вершин NFA фактически берутся 2^n вершин DFA (где каждая вершина соответствует состоянию интерпретатора NFA -- в каких вершинах мы сейчас находимся), но не сразу все, а в порядке появления, что в непатологических случаях даёт вменяемый результат.

Поэтому иногда оставляются Специальные Вершины, инициализирующие бэктрекинг.

[faceted-jacinth.livejournal.com]

Это не всегда возможно.

[a7sharp9.livejournal.com]

А я и не утверждаю, что всегда возможно; я только говорю, что всегда указывает на проблемы в дизайне программы.

[faceted-jacinth.livejournal.com]

Если "использование неподходящего регекс-движка" является проблемой дизайна, то да.

[avva.livejournal.com]

Попробуйте пример из этого треда.

Я это к тому, что вообще нормальные современные движки преобразуют НКА в ДКА

Вы что-то странное говорите. "Точки бэктрекинга" - это и есть те места, где НКА раздваивается, если их "оставлять по пути", то и так налицо ДКА. "Нормальные современные движки" могут, конечно, на простых случаях все делать без бэктрекинга вообще, путем преобразования НКА в ДКА, но если у вас есть хотя бы один capture внутри, то они по-моему уже не умеют этого делать - без связи с экспоненциальным ростом числа состояний.

который выдаёт довольно специфический подход. Мы ж не на алгоритм сортировки смотрим, которому злодейка-реальность может скормить худший случай, тут те inputs, от которых зависит производительность, задаём лично мы.

В целом согласен, хотя изредка есть случаи, когда наши регэкспы формируются реальностью (нетривиальным образом).

С другой -- совершенно очевидно, что на непатологических случаях реализация на ДКА рвёт реализацию на НКА раз в десять, наверное.

Меня интересует коэффициент "раз в десять". Если десять равно двум или трем, то это необязательно важно... интуитивно кажется, что больше, но в конечном итоге это зависит от того, как много бэктрекинга (пусть даже вполне линейного по своим масштабам, но как много конкретно) делает "типичный" случай.

[avva.livejournal.com]

Несомненно, в той неиллюзорной вселенной, в которой совершенно все данные уже и так записаны в виде S-expressions, твой подход весьма оправдан :)

[avva.livejournal.com]

Он не пытается сделать заново, что уже есть, он проповедует в жанре "хорошо забытое старое".

[eterevsky.livejournal.com]

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

Re: оффтоп

[avva.livejournal.com]

Потому что оператор .. умеет "магически" пробегать все значения между двумя строками, но эти строки должны состоять из цифр или английских букв, иначе он путается. Скажем, 'a0b' .. 'c5d' правильно пробежит по всем "промежуточным" значениям. Внутри оператора зашита логика, которая понимает только цифры и латинские буквы.

[avva.livejournal.com]

Мне кажется, вы не очень ясно представляете себе смысл выражения "механизм основан на конечных автоматах".

Под этой фразой можно подразумевать многое, как я объяснил в одном из комментов выше.

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

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

[eterevsky.livejournal.com]

Каюсь -- полностью читать статью у меня времени не было, и я её только просмотрел. Видимо, стоит исправить это упущение. :)

[avva.livejournal.com]

Спасибо за чистосердечное признание ;-)