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

[avva]

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

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

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

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

Comments

[a7sharp9.livejournal.com]

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

[faceted-jacinth.livejournal.com]

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

[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
-------------------
?

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

Re: оффтоп

[avva.livejournal.com]

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

Re: оффтоп

[alesk.livejournal.com]

все ясно,
спасибо огромное!

[plumqqz.livejournal.com]

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

[avva.livejournal.com]

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

[plumqqz.livejournal.com]

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

[eterevsky.livejournal.com]

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

[cmm.livejournal.com]

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

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

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

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

[avva.livejournal.com]

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

[stas]

Не понял, а как обрабатывать данные, сейчас обрабатываемые регекспами? Скажем, URL на части разобрать или из слабоструктутированного текста (HTML например) вынуть информацию?

[captain-solo.livejournal.com]

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

[eterevsky.livejournal.com]

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

[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, от которых зависит производительность, задаём лично мы.

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

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

[avva.livejournal.com]

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

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

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

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

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

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

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

[rasemon.livejournal.com]

Сижу в уральском аэропорту, рейс задерживается на два часа, пью коньяк. От нечего делать лезу через браузер своей нокии 6233(есть такое извращение) во френдленту. Появляется маленький кусочек текста "Я весьма рекомендую эту статью..." Дальше не видно, потому что в экран не влезает. Я почему-то думаю: это avva...
Пролистываю вниз. Это avva.
Потом лечу и думаю, почему же я сразу решил, что это avva. Может, сочетание "весьма рекомендую"?.. Не подскажете?

так до кучи,...

[lance10t.livejournal.com]

вот пример

   static  $xregexp='`
        (?P
            # main expression consists of atoms and operators
            \s*(?P[,:;.]+)?
            \s*(?P/|@=|@\.|@|and)?
            (?P
             \s*(?P
                    #atomic expressions
                    (?:
                         (?P[^\(\)\[\]{}&,|/+=\*~\'"@-]+)   # atom with bracket optionally
                         |(?=\(|{|\[|(?P>unary_ops)|$)           # or NOTHING followed by bracket, unary_ops, EOL
                    )
                    (?P
                     { (?P (?>(?P>main))* ) }
                    |
                    \[ (?P     (?>(?P>main))* )\]
                    |
                    \( (?P    (?>(?P>main))* )\)
                    )?
    	            |
                    (?P\'|")(?P.*?)(?
это регексп который парсит  xpath подобный синтаксис, и работает сам в себе рекурсивно =), 
очень мощная штука, и внешний код который строе синтаксическое дерево очень мал!
РЕГЕКСПЫ РУЛЯТ =)

Re: так до кучи,...

[lance10t.livejournal.com]

вот блин, он не прошел через постилку =)

Re: так до кучи,...

[lance10t.livejournal.com]

и кстати то что запостилось - это убитый регексп, он не так выглядет на самом деле =)

вроде получилось запостить =)

[lance10t.livejournal.com]

static $xregexp='` (?P<main> # main expression consists of atoms and operators \s*(?P<delimeters>[,:;.]+)? \s*(?P<unary_ops>/|@=|@\.|@|and)? (?P<joint_ops> \s*(?P<atomic> #atomic expressions (?: (?P<atom>[^\(\)\[\]{}&,|/+=\*~\'"@-]+) # atom with bracket optionally |(?=\(|{|\[|(?P>unary_ops)|$) # or NOTHING followed by bracket, unary_ops, EOL ) (?P<expression> { (?P<context> (?>(?P>main))* ) } | \[ (?P<set> (?>(?P>main))* )\] | \( (?P<func> (?>(?P>main))* )\) )? | (?P<quote>\'|")(?P<string>.*?)(?<!\\\\)(?P=quote) )\s* ) ) `xs';