Скорость регулярных выражений

[maxkar]

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

Сообщение от ProxyGreen

Тесты вам ни чего не показывают.

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

Ни нка ни дка ни где не используются, их судя по всему вообще не существует.

Используются. В тех задачах, для которых подходят. А в тех, которых не походят, не используются.

Что используется тогда? Как называется механизм, который используется в регулярных выражениях?

Вообще, он может никак не называться. Иногда там совершенно банальный перебор с возвратом с присущими ему тормозами на совершенно ровном месте. В некоторых случаях - с оптимизацями под какие-то особые сценарии (гибридные механизмы). Чисто теоретически, на некоторых видах выражений (для хороших выражений) он может строить дка и ходить по нему. А может не строить. Кстати, этот самый "перебор с возвратом" гораздо лучше описывает идею разбора регулярных выражений. Он же описывает и разницу в записях [abc] и (a|b|c) (в одном случае отктаты есть, в другом - нет). Откуда там хоть какие-то автоматы - хз.

Вот вам ещё ссылка:
http://lipetsk.lug.ru/projects/re/re...l#theorysearch
Но она тоже наверное врёт, там-же цитируют Фридла.

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

Обратите внимание, в 5-м абзаце пункта 6.1 автор пишет, что нка и дка преобразуются друг в друга. Я это вам уже говорил. Так что точнее механику называть "перебором с возвратом", а не нка.

[ProxyGreen]

Вообще, он может никак не называться. Иногда там совершенно банальный перебор с возвратом с присущими ему тормозами на совершенно ровном месте. В некоторых случаях - с оптимизацями под какие-то особые сценарии (гибридные механизмы). Чисто теоретически, на некоторых видах выражений (для хороших выражений) он может строить дка и ходить по нему. А может не строить. Кстати, этот самый "перебор с возвратом" гораздо лучше описывает идею разбора регулярных выражений. Он же описывает и разницу в записях [abc] и (a|b|c) (в одном случае отктаты есть, в другом - нет). Откуда там хоть какие-то автоматы - хз.

Ни как не называется, иногда, в некоторых случаях... Вода и общие фразы одни, в каких случаях какой механизм, где используется и как называется?

Там фраза "при использовании логики НКА"

Ну извините пока продолжаю гуглить по вопросу:

Вот вам ещё ссылка:
http://rus-linux.net/nlib.php?name=/...s_in_C_ru.html
Читайте пункт "Автомат".

Вот ещё одна интересная:
http://www.piter-press.ru/attachment...215&at=exc&n=0

Здесь мимолётное упоминание вначале раздела "основы".
http://www.opennet.ru/base/dev/php_regexp.txt.html

Тут:
http://www.devexp.ru/2011/02/konechn...y-v-c/#more-78
в разделе "Практическое применение автоматов".

Вот здесь автор пишет что регулярные выражения в MySQL обрабатываются с помощью дка механизма.
http://team-madalf.com/index.php?showtopic=48990
О чём кстати упоминает Фридл.

Наверное хватит пока, потом ещё поглубже попробую порыть.

Обратите внимание, в 5-м абзаце пункта 6.1 автор пишет, что нка и дка преобразуются друг в друга. Я это вам уже говорил. Так что точнее механику называть "перебором с возвратом", а не нка.

Ну и ладно, я с этим и не спорил особенно. Только при чём тут это?

[alatar]

Почему бы просто не посмотреть исходный код?

[maxkar]

Сообщение от ProxyGreen

Ни как не называется, иногда, в некоторых случаях... Вода и общие фразы одни, в каких случаях какой механизм, где используется и как называется?

Зависит. В MySQL regex - ДКА. Во flash - перебор с возвратом (backtraking). В Java - тоже перебор с возвратом. Какие еще эвристики добавляют в код - можно посмотреть в коде соответствующих пользователей. Я вот посмотрел в код tamarin'а - там используется pcre. Краткий поиск по pcre дает следующее:
ссылка1. Здесь автор пришет "We originally planned to use PCRE for the regular expression search, until we realized that it used a backtracking algorithm, meaning it is easy to make searches take exponential time or arbitrary stack depth". И я с ним согласен - ваши эксперименты по быстродействию регулярных выражений подтверждают именно его точку зрения, а не использование нка. В wiki пишут, например, что в PCRE есть жесткое ограничение на глубину рекурсии. Откуда в НКА может взяться рекурсия - совсем не понятно.

Да, если очень покопаться, там скорее всего можно будет накопать "автомат" (не нка или дка!). Но "автомат" можно при желании много где накопать - достаточно наличия чуть ли не любого состояния.

Ну извините пока продолжаю гуглить по вопросу:

Не надо гуглить! Нужно вырабатывать понимание вопроса. Вы так и не ответили на вопрос о том, что понимаете под нка/дка. Извините, но у меня складывается впечатление, что вместо попыток понять проблему вы только ищете ссылки, которые якобы доказывают вашу правоту.

Вот вам ещё ссылка:

Чтобы вы понимали разницу, давайте введем развеем путаницу, существующую во многих книгах и описаниях. Есть "классические" регулярные выражения из Computer Science. Это то, что у вас по первой ссылке ("Реализакция механизма обработки регулярных выражений на языке C++"). Фактически это литералы, closure (звездочка), конкатенация и выбор (|). Для них работает вся теория автоматов. Эти регулярные языки описывают регулярные (автоматные) грамматики. Назовем такие и только такие регулярные выражения cs-regex. В большинстве библиотек в регулярные выражения добавляют дополнительные возможности - группы захвата (capturing groups), обратные ссылки (back references), различные типы матчинга (greedy/reluctang/posessive - в AS их нет, но есть, например, в java). Назовем все такое семейство p-regex. Будем рассматривать пока только те, в которых есть backreference. Так вот, как я показывал, backreferences не могут распознаваться дка (и нка тоже). На практике для работы с p-regex в библиотеках используются не нка и дка автоматы (которые просто не могут работать), а перебор (backtracking). Большинство авторов рассматривают теоретическую часть, а затем говорят, что "практические библиотеки" тоже используют автоматы. Ведь и то, и другое - "регулярные выражения". Ну бывает, есть такая ошибка в рассуждениях.

http://rus-linux.net/nlib.php?name=/...s_in_C_ru.html
Читайте пункт "Автомат".

Посмотрел по-диагонали. Хорошая статья. Претензий к автору нет. Его регулярные выражения являются cs-regex (обратите внимание на список используемых возможностей). Для них прекрасно работают автоматы, что автор и демонстрирует. Но не демонстрирует, как работают p-regex (и даже задачу такую не ставит!). И в заблуждение по поводу реализации других библиотек не вводит (о других библиотека автор просто не упоминает)!

Вот ещё одна интересная:
http://www.piter-press.ru/attachment...215&at=exc&n=0

Ну да. Автор не различает cs-regex и p-regex. Большая часть статьи - про p-regex. Настоящие p-regex разбираются перебором. И их автомат (state machine, где состояние - "позиция разбора") очень далек от нка.

Здесь мимолётное упоминание вначале раздела "основы".
http://www.opennet.ru/base/dev/php_regexp.txt.html

Ага, видел. Автор отсылает в математическую литературу и при этом не упоминает о том, что в литературе речь идет о cs-regex, а он рассказывает про p-regex. Названия-то у них одинаковые.

Тут:
http://www.devexp.ru/2011/02/konechn...y-v-c/#more-78
в разделе "Практическое применение автоматов".

Ага. Только вот автор не конретизирует, какие именно выражения транслируются в конечные автоматы . А детали важны - cs-regex транслируются, а вот p-regex - нет.

Вот здесь автор пишет что регулярные выражения в MySQL обрабатываются с помощью дка механизма.
http://team-madalf.com/index.php?showtopic=48990

Ага. Вы на документацию посмотрите. Это же классический cs-regex! Там даже операции только классические - проверить строку на совпадение (без поиска подстроки). И результат - "matched/not matched". Никих backreferences.

Наверное хватит пока, потом ещё поглубже попробую порыть.

Если интересно - попробуйте найти, как реализуются backreferences на нка или дка. Я с удовольствием почитаю. Что-то мне кажется, там будет не совсем нка/дка (а, скорее, совсем не нка, хотя и автомат). Только вот сложно вам будет - большинство авторов это скользкий вопрос очень аккуратно обходят и не упоминают .

Ну и ладно, я с этим и не спорил особенно. Только при чём тут это?

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

Добавлено через 5 минут

Сообщение от alatar

Почему бы просто не посмотреть исходный код?

Так у нас спор скорее теоретический, а не практический. По ссылке посмотрел - в AS3 используется pcre. И вроде бы предоставляется только часть их возможностей.

Pcre - это backtracking. Автоматы - это, например Re2.

[ProxyGreen]

Зависит. В MySQL regex - ДКА. Во flash - перебор с возвратом (backtraking). В Java - тоже перебор с возвратом. Какие еще эвристики добавляют в код - можно посмотреть в коде соответствующих пользователей. Я вот посмотрел в код tamarin'а - там используется pcre. Краткий поиск по pcre дает следующее:
ссылка1. Здесь автор пришет "We originally planned to use PCRE for the regular expression search, until we realized that it used a backtracking algorithm, meaning it is easy to make searches take exponential time or arbitrary stack depth". И я с ним согласен - ваши эксперименты по быстродействию регулярных выражений подтверждают именно его точку зрения, а не использование нка. В wiki пишут, например, что в PCRE есть жесткое ограничение на глубину рекурсии. Откуда в НКА может взяться рекурсия - совсем не понятно.

Да, если очень покопаться, там скорее всего можно будет накопать "автомат" (не нка или дка!). Но "автомат" можно при желании много где накопать - достаточно наличия чуть ли не любого состояния.

Но pcre - это библиотека, а не механизм, и потом дальше автор пишет "As an alternative to PCRE, I wrote a new, carefully reviewed regular expression parser wrapped around Ken Thompson's open source grep implementation, which uses a fast DFA."
Примерный перевод:
Бла бла бла PCRE - это чушь для тысяч буков, а я написал свой парсер обёртку вокруг grep, которая использует быструю ДКА. Ага использует! Быструю!
И почему он кстати, всю статью упоминает няфу и дафу, всячески сравнивает их если они только для "игрушечных реализаций годятся"?

Вот здесь например написано что pcre основана на НКА механизме:
http://www.hostland.su/books/php5/page/224.html
Представляю уже что вы ответите: "Пошто гуглишь?! Автор профан! Учи матан!(OBEY!)"

Вы так и не ответили на вопрос о том, что понимаете под нка/дка.

Пффф... я могу сказать, что толком ни чего под ними не понимаю (потому что стараюсь относиться к себе объективно, в отличие от некоторых) т.к. это какой-то матан, и даже не "Анализ посредством бесконечно малых", а вообще неведома зверушка какая-то, открываешь мат. энциклопедию или вики, там схемки какие-то с графами, или формулки ЗЮ(состояния, входной алфавит, выходной алфавит, ф-ия перехода) и т.д. Ну и что? Как это с кодом соотноситься? С чего бы мне вообще в таких делах разбираться? А ваша логика не верна(по моему), т.к. вы излишне (на мой взгляд) придираетесь к формулировкам. Если для перебора строки используются нка\дка с какими либо надстройками\плюшками, то это ни какие не нка\дка, а неведомо что, без имени и фамилии. Так следуя вашей логике Math.PI - это ни какое ни число Пи, а число близкое к числу Пи, поэтому те кто считает синусы\косинусы с помощью этого числа определённо грешат, а если не упомянуть в книжке именно так: "число близкое к числу Пи", то книжка - врёт, а автор - дурак. По форме правильно, по существу издевательство.

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

Если что-то во что-то преобразуется, то не обязательно это что-то ведёт себя так-же как то, во что оно преобразуется, следовательно это не логичное утверждение, хотя может и истинное. Ведь если построить силлогизм:
Все механизмы преобразующиеся в другие механизмы ведут себя, после преобразования, так-же как до преобразования.
НКА и ДКА механизмы.
ДКА преобразуется в НКА.
Следовательно НКА ведёт себя так-же как ДКА.

Что-то меня смущает в этом всём. Мало ли что, во что преобразуется.

(greedy/reluctang/posessive - в AS их нет, но есть, например, в java)

Они и в AS есть между прочим, и написано не правильно :Р
"Матчинг" это захват что-ли? Можно и русские аналоги использовать.